Classes

This is the archived website of SI 335 from the Spring 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

The lectures are broken into 7 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–9)
Recursive analysis, MergeSort, Lower bound for sorting
Unit 3: Number-Theoretic Computations (Classes 10–16)
Modular arithmetic, Euclidean algorithm, Primality testing, RSA
Unit 4: Multiplication (Classes 17–23)
Karatsuba's algorithm, Strassen's algorithm, Master method, Chain multiplication, Dynamic programming
Unit 5: Graph Search (Classes 24–30)
Basic traversal, All-pairs shortest paths, Backtracking, Approximation algorithms
Unit 6: Completeness and Complexity (Classes 31–36)
Complexity classes, Reductions, NP-Complete problems
Unit 7: Advanced Sort & Search (Classes 37–41)
QuickSelect, Randomized algorithms, QuickSort, Non-comparison based sorting