Popcorn Hacks – Big-O and Undecidability
Popcorn Hack 1: Undecidable Problem Solvability
Question:
An algorithm can be used to solve an undecidable problem.
Answer: ❌ False
Undecidable problems, by definition, have no algorithm that can solve all possible inputs.
Popcorn Hack 2: Approximating Undecidable Problems
Question:
If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time.
Answer: ✅ True
While there’s no guaranteed solution for every input, heuristics or approximate algorithms can be used to solve many cases in practice.
Popcorn Hack 3: Identifying a Decidable Problem
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
Answer: ✅ D. Bubble sorting
Bubble sorting is a deterministic and well-understood sorting algorithm, so it’s a decidable problem.
Undecidable Problems Homework
How Systems Handle Infinite Loops or Long-Running Code
🖥️ Operating Systems
Modern OSes can’t guarantee detection of infinite loops, but they use tools like:
- Task scheduling: Limits CPU time per process.
- Watchdog timers: Force restarts if tasks hang.
- Resource monitors: Detect high memory/CPU usage.
Example: Windows Task Manager lets users kill unresponsive apps. Linux uses the OOM Killer to stop memory-hogging processes.
🌐 Web Browsers
Browsers use safeguards like:
- Script timeouts: If JS runs too long, it shows a warning.
- Web Workers: Run tasks in background threads to avoid freezing.
- Error messages:
- Chrome: “Page Unresponsive”
- JS: “Maximum call stack size exceeded”
✅ Summary
OSes and browsers can’t solve the halting problem, but they use timeouts, limits, and user prompts to keep systems stable and responsive.
This is all for the other stuff, graphs part
Popcorn Hacks
Popcorn Hack #1
True or False:
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.
Answer: False
In a directed graph, edges have direction. An edge from A to B does not imply one from B to A.
Popcorn Hack #2
True or False:
Heuristics always provide faster solutions than exact algorithms, but they may sacrifice accuracy for speed.
Answer: True
Heuristics are used to find good-enough solutions quickly, often trading off some accuracy for efficiency.
Popcorn Hack #3
True or False:
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.
Answer: True
Heuristics for problems like TSP (Traveling Salesman Problem) are fast but not guaranteed to be optimal, especially as complexity scales.
Homework: Social Network Analysis
How Graphs Are Used in Social Media
In social network analysis, users are represented as nodes (vertices) and their relationships (e.g., friendships, follows, likes) are represented as edges (connections) between those nodes. These graphs can be directed (e.g., Twitter follows) or undirected (e.g., Facebook friendships).
Edges may also carry weights or attributes, such as frequency of communication or strength of interaction.
Real-World Example
Platform: Facebook
Graph theory is used to analyze mutual friendships, suggest new friends through common connections, detect communities, and identify influential users. The “People You May Know” feature is one practical application powered by analyzing the underlying social graph.