Lectures

1 20 Jan Lecture 1: Overview & Complexity 101
NP-Hardness, 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, Ski-rental, 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