Lectures
1  20 Jan  Lecture 1: Overview & Complexity 101 NPHardness, Approximation Concepts 

2  23 Jan  Lecture 2: Greed is Good Greedy Algorithms, Set Cover, Steiner Tree 

3  27 Jan  Lecture 3: Linear Programming 101 Basic Solutions, LP Algorithms, Duality 

4  30 Jan  Lecture 4: Knapsack Packing Knapsack Problems (1D, PTAS, FPTAS) 

5  3 Feb  Lecture 5: More Knapsack Packing Knapsack Problems (2D, mD, Complex) 
Asg 1 Due 
6  6 Feb  Lecture 6: How to Stop Lying Incentive Compatibility 

7  10 Feb  Lecture 7: How to Stop Lying II Incentive Compatible Approximation Mechanisms 

8  13 Feb  Lecture 8: More Fun of Knapsack Packing Incentive Compatible Knapsack Problem 

9  17 Feb  Lecture 9: Tightrope Walking into the Future Online Algorithms, Skirental, Paging 

10  20 Feb  Lecture 10: How to Make Money Online Algorithms for Trading 
Asg 2 Due 
11  24 Feb  Lecture 11: On or Off? Online Algorithms for Power Management 

12  27 Feb  Lecture 12: Probability 101 Probabilistic Methods, Tail Distribution 

13  3 Mar  Lecture 13: Probability 102 Large Deviation, Concentration of Measure 

14  6 Mar  Lecture 14: Power of Random Bits Hashing, Streaming Algorithms, Sampling 

15  10 Mar  Lecture 15: Power of Random Bits II Random Routing, Random Walk 
Asg 3 Due 
16  13 Mar  Seminar  
17  18 Mar  Seminar  
18  20 Mar  Seminar  
19  24 Mar  Seminar  
20  27 Mar  Seminar  Asg 4 Due 
31 Mar  Spring Break  
3 Apr  Spring Break  
7 Apr  Spring Break  
10 Apr  Spring Break  
21  14 Apr  Seminar  
22  17 Apr  Seminar  
23  21 Apr  Seminar  
24  24 Apr  Seminar  
25  28 Apr  Seminar  
26  1 May  Seminar  
27  5 May  Seminar  
28  8 May  Seminar  