3.18 Team Teach Notes

My notes for big idea 3.18 team teach

• 3 min read

CSP Big Idea 3.18

Undecidable Problems

An undecidable problem is a problem for which no algorithm can be constructed that will always provide a correct yes/no answer for all possible inputs.

Key Characteristics

  1. No single algorithm can always provide a correct answer.
  2. Some instances may have a solution, but no algorithm can solve all instances.
  3. A classic example is the Halting Problem.

Example: The Halting Problem

  • Introduced by Alan Turing.
  • Asks whether a given computer program will eventually stop (halt) or continue running forever when given a specific input.
  • Turing proved it is impossible to create an algorithm that can determine whether every possible program will halt or run forever.
  • Sometimes a program might take an unreasonable amount of time to reach an ending—if it even exists.

Real-World Analogy: A Website Taking Too Long to Load

  • Imagine clicking on a website, and it just keeps loading indefinitely.
  • Question: Is the page just taking a long time, or will it never load?
  • There is no general way to determine if the website will ever finish loading.
  • Similar to the Halting Problem, we cannot predict for all cases whether a webpage will load successfully.

Decidable Problems

A decidable problem is a problem for which an algorithm can always be written to provide a correct yes/no output for any input.

Key Characteristics

  1. An algorithm exists that solves every possible case of the problem.
  2. The algorithm always terminates with a correct answer.

Example

  • Checking if a number is divisible by 3.

1. Introduction to Graphs

A graph is a data structure used to represent relationships between objects.
A graph consists of:

  • Nodes (Vertices):** The entities being connected.
  • Edges: The connections or relationships between nodes.

Types of Graphs

  1. Undirected Graphs:
    • Edges are bidirectional.
    • Example: Facebook friendships.
  2. Unweighted Graphs:
    • All edges are considered equal.
  3. Directed Graphs:
    • Edges have direction.
    • Example: Twitter followers.
  4. Weighted Graphs:
    • Edges have values like distance or cost.
    • Example: Road networks.

Applications of Graphs

  • Social Networks: Connecting users and their relationships.
  • Navigation Systems: Finding the shortest route in apps like Google Maps.
  • Recommendation Systems: Suggesting content on platforms like Netflix.

3. Heuristics

A heuristic is a problem-solving strategy that simplifies solutions using rules of thumb, rather than exact, exhaustive search.

Real-World Example

  • Brute Force: Search every shelf one by one.
  • Heuristic: Go straight to the Science section if looking for a science book.

Examples of Heuristic Algorithms

  • Greedy Algorithms: Always pick the best immediate option.
  • A* Search: Finds the shortest or quickest path from one point to another.

Real-World Application of Heuristics

  • Navigation Systems:
    • Google Maps uses heuristic-based approximations for shortest routes (e.g., Dijkstra’s algorithm).

Traveling Salesman Problem (TSP)

A famous optimization problem that asks:

“Given a set of cities and the distances between them, what is the shortest possible route that visits each city exactly once and returns to the starting point?”

Small Example:

  • Nearest Neighbor Algorithm:
    • A greedy heuristic often used for approximation.
    • Fast but does not guarantee the shortest path.

Large Example:

  • Solving for large numbers of cities becomes computationally impossible through brute-force.

Why is TSP Hard?

  • Number of Routes: For n cities, the total routes = (n-1)!
  • As n increases, the route count grows exponentially, making brute-force infeasible.

Example of Route Growth:

Cities (n) Possible Routes ((n-1)!)
4 6
5 24
10 3,628,800
100 More than the atoms in the universe! 😲💥