CS 401 / MCS 401 - Computer Algorithms I
University of Illinois - Chicago
Fall 2023

This course will cover the important principles behind the design and analysis of computer algorithms. We will study techniques such as divide-and-conquer, dynamic programming, and greedy methods, as well as algorithms for sorting, searching, graph computations, and pattern matching. We will also discuss the theory of NP-completeness.

Basic Information

Syllabus: pdf
Time and Location: M-W-F 2:00–2:50pm, 180F Thomas Beckham Hall (TBH)
Instructor: Lev Reyzin, SEO 417
TA/Grader: Thomas Maranzatto
Textbook: J. Kleinberg and É. Tardos, Algorithm Design, 1st edition
Instructor's Office Hours: T 11:00-11:50am (online), F 11:00-11:50am (in-person)
TA/Grader Office Hours: T 9:00-11:00 (online)
Piazza site: please sign up via this link

Exam Dates

midterm exam: Wednesday, November 1st, 2:00-2:50pm
final exam: Wednesday, December 6th, 1:00-3:00pm

Problem Sets

problem set 1 due 9/13/23
problem set 2 due 9/29/23
problem set 3 due 10/13/23
problem set 4 due 10/25/23
problem set 5 due 11/17/23
problem set 6 due 12/1/23

Lectures and Readings

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

Lecture 1 (8/21/23)
covered material: intro to the course, overview of covered material, introduction to stable marriage problem
reading: preface

Lecture 2 (8/23/23)
covered material: the Gale-Shapley stable marriage algorithm
reading: chapter 1.1
optional reading: chapter 1.2

Lecture 3 (8/25/23)
covered material: measuring algorithm complexity, efficient algorithms, asmyptotic analysis
reading: chapter 2.1, 2.2

Lecture 4 (8/28/23)
covered material: implementing Gale-Shapley, common running times
reading: chapters 2.3, 2.4

Lecture 5 (9/30/23)
covered material: graph algorithms, graph connectivity, bredth-first search (BFS), depth-frst search (DFS)
reading: chapter 3

Lecture 6 (9/1/23)
covered material: priority queues, implementation with heaps
reading: chapter 2.5

Lecture 7 (9/6/23)
covered material: introduction to greedy algorithms, interval scheduling (guest lecture by Gyorgy Turan)
reading: chapter 4.1

Lecture 8 (9/8/23)
covered material: scheduling to minimize maximum lateness, an exchange argument (guest lecture by Gyorgy Turan)
reading: chapter 4.2

Lecture 9 (9/11/23)
covered material: shortest path trees and Dijkstra's algorithm, implementing with priority queues (online recording by Srini Devadas at MIT)
reading: chapter 4.4

Lecture 10 (9/13/23)
covered material: the MST problem, Prim's and Kruskal's and Reverse-Delete algorithms (guest lecture by Thomas Maranzatto)
reading: chapter 4.5

Lecture 11 (9/15/23)
covered material: review of greedy algorithms

Lecture 12 (9/18/23)
covered material: union-find for implementing Kruskal's
reading: chapter 4.6

Lecture 13 (9/20/23)
covered material: prefix-free codes, Huffman trees and codes
reading: chapter 4.8

Lecture 14 (9/22/23)
covered material: introduction to divide and conquer, mergesort, the master theorem
reading: chapter 5.1 and this statement of the master theorem
optional reading: chapter 5.2 and these notes on the master theorem

Lecture 15 (9/25/23)
covered material: review of problem set 1

Lecture 16 (9/27/23)
covered material: integer multiplication and counting inversions using divide and conquer
reading: chapters 5.3 and 5.5

Lecture 17 (9/29/23)
covered material: finding the closest pair of points in the plane
reading: chapter 5.4

Lecture 18 (10/2/23)
covered material: the fast Fourier transform
reading: chapter 5.6

Lecture 19 (10/4/23)
covered material: intro to dynamic programming via the Fibonacci sequence
reading: chapter 6.2

Lecture 20 (10/6/23)
covered material: dynamic program for weighted interval scheduling, segmented least squares
reading: chapters 6.1, 6.3

Lecture 21 (10/9/23)
covered material: review of problem set 2

Lecture 22 (10/11/22)
covered material: subset sum, knapsack, sequence alignment
reading: chapters 6.4, 6.6

Lecture 23 (10/13/23)
covered material: the Bellman-Ford dynamic programming algorithm for shortest paths in graphs with negative edges
reading: chapter 6.8

Lecture 24 (10/16/23)
covered material: RNA secondary structure
reading: chapter 6.5

Lecture 25 (10/18/23)
covered material: the max-flow problem
reading: chapter 7.1

Lecture 26 (10/20/23)
covered material: the Ford Fulkerson algorithm, min-cut problem
reading: chapter 7.2

Lecture 27 (10/23/23)
covered material: scaling max-flow, using max-flows to solve the perfect matching problem
reading: chapter 7.3

Lecture 28 (10/25/23)
covered material: review of problem sets 3 and 4

Lecture 29 (10/27/23)
covered material: Hall's theorem
reading: chapter 7.5

Lecture 30 (10/30/23)
covered material: review for midterm exam

Lecture 31 (11/1/23)
midterm exam

Lecture 32 (11/3/23)
covered material: make-up to go over midterm

Lecture 33 (11/6/23)
covered material: edge-disjoint paths, circulations with demands (and lower bounds)
reading: chapters 7.6, 7.7

Lecture 34 (11/8/23)
covered material: flows for survey design, airline scheduling, and image segmentation
reading: chapters 7.8, 7.9

Lecture 35 (11/10/23)
covered material: introduction to computational complexity, reductions
reading: chapter 8.1

Lecture 36 (11/13/23)
covered material: gadget reductions, 3SAT
reading: chapters 8.2

Lecture 37 (11/15/23)
covered material verifier definition of NP
reading: chapter 8.3

Lecture 38 (11/17/23)
covered material: NP-Completeness
reading: chapter 8.4

Lecture 39 (11/20/23)
covered material: assymetry of NP
reading: chapter 8.9

Lecture 40 (11/22/23)
covered material: gadget reduction to HAMPATH, TSP
reading: chapter 8.5

Lecture 41 (11/27/23)
covered material: partitioning and coloring hardness
reading: chapters 8.6 and 8.7

Lecture 42 (11/29/23)
covered material: subset sum and other NP-Complete problems
reading: chapter 8.8 and 8.10

Lecture 43 (12/1/23)
covered material: final exam review