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

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

- 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

- 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 in examinations is strictly prohibited.

Scribing template: .tex, .pdf

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

Date | Contents | References | Remarks | Scribe notes^{2} |
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^{1} on Fibonacci heaps |
Notes |

Lecture 2 | Thurs Aug 29 | Splay trees; Introduction to network flows | PSET 1 out | Notes^{1} on splay trees |
Notes | |

Network Flows | ||||||

Lecture 3 | Tues Sep 3 | Augmenting Paths | CLRS: Chapter 26 KT: Chapter 7 |
Notes^{1}, more notes^{1} on augmenting paths |
Notes Notes | |

Lecture 4 | Thurs Sep 5 | Blocking flows | Notes^{1} 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^{1} 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 |