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