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