Fall 2021: T-Th 5:00 pm -- 6:15 pm, Taft Hall (TH) 215
| Week | Date | Topic | Notes |
|---|---|---|---|
| 1 | T. 8/24 | Course Introduction | Course Syllabus Course Topics |
| Th. 8/26 | Complexity Classes | Class Notes | |
| 2 | T. 8/31 | NP Complete problems: SAT, 3SAT, MIS | Class Notes |
| Th. 9/2 | NP Complete problems: Clique, Vertex Cover, Set Cover | Class Notes | 3 | T. 9/7 | Set cover, 3D matching | Class Notes |
| Th. 9/9 | Subset Sum, Exact cover by 3-sets, Set Partitioning, Max Cover | Class Notes | |
| 4 | T. 9/14 | Subgraph isomorphism, Min. Steiner tree | Class Notes |
| Th. 9/16 | Hamiltonian Cycle, TSP | Class Notes | |
| 5 | T. 9/21 | Bin Packing, 0/1 Knapsack, 0/1 Int Programming | Class Notes |
| Th. 9/23 | Introduction to Approximation algorithms, PTAS/FPTAS, Vertex Cover and MIS, General TSP | Class Notes | |
| 6 | T. 9/28 | Metric-TSP Approximation | Class Notes |
| Th. 9/30 | Set cover approximation | Class Notes | |
| 7 | T. 10/5 | Introduction to LP and ILP | Class Notes |
| Th. 10/7 | Course Review | ||
| 8 | T. 10/12 | Midterm Exam | |
| Th. 10/14 | Introduction to LP Relaxation; LP-Relaxation for Vertex Cover | Class Notes | |
| 9 | T. 10/19 | FPTAS for Subset Sum |
Class Notes (Optional) PTAS for Euclidian TSP by Sanjeev Arora |
| Th. 10/22 | Submodular Functions and their optimization | Class Notes | |
| 10 | T. 10/26 | Approximation Algorithm for Max k-cover Introduction to Randomized Algorithms Las Vegas/Monte Carlo paradigms |
Class Notes |
| Th. 10/28 | Randomized Quick Sort; Max 3 SAT | Class Notes (R-Qsort) Class Notes (Max-3-SAT) |
|
| 11 | T. 11/2 | Randomized Min cut | Class Notes |
| Th. 11/4 | Occupancy Problems | Class Notes | |
| 12 | T. 11/9 | Markov Inequality; Chebyshev inequality; Stable Marriage | Class Notes: Tail Inequalities |
| Th. 11/11 | Coupon Collector's Problem | Class Notes | |
| 13 | T. 11/16 | Chernoff bound and applications Sampling: Inverse CDF Method; Menote-Carlo (Accept-Reject) Sampling |
Class Notes (Chernoff Bound) Class Notes (Sampling-1) |
| Th. 11/18 | Reservoir Sampling; Metropolis Hasting's Algorithm | Class Notes (Reservoir Sampling) Class Notes (Metropolis Hasting) |
|
| 14 | T 11/23 | Nearest Neighbor Research; Local Sensitive Hashing (LSH) | Class Notes (updated) |
| 15 | T. 11/30 | Probablistic Method; Randomized rounding (Max-SAT) | Class Notes |
| Th. 12/2 | Course Review | ||
| Th. 12/9 | FINAL EXAM. 3:30 PM 5:30 PM 2TH 215 | ||