Undecidable vs Decidable
Popcorn Hack 1
An algorithm can be used to solve an undecidable problem. (True/False)
The answer is false. This is because by definiiton an undecidable problem is one that cannot be solved with an algorithm
Popcorn Hack 2
If a programmer encounters an undecidable problem, they can just use an alogirhtm that works most of the time. (True/False)
THis answer is true. This is because programmers can use approximations, which we learned is called “heuristics”
Popcorn Hack 3
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
The rest are undecidable problems.
Homework Hack
- Web browsers, such as Google Chrome, include script timeouts and will display an error messages like “Page Unresponsive” or “A script on this page may be busy or may have stopped responding” when a script runs too long. Users are prompted to stop or continue the script.
- Operating Systems use process management tools to handle unresponsive applications. Windows has its Task Manager that allows users to terminate processes that stop responding. This prevents prevents the whole computer from eventually freezing and stopping.
Graphs & Heuristics
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.
This is false because an edge between A to B doesn’t always mean there will be a corresponding edge from B to A, it depends on how the nodes were connected.
Popcorn Hack 2
True or False: Heuristics always provide faster solutions than exact algorithms, but they may sacrifice accuracy for speed.
This is true because heuristics look for the fastest way possible, while an algorithm that takes longer can take into account many things while sacrificing speed.
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.
This is true. Heuristics sacrifice accuracy for speed, and as there are more things to calculate, accuracy can be quite low.
Homework Hack
In social network analysis, a graph is used to represent connections between individuals. Users** are modeled as nodes (or vertices), and the relationships between them (follows, likes, comments, etc) are represented as edges. Edges can be:
- Directed (e.g., Twitter follows: A follows B, but B may not follow A)
- Undirected (e.g., Facebook friendships: A and B are mutually connected)
- Weighted to show interaction strength (e.g., message frequency)
Graphs help analyze patterns, detect communities, and measure influence using concepts like centrality, clustering, and shortest paths.
Real-World Example
Platform: LinkedIn
LinkedIn uses graph theory to recommend new connections, analyze professional networks, and find the shortest or strongest connection path between users for networking and job referrals. This is really important for LinkedIn because LinkedIn is all about making connections between people looking for jobs/hiring.