Undecideable Problems, Graphs + Heuristics

🔍 Graphs, Heuristics, and Undecidable Problems

📊 Graphs

Graphs are a fundamental data structure in computer science used to model relationships between objects.

Key Concepts:

• Graphs consist of nodes (vertices) connected by edges.
• Used in applications like pathfinding (e.g., Google Maps), web page ranking (e.g., PageRank), and network routing.

Adjacency Matrix:

• Represents a graph as a matrix of booleans (0’s and 1’s).
• Used for both directed and undirected graphs.

Adjacency List:

• Represents a graph as an array of lists, where each list stores adjacent vertices.
• Efficient in terms of space when dealing with sparse graphs.

Popcorn Hack #1
How would you use graphs to optimize the delivery route for a delivery driver? Consider factors like traffic and distances.

Model intersections as nodes and roads as edges with weights (like distance or traffic time). Use Dijkstra's or A* algorithm to find the shortest or fastest route based on current traffic data.

🧠 Heuristics

Heuristics are problem-solving techniques that provide “good enough” solutions when optimal ones are too complex or costly to compute.

Common Examples:

• Nearest Neighbor Heuristic: Used in the Traveling Salesperson Problem (TSP) to pick the closest unvisited location.
• Greedy Algorithms: Make the best immediate choice at each step (e.g., Greedy Coin Change algorithm).
• Heuristic Search Strategies: Use estimates like Manhattan or Euclidean distance to guide pathfinding algorithms like A*.

Greedy Coin Change Algorithm:

• Choose the largest coin first to minimize the number of coins.
• Test the strategy by reversing the order of the coins.

Popcorn Hack #2
What effect does reversing the greedy strategy have on the number of coins used? Is it more or less efficient?

Reversing the greedy strategy usually makes it less efficient. Using smaller coins first may increase the total number of coins used because it skips better larger options.

❓ Undecidable Problems

Undecidable problems are those for which no algorithm can always provide a correct yes or no answer. The Halting Problem is a classic example.

Key Concepts:

• An algorithm becomes undecidable if some instances have a solution but not all of them do.
• The Halting Problem, proven by Alan Turing, shows that no algorithm can predict whether a program will halt or run forever in all cases.

Popcorn Hack #3
Can you write a program that tells whether another program will halt or run forever? Why or why not?

No, due to the Halting Problem. Turing proved it's impossible to create an algorithm that always correctly determines whether any program halts or loops forever.