Fall 2015 - COMPSCI 532 - 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
Allen Xiao
D208 LSRC
Email: axiao@cs.duke.edu
Office Hours: 3-4 pm on Tuesdays (in LSRC D301)

Lectures: Wednesdays and Fridays 4:40-5:55 pm in LSRC D106

Announcements

11/06: Homework 5 is out.
11/06: Midterm 1 solutions on Sakai.
10/14: Friday lecture (10/16) canceled, will be rescheduled.
10/14: Homework 4 is out.
10/14: Homework 2 solutions on Sakai.
10/04: Homework 3 deadline extended by one week (10/16).
09/29: Notes for lectures 1-10 updated.
09/23: Homework 3 is out.
09/22: Homework 1 solutions on Sakai.
09/21: Homework 2 deadline extended to Sunday (9/27).
09/11: Homework 1 deadline extended to Sunday (9/13).
09/11: Notes for lectures 1-5 updated.
09/09: Homework 2 is out.
09/07: Homework 1 deadline extended to Friday (9/11).
08/26: Homework 1 is out.
08/26: Please sign up for a grading slot on Piazza.
08/26: Make sure you're enrolled in ACES, Sakai, and Piazza.

Synopsis

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

Network flows: augmenting paths; blocking flows; push-relabel; scaling
Linear programming: solvers; separation oracles; duality; applications
Randomized algorithms: sampling; Monte Carlo and Las Vegas algorithms; big data algorithmics
NP-hardness and approximation algorithms: polynomial-time reductions; approximation algorithms; LP relaxations and rounding; integrality gaps; primal-dual algorithms; semi-definite programming
Other topics: online algorithms and competitive analysis; impossibility and lower bounds

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 531.

Evaluation

The course grades will be determined based on:

5 homework assignments, one roughly every two weeks, and due before the next one is released (total weightage: 45%)
2 in-class midterm exams (total weightage: 50%)
Class participation (weightage: 5%)

Homework

Homework assignments have to be submitted by 11:59 pm Eastern time using Sakai on the due date. Late submissions will receive 50% credit within one week of the due date, and no credit thereafter. In exceptional circumstances, students can submit homework assignments late without any loss in credit if prior permission is obtained from the instructor.

Review the detailed guidelines on collaboration in homework assignments. Any violation will be reported without exception to the relevant authority for disciplinary action.

Exams

There will be two in-class, closed book, proctored midterm exams. There is no final exam.

No collaboration is allowed in exams.

Discussions

We will use Piazza for course-related discussions, polls, etc. Please do not email the course staff with questions, instead post them on Piazza and the course staff will answer them.

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. Scribe notes will also be provided. The following books may be useful in general as reference books:

[BE] A. Borodin and R. 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
		Network Flows
Lecture 1	Wed Aug 26	Introduction, the max-flow min-cut theorem	CLRS: Chapter 26 KT: Chapter 7 Goldberg-Rao paper	HW 1 out	Notes
Lecture 2	Fri Aug 28	Augmenting paths, blocking flows			Notes
Lecture 3	Wed Sep 2	Scaling: The Goldberg-Rao algorithm			Notes
Lecture 4	Fri Sep 4	Preflows and push-relabel algorithms			Notes
Lecture 5	Wed Sep 9	Minimum cost flows: cycle calcellation, cost scaling		HW 2 out	Notes
		Linear programming
Lecture 6	Fri Sep 11	Introduction and examples, weak duality	CLRS: Chapter 29 DPV: Chapter 7 KT: Chapter 11.6 V: Chapter 12 WS: Chapter 1.2, 4.3	HW 1 due	Notes
Lecture 7	Wed Sep 16	Strong duality, complementary slackness, applications			Same as 6
Lecture 8	Wed Sep 16	LP solvers (basics): simplex, ellipsoid and separation oracles, interior point methods			Notes
	Fri Sep 18	Dept meeting: Lecture rescheduled to Sep 16
Lecture 9	Wed Sep 23	Separation oracles			Same as 8
		Randomized Algorithms
		Probabilistic tools: Linearity of expectation, coupon collector, balls in bins	MR: Chapter 3, 4 MR: Chapter 11.1, 11.2 MR: Chapter 1, 10.2	HW 2 due HW 3 out	Notes
Lecture 10	Fri Sep 25	Probabilistic tools: Tail bounds (Markov, Chebyshev, Chernoff)			Same as 9
Lecture 11	Wed Sep 30	Monte Carlo sampling, DNF counting			Notes
Lecture 12	Fri Oct 2	Monte Carlo algorithms: randomized contraction for global min-cut Las Vegas algorithms: randomized quicksort			Notes
	Wed Oct 7	Midterm 1
		NP-hardness and Approximation Algorithms
Lecture 13	Fri Oct 9	The complexity classes P and NP NP-hardness and NP-completeness: Polynomial-time reductions Introduction to approximation algorithms: vertex cover	CLRS: Chapter 34, 35 KT: Chapter 8, 11.3, 11.4 V: Appendix A, Chapter 1, 2 WS: Appendix B, Chapter 1.6		Notes
Lecture 14	Wed Oct 14	Greedy approximation: set cover, bipartite matching Dual fitting: vertex cover	V: Chapter 13 WS: Chapter 1.6, 9.4	HW 4 out	Notes
	Fri Oct 16	Instructor travel: Lectures on Oct 23 and Oct 28 extended		HW 3 due
Lecture 15	Wed Oct 21	Dual fitting: set cover, bipartite matching LP rounding: vertex cover (threshold rounding), set cover (randomized rounding)	KT: Chapter 11.6 V: Chapter 14, 16, 17 WS: Chapter 1.7, 5, 11.1		Same as 14 Notes
Lecture 16	Fri Oct 23	LP rounding: bipartite matching (iterative rounding) Steiner tree and TSP: MST, Christofides			Notes
Lecture 17	Fri Oct 23 Wed Oct 28	Primal-dual methods: MST algorithms, Steiner forest (AKR/GW)	V: Chapter 22, 24 WS: Chapter 1.5, 7.3, 7.4, 7.6 Goemans-Williamson paper		Notes
Lecture 18	Wed Oct 28	Strong and Weak NP-hardness Polynomial-time Approximation Schemes	MR: Chapter 11 V: Chapter 8 WS: Appendix B, Chapters 1.1, 3		Notes
Lecture 19	Fri Oct 30	Semi-definite programming	V: Chapter 26 WS: Chapter 6	HW 4 due	Notes
Lecture 20	Wed Nov 4	Integrality gaps: vertex cover, minimum spanning tree			Notes
		Other Topics
Lecture 20	Wed Nov 4	Online Algorithms: Rent-or-buy problems	BE: Chapter 3, 4 MR: Chapter 13		Notes
Lecture 21	Fri Nov 6	Online Algorithms: Paging and k-server	BE: Chapter 12	HW 5 out	Same as 20
Lecture 22	Wed Nov 11	Data Streaming Dimensionality reduction			Notes
Lecture 23	Fri Nov 13	Lower bounds: information-theoretic and computational			Same as 22
Lecture 24	Wed Nov 18	Beyond worst-case analysis		HW 5 due
	Fri Nov 20	Midterm 2