Spring 2020: T-Th 9:30 am -- 10:45 am, Thomas Beckham Hall 180D
| Week | Date | Topic | Notes |
|---|---|---|---|
| 1 | T. 1/14 | Course Introduction | |
| Th. 1/16 | Complexity Hierarchy | ||
| 2 | T. 1/21 | Polynomial Reductions | Notes by Kylash Viswanathan |
| Th. 1/23 | NP Complete problems: 3SAT, Vertex Cover, Max Independent Set | Notes by Eryk Zagorski | |
| F. 1/24 | Last day to complete late registration; last day to add a course(s) or make section changes; last day to drop individual courses via XE Registration without receiving W (Withdrawn) grade on academic record. Last day to Web Drop courses via XE Registration and receive 100% cancellation of tuition and fees. | ||
| 3 | T. 1/28 | Clique, Set cover, Subset Sum | Class Notes |
| Th. 1/30 | 3D matching, Exact cover by 3 sets, Subgraph isomorphism | Class Notes | |
| 4 | T. 2/4 | Graph coloring, Min. Steiner tree | Class Notes |
| Th. 2/6 | Hamiltonian Cycle, TSP, Set Partitioning, Bin Packing, 0/1 Knapsack | Class Notes Excercise Questions |
|
| 5 | T. 2/11 | Course Review | |
| Th. 2/13 | Exam 1 | ||
| 6 | T. 2/18 | Introduction to Approximation algorithms, Vertex Cover and Maximum Independent Set | Class Notes |
| Th. 2/20 | TSP Approximation | Class Notes | |
| 7 | T. 2/25 | Set cover approximation | Class Notes |
| Th. 2/27 | Introduction to LP and ILP | Class Notes | |
| 8 | T. 3/3 | ILP Approximation for Vertex Cover | Class Notes |
| Th. 3/5 | FPTAS for Subset Sum |
Class Notes (Optional) PTAS for Euclidian TSP by Sanjeev Arora |
|
| 9 | T. 3/10 | Submodular Functions and their optimization | |
| Th. 3/12 | Approximation Algorithm for Max k-cover Introduction to Randomized Algorithms |
Class Notes Excercise Questions |
|
| 10 | T. 3/31 | Las Vegas/Monte Carlo paradigms Randomized Quick Sort |
Class Notes |
| Th. 4/2 | Randomized Min cut; Max 3 SAT | Class Notes | |
| 11 | T. 4/7 | Occupancy Problems; Markov Inequality | Class Notes: Occupancy Problems |
| Th. 4/9 | Chebyshev inequality Stable Marriage; Coupon Collector's Problem |
Class Notes: Tail Inequalities | |
| 12 | T. 4/14 | Chernoff bound and applications | Class Notes |
| Th. 4/16 | Sampling: Inverse CDF Method; Menote-Carlo (Accept-Reject) Sampling | Class Notes | |
| 13 | T. 4/21 | Reservoir Sampling; Metropolis Hasting's Algorithm | Class Notes |
| Th. 4/23 | Probabilistic routing | Class Notes | |
| 14 | T. 4/28 | Nearest Neighbor Research; Local Sensitive Hashing (LSH) | Class Notes |
| Th. 4/30 | Probablistic Method; Randomized rounding (Max-SAT) | Class Notes | |