# CS:5350 Design and Analysis of Algorithms

Fall 2019, 9:30-10:45 TTh 15 SH (Schaeffer Hall)

Instructor: Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:30-2:30 M, 10:30-11:30 W, 2:00-3:00 F (and by appointment).

Course webpage: homepage.cs.uiowa.edu/~sriram/5350/fall19/
Department website: http://www.cs.uiowa.edu/

This is the graduate algorithms course aimed at CS PhD students. It will be assumed that a typical student in the course has a solid background in undergraduate-level algorithms material. Please refer to the syllabus of a recent offering of CS:3330 (e.g., https://homepage.divms.uiowa.edu/~sriram/3330/spring18/syllabus.html) to better understand this expectation. Facility in discrete math, especially discrete probability, will be a definite benefit for students in this course. The course material is organized into 4 parts: (i) combinatorial optimization, (ii) randomized algorithms, (iii) approximation algorithms, and (iv) streaming and parallel algorithms. The material on streaming and parallel algorithms can be viewed as a modern application of the material in Parts (I)-(III).

## Other Resources

• Sample latex source files for scribe notes are in this directory.
• The appendices in the textbook Introduction to Algorithms (2nd ed) by Cormen, Leiserson, Rivest, and Shamir contain a helpful overview of discrete math that will be used in this course. Specifically, Appendix C on "Counting and Probability" will be helpful for students seeking to brush up their discrete probability knowledge.
• Read the proof of the specific version of the flow-decomposition theorem we discussed in class, in these lecture notes by Luca Trevisan. See Lemma 2 and its proof.

## Weekly Topics

• 8/26-8/30
(8/27) Overview of course content. We placed flow, cut, and matching problems in the landscape of graph problems. Definitions of flow, flow conservation, feasible flow, and flow value. Statement of the MAXFLOW problem.
8.27 Notes
(8/29) Applications of the MAXFLOW problem. Example of a reduction of the Baseball Elimination problem to MAXFLOW. Linear programming (LP) formulation of the MAXFLOW problem. 8.29 Notes
Readings: Sections 10.1, 10.2, and 11.6.

• 9/2-9/6
(9/3) Statement of the MINCUT problem. Introduction to the duality between MAXFLOW and MINCUT. Proof of the weak version of the maxflow-mincut theorem. Description of the proof stretegy of the maxflow-mincut theorem. 9.3 Notes
(9/5) Definitions of residual capacities, residual graph, and augmenting paths. Working on the proof of the maxflow-mincut theorem.9.5 Notes

• 9/9-9/13
(9/10) Completion of the proof of the maxflow-mincut theorem. Analysis of the Ford-Fulkerson algorithm. Introduction to the Edmonds-Karp "fat pipe" heuristic.
(9/12) The flow decomposition theorem. Analysis of the Edmonds-Karp "fat pipe" heuristic. Analysis of the Edmonds-Karp "fewest pipes" heuristic.9.12 Notes

• 9/16-9/20
(9/17) Completion of analysis of the Edmonds-Karp "fewest pipes" heuristic. Introduction to LP duality. The weak duality and strong duality theorems. 9.17 Notes
(9/19) More on LP duality. The primal LP for max-flow and its dual LP. 9.19 Notes
Readings: Section 10.6, specifically the proofs of Lemma 10.2 and Lemma 10.3, Luca Trevisan's lecture notes on LP duality and his lecture notes on flow and cut LPs.

• 9/23-9/27
(9/24) Interpretation of the dual LP as a min-cut relaxation. Proving that the integral version of the dual LP models the min-cut problem. Concluding via the maxflow-mincut theorem that the dual LP has an integral optimal solution. 9.24 Notes
(9/26) Introduction to the maximum matching problem. Bipartite matchiing, a special case of the maximum matching problem. Reducing the bipartite matching problem to maximum flow. Introduction to the distributed Maximal Independent Set (MIS) problem. A deterministic, greedy O(n)-round algorithm for the problem.9.26 Notes
Readings: Luca Trevisan's notes on maximum matching in bipartite graphs.

• 9/30-10/4
(10/1) Description of Luby's randomized algorithm for the distributed MIS problem. Starting the analysis for showing that the algorithm runs in O(log Delta log n) rounds.10.1 Notes
(10/3) Analysis of Luby's algorithm showing that in an iteration, a high degree node has at least constant probability of being deactivated.10.3 Notes
Readings: Gopal Pandurangan's book on distributed MIS. Read Chapter 6, pages 69-75 (until "Better Analysis").

• 10/7-10/11
(10/8) Completed the analysis of Luby's algorithm. 10.8 Notes
(10/10) Solved problems, in preparation for the midterm, on (i) Luby's MIS algorithm analysis, (ii) reducing problems to maxflow/mincut problems, and (iii) integer programs, LP relaxations, LP duality. 10.10 Notes
Readings: Gopal Pandurangan's book on distributed MIS. Read Chapter 6, pages 69-75 (until "Better Analysis").

• 10/14-10/18
(10/15) Defining the running time and error probability of randomized algorithms, Types of randomized algorithms: Las Vegas and Monte Carlo. ``Toy'' examples of Las Vegas and Monte Carlo algorithms using the Balanced Partition problem. The MINCUT problem and introduction to Karger's MINCUT algorithm. 10.15 Notes
(10/17) Analysis of Karger's MINCUT algorithm. 10.17 Notes

• 10/21-10/25
(10/22) Linearity of expectation, indicator random variables. Example of the use of linearity of expectation in the analysis of randomized Quicksort. Proof that randomized Quicksort runs in O(n log n) expected time. Another example of linearity of expectation in action: Coupon Collector's problem. 10.22 Notes
(10/24) Analysis of Coupon Collector's problem. Markov's Inequality. The use of Markov's Inequality in the analysis of a 1/4-approximation to MAXCUT. 10.24 Notes
Readings: Lecture notes on randomized algorithms from Stanford..

• 10/28-11/1
(10/29) Introduction to approximation algorithms. Definition of an alpha-approximation algorithm for minimization/maximization problems. A 2-approximation algorithm for Minimum Vertex Cover (MVC) via maximal matchings. 10.29 Notes
(10/31) Analysis of 2-approximation algorithm for MVC. A primal-dual view of this algorithm using LP duality. A 2-approximation algorithm for MVC using deterministic LP-rounding. 10.31 Notes

• 11/4-11/8
(11/5) Greedy approximation algorithms. A greedy 2-approximation algorithm for the k-CENTER problem. 11.5 Notes
(11/7) Analysis of k-CENTER greedy 2-approximation algorithm. Reduction from Minimum Dominating Set showing that a rho-approximation, for rho strictly less than 2, for k-CENTER is not possible unless P = NP. 11.7 Notes
Readings: Lecture notes by Michael Dinitz.

• 11/11-11/15
(11/12) The SETCOVER problem. A greedy approximation-algorithm for SETCOVER, yielding an O(log m)-approximation, where m = size of ground set. 11.12 Notes
(11/14) A pseudopolynomial time dynamic programming algorithm for KNAPSACK. Idea of a Fully Polynomial-time Approximation Scheme (FPTAS) for KNAPSACK.11.14 Notes (unedited)
Readings: Section 1.6 (A greedy algorithm for SETCOVER) and Section 3.1 (The Knapsack problem) from "The Design of Approximation Algorithms" by Williamson and Shmoys.

• 11/18-11/22
(11/19) Analysis of FPTAS for KNAPSACK.11.19 Notes (unedited)

(11/21) Introduction to approximation algorithms via LP-rounding. An f-approximation for SETCOVER via deterministic LP-rounding. An O(log m)-approximation via randomized rounding.11.21 Notes (unedited)

Readings: Section 3.1 (The Knapsack problem) and Section 1.7 (A randomized rounding algorithm for SETCOVER) from "The Design of Approximation Algorithms" by Williamson and Shmoys.

• 12/2-12/6
(12/3) Finished up analysis of randomized rounding for SETCOVER. MAXSAT: a randomized 1/2-approximation for MAXSAT.12.3 Notes (unedited)

(12/5) A (1-1/e)-approximation via LP randomized rounding for MAXSAT. A "best of two algorithms" approach to get a 3/4-approximation to MAXSAT.
Readings: Sections 5.4 and 5.5 (Randomized Rounding for MAXSAT) from "The Design of Approximation Algorithms" by Williamson and Shmoys.

• 12/9-12/13
(12/10) Derandomization of MAXSAT randomized approximation algorithm, using the method of conditional expectations.12.10 Notes (unedited)
(12/12) Solved practice problems for finale exam.