Divide and Conquer

Lecture Description

Course Description

This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.

Course Index

1. Analysis of Algorithms
2. Asymptotic Notation and Recurrences
3. Divide and Conquer
4. Quicksort
5. Sorting Lower Bounds and Linear-Time Sorting
6. Order Statistics
7. Hashing I
8. Hashing II
9. Randomly Built Binary Search Trees
10. Balanced Search Trees
11. Skip Lists
12. Amortized Analysis
13. Competitive Analysis
14. Dynamic Programming
15. Greedy Algorithms (and Graphs)
16. Shortest Paths I
17. Shortest Paths II
18. Shortest Paths III
19. Advanced Topics
20. Advanced Topics (cont.)
21. Advanced Topics (cont.)
22. Advanced Topics (cont.)