Graphs, Heuristics, and Undecidable Problems Hacks

• 4 min read

Tri 3 Team Teach Hacks

Undecidable Problems

Popcorn Hack 1

# First loop: Halts
num = 10
while num != 0:
    print(num)
    num -= 1

# Second loop: Runs forever
num = 1
while num != 0:
    print(num)
    num += 1

In the first loop, num decreases and eventually reaches 0, so the loop stops.

In the second loop, num keeps increasing and never reaches 0, so the loop runs forever.

The undecidable problem here is that, in general, you cannot always determine by looking at code whether a loop will eventually stop or run forever. This is related to the Halting Problem, which proves there is no universal method to decide this for all programs.

Popcorn Hack 2

  1. False
  2. False

Homework Hack 1

Part 1: Identify the Problem Type

  1. “Is this number divisible by 2?”
    Answer: Decidable
    Reason: This is a simple mathematical operation. You can easily determine if a number is divisible by 2 by checking if it’s even (i.e., number % 2 == 0).

  2. “Will this program stop or run forever?”
    Answer: Undecidable
    Reason: This is the Halting Problem, proven by Turing. There is no algorithm that can universally predict if a program will halt or run forever for all possible programs.

  3. “Does this sentence contain the word ‘banana’?”
    Answer: Decidable
    Reason: This is a straightforward string search. You can use algorithms like find() or regular expressions to check if the word ‘banana’ exists in the sentence.

  4. “Will this AI ever become sentient?”
    Answer: Undecidable
    Reason: Predicting if an AI will become sentient is a philosophical and scientific question with no clear, universally applicable answer, making it undecidable.

Part 2: Algorithm Detective

  1. Step 1: Input a number
    Step 2: If the number is even, say “Yes.” If not, say “No.”
    Answer: Decidable
    Reason: This is a simple check for evenness, which can be done in constant time using the modulus operation.

  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
    Answer: Undecidable
    Reason: This is a direct representation of the Halting Problem, which is undecidable because there is no general algorithm that can predict whether all programs halt.

Part 3: Real-Life Connection

Example: Deciding if a new business venture will succeed.
Reason: You can’t be sure if a business will succeed unless you go through the entire process, as there are too many unpredictable factors such as market conditions, competition, and customer behavior.

Heuristics

Homework Hack 1

How did changing the order of coins affect the result?

Changing the order of coins can affect the result in some cases. The greedy algorithm always selects the largest coin available, so if you change the order of the coins, it will prioritize different coins. For example, if you use the smaller coins first, the algorithm might need more coins to make the total amount.

Which algorithm used fewer coins?

The algorithm using the coins ordered from largest to smallest will usually use fewer coins, as it maximizes the value taken at each step.

Where might greedy algorithms work well? Where might they fail?

Greedy algorithms work well when making locally optimal choices leads to a globally optimal solution, such as in the case of coin change when the denominations are a set of standard coins like 25¢, 10¢, 5¢, and 1¢. However, they fail in situations where a more complex combination of smaller coins might lead to a better solution (e.g., when the denominations are non-standard).

What is one thing you changed, and what did it show you?

Changing the order of coins from largest to smallest vs. smallest to largest showed me that the greedy algorithm always takes the largest coin first, but this doesn’t guarantee the minimum number of coins in all cases (though it works fine for standard U.S. coin denominations).

2-3 Sentence Summary:

Greedy algorithms can provide an efficient solution for coin change problems when the coin denominations lead to locally optimal choices that also result in a globally optimal solution. However, changing the order of coins can impact the outcome, and greedy algorithms may not always produce the fewest coins when the denominations are non-standard. This highlights the importance of choosing the right algorithm for the problem at hand.

Graphs

Popcorn Hack 1

Done on whiteboard(I was part of one of the groups)

Homework Hack 1

  1. A - Configuration 1 only
  2. B- Two