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

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:50 p.m., 180F Thomas Beckham Hall (TBH)
Instructor Contact Information: Lev Reyzin, SEO 418, (312)-413-3745
TA/Grader Contact Information: Stoyan Dimitrov and Mano Vikash Janardhanan
Textbook: J. Kleinberg and É. Tardos, Algorithm Design, 1st edition
Instructor's Office Hours: M 10:00-10:50am, W 11:00-11:50am
TA Office Hours: Stoyan: T 9:00am-11:00am (MSLC in SES); Mano: T 11:00am-1:00pm (MSLC in SES), T 1:00pm-2:00pm (SEO 518)

Exam Dates

Midterm Exam 1: Wednesday, October 10, 2:00-2:50 PM in TBH 180F
Midterm Exam 2: Monday, November 12, 2:00-2:50 PM in TBH 180F
Final Exam: Wednesday, December 12, 1:00-3:00 PM in TBH 180F

Problem Sets

problem set 1 due 9/17/18
problem set 2 due 9/28/18
problem set 3 due 10/8/18
problem set 4 due 10/29/18
problem set 5 due 11/9/18
problem set 6 due 12/7/18

Lectures and Readings

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

Lecture 1 (8/27/18)
covered material: intro to the course, overview of covered material, introduction to stable marriage problem
reading: begin chapter 1

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

Lecture 3 (8/31/18)
covered material: measuring algorithm complexity, asymptotic notation
reading: chapter 2.1 and 2.2

Lecture 4 (9/5/18)
covered material: implementing and analyzing the Gale-Shapley algorithm, common running times of algorithms, intro to graphs
reading: chapters 2.3, 2.4, and 3.1
other: problem set 1 assigned

Lecture 5 (9/7/18)
covered material: graph algorithms, graph connectivity and trees, BFS, DFS, priority queues and heaps
reading: chapter 3.2, 3.3, and 2.5

Lecture 6 (9/10/18)
covered material: introduction to greedy algorithms, interval scheduling (guest lecture by Anastasios Sidiropoulos)
reading: chapter 4.1

Lecture 7 (9/12/18)
covered material: scheduling to minimize lateness, exchange arguments
reading: chapter 4.2

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

Lecture 9 (9/17/18)
covered material: the MST problem, Prim's and Kruskal's algorithms, cut and cycle properties, Union-Find
reading: chapters 4.5 and 5.6
other: problem set 2 assigned

Lecture 10 (9/19/18)
covered material: Huffman codes (guest lecture by Brian Ziebart)
reading: chapt 4.8

Lecture 11 (9/21/18)
covered material: introduction to divide and conquer via Mergesort, recurrences and the Master theorem
reading: chapters 5.1 and 5.2 and the statement of the Master theorem
optional reading: notes on the Master theorem

Lecture 12 (9/24/18)
covered material: counting inversions, multiplying integers in subquadratic time
reading: chapters 5.3 and 5.5

Lecture 13 (9/26/18)
covered material: Strassen's algorithm for matrix multiplication, finding the closest pair of points in the plane
reading: notes on Strassen's algorithm, chapter 5.4

Lecture 14 (9/28/18)
covered material: the Fast Discrete Fourier Transform
reading: chapter 5.6
other: problem set 3 assigned

Lecture 15 (10/1/18)
covered material: intro to dynamic programming via the Fibonacci sequence
reading: chapter 6.2

Lecture 16 (10/3/18)
covered material: weighted interval partitioning, introduction to least squares regression
reading: chapter 6.1, begin chapter 6.3

Lecture 17 (10/5/18)
covered material: homework and midterm review
reading: chapter 3.4 - 3.6 (which you need to know but was not assigned earlier)

Lecture 18 (10/8/18)
covered material: more midterm review
other: midterm exam Wednesday

Lecture 19 (10/10/18)
midterm exam: no lecture

Lecture 20 (10/12/18)
covered material: went over midterm 1, segmented least squares
reading: chapter 6.3

Lecture 21 (10/15/18)
covered material: sequence alignment and multidimensional tables
reading: chpater 6.6

Lecture 22 (10/17/18)
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 23 (10/19/18)
covered material: the dynamic program for subset sum
reading: chapter 6.4

Lecture 24 (10/22/18)
covered material: dynamic program for finding RNA secondary structure
reading: chapter 6.5

Lecture 25 (10/24/18)
covered material: the max-flow problem, the Ford Fulkerson algorithm
reading: chapter 7.1

Lecture 26 (10/26/18)
covered material: the min-cut problem, proof of Ford Fulkerson via min-cut duality, scaling max-flow
reading: chapter 7.2
optional reading: chapter 7.3

Lecture 27 (10/29/18)
covered material: using max-flows to solve the perfect matching problem
reading: chapter 7.5

Lecture 28 (10/31/18)
covered material: using flows to prove Hall's theorem, disjoint paths in directed graphs
reading: chapter 7.6

Lecture 29 (11/2/18)
covered material: circulations with demands (and lower bounds), using circulations to solve survey design
reading: chapters 7.7 and 7.8

Lecture 30 (11/5/18)
covered material: flows for image segmentation
reading: chapter 7.10

Lecture 31 (11/7/18)
covered material: airline scheduling
reading: chapter 7.9

Lecture 32 (11/9/18)
covered material: midterm 2 review
other: miterm 2 on Monday!

Lecture 33 (11/12/18)
midterm exam: no lecture

Lecture 34 (11/14/18)
covered material: introduction to computational complexity, review of reductions
reading: chapter 8.1

Lecture 35 (11/16/18)
covered material example reductions and verifier definition of NP
reading: chapter 8.3

Lecture 36 (11/19/18)
covered material: NP-Completeness, CIRCUIT-SAT and 3-SAT are NP-Complete
reading: chapter 8.4

Lecture 37 (11/21/18)
covered material: went over midterm 2

Lecture 38 (11/26/18)
covered material: SAT, 3-SAT, and gadget reduction from 3-SAT to independent set
reading: chapter 8.2
other: problem set 6 assigned

Lecture 39 (11/28/18)
covered material: sequencing problems, gadget reduction to Hamiltonian path, additional NPC problems
reading: chapter 8.5, remainder of chapter 8 for NPC problems

Lecture 40 (11/30/18)
covered material: assymetry of NP, coNP, PSPACE
reading: chapters 8.9 and 9.1

Lecture 41 (12/3/18)
covered material: approximating vertex cover and set cover via greedy algorithms
reading:chapter 11.3 and 11.4

Lecture 42 (12/5/18)
covered material: advanced algorithms: linear-time median finding, Karger's algorithm for min-cut
reading: chapter 13.2 and 13.5

Lecture 43 (12/7/18)
covered material: exam review
other: the final exam will be on Wednesday, December 12