Fall 2013 - COMPSCI 530 - Design and Analysis of Algorithms


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



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


The course grades will be determined based on:

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.


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

Scribing template: .tex.pdf


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:

Course Plan

Date Contents References Remarks Scribe notes2                       Instructor notes
Data Structures
Lecture 1 Tues Aug 27 Introduction and administrivia
Fibonacci heaps and application to Shortest Paths
CLRS: Chapter 20 Course Info Notes1 on Fibonacci heaps
Lecture 2 Thurs Aug 29 Splay trees; Introduction to network flows PSET 1 out Notes1 on splay trees
Network Flows
Lecture 3 Tues Sep 3 Augmenting Paths CLRS: Chapter 26

KT: Chapter 7
Notes1, more notes1 on augmenting paths Notes Notes
Lecture 4 Thurs Sep 5 Blocking flows Notes1 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
Notes1 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
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


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

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 JiNotes
Lecture 24 Thurs Nov 21 Potential function: scheduling on unrelated machines BE: Chapter 12

Aspnes-Azar-Fiat-Plotkin-Waarts paper
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
1 Notes courtesy of David Karger, from the graduate algorithms course at MIT.
2 Disclaimer: The scribe notes have not been reviewed for correctness.