Undecidable Problems

Popcorn Hacks

Popcorn Hack 1

Algorithms cannot be used to solve an undecidable problem, so it is false.

Popcorn Hack 2

Using a program that works most of the time in the case of an undecidable problem is a good idea, so true.

Popcorn Hack 3

Answer is D, as all of the other problems are undecidable problems proven to not exist.

Homework Hack:

Modern operating systems and web browsers are built with safeguards to handle situations like infinite loops or scripts that run too long, which could otherwise freeze your system or crash your browser. These mechanisms are meant to keep things running smoothly and protect users from unresponsive programs.

In Operating Systems

  1. Process Scheduling & Preemption: Operating systems like Windows, macOS, and Linux use preemptive multitasking. That means they give each process (like a code or app) a slice of CPU time. If code enters an infinite loop, the OS doesn’t freeze—it just moves on and gives CPU time to other processes.

  2. Watchdogs and Resource Limits: On systems like Linux, administrators can set CPU time limits using tools like ulimit or cgroups. If a script goes rogue and uses too much CPU for too long, the OS can automatically kill it.

Example: Running a Python script with ulimit -t 5 limits it to 5 seconds of CPU time. After that, the system sends a SIGXCPU signal and stops the process.

In Web Browsers

  1. Script Timeouts: Browsers like Chrome, Firefox, and Safari are especially cautious about infinite loops in JavaScript. If a script runs too long without yielding control back (like in a while(true) loop), the browser steps in.

Real-World Example:

  • Chrome: “Page Unresponsive – You can wait for it to become responsive or exit the page.”
  • Firefox: “A script on this page may be busy, or it may have stopped responding.”

These messages give users the option to stop the script, preventing browser crashes.

  1. setTimeout and requestAnimationFrame: Browsers encourage asynchronous design. Functions like setTimeout() and requestAnimationFrame() help prevent long blocking operations by letting scripts break their tasks into smaller chunks and yield back control regularly.

  2. Developer Console Warnings: If a script causes high memory use or performance issues, the browser’s dev tools often flag it. For instance, Chrome may show:

    • “Long-running script detected”
    • This helps developers debug inefficient code.

Recovery & Isolation

  1. Process Isolation (Browser Sandboxing): Modern browsers run each tab in a separate process. So if a script crashes one tab, it won’t take down the whole browser.

  2. Automatic Tab Suspension: Browsers like Edge and Chrome now suspend inactive tabs to save resources. If a background tab is running a long script, it might be frozen or deprioritized. Summary

In short, both operating systems and browsers are equipped to detect infinite loops or excessively long-running scripts. They do this using process management, timeout detection, script throttling, and user prompts. These systems make sure that even if your code goes wild, it doesn’t take the whole system down with it.

Graphs and Heuristics

Popcorn Hack 1

False: Graphs are not always bidirectional so this statement is false.

Popcorn Hack 2

True: Heuristics are always faster, but with speed comes limited accuracy, as the progam may skip over specific necessary actions.

Popcorn Hack 3

True: Heuristic-based approach doesn’t guarantee the optimal solution, but it comes closer than algorithmic approaches within reasonable time.

Homework Hack:

Social Network Analysis (SNA) is the study of relationships and interactions within a network of individuals, groups, or organizations—most often visualized and analyzed using graph theory.

How Graphs Represent Social Networks

In graph theory terms:

  • Nodes (Vertices) = represent users or entities.

  • Think of each person on Instagram, Twitter, or LinkedIn as a dot on a graph.

  • Edges (Links) = represent relationships or interactions.
  • These could be follows, friendships, mentions, likes, retweets, etc.

Edges can be:

  • Directed (e.g., Twitter follow: A follows B, but B might not follow back)
  • Undirected (e.g., Facebook friends: A and B are mutually connected)
  • Weighted (more frequent interaction = higher weight)

This structure allows platforms to model not just who is connected, but how strong or important those connections are.

Real-World Example: Twitter (X)

Twitter is a perfect real-world case of graph theory in action.

  • Nodes = Users
  • Edges = Follow relationships (directed), Retweets, Mentions (directed & often weighted)

How Twitter Uses Graph Theory:

  • Influencer Detection: By calculating centrality (like PageRank), Twitter can find users who have the most influence or reach.
  • Community Detection: Clustering algorithms find groups of users who interact frequently (echo chambers, interest groups).
  • Recommendation Systems: “Who to Follow” suggestions rely heavily on analyzing graph structures (mutual follows, follower overlap).
  • Trend Propagation: Understanding how tweets spread helps find the key nodes that help a hashtag go viral