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 2:30-3:30 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. Check EdStem for the latest updates to the office hours.
Administrivia
Homework
- Homework 0 (not graded) [solutions]
- Homework 1 [.tex] (due Feb 6 Thu 10am) [solutions]
- Homework 2 [.tex] (due Feb 13 Thu 10am) (2/10: changed infinities to 0 in HW2.1a,b) [solutions]
- Homework 3 [.tex] (due Feb 20 Thu 10am) (2/15:
correct typo in HW3.2 example and space bounds in HW3.3(a,b))
- Homework 4 (due Mar 6 Thu 10am)
- Homework 5 (due Mar 13 Thu 10am)
- Homework 6 (due Mar 27 Thu 10am)
- Homework 7 (due Apr 3 Thu 10am)
- Homework 8 (due Apr 17 Thu 10am)
- Homework 9 (due Apr 24 Thu 10am)
- Homework 10 (due May 1 Thu 10am)
Exams
- Midterm 1 (Feb 24 Mon 7:00pm-9:00pm, 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 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).
- We will provide some practice exam questions soon...
- 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.)
- Midterm 2 (Apr 7 Mon 7pm-9pm)
- 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.)