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

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:50pm, Behavioral Sciences Building (BSB) 319
Instructor Contact Information: Lev Reyzin, SEO 418, (312)-413-3745,
TA/Grader Contact Information: Yi Huang, SEO 400, (312)-996-2305,
Textbook: J. Kleinberg and É. Tardos, Algorithm Design, 1st edition
Instructor's Office Hours: T 10:00AM-11:00AM, F 2:00PM-3:00PM
TA's Office Hours: F 1:00 - 4:00PM in MSLC (SEO 430)

Exam Dates

Midterm 1: 11:00-11:50 a.m. Friday, March 4 (in class)
Midterm 2: 11:00-11:15 a.m. Friday, April 8 (in class)
Final Exam: 10:30-12:30 p.m. Thursday, May 5

Problem Sets

problem set 1 (pdf), due 2/1/16
problem set 2 (pdf), due 2/15/16
problem set 3 (pdf), due 2/29/16
problem set 4 (pdf), due 3/18/16
problem set 5 (pdf), due 4/4/16
problem set 6 (pdf), due 4/27/16

Lectures and Readings

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

Lecture 1 (1/11/16)
covered material: intro to the course, overview of covered material
reading: begin chapter 1

Lecture 2 (1/13/16)
covered material: the Gale-Shapley stable marriage algorithm
reading: finish chapter 1.1

Lecture 3 (1/15/16)
covered material: efficient algorithms, asymptotic notation, properties of big-O, big-Omega, and big-Theta
reading: chapters 2.1 and 2.2

Lecture 4 (1/20/16)
covered material: implementing and analyzing the Gale-Shapley algorithm, common running times of algorithms
reading: chapters 2.3 and 2.4

Lecture 5 (1/22/16)
covered material: intro to graphs and graph algorithms, graph representations, BFS and DFS
reading: chapters 3.1 and 3.2
other: problem set 1 assigned

Lecture 6 (1/25/16)
covered material: implementing breadth and depth first search with queues and stacks
reading: chapter 3.3

Lecture 7 (1/27/16)
covered material: testing bipartness, connectivity in digraphs, DAGS and topological orderings, priority queues and binary heaps
reading: chapters 2.5 and 3.4 to 3.6

Lecture 8 (1/29/16)
covered material: interval scheduling, coin changing, and interval partitioning
reading: chapter 4.1
other: this was a guest lecture by Prof. Brian Ziebart, see slides

Lecture 9 (2/1/16)
covered material: scheduling to minimize lateness, exchange arguments
reading: chapter 4.2

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

Lecture 11 (2/5/16)
covered material: minimum spanning trees, Prim's and Kruskal's algorithms
reading: chapter 4.5
other: this was a guest lecture by Prof. Brian Ziebart, see slides

Lecture 12 (2/8/16)
covered material: priority queues and union-find for MST, clusterings of maximum spacing
reading: chapters 4.6 and 4.7

Lecture 13 (2/10/16)
covered material: introduction to divide and conquer and recurrence relations, mergesort
reading: chapter 5.1

Lecture 14 (2/12/16)
covered material: more on recurrence relations, counting the number of inversions
reading: chapters 5.2 and 5.3

Lecture 15 (2/15/16)
covered material: finding the closest pair of points in the plane
reading: chapter 5.4

Lecture 16 (2/17/16)
covered material: a subquadratic algorithm for integer multiplication, computing the convolution of two vectors
reading: chapter 5.5 and begin chapter 5.6

Lecture 17 (2/19/16)
covered material: connections between vector convolution and polynomial multiplication, the complex roots of unity
reading: continue chapter 5.6
other: problem set 3 assigned

Lecture 18 (2/22/16)
covered material: recursive polynomial evaluation, polynomial interpolation, and the Fast (Discrete) Fourier Transform
reading: finish chapter 5.6

Lecture 19 (2/24/16)
covered material: the Master theorem, Strassen's matrix multiplication algorithm
reading: notes on the Master theorem and notes on Strassen's algorithm

Lecture 20 (2/26/16)
covered material: intro to dynamic programming, memoization, and bottom-up recursion, weighted interval partitioning
reading: chapter 6.1

Lecture 21 (2/29/16)
covered material: efficiently getting solution structures from dynamic programming, general dynamic programming principles
reading: chapter 6.2

Lecture 22 (3/2/16)
covered material: midterm review
other: a reminder that midterm 1 is on Friday

Lecture 23 (3/4/16)
midterm exam 1: no lecture

Lecture 24 (3/7/16)
covered material: regression, least squares, and a dynamic programing solution to segmented least squares
reading: chapter 6.3

Lecture 25 (3/9/16)
covered material: dynamic programming with two-dimensional tables, the sequence alignment problem
reading: chapter 6.6

Lecture 26 (3/11/16)
covered material: the Bellman-Ford dynamic programming algorithm for shortest paths in graphs with negative edges
reading: chapter 6.8
other: problem set 4 assigned

Lecture 27 (3/14/16)
covered material: introduction to the maximum flow problem, relationship to minimum cuts
reading: chapter 7.1

Lecture 28 (3/16/16)
covered material: the Ford-Fulkerson algorithm for max-flow/min-cut, its running time and proof of correctness
reading: chapter 7.2

Lecture 29 (3/18/16)
covered material: discussion of strongly polynomial time algorithms and of inefficiency in naive implementation of Ford-Fulkerson
reading: begin chapter 7.3

Lecture 30 (3/28/16)
covered material: choosing good augmenting paths, the scaling max-flow algorithm, applying max-flow to bipartite matchings
reading: finish chapter 7.3, begin chapter 7.5
other: problem set 5 assigned

Lecture 31 (3/30/16)
covered material: algorithmic proof of Hall's Theorem via min-cut, circulations with demands
reading: finish chapter 7.5, chapter 7.7

Lecture 32 (4/1/16)
covered material: lower bounds on flows, using circulations to solve survey design and airline scheduling problems
reading: chapter 7.8, chapter 7.9

Lecture 33 (4/4/16)
covered material: brief discussion of edge-disjoint paths, introduction to computational complexity and polynomial-time reductions
reading: chapter 7.6, begin chapter 8.1

Lecture 34 (4/6/16)
covered material: midterm review
other: a reminder that midterm 2 is on Friday

Lecture 35 (4/8/16)
midterm exam 2: no lecture

Lecture 36 (4/11/16)
covered material: vertex cover and set cover
reading: finish chapter 8.1

Lecture 37 (4/13/16)
covered material: gadget reductions and the verifier definition of NP
reading: chapter 8.2, chapter 8.3

Lecture 38 (4/14/16)
covered material: NP-Completeness and its consequences
reading: chapter 8.3

Lecture 39 (4/18/16)
covered material: NP-Completness of CIRCUIT-SAT, reduction from 3SAT to Hamiltomian path
reading: chapter 8.4 and 8.5

Lecture 40 (4/20/16)
covered material: additional NP-Complete problems, co-NP and the asymmetry of NP
reading: chapter 8.9, skim chapters 8.6 - 8.8 and skim chapter 8.10
other: problem set 6 assigned

Lecture 41 (4/22/16)
covered material: space-constrained algorithms and PSPACE, SAT in linear space, extending the limits of tractability
reading: chapter 9.1, chapter 10 introduction

Lecture 42 (4/25/16)
covered material: finding small vertex covers, solving NP-Hard problems on trees
reading: chapter 10.1 and chapter 10.2

Lecture 43 (4/27/16)
covered material: approximation algorithms via greedy and charging schemes, with applications to vertex cover and set cover
reading: chapter 11.3, chapter 11.4

Lecture 44 (4/29/16)
covered material: final exam review
other: a reminder that the final is on Thursday