Graphs Popcorn Hack 1
Graphs Homework Hack:
- Question 1: A
- Question 2: B
Heuristics Hack 1
def greedy_coin_change(amount, coins=[25, 10, 5, 1]):
change = []
for coin in coins:
while amount >= coin:
amount -= coin
change.append(coin)
return change
# Example usage:
amount = 63
result = greedy_coin_change(amount)
print(f"Change for {amount}¢: {result}")
print(f"Total coins used: {len(result)}")
Change for 63¢: [25, 25, 10, 1, 1, 1]
Total coins used: 6
- How did changing the order of coins affect the result? Switching from largest-to-smallest to smallest-to-largest significantly increased the number of coins used.
- Which algorithm used fewer coins? The original algorithm required fewer coins, as it prioritized larger denominations first.
- Where might greedy algorithms work well? Where might they fail? Greedy algorithms perform well when locally optimal choices lead to a globally optimal solution, such as with U.S. coin denominations, but fail when this property doesn’t hold, resulting in suboptimal outcomes.
- What is one thing you changed, and what did it show you? Adjusting the order of denominations revealed that a greedy algorithm’s efficiency heavily depends on the structure and arrangement of choices.
Summary: Changing the order of coins from largest-to-smallest to smallest-to-largest demonstrated that prioritizing larger denominations is essential for efficiency in a greedy algorithm. The original algorithm was far more effective, highlighting that the success of greedy methods depends on the problem’s design and constraints.
Undecidable Problem Popcorn Hack
Popcorn Hack 1:
The sum can never be zero because it is always positive, ensuring the process will never terminate.
Popcorn Hack 2:
- Question 1: False
- Question 2: False
Undecidable Problems Homework Hack
“Is this number divisible by 2?”
Decidable
Reason: This problem has a clear algorithm that always terminates. We can check if a number is divisible by 2 by simply examining its last digit or performing modulo division by 2, which will always give a definitive yes or no answer in finite time.
“Will this program stop or run forever?”
Undecidable
Reason: This is the famous Halting Problem, proven by Alan Turing to be undecidable. No algorithm can determine for all possible program-input pairs whether the program will eventually halt or run forever.
“Does this sentence contain the word ‘banana’?”
Decidable
Reason: This is a simple string searching problem. We can check for the presence of “banana” by scanning through the sentence once, which will always terminate with a definitive answer in finite time.
“Will this AI ever become sentient?”
Undecidable
Reason: This question involves predicting a future state that depends on complex, undefined concepts (sentience) and potentially infinite future developments. There is no algorithm that can provide a guaranteed correct answer in finite time.