Popcorn Hack 1
False – An algorithm cannot solve an undecidable problem because, by definition, undecidable problems have no algorithm that can solve all cases correctly.
Popcorn Hack 2
True – While no algorithm can solve all instances of an undecidable problem, programmers may use heuristics or algorithms that work for some cases or most of the time.
Popcorn Hack 3
ANSWER: D – Bubble sorting is a standard, decidable algorithm. The others involve undecidable problems or theorems about them.
Homework Hack
Operating Systems
Mechanisms:
Process Scheduling: OSes use time slices (e.g., round-robin scheduling) to prevent any one process from hogging the CPU. This doesn’t stop infinite loops but ensures other programs stay responsive.
Watchdogs/Task Managers: Users or the system can terminate unresponsive processes via tools like:
Windows Task Manager
macOS Activity Monitor
Linux System Monitor / kill command
System Resource Limits: OSes can limit CPU time, memory, or execution time per process. This is common in servers or sandboxed environments.
Example:
In Windows, a program stuck in an infinite loop may be labeled “Not Responding,” allowing the user to force-quit it.
Web Browsers
Mechanisms:
Script Timeout Warnings: Browsers detect if a script is running too long and prompt the user with an option to stop it.
Event Loop & Thread Separation: JavaScript runs on a single thread, but browsers offload rendering/networking to keep the UI responsive.
Crash Recovery: Browsers like Chrome isolate tabs in separate processes. If one crashes due to an infinite loop, only that tab closes, not the entire browser.
Real-World Examples:
Chrome: Shows “Page Unresponsive – You can wait or exit.”
Firefox: Displays “A script on this page may be busy, or it may have stopped responding…”
Safari: Silently kills runaway scripts or prompts for user action.
Lesson: Graphs & Heuristics
Popcorn Hack 1
False – In a directed graph, edges have direction. An edge from node A to node B does not imply there is an edge from B to A unless it is explicitly defined.
Popcorn Hack 2
True – Heuristics are designed to find good-enough solutions more quickly than exact algorithms, but they may not always be accurate or optimal.
Popcorn Hack 3
True – Heuristic algorithms like Nearest Neighbor can greatly reduce computation time for the Traveling Salesman Problem (TSP), but they do not guarantee an optimal solution. As the number of cities increases, the difference between the heuristic and optimal solution can become significantly large.
Homework Hack
What is Social Network Analysis (SNA)?
Social Network Analysis is the use of graph theory to study relationships and interactions between individuals, groups, or organizations—commonly applied to social media platforms.
How Are Users and Relationships Represented?
Nodes (Vertices): Represent individual users, accounts, or entities in the network.
Edges (Links): Represent relationships or interactions between users. These can be:
Directed (e.g., A follows B on Twitter)
Undirected (e.g., A and B are friends on Facebook)
Edges can also have weights to indicate strength (e.g., message frequency).
Real-World Example: Facebook
On Facebook:
Nodes = Users
Edges = Friendships (undirected), likes, comments, or messages (can be directed)
Graph theory helps Facebook:
Recommend new friends using mutual connections.
Detect communities or interest groups.
Identify influential users.
Filter spam or detect fake accounts using patterns in connections.
Conclusion: Graphs allow social platforms to visualize and analyze vast networks of interactions. By modeling users and relationships as nodes and edges, platforms can improve user experience, security, and recommendation systems.