Undecidable Problems
Popcorn Hack 1
An algorithm can be used to solve an undecidable problem. (True/False)
Popcorn Hack 2
If a programmer encounters an undecidable problem, they can just use an algorithm that works most of the time. (True/False)
Popcorn Hack 3
Which of the following options is not an example of an undecidable problem?
A. Halting Problem
B. The Collatz Conjecture
C. Rice’s Theorem
D. Bubble sorting
Homework Hack 1
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.
When using Google Chrome browser engines, if a page is taking too long to load and is excessively running long scripts of JavaScript, it can return ‘Page Unresponsive’ to indicate to the user that the page is taking longer than usual. Then, the user has a choice to keep waiting or to exit out of the page.
Graphs & Heuretics
Popcorn Hack 1
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.
Popcorn Hack 2
True or False: Heuristics always provide faster solutions than exact algorithms, but they may sacrifice accuracy for speed.
Popcorn Hack 3
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.
Homework Hack 1
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 looks at how people connect online. It uses graphs made of dots (nodes) and lines (edges). Each dot is a person. Each line is a connection, like being friends or sending messages. On Instagram, a user is a node. If you follow someone, that’s a line going from you to them. This helps find popular people, groups of friends, and how posts spread. It also helps Instagram suggest new people to follow.