Classes

The lectures are broken into units, as shown below. The notes will be updated after every class. These pages are also reachable from the main calendar.

Unit 1: Design, Analysis, Implementation (Classes 1–4)
Introduction, Basic terminology, Asymptotic analysis
Unit 2: Sorting Part I (Classes 5–8)
Recursive analysis, MergeSort, Lower bound for sorting
Unit 3: Number-Theoretic Computations (Classes 9–13)
Modular arithmetic, Euclidean algorithm, Primality testing, RSA
Unit 4: Multiplication (Classes 14–19)
Karatsuba's algorithm, Strassen's algorithm, Master method, Chain multiplication, Dynamic programming
Unit 5: Sorting Part II (Classes 20–26)
QuickSelect, Randomized algorithms, QuickSort, Non-comparison based sorting
Unit 6: Graph Search (Classes 27–33)
Basic traversal, All-pairs shortest paths, Backtracking, Approximation algorithms
Unit 7: Completeness and Complexity (Classes 34–40)
Complexity classes, Reductions, NP-Complete problems
Unit 8: More Data Structures (Classes 41–41)
Dynamic arrays, Amortized analysis, Self-organizing search, Competitive analysis