Design and Analysis of Algorithms Aug-Dec 2015

Assignment II here

Steiner tree approximation algorithm (From: V. V. Vazirani, "Approximation Algorithms") here

Online Steiner tree approximation algorithm (Prof. Yair Bartal, Hebrew University) here

Multicast Routing: Best response dynamics and Nash Equilibrium (From: J. Kleinberg and E. Tardos, "Algorithm Design") here

LP rounding algorithm for vertex cover (Prof. Chandra Chekuri, University of Illinois) here

Set Cover Approximation Algorithm (From: S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani, "Algorithms") here

Cache Marking Algorithms (Prof. Moses Charikar, Princeton University) here

Exam I Solutions here

Assignment I here

Practice Problems in Dynamic Programming (Prof. Brian C. Dean, Clemson University) here

Two Useful Websites for Problems on Dynamic Programming and Greedy Algorithms (worth a visit - similar types could appear for the exam - But you lose marks if you study their solution blindly and it is not correct!) here and here

Interval Scheduling (Prof. Zack Butler, Rochester Institute) here