Invalid/Valid/Sound II + Hamiltonian/Eulerian Paths and Cycles
0As always, I track your performance on quizzes to see how quickly I should progress the class. Figuring out the difference between Invalid/Valid but not Sound/Valid and Sound arguments can be tricky, so I started class by going over that again.
Then we continued our discussion of graph theory (especially with definitions, which get a bit of time to get used to). We solved a famous math problem from Good Will Hunting during lab time (during which the video was paused), which taught what the degree of a vertex means, and how graphs are the same even if you move them around.
Finally, we finished by discussing the famous "Bridges of Konigsberg" (https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg) problem.
A "path" in a graph is when you walk through the graph, never backtracking, while visiting every edge (Eulerian path) or vertex (Hamiltonian path). A "cycle" is a path where you end up where you started. Figuring out if a Eulerian path is possible is very easy. Either all of the vertices have a degree of 2, or at most two of them have an odd degree - if this is the case, then a Eulerian path is possible. If all of the nodes have an even degree, it doesn't matter where you start, a path is trivially solvable. If two of the nodes have an odd degree, then you have to start in one of the places with an odd degree (because you leave and never come back, allowing it to be odd) and you end in the one with the other odd degree (because you arrive and you never leave).
A Hamiltonian path or cycle looks a lot easier to solve, but it's actually a very difficult problem to solve for a large graph. As such, you can actually use it to prove your identity. Making a graph with a Hamiltonian is easy, you just make a large ring of vertices, and then add a bunch of confounding edges to it. As long as you wrote down the original ring of vertices, you can solve it and nobody else can. So you could visit a friend and drop off a Hamiltonian puzzle, and then prove that it was you years later by giving them a solution to the puzzle.
Other Videos By Bill Kerney
| 2021-10-06 | Graph Traversal + Dijkstra's Algorithm |
| 2021-10-06 | The Infamous Kitty Rocket Launcher |
| 2021-10-06 | Swimming, Delta Time, Terminator Barrel, UMG HUDs |
| 2021-10-04 | ACM Talk: Hazelton Teaches Vim |
| 2021-10-04 | Writing to Files, Error Messages in C++ (scary), and Recursion |
| 2021-10-04 | Midterm Review + Equivocation Fallacy |
| 2021-10-02 | Reading from Files in C++ |
| 2021-10-02 | Fallacies Part I |
| 2021-09-30 | How to export and import assets between projects in UE4 |
| 2021-09-30 | Making an AI Enemy Part II |
| 2021-09-30 | Invalid/Valid/Sound II + Hamiltonian/Eulerian Paths and Cycles |
| 2021-09-30 | UE4 Damage System and HUDs with UMG |
| 2021-09-30 | Top-Down and Bottom-Up Programming |
| 2021-09-29 | Midterm I Review |
| 2021-09-29 | Making a Castle with the Procedural Spline Walls System |
| 2021-09-28 | Making an AI Opponent Part I |
| 2021-09-28 | Graph Theory I |
| 2021-09-27 | 2D Vectors and Arrays |
| 2021-09-27 | Scratch Part II |
| 2021-09-25 | Auto + Growing Vectors + Nonblocking I/O |
| 2021-09-24 | Introduction to Scratch |