Algorithms — running notes

Following CLRS (4th ed) for the core sequence. The fourth edition reorganises the dynamic programming chapter in a way I find easier to teach from than the third — start from rod cutting before matrix chain multiplication and the substructure idea is more obvious to students who have not yet developed pattern recognition.

Sorting — what I actually cover

• Insertion sort (motivation, loop invariants)
• Mergesort (divide and conquer template, master theorem)
• Quicksort (randomised analysis, why median-of-three matters in practice)
• Heapsort (briefly, mostly as motivation for priority queues)
• Counting/radix sort (only if there is time — students rarely remember it)

The pedagogical tension: introsort is what they will actually use. But teaching it requires teaching all three underlying algorithms first, so by then nobody is paying attention.

Dynamic programming

I no longer try to teach DP through Fibonacci. The example is too small to motivate memoisation and students who already know it switch off. Rod cutting works better. The two key ideas I try to land:

1. Identify the subproblem precisely. If you cannot state it in one English sentence, the recursion is wrong.
2. Draw the dependency graph. The order of solving falls out.

Worth reading

• Sedgewick and Wayne — Algorithms 4th ed. Sometimes the better undergraduate book than CLRS, especially for graph algorithms.
• Kleinberg and Tardos — Algorithm Design. Best treatment of network flow I know.
• Erickson — Algorithms (freely available online). Idiosyncratic but the recursion chapter is excellent.