Classes

This is the archived website of SI 335 from the Spring 2015 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–2)

Introduction, Basic terminology, Asymptotic analysis**Unit 2: Sorting Part I**(Classes 3–5)

Recursive analysis, MergeSort, Lower bound for sorting**Unit 3: Number-Theoretic Computations**(Classes 6–9)

Modular arithmetic, Euclidean algorithm, Primality testing, RSA**Unit 4: Multiplication**(Classes 10–15)

Karatsuba's algorithm, Strassen's algorithm, Master method, Chain multiplication, Dynamic programming**Unit 5: Graph Algorithms**(Classes 16–20)

Minimum Spanning Trees, Transitive Closure, Greedy algorithms, Backtracking, Approximation algorithms**Unit 6: Completeness and Complexity**(Classes 21–24)

Complexity classes, Reductions, NP-Complete problems**Unit 7: Advanced Sort & Search**(Classes 25–27)

QuickSelect, Randomized algorithms, QuickSort, Non-comparison based sorting