Undecidable Problems and Graphs

None

• 1 min read

Undecidable   Problems   and   Graphs

Popcorn Hack 1

An algorithm cannot be used to solve an undecidable problem.

Popcorn Hack 2

If a programmer somehow finds an algorithm that works most of the time when encountering an undecidable problem, they should just use that algorithm as there is no way to get it to work every time.

Popcorn Hack 3

D. Bubble sorting

Homework Hack 1

In some pages, they will detect some infinite loops written and/or monitor the runtime of a loop and break out of it if it runs for too long. Another page, Repl.it uses a method that doesn’t break out of the loop or prevent it, but instead uses other techniques to prevent the browser from overflowing with data, but this can cause problems with blocking keyboard or mouse input. Codepen, an online compiler, monitors loops that continue running after 2 seconds and break out of it after 2.2 seconds. These values can also be changed.

Popcorn Hack 1

False - in directed graphs, edges have directions, meaning that though there is may be an edge from a to b, it isn’t necessary that there is an edge from b to a as well

Popcorn Hack 2

True - somewhat estimates to find solutions faster, so they may be slightly innacurate but they will always be faster than exact algorithms

Popcorn Hack 3

True - exact/optimal solutions will grow exponentially as more options are presented and therefore the gap between heuristic algorithms and exact algorithms will also go exponentially

Homework Hack 1

In social networks, nodes are used for users or other similar things and edges represent actions/relationships/connections to the user. A real world social media platform where graph theory plays a crucial role is Instagram where users are nodes. Directed edges are used for things like when a user follows another user while undirected edges are used for when people are friends.