Graphs:
Popcorn hack:
Homework hack:
- Q1: Configuration I only
- Q2: C) Three
Heuristics:
Popcorn hack:
- Flipping the coin order generally makes the greedy algorithm less efficient for typical coin systems.
- The greedy algorithm with the largest coins first is not perfect because it may fail in some cases (e.g., if you have a non-standard coin system), but for most practical cases, it is good enough and efficient enough.
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)}")
Hueristics Homework Hacks
Wrap-Up: What Did You Learn About Heuristics?
- How did changing the order of coins affect the result?
- Changing the order of coins to start with the smallest coin made the algorithm less efficient, as it used more coins to make up the same amount compared to starting with the largest coin.
- Which algorithm used fewer coins?
- The algorithm that started with the largest coins first used fewer coins because it minimized the number of coins needed to reach the target amount.
- Where might greedy algorithms work well? Where might they fail?
- Greedy algorithms work well in situations where the problem has an optimal solution that can be reached by making locally optimal choices (like coin change with standard denominations). They may fail in problems that require more careful consideration of future decisions, like certain pathfinding or scheduling problems.
- What is one thing you changed, and what did it show you?
- Changing the coin order from largest to smallest showed me that the greedy algorithm may not always be the most efficient, especially in cases where it’s not considering the bigger picture and makes suboptimal choices based on local decisions.
Summary:
Changing the order of coins in a greedy algorithm can significantly affect the efficiency of the solution. Starting with smaller coins may lead to using more coins than necessary, while starting with the larger coins minimizes the total. Greedy algorithms are ideal in cases with optimal local choices but can fail in more complex problems that require considering future implications.
Undeciable problems:
Popcorn Hack 1
The issue here is that the condition num != 0 will never be satisfied because num is continually being incremented (num += 1). As a result, num will always be greater than 0, and the loop will run indefinitely, leading to an infinite loop.
This is an undecidable problem because it is impossible to determine the output without running the code.
Popcorn Hack 2
- An algorithm can be used to solve an undecidable problem.
- FALSE: An algorithm cannot always solve an undecidable problem because undecidable problems, by definition, cannot be determined with a finite, reliable algorithm.
- If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time.
- FALSE: While some problems may have heuristics or approximations, an undecidable problem cannot be reliably solved by any algorithm, even if it works in most cases.
HOMEWORK
Part 1: Identify the Problem Type
Read the following problems and decide whether they are decidable or undecidable. Write your answer and a short reason why.
- “Is this number divisible by 2?”
- Decidable: This is decidable because you can simply check if the number is even by checking if the remainder when divided by 2 is 0.
- “Will this program stop or run forever?”
- Undecidable: This is an undecidable problem, known as the Halting Problem. It’s impossible to determine, in general, whether an arbitrary program will eventually halt or run forever.
- “Does this sentence contain the word ‘banana’?”
- Decidable: This is decidable because you can scan the sentence and check if the word “banana” is present, which can be done in a finite amount of time.
- “Will this AI ever become sentient?”
- Undecidable: This is an undecidable problem because there is no clear, predictable method or algorithm to determine whether an AI will become sentient in the future. It depends on many unpredictable factors.
Part 2: Algorithm Detective
Look at the two mystery “algorithms” below. Figure out which one is decidable and which one is undecidable, then explain your reasoning in one sentence each.
- Step 1: Input a number
Step 2: If the number is even, say “Yes.” If not, say “No.”- Decidable: This algorithm is decidable because it simply checks whether the number is even or odd, which can be done in a finite number of steps.
- 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: This is undecidable because predicting whether a program will halt or run forever is the Halting Problem, which is proven to be undecidable.
Part 3: Real-Life Connection
Think of something in real life where you can’t be sure what will happen unless you go through the entire experience.
- Example: When you try a new recipe, you can’t be sure how it will turn out unless you actually cook it and see the results. Factors like ingredient quality, cooking time, and your personal cooking skills make it impossible to know the outcome ahead of time.