Undecideable Problems and Graphs and Heuristics
Undecidable Problems
A problem for which no algorithm can be constructed
Halting Problem
Is it possible to write a program that determines whether another algorithm halts or not? Machine H: Determines whether a program halts or not Machine D: Does the opposite of what H says. If H is fed D’s program, and H says D will halt, then D will do the opposite, contradicting H.
Popcorn Hack 1
False
Popcorn Hack 2
True
Popcorn Hack 3
D
Homework:
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.
Modern operating systems and browsers use safety checks to stop infinite loops or long-running scripts from crashing the system. Browsers like Chrome and Firefox have script timeout warnings that stop a web page if a script runs too long. For example, I might see an error like “A script on this page may be busy or may have stopped responding.” Operating systems can also step in by letting users end unresponsive programs using tools like Task Manager for Windows or Force Quit for Mac. These systems help keep the device running smoothly and prevent it from freezing.
Graphs and Heuristics
1) A graph is a data structure used to represent relationships between objects. A graph consists of nodes and edges. - Undirected graphs: Edges are bidirectional - Unweighed graphsL All adges are considered equal - Directed graphs: edges have direction - Weighted graphs: edges have values
Popcorn Hack 1:
False
Heuristic:
A problem solving approach that simplifies the process by using rules of thumb
- Ex:
Greedy algorithmsL always uses the best immediate option
A* SearchL Finds the quickest path from one point to another
Popcorn Hack 2:
True. Provide a faster route but accuracy can be compromised
Travelling salesman problem
Finds the shortest route for a trip to n number of destinations.
Popcorn Hack 3
True.
Homework:
Explore the concept of “Social Network Analysis” and explain how graphs are used in analyzing social media platforms. Specifically, focus on: How are users (nodes) and relationships (edges) represented in social networks? Provide one example of a real-world social media platform where graph theory plays a crucial role.
Social Network Analysis is the study of how people or things are connected and how information flows between them. In this type of analysis, users are shown as nodes, and the relationships between them, like friendships or followers—are shown as edges. These graphs help us understand who is most connected, who spreads information fastest, or how communities form. A real-world example is Twitter, where users are nodes, and the “follows” relationship is an edge. This helps analyze trends, find influencers, and study how tweets go viral. Graph theory makes it easier to see patterns in massive networks.