Algorithmic Paradigms

This course covers the main strategies for attacking a problem once you know the data structures: recursion, backtracking, greedy algorithms, and dynamic programming. Each is a general approach you apply across many problems, and most interview problems are an application of one of them.

This course assumes the data structures from "Arrays and Hashing" and "Graphs, Linked Structures" and some CS background, and is not intended as a substitute for general programming knowledge. It aims to be frugal with your time, acting as a crash course and refresher for the core algorithmic paradigms, and a repository you can look back on to remind yourself of the most immediately relevant details and intuitions for applying them.

What it covers

• Recursion: solving a problem in terms of smaller instances of itself, with a base case and a recursive case.
• Backtracking: searching a tree of choices, undoing a choice at a dead end, and pruning branches that cannot work.
• Greedy: committing to the locally-best choice when you can prove it is always safe, and recognizing when you cannot.
• Dynamic programming: storing and reusing subproblem answers, in one dimension and on a 2D grid.