Graphs Popcorn Hack 1

I answered this in class

Graphs Homework Hack 1

  1. B configuration II only
  2. B Two

Heuristics Popcorn Hack 1

The output of the code below is not that efficient because it displays 1 about 63 times and so is long and unnecessary.

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

Heuristics Homework Hack 1

Key Questions Answered

How does changing the order of coins affect the result? If the coins list is not in descending order (e.g., [1, 5, 10, 25]), the algorithm may use more coins than necessary (e.g., 63¢ would become 63 pennies!). The greedy approach requires sorted denominations to work correctly for standard coin systems.

Which algorithm used fewer coins? For the US coin system ([25, 10, 5, 1]), the greedy algorithm is optimal and matches the result of a dynamic programming solution. For non-canonical systems (e.g., [1, 3, 4] and amount = 6), greedy fails (greedy: [4, 1, 1] = 3 coins; optimal: [3, 3] = 2 coins).

Where might greedy algorithms work well? Where might they fail? Works well: Canonical coin systems (like US coins), scheduling problems (e.g., interval scheduling), or problems with the “greedy choice property” (e.g., Huffman coding). Fails: Non-canonical coin systems, knapsack problems, or when local choices don’t guarantee global optima.

What is one thing you changed, and what did it show you? Changing the coin order to ascending ([1, 5, 10, 25]) demonstrates that greedy algorithms depend heavily on input structure. It also highlights why sorting is critical for correctness.

2-3 Sentence Summary The greedy coin change algorithm prioritizes the largest denominations first, ensuring optimality for standard coin systems but failing for arbitrary ones. Testing changes (like coin order) reveals its reliance on problem structure, where it excels in canonical cases but struggles with non-intuitive setups. This underscores the importance of verifying algorithm suitability for specific constraints.

Udecidable Problems Homework Hack 1

Sure! Here’s a clear response for each part:

Part 1: Identify the Problem Type

  1. “Is this number divisible by 2?”
    Decidable – There’s a clear algorithm: check if the number mod 2 equals 0.

  2. “Will this program stop or run forever?”
    Undecidable – This is the Halting Problem, proven by Alan Turing to be unsolvable in general.

  3. “Does this sentence contain the word ‘banana’?”
    Decidable – You can scan the sentence for the word. It’s a straightforward string-matching problem.

  4. “Will this AI ever become sentient?”
    Undecidable – There’s no known algorithm or criteria that can definitively predict AI sentience.

Part 2: Algorithm Detective

  • Algorithm 1 (Number is even?)
    Decidable – This algorithm has a clear, finite process to determine if a number is even.

  • Algorithm 2 (Program halts?)
    Undecidable – This is another version of the Halting Problem; no algorithm can predict this for every possible program.

Part 3: Real-Life Connection

Example: Choosing a college major – You can research all you want, but you won’t really know if it’s the right fit until you experience classes and see how you feel over time.