Search spaces and optimisation
Topological sort, backtracking with pruning, dynamic programming and greedy algorithms you can defend.
Lessons
- 01Topological sortOrder the nodes of a dependency graph so every edge points forward, and detect cycles for free.
- 02BacktrackingBuild candidates one choice at a time, undo each choice on the way back, and prune branches that cannot succeed.
- 03Dynamic programmingDefine the state, write the recurrence, fix the base case and fill the table in an order where every dependency is ready.
- 04Greedy, and how to defend itMake the locally best choice when you can prove an exchange argument shows it never hurts.