CS 401 / MCS 401 - Computer Algorithms I
University of Illinois - Chicago
Spring 2022

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 11:00–11:50AM, 180G Thomas Beckham Hall (TBH), online first two weeks
Instructor: Lev Reyzin, SEO 417
TA/Grader: Thomas Maranzatto, Jinhua Xu
Textbook: J. Kleinberg and É. Tardos, Algorithm Design, 1st edition
Instructor's Office Hours: M 10:00–10:50AM in SE0 417, R 10:00–10:50AM online
TA/Grader Office Hours: R 10:00–11:50AM in MSLC (Maranzatto).
Piazza site: link for self sign-up (from where a Zoom link is available)

Exam Dates

Midterm Exam 1: Wednesday, March 9th, 11:00-11:50AM in TBH 180G
Midterm Exam 2: Wednesday, April 13th, 11:00-11:50AM in TBH 180G
Final Exam: Thursday May 5th, 10:30AM-12:30PM in TBH 180G

Problem Sets

problem set 1 due 1/28/22
problem set 2 due 2/18/22
problem set 3 due 3/4/22
problem set 4 due 3/30/22
problem set 5 due 4/11/22
problem set 6 due 4/29/22

Lectures and Readings

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

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

Lecture 2 (1/12/22)
covered material: the Gale-Shapley stable marriage algorithm
reading: begin chapter 1.1
optional reading: chapter 1.2

Lecture 3 (1/14/22)
covered material: proof of the Gale-Shapley algorithm
reading: finish chapter 1.1

Lecture 4 (1/19/22)
covered material: measuring algorithm complexity, efficient algorithms
reading: chapter 2.1

Lecture 5 (1/21/22)
covered material: asymptotic analysis, common running times
reading: chapters 2.2, 2.4

Lecture 6 (1/24/22)
covered material: implementing and analyzing Gale-Shapley
reading: chapter 2.3

Lecture 7 (1/26/22)
covered material: priority queues, implementation with heaps
reading: chapter 2.5

Lecture 8 (1/28/22)
covered material: graph algorithms, graph connectivity, bredth-first search (BFS), depth-frst search (DFS)
reading: chapter 3

Lecture 9 (1/31/22)
covered material: introduction to greedy algorithms, interval scheduling
reading: chapter 4.1

Lecture 10 (2/2/22)
covered material: scheduling to minimize lateness, an exchange argument
reading: chapter 4.2

Lecture 11 (2/4/22)
covered material: shortest path trees and Dijkstra's algorithm, implementing with priority queues
reading: chapter 4.4

Lecture 12 (2/7/22)
covered material: the MST problem, Prim's and Kruskal's and Reverse-Delete algorithms
reading: begin chapter 4.5

Lecture 13 (2/9/22)
covered material: cut and cycle properties of MSTs, prefix-free codes
reading: finish chapter 4.5

Lecture 14 (2/11/22)
covered material: implementing Kruskal's with Union-Find
reading: chapter 4.6

Lecture 15 (2/14/22)
covered material: prefix-free codes, Huffman trees and codes
reading: chapter 4.8

Lecture 16 (2/16/22)
covered material: proof that Huffman codes are optimal, introduction to divide and conquer via Mergesort
reading: chapter 5.1

Lecture 17 (2/18/22))
covered material: master theorem, multiplying integers in subquadratic time, binary search
reading: chapters 5.2 and 5.5 and this statement of the master theorem
optional reading: these notes on the master theorem

Lecture 18 (2/21/22)
covered material: counting inversions using divide and conquer
reading: chapter 5.3

Lecture 19 (2/23/22)
covered material: finding the closest pair of points in the plane
reading: chapter 5.4

Lecture 20 (2/25/22)
covered material: the Fast Fourier Transform
reading: chapter 5.6

Lecture 21 (2/28/22)
covered material: intro to dynamic programming via the Fibonacci sequence
reading: chapter 6.2

Lecture 22 (3/2/22)
covered material: weighted interval partitioning
reading: chapter 6.1

Lecture 23 (3/4/22)
covered material: segmented least squares
reading: chapter 6.3

Lecture 24 (3/7/22)
covered material: review for midterm 1

Lecture 25 (3/9/22)
midterm 1: no lecture

Lecture 26 (3/11/22)
covered material: sequence alignment
reading: chapter 6.6

Lecture 27 (3/14/22)
covered material: the dynamic program for subset sum
reading: chapter 6.4

Lecture 28 (3/16/22)
covered material: the Bellman-Ford dynamic programming algorithm for shortest paths in graphs with negative edges
reading: chapter 6.8

Lecture 29 (3/18/22)
covered material: the max-flow problem
reading: intro to chapter 7

Lecture 30 (3/28/22)
covered material: the Ford Fulkerson algorithm
reading: chapter 7.1

Lecture 31 (3/30/22)
covered material: the min-cut problem, proof of Ford Fulkerson via min-cut duality
reading: chapter 7.2

Lecture 32 (4/1/22)
covered material: scaling max-flow, using max-flows to solve the perfect matching problem
reading: chapters 7.3, 7.5

Lecture 33 (4/4/22)
covered material: circulations with demands (and lower bounds)
reading: chapters 7.7

Lecture 34 (4/6/22)
covered material: flows for survey design, airline scheduling, and image segmentation
reading: chapters 7.8, 7.9
optional reading chapter 7.10

Lecture 35 (4/8/22)
covered material: edge-disjoint paths, flows for other matchings
reading: chapter 7.6

Lecture 36 (4/11/22)
covered material: midterm 2 review

Lecture 37 (4/13/22)
midterm 2: no lecture

Lecture 38 (4/15/22)
covered material: introduction to computational complexity
reading: intro to chapter 8

Lecture 39 (4/18/22)
covered material: polynomial-time reductions
reading: chapter 8.1

Lecture 40 (4/20/22)
covered material verifier definition of NP
reading: chapter 8.3

Lecture 41 (4/22/22)
covered material: gadget reductions, reduction to INDEPENDENT-SET, NP-Completeness
reading: chapter 8.2, chapter 8.4

Lecture 42 (4/25/22)
covered material: sequencing problems, gadget reduction to HAMPATH
reading: chapter 8.5

Lecture 43 (4/27/22)
covered material: more NPC problems
reading: chapter 8.10

Lecture 44 (4/29/22)
covered material: final exam review