Popcorn Hack 1

An algorithm can be used to solve an undecidable problem. (True/False)

False

Popcorn Hack 2

If a programmer encounters an undecidable problem, they can just use an alogorithm that works most of the time. (True/False)

True

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

D. Bubble sorting

Undecideable Problems Homework:

Question/research:

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.

Lots of pages and apps have a timeout that will handle cases that have infinity loops. If an app is running in a loop for too long, and the program is aware that this loop is a possiblility, it will use a timeout (set to a specific time) to determine if the application took too long and is deemed infinite. This is used when we run our MAKEFILE after 60 seconds.

Graphs and Heuristics

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.

False

Popcorn Hack #2

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

True

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.

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.

Graphs are used in analyzing social media platforms. For example on Instagram, if User A follows User B then it creates an edge between the User A node and the User B node. This edge represents a follow event. Graph theory plays a crucial role in Instagram to represent relationships between users. Another example would be likes and shares a user has on their account (these would be an edge from the person who liked the post to the user who recieved the like).