CS 501 / MCS 501 - Computer Algorithms II
University of Illinois - Chicago
Spring 2024

This course will introduce students to the fundamental ideas underlying modern algorithmic techniques. Students will be taught how to design and analyze approximation algorithms and randomized algorithms, as well as other advanced topics. Knowledge of topics covered in Computer Algorithms I (CS 401 / MCS 401 or equivalent) is required.

This course is represented in the CS Ph.D. prelim exam in the MSCS department.

Basic Information

Syllabus: pdf
Time and Location: M-W-F 9:00–9:50 a.m., Addams Hall 307
Instructor Contact Information: Lev Reyzin, SEO 417
Required Textbook: D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms (available free online)
Instructor's Office Hours: M 10:00-10:50am, W 11:00-11:50am
Piazza site: please sign up via this link

Exam Dates

Midterm exam: Wednesday, March 13th, 2024, 9:30am-9:50am, in class
Final exam: Tuesday, April 30th, 2024, 10:30am-12:30pm, in class

Problem Sets

problem set 1, due 2/7/24
problem set 2, due 2/16/24
problem set 3, due 3/6/24
problem set 4, due 4/5/24
problem set 5, due 4/26/24

Lectures and Readings

Note: lectures will have material not covered in the readings.

Lecture 1 (1/8/24)
covered material: intro to the course, discussion of modern algorithms vs traditional approaches

Lecture 2 (1/10/24)
covered material: review of Ford-Fulkerson algorithm, reduction from min-cut to min-s-t-cut
reading: review these notes on flows by Kevin Wayne (Princeton)

Lecture 3 (1/12/24)
covered material: Karger's randomized algorithm for min-cut
reading: these notes by Eric Vigoda (Georgia Tech)

Lecture 4 (1/17/24)
covered material: the Karger-Stein improvement to randomized min-cut
reading: these notes by Sasho Nikolov (Toronto)
for review: these notes on the master theorem

Lecture 5 (1/19/24)
covered material: introduction to approximation algorithms
reading: 1.1 of Williamson and Shmoys

Lecture 6 (1/22/24)
covered material: metric k-center approximation, related problems
reading: 2.2 of Williamson and Shmoys
optional reading: these notes by Patrick Jaillet (MIT)

Lecture 7 (1/24/24)
covered material: greedy algorithms for SC and VC
reading: 1.6 of Williamson and Shmoys and these notes by Dieter van Melkebeek (Wisconsin)

Lecture 8 (1/26/24)
covered material: linear programming (LP) relaxations for SC and VC
reading: 1.2 of Williamson and Shmoys

Lecture 9 (1/29/24)
covered material: deterministic and randomized rounding of LP relaxation for VC and SC
reading: 1.3 and 1.7 of Williamson and Shmoys

Lecture 10 (1/31/24)
covered material: hardness by reducing from NP-Complete (NPC) problems
reading: 16.1 of Williamson and Shmoys
optional reading: appendix B of Williamson and Shmoys for background on NPC

Lecture 11 (2/2/24)
covered material: minimum spanning trees (MST), nearest addition for metric traveling salesman problem (TSP)
reading: these notes by Santosh Vempala (Georgia Tech) for review of MSTs

Lecture 12 (2/5/24)
covered material: Christofides algorithm
reading: 2.4 of Williamson and Shmoys

Lecture 13 (2/7/24)
covered material: review of dynamic programming, subset sum
reading: these notes by Deeparnab Chakrabarty (Dartmouth)

Lecture 14 (2/9/24)
covered material: dynamic programming for knapsack, towards an FPTAS
reading: 3.1 of Williamson and Shmoys

Lecture 15 (2/12/24)
covered material: FPTAS for knapsack
reading: these notes from Goemans's class (MIT)

Lecture 16 (2/14/24)
covered material: prize-collecting Steiner tree (PCST), problem of connectivity with exponential-size IPs/LPs
reading: 4.4 of Williamson and Shmoys

Lecture 17 (2/16/24)
covered material: separation oracle and rounding scheme for PCST 3-approximation
reading: 4.3 of Williamson and Shmoys

Lecture 18 (2/18/24)
covered material: ellipsiod method (optional)
optional reading: these notes by Michel Goemans (MIT)

Lecture 19 (2/21/24)
covered material: randomized approximations for MAX-CUT and MAX-3SAT, derandomization using conditional expectations
reading: 5.1 and 5.2 of Williamson and Shmoys

Lecture 20 (2/23/24)
covered material: biased rounding for improved MAX-SAT approximation
reading: 5.3 of Williamson and Shmoys

Lecture 21 (2/26/24)
covered material: introduction to linear programming
reading: begin appendix A of Williamson and Shmoys

Lecture 22 (2/28/24)
covered material: linear programming duality
reading: finish appendix A of Williamson and Shmoys

Lecture 23 (3/1/24)
covered material: linear rounding scheme for MAX-SAT and choosing the better of two solutions
reading: 5.4 and 5.5 of Williamson and Shmoys

Lecture 24 (3/4/24)
covered material: non-linear rounding schemes, integrality gaps, application to MAX-SAT
reading: 5.6 of Williamson and Shmoys
optional reading: 5.7 of Williamson and Shmoys for non-linear rounding improvement for PCST

Lecture 25 (3/6/24)
covered material: intro to semidefinite programming (SDP), positive semidefiniteness (psd), vector programming (VP) SDP form
reading: 6.1 of Williamson and Shmoys

Lecture 26 (3/8/24)
covered material: SDP for MAX-CUT, random hyperplane method for rounding SDPs, Goemans-Williamson MAX-CUT approximation
reading: 6.2 of Williamson and Shmoys

Lecture 27 (3/11/24)
covered material: unit vectors in IPs for clustering, SDP relaxation
reading: begin 6.4 of Williamson and Shmoys

Lecture 28 (3/13/24)
covered material: midterm exam, no lecture

Lecture 29 (3/15/24)
covered material: SDP rounding and approximation for correlation clustering
reading: finish 6.4 of Williamson and Shmoys

Lecture 30 (3/25/24)
covered material: Wigderson's algorithm for approximately coloring 3-colorable graphs, SDP formulation for improvement
reading: sections 2 and 3 of these notes by Thore Husfeldt (ITU Copenhagen)

Lecture 31 (3/27/24)
covered material: semicolorings, SDPs for improved coloring approximation for 3-colorable graphs
reading: 6.5 of Williamson and Shmoys

Lecture 32 (3/29/24)
covered material: LP duality, LP dual for SC
reading: 7.1 of Williamson and Shmoys

Lecture 33 (4/1/24)
covered material: rounding a dual solution for SC, complementary slackness
reading: 1.4 of Williamson and Shmoys

Lecture 34 (4/3/24)
covered material: introduction to primal-dual methods, a primal-dual algorithm for SC
reading: 1.5 of Williamson and Shmoys

Lecture 35 (4/5/24)
covered material: the feedback vertex set problem (FVS), primal relaxation and dual LP, developing primal-dual algorithm for FVS
reading: 7.2 of Williamson and Shmoys

Lecture 36 (4/8/24)
covered material: on the P vs NP problem, a talk by Avi Wigderson (asynchronous)
optional reading: section 2 of this paper by Avi Wigderson (IAS)

Lecture 37 (4/10/24)
covered material: a primal-dual method for optimally solving SP that yields Dijkstra's algorithm
reading: 7.3 of Williamson and Shmoys

Lecture 38 (4/12/24)
covered material: review of mapping versus Turing reductions, introduction to approximation-preserving reductions
reading: 16.1 of Williamson and Shoys

Lecture 39 (4/15/24)
covered material: L-reductions, approximation preserving reduction from MAX-E3SAT to MAX-2SAT
reading: 16.2 of Williamson and Shmoys

Lecture 40 (4/17/24)
covered material: review of verifier definition of NP, Probabilistically Checkable Proofs (PCPs), the PCP theorem
reading: these notes by Christian Scheideler (Paderborn)
optional reading: this article for the general public by Alex Bellos

Lecture 41 (4/19/24)
covered material: 3-bit PCPs, hardness for the even/odd constraint satisfaction problem (CSP), optimal hardness for MAX-E3SAT
reading: 16.3 of Williamson and Shmoys

Lecture 42 (4/22/24)
covered material: unique games problem, unique games conjecture (UGC), MAX-2LIN
reading: 16.5 of Williamson and Shmoys

Lecture 43 (4/24/24)
covered material: label cover hardness of approximation, unique games SDP, relationship to other problems
reading: 13.3 of Williamson and Shmoys
optional reading: 16.4 of Williamson and Shmoys

Lecture 44 (4/26/24)
covered material: final exam review