Fall 2015 - COMPSCI 532 - Design and Analysis of Algorithms


Debmalya Panigrahi
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
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



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


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.


The course grades will be determined based on:


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.


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

No collaboration is allowed in exams.


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.


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:

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
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
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
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
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
Lecture 16 Fri Oct 23 LP rounding: bipartite matching (iterative rounding)
Steiner tree and TSP: MST, Christofides
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
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
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
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
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