Undecidable Problems & Graphs HW

Popcorn Hack 1

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

Correct Answer: FALSE

Popcorn Hack 2

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

Correct Answer: 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

ANSWER: D

HW HACK

Modern operating systems and browsers have ways to handle infinite loops or long-running scripts to keep things running smoothly. In operating systems like Windows and macOS, processes are monitored, and if something takes too long or uses too many resources, it might be automatically stopped. For example, on Windows, a program stuck in an infinite loop might show a “Not Responding” message, allowing you to close it. Browsers like Chrome and Firefox also handle this by setting time limits on scripts. If a script takes too long, the browser stops it and shows a message like “A script is running slowly.” This keeps the browser from freezing. Both operating systems and browsers use these methods to keep your system and apps responsive, making sure a stuck process doesn’t crash everything.

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.

Correct Answer: False

Popcorn #2

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

Correct Answer: True

Popcorn #3

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.

Correct Answer: True

HW HACK

Social Network Analysis (SNA) uses graphs to represent users as nodes and their relationships as edges. For example, on platforms like Facebook or Twitter, users are nodes, and their interactions, like following or liking posts, are edges connecting them. These relationships can be directed (one-way, like following someone) or undirected (mutual, like being friends). An example is Twitter, where users are connected by directed edges representing follows. Graph theory helps analyze how information spreads, identify influencers, and detect user communities. It also helps in recommending accounts to follow and predicting the popularity of content. This makes graph theory essential in understanding and improving social media platforms.