CS356 LIST
==========

+ Minimum Vertex Cover IP (W1 - 2)
+ Integrality Gap (W1 - 2)
+ LP Relaxation (W1 - 2)
+ Approximation Ratio (W1 - 2)
+ Minimum Set Cover (W1 - 3)
+ LP Duals (W2 - 1)
+ Greedy Algorithm for Set Cover (W2 - 2)
+ Complementary Slackness (Alpha-Beta Complementary Slackness !!) (W3 - 1)
+ Min Set Cover Freezing Alg (Complementary Slackness Alg) (W3 - 2)
+ Primal Dual for Set Cover (W3 - 2 contained in above)
+ Min Knapsack Cover (Complementary Slackness Alg) (W3- 3) (!! complex approximation ratio)
+ Markov's Inequality (Rehearse proof) (W4 - 1)
+ Randomized Rounding for Minimum Set Cover (W5 - 1 Page 28 of Book)
+ Chernoff Bounds (W5 - 2) (MEMORIZE!!!) (Proof in notebook)
+ Rand Round for MSC Analysis using Chernoff Bounds (Important!)
+ Max Cut (W6 - 2)
+ Randomized Max Cut (W6 - 2)
+ Derandomization via Conditional Expectation (W7 - 1)
+ Derandomizing Max-Cut (W7 - 2) (Some complexity in calculating lambda(alpha i))

- Min Cut (W8 - 1, separate notes)
- Facility Location (W8 - 2)
- Big Oh/Omega (Outside of lectures)