TechPrep

Search spaces and optimisation

Topological sort, backtracking with pruning, dynamic programming and greedy algorithms you can defend.

Lessons

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