Popcorn Hack 1

Popcorn Hack 2

## ORIGINAL CODE:

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

## CHANGED CODE

def greedy_coin_change(amount, coins=[1, 5, 10, 25]):
    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¢: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Total coins used: 63

🧠 See how it affects the number of coins used

The modified code results in using 63 coins, which is significantly more than the 6 coins used in the original code. This demonstrates that the modified code is less efficient in minimizing the number of coins.

📊 Reflect: is it more or less efficient? Is it perfect? Is it good enough?

The modified code is less efficient because it does not prioritize larger denominations first, leading to a higher total number of coins used. It is not perfect, as the goal of a greedy coin change algorithm is typically to minimize the number of coins. It is not good enough for practical purposes where efficiency is important.

Popcorn Hack 3

num = 10

while num != 0:
    print(num)
    num -= 1

num = 1

while num != 0:
    print(num)
    num += 1

Explain why there is an undecidable problem above.

The undecidable problem in the two code blocks arises from the halting problem, which states that it is impossible to determine, in all cases, whether a given program will finish running or continue to run forever.

In the first code block:

The loop starts with num = 10 and decrements num by 1 in each iteration
The loop condition checks if num != 0, so it will terminate when num equals 0
Since num is decreasing by a fixed amount and will eventually reach 0, we can determine that this program will halt after 10 iterations

In the second code block:

The loop starts with num = 1 and increments num by 1 in each iteration
The loop condition checks if num != 0, and since num is increasing, it will never equal 0
Therefore, this program will run indefinitely (infinite loop)

Popcorn Hack 4

#1. An algorithm can be used to solve an undecidable problem (True or False)

This is false because by definition undecidable problems can’t be solved algorithmically.

#2. If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time. (True or False)

This is false because like I explained earlier it is impossible to solve undecidable problems with algorithms, by definition.

Homework Hack 1

Homework Hack 2

Wrap-Up: What Did You Learn About Heuristics?
Take a moment to reflect or turn and talk:

How did changing the order of coins affect the result?
Changing the order of coins from largest to smallest to smallest to largest significantly increased the number of coins used.

Which algorithm used fewer coins?
The original algorithm used fewer coins because it prioritized larger denominations first.

Where might greedy algorithms work well? Where might they fail?
Greedy algorithms work well when the problem allows for locally optimal choices to lead to a globally optimal solution, such as with U.S. coin denominations. They fail in cases where this property does not hold, leading to suboptimal results.

What is one thing you changed, and what did it show you?
Changing the order of coins showed that the greedy algorithm’s efficiency heavily depends on the order of denominations.

Write a 2-3 Sentence Summary of all these questions: Changing the order of coins from largest to smallest to smallest to largest demonstrated the importance of prioritizing larger denominations in a greedy algorithm. The original algorithm was more efficient, using only 6 coins compared to 63 in the modified version. This highlights that while greedy algorithms can be effective, their success depends on the problem’s structure and the order of choices.*How did changing the order of coins affect the result?

Homework Hack 3

Part 1: Identify the Problem Type

“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 us 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.

Part 2: Algorithm Detective

Algorithm 1:

Step 1: Input a number  
Step 2: If the number is even, say "Yes." If not, say "No."  

Decidable
Reason: This algorithm performs a simple parity check that always terminates in one step with a definitive answer, regardless of input.

Algorithm 2:

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  

Undecidable
Reason: This algorithm attempts to solve the Halting Problem, which Turing proved cannot be solved by any general algorithm for all possible programs.

Part 3: Real-Life Connection

A real-life example of undecidability is predicting whether a novel medical treatment will be effective for a particular patient with a complex condition. While we can make educated guesses based on data, the only way to know with certainty is to go through the entire treatment process, as there are too many individual variables and potential interactions to create an algorithm that guarantees a correct prediction beforehand.

Yash Parikh - Lesson Day 8 - Graphs, Heuristics, and Undecidable Problems