CS 473 (Spring 2025)
Algorithms
Instructor
Timothy Chan (tmc "at" illinois.edu)
TAs
Zhengcheng Huang (zh3), Shubhang Kulkarni (smkulka2)
CAs
Ved Kommalapati (vkomm4), Dhiraj Kuttichirayil (dhiraj2), Jake Mayer (jmmayer3), Letian Zhang (letianz4)
Lecture Time/Place
Wed & Fri 12:30pm-1:45pm, DCL 1310
Office Hours
- Mon 3:00-4:00 Shubhang
- Tue 3:00-4:00 Timothy
- Wed 3:00-4:00 Zhengcheng
All office hours are held in the open study space in the basement of Siebel (unless stated otherwise). Check EdStem for the latest updates to the office hours.
Administrivia
Homework
Exams
- Midterm 1 (Feb 24 Mon 7:00pm-9:00pm, 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 Feb 14'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
- Conflict exams: Conflict exams (on Feb 25 Tue) will be offered only to students with a valid reason. To get permission, you must fill in this form before Feb 19 Wednesday 2:00pm. (For DRES students, please email Timothy (tmc) ASAP.)
- Timothy will have an extra office hour on Friday Feb 21 at 4pm-5pm in his office Siebel 3230, and will cancel his office hour on Tuesday Feb 25
- Midterm 2 (Apr 7 Mon 7pm-9pm, in Siebel 1404)
- 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
from Feb 19 to Apr 2's lectures (randomized algorithms and matching/flows).
- practice problems and a past exam will be posted later...
- Conflict exams: Conflict exams (on Apr 8 Tue) will be offered only to students with a valid reason. To get permission, you must fill in this form before March 28 Wednesday 5:00pm.
- Final Exam (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)
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.)
- Jan 22: 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]
- Jan 24 and Jan 29: 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]
- Jan 31: Matrix multiplication.
[Ref: Dasgupta, Papadimitriou, and Vazirani's book]
- Feb 5: Dynamic programming. Example: line break problem.
[Ref: Jeff's book; some general tips about DP I wrote for CS374 which may still be useful]
- Feb 7: 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]
- Feb 12: Max-perimeter subpolygon, and speedup via Monge property.
[Ref: F. Yao's paper]
- Feb 14: Optimal binary search trees (and Monge again). Subset sum (and convolution).
[Ref: Sec D.4 of Jeff's notes]
- Feb 19: Randomized algorithms.
- Feb 21: Optional midterm 1 review (no lecture, but we will go over some selected questions from here)
- Feb 26: Primality testing (Miller-Rabin).
[Ref: Sec 14.6 of Motwani and Raghavan's book; Chris Caldwell's PrimePages; the AKS paper]
- Feb 28: String matching (Rabin-Karp).
[Ref: Ch7 of Motwani and Raghavan's book, or Jeff's notes]
- Mar 5 and Mar 7: Hashing (universal, perfect, ...).
[Ref: Sec 8.4 of Motwani and Raghavan, or Jeff's notes]
- Mar 12: Min enclosing circle (Seidel-Welzl and randomized incremental algorithms).
[Ref: Welzl's paper (and Sec 5.1 of Cormen-Leiserson-Rivest-Stein on the "hiring problem")]
- Mar 14: Median finding (Floyd-Rivest and random sampling). Optimization...
[Ref: Sec 3.3 and 4.1 of Motwani and Raghavan]
- Mar 19 and 21: Spring break.
- Mar 26: Max bipartite matching (Hungarian method, and Hopcroft-Karp (briefly)).
[Ref: Sariel's notes on matching]
- Mar 28: Max flow (Ford-Fulkerson)...
[Ref: Jeff's book]