Undecidable Problems Homework Hacks

This is hacks

• 4 min read

Popcorn Hack 1

Q: An algorithm can be used to solve an undecidable problem.
A: False

Popcorn Hack 2

Q: If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time.
A: True

Popcorn Hack 3

Q: Which of the following options is not an example of an undecidable problem?
A: D. Bubble sorting

Question/Research

Q: Investigate and describe how modern operating systems and browsers handle infinite loops or excessively long-running scripts. What mechanisms are in place to detect and mitigate such issues? Provide real-world examples of these mechanisms in action, such as specific error messages, timeouts, or automated recovery processes.

📱 Operating Systems

Modern operating systems use several mechanisms to detect and manage infinite loops or excessively long-running processes:

  • CPU Scheduling and Time Slices: Operating systems use preemptive multitasking, where each process is given a fixed “time slice.” If a process exceeds its allocated time or becomes unresponsive, it can be deprioritized or terminated.

  • Task Manager / Activity Monitor: Tools like Windows Task Manager or macOS Activity Monitor let users manually end unresponsive programs.

  • Watchdog Timers (System-Level): Some systems use watchdog timers to detect hangs and restart services or the entire system.

🔧 Real-World Example:
On Windows, if a program becomes unresponsive due to an infinite loop, it will trigger the “Not Responding” label in the title bar. The user may be prompted to close the application manually.

🌐 Web Browsers

Browsers also have built-in protections to handle long-running or infinite JavaScript:

  • Script Timeouts: Browsers monitor the execution time of scripts. If a script runs too long, it may prompt the user with a message like:

    “A script on this page may be busy, or it may have stopped responding.”

  • Worker Threads: Browsers can offload long-running code to Web Workers. If a worker becomes unresponsive, it can be terminated without freezing the main UI thread.

  • Performance Monitoring Tools: DevTools in Chrome and Firefox include performance profilers to detect inefficient or looping code.

🔧 Real-World Example:
In Firefox, when a script takes too long to run, users may see:

“Warning: Unresponsive script — A script on this page may be busy, or it may have stopped responding…”

In Chrome, long-running JavaScript can cause the browser tab to crash with an “Aw, Snap!” error.

✅ Summary

Platform Detection Mechanism User Action / System Response
OS (Windows) Task Manager, CPU monitoring End task manually or auto-prompted
OS (macOS) Activity Monitor Force quit app
Web Browsers Script timeout, Web Workers, DevTools Show error message or crash tab

These safeguards ensure that infinite loops don’t crash entire systems or ruin user experience.

Graphs and Heuristics Lesson hacks

Popcorn Hack #1

Q: 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.
A: False

Popcorn Hack #2

Q: True or False: Heuristics always provide faster solutions than exact algorithms, but they may sacrifice accuracy for speed.
A: True

Popcorn Hack #3

Q: 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.
A: True

Homework: Social Network Analysis

📘 What is Social Network Analysis?

Social Network Analysis (SNA) is the process of investigating social structures through the use of networks and graph theory. It helps understand how individuals (or entities) are connected and how information or influence flows through social systems.

🔗 Graph Representation in Social Media

In graph theory:

  • Nodes (Vertices): Represent individual users or entities.
  • Edges (Links): Represent relationships between those users (e.g., friendships, follows, messages).

Types of Graphs in SNA:

  • Directed Graphs: Used when relationships have a direction (e.g., Twitter follows — A follows B doesn’t mean B follows A).
  • Undirected Graphs: Used when relationships are mutual (e.g., Facebook friends — both users have to accept the connection).
  • Weighted Graphs: Edges can have weights showing the strength of a relationship (e.g., number of messages exchanged).

🌐 Real-World Example: Facebook

Facebook is a prime example of a platform where graph theory is crucial.

  • Each user is a node.
  • Friendships are undirected edges between users.
  • Facebook uses graph algorithms for:
    • Friend Recommendations (“People You May Know”)
    • Community Detection (e.g., suggested groups)
    • Content Spreading (e.g., how posts go viral)
    • News Feed Ranking (based on interaction patterns)

Facebook even created a framework called Graph API which allows developers to query the social graph and retrieve structured data.

✅ Summary Table

Graph Component Social Media Equivalent
Node User profile
Edge Follow, friend, or message
Directed Edge Follows (Twitter, Instagram)
Undirected Edge Mutual friends (Facebook)
Weight Interaction frequency

Graphs are essential to understanding user behavior, influence, and connectivity in digital social environments.