Undecidable Problems and Graphs Homework and Popcorn hacks

Undecidable Problems

Popcorn Hack #1

False.

An algorithm cannot be used to solve an undecidable problem in general. By definition, an undecidable problem is one for which no algorithm exists that can correctly solve all instances of the problem.

Popcorn Hack #2

True.

While an undecidable problem cannot be solved by an algorithm in all cases, a programmer can often use an algorithm that works in many practical cases or for a specific subset of inputs. These are called heuristics or semi-decision procedures, and they can be very useful—even if they don’t guarantee a correct answer every time.

Popcorn Hack #3

D. Bubble sorting – This is a simple, fully decidable algorithm for sorting items. It’s not a problem of decidability at all.

Homework

Modern operating systems handle infinite loops and long-running processes using preemptive multitasking, time-slicing, and process management tools. Each process is given a limited amount of CPU time before the system switches to another, preventing any one program from freezing the whole system. Additionally, operating systems enforce resource limits and use watchdog timers to detect and manage unresponsive applications. Tools like Task Manager (Windows), Activity Monitor (macOS), or commands like kill on Linux allow users to manually terminate hung processes. In some cases, such as Linux’s OOM Killer, the OS will automatically end programs that consume excessive memory.

Web browsers take a more active role in handling long-running scripts because they can easily freeze the user interface. They monitor JavaScript execution time and trigger warnings or stop the script if it runs too long without yielding. Browsers like Chrome and Firefox display messages like “Page Unresponsive” or “A script on this page may be busy,” offering options to stop the script or wait. Modern browsers also isolate each tab into its own process, so one misbehaving tab doesn’t crash the entire browser. Developers are encouraged to use Web Workers for heavy computations and break up tasks with setTimeout or await to keep the UI responsive.

Graphs & Heuristics

Popcorn Hack #1

False.

In a directed graph, an edge from node A to node B (written as A → B) does not imply that there is an edge from node B to node A (B → A). The direction of the edge matters, and unless explicitly stated, the reverse edge may not exist.

Popcorn Hack #2

True.

Heuristics are designed to find good enough solutions quickly, especially for complex or hard problems, often at the cost of accuracy or optimality. They typically run faster than exact algorithms, but there’s no guarantee the solution is the best possible—just that it’s found efficiently.

Popcorn Hack #3

True.

Heuristic algorithms like the Nearest Neighbor algorithm for the Traveling Salesman Problem (TSP) are much faster than exact algorithms but do not guarantee an optimal solution. As the number of cities increases, the gap between the heuristic’s solution and the optimal one can grow significantly—in some cases, even exponentially. These heuristics are useful for large instances where exact solutions are computationally impractical, but their accuracy diminishes with scale.

Homework

Social Network Analysis (SNA) is a method used to study social structures by modeling relationships as graphs. In this context, graph theory provides a powerful framework for representing and analyzing the complex web of interactions between users on social media platforms. Each user in a network is represented as a node (or vertex), while the connections or interactions between them—such as friendships, follows, or messages—are represented as edges. These edges can be either directed, showing a one-way relationship (as in Twitter, where user A can follow user B without B following back), or undirected, indicating a mutual relationship (such as Facebook friendships). Additionally, edges can have weights to reflect the strength or frequency of the interaction between users.

A prominent real-world example of social network analysis in action is Facebook. Facebook models its entire ecosystem using what it calls the “Social Graph.” This is essentially a massive graph where nodes represent users, pages, groups, or events, and edges represent various interactions such as friendships, likes, comments, and shares. Graph-based algorithms allow Facebook to recommend new friends by analyzing shared connections, suggest pages and groups based on user interests, and detect communities or clusters of users with similar behavior. These same tools are also used to identify central figures in a network (influencers), detect fake or malicious accounts, and tailor content to keep users engaged.

By applying social network analysis, platforms like Facebook gain deep insights into user behavior and social dynamics, enabling them to make data-driven decisions for features, content delivery, and safety.