Popcorn Hack 1
[A]
/ \ 5 / \ 3 / \ [B]---2---[C]---4---[E] \ \ / \6 \ /1
\ \ /
[D]--------
HW hack 1
1) A 2) C
Popcorn hack 2
🔁 What happens when we reverse the greedy coin order?
When you use: [25, 10, 5, 1] The algorithm grabs the biggest coins first. For 63¢, it picks [25, 25, 10, 1, 1, 1] → 6 coins ✅ Efficient
[1, 5, 10, 25] (smallest → largest): It keeps choosing 1¢ over and over before ever reaching bigger coins. For 63¢, it picks [1, 1, …, 1] → 63 coins ❌ Not efficient at all
💡 So… is it more or less efficient? ✅ Descending (Greedy): More efficient in U.S. coin systems.
❌ Ascending (Reversed): Way less efficient—it delays using better coins.
🎯 Is the Greedy strategy perfect? Not always. It’s perfect for coins like [25, 10, 5, 1] (U.S. coins), where greedy always finds the best solution.
But with coins like [9, 6, 1], greedy fails:
To make 11¢, greedy gives [9, 1, 1] → 3 coins
But [6, 5] is better → only 2 coins
So: 🔸 Greedy is not perfect 🔸 But it’s often “good enough” and very fast (O(n))
HW hack 2
Changing the order of coins significantly affected the result—using coins from largest to smallest (greedy) used far fewer coins than starting from the smallest. The greedy algorithm performed best when coins were ordered in descending value and matched well with the currency system, but it can fail with unusual coin sets where a non-greedy approach gives a better solution. I learned that while greedy algorithms are fast and often good enough, they aren’t always optimal and need to be tested carefully depending on the problem.
Popcorn hack 3
The program creates an infinite loop because num will never become 0, so the condition while num != 0 is always true. This is an example of an undecidable problem because there’s no way for a general algorithm to determine if such a loop will halt without actually running it.
Popcorn hack 4
1) false 2) true
HW hack 3
HOMEWORK Part 1: Identify the Problem Type
-
“Is this number divisible by 2?”
Answer: Decidable
Reason: This is a simple check, and an algorithm can be written to determine whether a number is divisible by 2, making it a decidable problem. -
“Will this program stop or run forever?”
Answer: Undecidable
Reason: This is the Halting Problem, proven to be undecidable because there is no general algorithm that can determine whether all programs will halt or run forever. -
“Does this sentence contain the word ‘banana’?”
Answer: Decidable
Reason: This can be easily solved with a string search algorithm, which is a definite, solvable problem, so it is decidable. -
“Will this AI ever become sentient?”
Answer: Undecidable
Reason: The concept of AI sentience is not well-defined, and there’s no algorithm or test that can conclusively predict whether an AI will become sentient, making it undecidable.
Part 2: Algorithm Detective
-
Step 1: Input a number
Step 2: If the number is even, say “Yes.” If not, say “No.”
Answer: Decidable
Reasoning: This is a simple even/odd check, and the algorithm will always stop with a definite answer. It’s a decidable problem. -
Step 1: Input any program
Step 2: Predict if it will ever stop running
Step 3: Output “Yes” if it will stop, “No” if it will run forever
Answer: Undecidable
Reasoning: This algorithm is trying to solve the Halting Problem, which is undecidable. There is no general way to predict whether an arbitrary program will stop or run forever.
Part 3: Real-Life Connection
Example: Choosing a career path.
Explanation: You can never be 100% sure how a specific career will unfold for you until you actually experience it. There are too many variables that you can’t fully predict without going through the process.