Undecidable/Decidable Problems

Popcorn Hack 1 Question: An algorithm can be used to solve an undecidable problem.

  • Answer: False

Explanation:

  • An undecidable problem is one that no algorithm can solve for every input. There might be some algorithms that work for some cases meaning that the problem remains undecidable.

Popcorn Hack 2 Question: If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time. Answer: True

Explanation:

  • Even though there’s no perfect algorithm that works for all cases in an undecidable problem, programmers sometimes create algorithms that work for most inputs or give an answer within a time limit. It’s a useful shortcut, even if it’s not guaranteed to always be correct.

Popcorn Hack 3 Question: Which of the following options is not an example of an undecidable problem?

A. Halting Problem

B. The Collatz Conjecture

C. Rice’s Theorem

D. Bubble sorting

Explanation:

  • Bubble sorting is a decidable problem because it’s a simple algorithm that sorts a list of numbers — and we can write code that always works. The other three deal with problems that computers can’t solve completely for all inputs (undecidable problems).

Undecideable Problems Homework Question/research:

Investigate and describe how modern operating systems and browsers handle infinite loops or excessively long-running scripts. What mechanisms are in place to detect and mitigate such issues? Provide real-world examples of these mechanisms in action, such as specific error messages, timeouts, or automated recovery processes.

Undecidable Problems Homework

Modern operating systems and web browsers have ways to stop programs or scripts that run too long or get stuck in a loop. These tools help prevent computers from freezing, crashing, or slowing down.

How Operating Systems Handle It

  • Task Manager (Windows) and Activity Monitor (Mac) show what programs are using a lot of CPU or memory.
  • If a program freezes or runs forever, users can “End Task” or “Force Quit” it to stop the issue.
  • The OS might show a message like “Not Responding” to let you know something is wrong.

Example: If a game or app freezes, Task Manager lets you close it manually.

How Browsers Handle It

  • Browsers like Chrome, Firefox, and Safari track how long scripts are running.
  • If a script runs too long, they stop it and show an error message like:
    “A script on this page is causing your browser to run slowly. Do you want to stop it?”
  • Browsers use timeouts to kill long-running code and sandboxing to isolate each tab so one crash doesn’t affect others.

Example: Chrome shows an “Aw, Snap!” error when a tab crashes, but the rest of the browser still works.

Why This Matters

These tools help protect users and systems from code that might never stop running. Even though undecidable problems can’t be solved with a perfect algorithm, operating systems and browsers use timeouts, crash handling, and user alerts to keep things safe and running smoothly.

Graphs and Heuristics

True or False Questions

  1. In a directed graph, an edge from node A to node B implies that there is always a corresponding edge from node B to node A.
    False
    In a directed graph, edges have direction. If there is an edge from A to B, that does not mean there is one from B to A unless it is added separately.

  2. Heuristics always provide faster solutions than exact algorithms, but they may sacrifice accuracy for speed. True
    Heuristics are used to get quick solutions that are “good enough.” They are faster, but sometimes not completely accurate compared to exact algorithms.

  3. While heuristic algorithms like the Nearest Neighbor algorithm can significantly reduce the computational time for TSP, they can never guarantee an optimal solution, and the gap between the heuristic solution and the optimal solution can grow exponentially as the number of cities increases. True
    Heuristic algorithms like Nearest Neighbor are faster but can’t promise the best answer. As you add more cities, the difference between the quick answer and the best answer can get much bigger.

Homework: Social Network Analysis

How are users and relationships represented in social networks?

  • In graph theory, users are shown as nodes (or vertices).
  • Relationships (like friendships or followers) are shown as edges (or links) between those nodes.
  • If the relationship is two-way (like a Facebook friendship), the graph is undirected.
  • If it’s one-way (like a Twitter follow), the graph is directed.

Real-World Example:

  • Facebook uses graph theory to show friend connections between people.
  • Each user is a node, and a friendship between two users is an edge.
  • Facebook uses this to suggest friends, find communities, and even detect fake accounts.

Graph theory helps platforms understand who talks to who, how information spreads, and which users are most influential in the network.