When designing an algorithm, ask yourself :
For which cases does the obvious method work?
Then find a new way to tackle the remaining cases!
Find a hamiltonian path through a tournament graph.
Using a more-of-input approach, we claim to have a solution while pretending that the nodes we have processed so far is the entire input instance.
We want to maintain the Loop Invariant by adding a new node and finding a new hamiltonian path through this new input instance (sub-instance).
How to do this? Case Analysis
We established that we have a hamiltonian path through
To get a new solution with added to form a new sub-instance, pretended to be the entire input,
|[Math] Definitions of Functions, Injection, Surjection, Bijection, and Inverse (0)||2018.07.04|
|How to Count - Number of Ways (경우의 수) (0)||2018.04.26|
|How to Count (The Fencepost Problem) - Off by One Errors! (0)||2018.04.26|
|Proof by Induction on Graphs - Why You Should Always Remove a Vertex (0)||2018.01.07|
|How to Design - Case by Case (0)||2017.12.18|
|How to Iterate over a fixed range of integers (0)||2017.12.15|
- Independent Set