CS 401 / MCS 401 - Computer Algorithms I
University of Illinois - Chicago
Fall 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 9:00-9:50pm, 208 Burnham Hall (BH)
Instructor Contact Information: Lev Reyzin, SEO 418, (312)-413-3745
TA/Grader Contact Information: Yi Huang and Shelby Heinecke
Textbook: J. Kleinberg and É. Tardos, Algorithm Design, 1st edition
Instructor's Office Hours: T, F 10:00am-10:50am
TA's Office Hours: T 12:00pm-1:00pm, 3:00pm-4:00pm (Yi Huang) and T, R 3:00pm-4:00pm (Shelby Heinecke) in MSLC (SEO 4th floor)

Exam Dates

Midterm 1: Friday October 14, 9:00 a.m. - 9:50 a.m. (in class)
Midterm 2: Friday November 18, 9:00 a.m. - 9:50 a.m. (in class)
Final Exam: Tuesday December 6, 10:30 a.m. - 12:30 p.m.

Problem Sets

problem set 1 (pdf), due 9/12/16
problem set 2 (pdf), due 10/5/16
problem set 3 (pdf), due 10/12/16
problem set 4 (pdf), due 11/2/16
problem set 5 (pdf), due 11/14/16
problem set 6 (pdf), due 12/2/16

Lectures and Readings

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

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

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

Lecture 3 (8/26/16)
covered material: finishing Gale-Shapley discussion, measuring algorithm complexity
reading: chapter 2.1

Lecture 4 (8/29/16)
covered material: efficient algorithms, asymptotic notation, properties o f big-O, big-Omega, and big-Theta
reading: chapter 2.2

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

Lecture 6 (9/2/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 7 (9/7/16)
covered material: implementing BFS and DFS with queues and stacks, intro to priority queues
reading: chapter 3.3, begin chapter 2.5

Lecture 8 (9/9/16)
covered material: priority queues and binary heaps, connectivity and bipartiteness testing
reading: finish chapter 2.5, chapter 3.4

Lecture 9 (9/12/16)
covered material digraphs, intro to greedy algorithms, interval scheduling and "keeping up with OPT''
reading chapters 3.5 and 3.6, chapter 4.1

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

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

Lecture 12 (9/19/16)
covered material: the minimum spanning tree problem, Prim's and Kruskal's algorithms (guest lecture by Yi Huang)
reading: begin chapter 4.5

Lecture 13 (9/21/16)
covered material: the cycle property and clusterings of maximum spacing (guest lecture by Brian Ziebart)
reading: finish chapter 4.5, chapter 4.7

Lecture 14 (9/23/16)
covered material: Huffman codes (guest lecture by Yi Huang)
reading: chapter 4.8

Lecture 15 (9/26/16)
covered material: Union-Find, introduction to divide and conquer via Mergesort, the Master theorem
reading: chapters 4.6, 5.1, 5.2 and these notes on the Master theorem
other: problem set 2 assigned

Lecture 16 (9/28/16)
covered material: counting inversions, finding the closest pair of points in the plane
reading: chapters 5.3 and 5.4

Lecture 17 (9/30/16)
covered material: multiplying integers in subquadratic time, Strassen's algorithm for multiplying matrices
reading: chapter 5.5, notes on Strassen's algorithm

Lecture 18 (10/3/16)
covered material: connections between vector convolution and polynomial multiplication, the complex roots of unity
reading: begin chapter 5.6

Lecture 19 (10/5/16)
covered material: recursive polynomial evaluation and the Fast (Discrete) Fourier Transform (FFT)
reading: continue chapter 5.6
other: problem set 3 assigned

Lecture 20 (10/7/16)
covered material: polynomial interpolation for the FFT
reading: finish chapter 5.6

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

Lecture 22 (10/12/16)
covered material: review for midterm 1
other: the midterm will be in-class on Friday

Lecture 23 (10/14/16)
midterm exam 1: no lecture

Lecture 24 (10/17/16)
covered material: principles of dynamic programming, introduction to least squares
reading: chapters 6.2, begin chapter 6.3

Lecture 25 (10/19/16)
covered material: segmented least squares, dynamic programming with two-dimensional tables, the sequence alignment problem
reading: finish chapter 6.3, chapter 6.6

Lecture 26 (10/21/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 (10/24/16)
covered material: dynamic programing for the subset sum and knapsack problems
reading: chapter 6.4

Lecture 28 (10/26/16)
covered material: the max-flow problem, the Ford Fulkerson algorithm
reading: chapter 7.1

Lecture 29 (10/28/16)
covered material: the min-cut problem, proof of Ford Fulkerson via min-cut duality, choosing good augmenting paths
reading: chapter 7.2, begin chapter 7.3

Lecture 30 (10/31/16)
covered material: scaling max-flow, strongly polynomial time algorithms, applying max-flow to bipartite matchings and Hall's theorem
reading: finish chapter 7.3, chapter 7.5

Lecture 31 (11/2/16)
covered material: disjoint paths via flows, circulation problems with demands
reading: chapter 7.6, chapter 7.7

Lecture 32 (11/4/16)
covered material: using circulations to solve survey design and airline scheduling problems
reading: chapter 7.8, chapter 7.9
other: problem set 5 assigned

Lecture 33 (11/7/16)
covered material: introduction to computational complexity and polynomial-time reductions, vertex cover and independent set
reading: chapter 8.1

Lecture 34 (11/9/16)
covered material: gadget reductions from 3SAT
reading: chapter 8.2

Lecture 35 (11/11/16)
covered material: the verifier definition of NP (guest lecture by Brian Ziebart)
reading: chapter 8.3

Lecture 36 (11/14/16)
covered material: SAT, CIRCUIT-SAT, and NP completeness
reading: chapter 8.4

Lecture 37 (11/16/16)
covered material: review for midterm 2
other: the midterm will be in-class on Friday

Lecture 38 (11/18/16)
midterm exam 1: no lecture

Lecture 39 (11/21/16)
covered material: sequencing problems: Hamiltonian path (HAMPATH) and traveling salesperson (TSP)
reading: chapter 8.5

Lecture 40 (11/23/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 (11/28/16)
covered material: space complexity, PSPACE, small vertex covers, NP-hard problems on trees
reading: chapters 9.1, 10.1, and 10.2

Lecture 42 (11/30/16)
covered material: approximation algorithms for vertex cover and set cover
reading: chapters 11.3 and 11.4

Lecture 43 (12/2/16)
covered material: review for final
other: the final exam will be on Tuesday, December 6