Fall 2013 - COMPSCI 530 - Design and Analysis of Algorithms

Administration

Instructor
Debmalya Panigrahi
D203, LSRC
Email: debmalya@cs.duke.edu
Office Hours: 3-4 pm on Wednesdays and 2-3 pm on Fridays (in LSRC D203)

Teaching Assistant
Jiangwei Pan
D211 LSRC
Email: jwpan@cs.duke.edu
Office Hours: 12:30-1:30 pm on Mondays and 4:40-5:40 pm on Wednesdays (in LSRC D301)

Lectures: Tuesdays and Thursdays 4:40-5:55 pm in LSRC D106

Announcements

11/21: PSET 6 Question 4 removed and a course feedback question added.
11/18: Instructor office hour on Wednesday (11/20) moved to 2-3pm.
11/14: Instructor office hour on Friday (11/15) moved to 1-2pm.
11/12: PSET 6 Question 2 updated.
10/20: HW4 Q1: the n variables are independent.
10/12: office hour on next Wed (10/16) of Prof. Panigrahi has been canceled.
10/9: Homework 3: 2(d) updated - solving at most min(|U|, |V|) LPs
10/7: Homework 3: LP of problem 2 updated
9/17: Office hour of instructor on 9/18 is moved from 3-4pm to 2-3pm.
9/5: Scribing templates have been uploaded
9/5: Because of Fall break, some adjustments have been made to the lecture schedule and the PSET release/submission dates.
8/29: Instructor's office hour scheduled for Friday 8/30 at 2-3 pm is rescheduled to Tuesday 9/3 at 11 am-12 noon.
8/29: TA's office hour on Monday 9/2 is cancelled because of Labor Day.

Synopsis

This course covers the design and analysis of algorithms at a graduate level. Topics include:

Data structures: Fibonacci heaps; splay trees
Network flows: Augmenting paths; blocking flows; push-relabel; scaling
Linear programming: Duality; separation oracles; applications
Randomized algorithms: Tail bounds; counting via sampling; Monte Carlo and Las Vegas algorithms; power of two choices
NP-hardness and approximation algorithms: Polynomial-time reductions; examples of approximation algorithms; strong NP-hardness and polynomial-time approximation schemes; LP relaxations and rounding; primal-dual algorithms
Online algorithms: Competitive analysis; paging and k-server; online LP rounding

Prerequisites

COMPSCI 330 (or an equivalent undergraduate course in algorithms) is a hard prerequisite. In addition, students must demonstrate maturity in mathematical reasoning. If you are looking for a graduate algorithms course with more of an applications focus, you should consider taking COMPSCI 590.02.

Grading

The course grades will be determined based on:

6 Problem Sets (PSETS), one roughly every two weeks, and due before the next PSET is released (total weightage: 40%)
MIDTERM examination (weightage: 30%)
FINAL examination (weightage: 30%)

Collaboration Policy

Collaboration is allowed on PSETS. However, every student MUST write his/her own answer after understanding the solution and clearly state the names of all collaborators for each problem. Students will be heavily penalized if they are unable to explain their answers on being asked to do so. Collaboration should be limited to groups of 2-3 students.

Collaboration in examinations is strictly prohibited.

Late Submissions

PSETS submitted within one week of the deadline will be awarded 50% credit. PSETS submitted more than one week late will receive no credit. In exceptional circumstances, students can submit PSETS late without any loss in credit if prior permission is obtained from the instructor.

Scribing

Every student should expect to scribe approximately one lecture over the course of the semester.

Scribing template: .tex, .pdf

References

The instructor will give a list of book chapters and/or research papers that will serve as reference for the material covered in each lecture. The following books may be useful in general as reference books:

[BE] Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1st ed., 1998
[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2nd ed., 2001
[DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006
[KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 1st ed., 2005
[MR] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[V] V. V. Vazirani, Approximation Algorithms, Springer-Verlag, Berlin, 2001.
[WS] D. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

Course Plan

	Date	Contents	References	Remarks	Scribe notes²	Instructor notes
		Data Structures
Lecture 1	Tues Aug 27	Introduction and administrivia Fibonacci heaps and application to Shortest Paths	CLRS: Chapter 20	Course Info	Notes¹ on Fibonacci heaps	Notes
Lecture 2	Thurs Aug 29	Splay trees; Introduction to network flows		PSET 1 out	Notes¹ on splay trees	Notes
		Network Flows
Lecture 3	Tues Sep 3	Augmenting Paths	CLRS: Chapter 26 KT: Chapter 7		Notes¹, more notes¹ on augmenting paths	Notes Notes
Lecture 4	Thurs Sep 5	Blocking flows			Notes¹ on blocking flows	Notes
Lecture 5	Tues Sep 10	Preflows and the push-relabel algorithm			Notes by Yuzhang Han	Notes Notes
Lecture 6	Thurs Sep 12	Scaling: The Goldberg-Rao algorithm	Goldberg-Rao paper	PSET 1 due PSET 2 out	Notes By Abhishek Kumar Dubey	Notes
		Linear programming
Lecture 7	Tues Sep 17	Duality, Farkas' lemma, and complementary slackness	CLRS: Chapter 29 DPV: Chapter 7 KT: Chapter 11.6 V: Chapter 12 WS: Chapter 1.2, 4.3		Notes by Hieu Bui	Notes
Lecture 8	Thurs Sep 19	Separation oracles and the ellipsoid algorithm			Notes by Chao Xu	Notes
Lecture 9	Tues Sep 24	Applications: Flow-cut duality and matchings			Notes by Zilong Tan	Notes
Lecture 10	Thurs Sep 26	Applications: Min-cost flows		PSET 2 due PSET 3 out	Notes¹ on min-cost flows	Notes
		Randomized Algorithms
Lecture 11	Tues Oct 1	Probabilistic tools: Linearity of expectation, Tail bounds Counting via sampling: The Monte Carlo method	MR: Chapter 3, 4 MR: Chapter 11.1, 11.2 MR: Chapter 1, 10.2 Power of two choices paper		Notes by Nat Kell	Notes
Lecture 12	Thurs Oct 3	Biased sampling and DNF counting Monte Carlo algorithms: global min-cut				Notes Notes
Lecture 13	Tues Oct 8	Las Vegas algorithms: randomized quicksort Power of two choices: load balancing				Notes Notes
	Thurs Oct 10	MIDTERM examination		PSET 4 out
	Tues Oct 15	Fall Break: NO CLASS
Lecture 14	Thurs Oct 17	Randomized lower bounds: Yao's min-max principle		PSET 3 due		Notes
		NP-hardness and Approximation Algorithms
Lecture 15	Tues Oct 22	Polynomial-time reductions Approximation algorithms: vertex cover, set cover, maximum coverage, metric TSP	CLRS: Chapters 34, 35 KT: Chapters 8, 11.3, 11.4 V: Appendix A, Chapters 1, 2, 3 WS: Appendix B, Chapters 1.6, 2.4		Notes by Ang Li	Notes
Lecture 16	Thurs Oct 24	Strong NP-hardness and PTAS/FPTAS: knapsack, bin packing	KT: Chapter 11.8 V: Chapters 8, 9 WS: Chapter 3	PSET 4 due PSET 5 out	Notes by Utku Sirin	Notes
Lecture 17	Tues Oct 29	Guest Lecture: Prof. Pankaj K. Agarwal More approximation algorithms			Notes By Fangjian Guo
Lecture 18	Thurs Oct 31	LP relaxation: vertex cover via threshold rounding, set cover via randomized rounding	KT: Chapter 11.6 V: Chapter 14 WS: Chapter 1.7		Notes By Lucas Spangher	Notes
Lecture 19	Tues Nov 5	LP relaxations and rounding (contd.): scheduling on unrelated machines, max-SAT	V: Chapters 16, 17 WS: Chapters 5, 11.1	PSET 6 out	Notes by Ergys Ristani	Notes
Lecture 20	Thurs Nov 7	Set cover analysis via Dual Fitting; Integrality gap of set cover LP	V: Chapter 13 WS: Chapter 1.5	PSET 5 due	Notes by Reem Mokhtar	Notes Notes
Lecture 21	Tues Nov 12	Primal-Dual methods: metric facility location	V: Chapter 24 WS: Chapter 7.6 Jain-Vazirani paper			Notes
Lecture 22	Thurs Nov 14	Primal-dual methods: shortest path, steiner forest	V: Chapter 22 WS: Chapters 7.3, 7.4 Agrawal-Klein-Ravi paper Goemans-Williamson paper		Notes by Abhinandan Nath
		Online Algorithms
Lecture 23	Tues Nov 19	Competitive ratio, online lower bounds, randomization: rent or buy problems, paging	BE: Chapters 3. 4 MR: Chapter 13		Notes By Hangjie Ji	Notes
Lecture 24	Thurs Nov 21	Potential function: scheduling on unrelated machines	BE: Chapter 12 Aspnes-Azar-Fiat-Plotkin-Waarts paper			Notes
Lecture 25	Tues Nov 26	Linear programming: set cover	Buchbinder-Naor survey Alon-Awerbuch-Azar-Buchbinder-Naor paper	PSET 6 due	Notes by Nisarg Raval
	Fri Dec 13	FINAL examination

¹ Notes courtesy of David Karger, from the graduate algorithms course at MIT.
² Disclaimer: The scribe notes have not been reviewed for correctness.