Question

📌 Q1: Redundant Routing Between Q and V

Answer: C) Both configuration I and configuration II

Both configs have multiple independent paths from Q to V. Redundancy exists either way.

📌 Q2: Minimum Connections to Break T–U Communication

Answer: B) Two

In Configuration I, breaking T–P and T–V severs all direct/indirect links between T and U.

🧠 Popcorn Hack: Cities as Graphs

When we represent cities and roads using a graph, it’s like building a map out of math. Each city becomes a node, roads are edges, and if we care about things like distance or cost, we add weights to those edges.

🏙️ Example: 5-City Graph

Let’s say we have cities A, B, C, D, and E. Here’s how they’re connected:

  • A to B (5 miles)
  • A to C (10 miles)
  • B to D (7 miles)
  • C to D (3 miles)
  • D to E (4 miles)

So if you’re trying to get from A to E, you could take:

  • A → B → D → E, or
  • A → C → D → E

Depending on the route, the total distance changes. That’s where algorithms like Dijkstra’s come in — they help find the shortest or cheapest path.

🪙 Greedy Coin Change Hack

The greedy coin change algorithm tries to make change by grabbing the biggest coin possible at each step. So for 63¢, it’ll go: 25, 25, 10, then a few 1s — only 6 coins total. Pretty slick.

But if you flip the coin order and start with the smallest first (1, 5, 10, 25), the algorithm ends up using way more coins — and takes longer. Why? Because it’s not thinking ahead — just grabbing whatever looks good right now.

What did I learn?

Greedy is fast, but not always smart. It works great in some situations — like U.S. coin systems — but if you mess with the coin values, the greedy approach totally falls apart.

📟 Code Recap (Greedy Version)

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

amount = 63
result = greedy_coin_change(amount)
print(f"Change for {amount}¢: {result}")
print(f"Total coins used: {len(result)}")

Output:
Change for 63¢: [25, 25, 10, 1, 1, 1]
Total coins used: 6

❓ Popcorn Hack #1: Why is there an Undecidable Problem Here?

The undecidable part comes from trying to predict if a program will ever stop running. This is known as the Halting Problem — and it’s one of those classic computer science puzzles. Basically, there’s no perfect way to know if a program will finish or just keep looping forever. It’s like trying to guess if a website that’s been “loading” for 10 minutes is just slow… or broken forever.

✅ Decidable Example

def divisibleByThree(num):
    return num % 3 == 0

This is decidable. You feed it a number, it runs a simple check, and spits out true or false. Done.

🧪 Popcorn Hack #2: Practice Questions

Q1: Can an algorithm solve an undecidable problem?

Answer: False
If it’s truly undecidable, then no algorithm in the world can solve it for every possible input. That’s what makes it undecidable.

Q2: Can you just write an algorithm that works most of the time for an undecidable problem?

Answer: Still false
You might write something that seems to work, but that doesn’t actually solve the problem — it’s just a guess. That’s not reliable.

🏁 Homework Part 1: Decidable or Not?

  • Is this number divisible by 2?
    ✅ Decidable — easy math check, always gives an answer.

  • Will this program stop or run forever?
    ❌ Undecidable — can’t predict this for all programs.

  • Does this sentence contain the word ‘banana’?
    ✅ Decidable — just search the text, easy.

  • Will this AI ever become sentient?
    ❌ Undecidable — nobody can say for sure. That’s philosophy mixed with code.

🕵️ Part 2: Algorithm Detective

  • Step 1: Input a number. Step 2: If it’s even, say “Yes.” If not, say “No.”
    ✅ This one’s decidable. You’ll always know if a number is even or not. Super straightforward.

  • Step 1: Input a program. Step 2: Predict if it will ever stop.
    ❌ Undecidable — that’s literally the Halting Problem again. You can’t always know without actually running it.

🧩 Part 3: Real-Life Connection

A good real-life comparison is when a website just keeps loading… and loading… and you don’t know if it’s actually going to finish or if it’s just frozen. You either sit there hoping, or give up — but there’s no way to be sure unless you wait it out.

📝 Wrap-Up: What Did I Learn About Heuristics?

Reordering the coins totally changed how well the greedy algorithm worked. Starting with big coins used fewer coins overall. But when we started with small ones, the algorithm fell apart — it didn’t look ahead and ended up doing more work.

Greedy algorithms are great when they match the structure of the problem — like the U.S. coin system. But they can fail hard when the setup changes. What I learned is: greedy isn’t always smart — it’s just fast. Sometimes, you need something smarter, like dynamic programming, if you want the best result.