CS 473 (Fall 2026)
Algorithms
Instructor
Timothy Chan (tmc "at" illinois.edu)
TAs
Harshul Sagar (harshul4), Yuancheng Yu (yyu51)
CAs
Ian Chen (ianchen3), Ajitesh Dasaratha (asd11), Zhiyuan Ma (zm25), Navid Tajkhorshid (navidt)
Lecture Time/Place
Tue & Thu 2:00pm-3:15pm, Loomis Lab 151
Office Hours
- Mon 4:00-5:00 Yuancheng
- Tue 3:30-4:30 Timothy
- Wed 1:00-2:00 Harshul
(starting Aug 30 onward). All office hours are held in the open study space in the basement of Siebel (unless stated otherwise). Check Ed for the latest updates to the office hours.
Administrivia
Homework
Exams
- Midterm 1 (Sep 30 Wed 7:00pm-9:30pm, in Siebel 1404)
[exam and solutions]
- Instructions: Except for the cheat sheets (see below), exams are closed-everything. In particular: No medically unnecessarily electronic devices are allowed in exams, including smart watches and headphones/earbuds.
- Cheat sheets: You may bring one double-sided 8.5" x 11"; sheet of paper with anything you like written on both sides, with your name and NetID written on the upper right corner. (Two single-sided sheets are okay.) You must write your own cheat sheets by hand on paper, unless you have a documented writing disability. No printing or photocopying. We may not return or scan the cheat sheets, so if you want to keep a copy, you should photocopy or scan your cheat sheet before the exam.
- All exams are strictly confidential for at least 24 hours, or until all conflict exams have been taken. Do not discuss your exam with anyone, in person or online.
- Coverage: The exam will cover everything up to and including Sep 17's lecture (in particular, material corresponding to HW0-HW3, including prerequisite material, divide-and-conquer, and dynamic programming... but no randomized algorithms).
- Some practice exam questions (we don't provide official solutions, but we may go over some of them in the review session)
- a past midterm
with solutions
- another past midterm
with solutions
- Conflict exams: Conflict exams (on Oct 1 Thu) will be offered only to students with a valid reason. To get permission, you must fill in this form before Sep 25 Fri 2:00pm. (For DRES students, please email Timothy (tmc).)
- Timothy will have an extra office hour on Friday Sep 25 at 2pm-3pm in his office Siebel 3230
- Midterm 2 (Nov 4 Wed 7:00pm-9:30pm)
- Final (TBA)
About the Course
CS 473 (also cross-listed as Math 473 and CSE 414) is an algorithms course aimed at advanced undergraduates and graduate students in computer science and related disciplines. The course covers a wide range of topics in algorithm design and analysis, including the following:
- Divide-and-conquer (such as FFT)
- Dynamic programming
- Randomized algorithms
- Optimization: matching, network flow, linear programming
- NP-completeness and reductions
- Approximation algorithms
Prerequisites: CS/ECE 374 or equivalent, or graduate standing (see things you should already know)
[Note: grad students who have not taken a theory-oriented algorithms course at the level of CS 374 may be interested instead in the new CS498M24 "MCS Algorithms" course this semester.]
Lectures
Although lectures will be recorded, it is expected that students will attend most of the lectures. Recordings may be accessed on mediaspace for registered students. I will provide scribbles from class, and some links to relevant resources, below. There is no textbook, but Jeff's book and notes are excellent. (Other useful general resources can be found here.)
- Aug 25: Divide-and-conquer. Closest pair and Shamos's algorithm.
[Ref: Jeff's notes on recursion and Sec 5.4 of Preparata and Shamos's book]
- Aug 27 and Sep 1: Polynomial multiplication (convolution), FFT, and applications (to string matching with don't cares).
[Ref: Jeff's notes or Dasgupta, Papadimitriou, and Vazirani's book; Clifford and Clifford's paper]
- Sep 3: Matrix multiplication.
[Ref: Dasgupta, Papadimitriou, and Vazirani's book; see this for the latest result]
- Sep 8: Dynamic programming. Example: line break problem.
[Ref: Jeff's book; some general tips about DP I wrote for CS374 which may still be useful]
- Sep 10: Longest common subsequence (LCS), with linear space or slightly subquadratic time.
[Ref: see Sec D.1-D.2 of Jeff's notes on Chowdhury and Ramachandran's space saving trick and the four-Russians speedup]
- Sep 15: Max-perimeter subpolygon, and speedup via Monge property.
[Ref: F. Yao's paper]
- Sep 17: Optimal binary search trees (and Monge again). Subset sum (and convolution).
[Ref: Sec D.4 of Jeff's notes]
- Sep 22 and Sep 24: Randomized algorithms. Primality testing (Miller-Rabin).
[Ref: Sec 14.6 of Motwani and Raghavan's book; Chris Caldwell's PrimePages; the AKS paper]
- Sep 29: Optional midterm 1 review (no lecture, but we will go over some selected problems, e.g., from here).
- Oct 1: String matching (Rabin-Karp).
[Ref: Ch7 of Motwani and Raghavan's book, or Jeff's notes]
- Oct 6: Hashing (universal, perfect, ...).