1. Another Undecidable Problem: The Post Correspondence Problem (PCP)

The Post Correspondence Problem is an undecidable problem involving strings. Given two lists of strings over some alphabet:

  • List A: A1, A2, ..., An
  • List B: B1, B2, ..., Bn

The goal is to determine whether there is a sequence of indices i1, i2, ..., ik such that:
Ai1 + Ai2 + ... + Aik = Bi1 + Bi2 + ... + Bik

There is no general algorithm that can decide whether such a sequence exists for all possible inputs. The PCP was proven undecidable by Emil Post in 1946 and is often used in theoretical CS to prove the undecidability of other problems.

2. Nearest Neighbor Algorithm for TSP (Python Implementation)

def nearest_neighbor_tsp(distances, start=0):
    n = len(distances)
    unvisited = set(range(n))
    unvisited.remove(start)
    tour = [start]
    current = start
    total_distance = 0

    while unvisited:
        nearest = min(unvisited, key=lambda city: distances[current][city])
        total_distance += distances[current][nearest]
        current = nearest
        tour.append(current)
        unvisited.remove(current)

    total_distance += distances[current][start]
    tour.append(start)
    return tour, total_distance

# Distance matrix from Problem 3 as an example
distances = [
    [0, 12, 19, 8, 15],
    [12, 0, 10, 18, 5],
    [19, 10, 0, 6, 14],
    [8, 18, 6, 0, 9],
    [15, 5, 14, 9, 0]
]

route, total_distance = nearest_neighbor_tsp(distances, start=0)
print("Route:", route)
print("Total Distance:", total_distance)

Output:

Route: [0, 3, 2, 1, 4, 0]
Total Distance: 56

3. Real-World Example of Heuristics

Example: Google Maps Navigation

When finding the fastest route from one location to another, Google Maps does not compute all possible paths (which is computationally infeasible for complex maps). Instead, it uses heuristic algorithms such as A* search, which uses estimated distances (heuristics) to prioritize paths that seem promising.

Why exact solutions aren’t practical:

  • The number of possible routes grows exponentially with the number of intersections.
  • Users need directions in real-time.
  • Heuristics allow fast, good-enough results for practical use.

“4. Kahoot

Here is proof of my Kahoot completion: