Early undergraduateComputationPlanned
Algorithm design and analysis
Recursion and divide and conquer, greedy algorithms, dynamic programming, graph algorithms (breadth- and depth-first search, shortest paths, spanning trees), asymptotic analysis and correctness proofs.
math.comp.algorithm-design
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
Builds on
Required prerequisites, all the way down: 18
You will learn to
- Design divide-and-conquer algorithms and analyse them with recurrences, as for mergesort.
- Prove the correctness of greedy algorithms such as Kruskal's algorithm and Dijkstra's algorithm with non-negative weights.
- Design dynamic-programming algorithms for problems such as longest common subsequence.
Definition
- Divide and conquer splits a problem into smaller instances, solves them recursively and combines the results.
- Dynamic programming solves a problem by combining solutions of overlapping subproblems, storing them to avoid recomputation.
Theorem
- Mergesort runs in O(n log n) time.
- Dijkstra's algorithm finds shortest paths from a source vertex when all edge weights are non-negative.
- Kruskal's algorithm finds a minimum spanning tree of a connected weighted graph.
Common misconceptions
- Using Dijkstra's algorithm when some edge weights are negative.
- Assuming a greedy algorithm is correct without a proof.
Leads to
Optional discoveries
- Graph theory Matching and network-flow algorithms are algorithmic counterparts of theorems such as Hall's and Menger's.
- ← Dots and lines: networks and puzzles
Learning pathways
Further reading
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005)