CS 473, Spring 2023
Algorithms
Course Staff
Instructor: Timothy Chan (tmc)
Co-instructor: Bhaskar Ray Chaudhury (braycha)
TAs: Tanvi Bajpai (tbajpai2), Christian Howard (howard28)
CAs: Changsheng Chen (cc81), Yirong Chen (yirongc3), Sam Ruggerio (samuelr6), David Yao (dyyao2)
Lecture Time/Place
Tue & Thu 2:00pm-3:15pm, Siebel 1404
Office Hours
- Mon 3:00-4:00 Christian
- Tue 3:30-4:30 Timothy
- Wed 3:00-4:00 Tanvi
- Fri 3:00-4:00 Sam
- Mon 9:00-10:00 Bhaskar
All office hours to be held in the open lounge area on the 3rd floor of Siebel (outside of 3240).
Administrivia
Homework
Exams
- Midterm 1 (Feb 20 Mon 7pm-9pm, Loomis Lab of Physics 141 (in-person)) [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, either in person or online.
- Coverage: The exam will cover everything up to and including Feb 9's lecture (in particular, material corresponding to HW0-HW3, including prerequisite material, divide-and-conquer, and dynamic programming).
- Some practice exam questions (we don't provide official solutions, but we may go over some of them in the review session)
- Conflict exams: Conflict exams (on Feb 21 Tuesday) will be offered only to those with a valid reason. To get permission, you must fill in this form no later than Feb 15 Wednesday.
- Midterm 2 (Apr 3 Mon 7pm-9pm, Loomis Lab of Physics 141 (in-person)) [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, either in person or online.
- Coverage: The exam will cover everything from Feb 14 to Mar 28's lectures (randomized algorithms and matching/flows).
- Some practice exam questions (we don't provide official solutions, but we may go over some of them in the review session)
- Conflict exams: Conflict exams (on Apr 4 Tuesday) will be offered only to those with a valid reason. To get permission, you must fill in this form no later than Mar 28 Tuesday.
- Final Exam (May 10 Wed 7pm-10pm, Siebel 1404 (in-person)) [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 two 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. (Four 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, either in person or online.
- Coverage:
the final exam will be cumulative, though there will be greater emphasis on post-midterm-2 material
- Some practice exam questions (we don't provide official solutions, but we may go over some of them in the review session)
- Conflict exams: Conflict exams will not be offered unless there are truly legitimate reasons. Email Timothy (tmc) to ask for permission,
no later than May 4 Thursday.
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 17: 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 19: Convolution (polynomial multiplication) and FFT.
[Ref: Jeff's notes or Dasgupta, Papadimitriou, and Vazirani's book]
- Jan 24: Applications of convolution/FFT (to 3SUM and string matching with "don't cares").
Note: Timothy will be away, but please watch the pre-recorded 50-min video clip on mediaspace.
[Ref: Clifford and Clifford's paper]
- Jan 26: FFT cont'd. Matrix multiplication.
[Ref: Dasgupta, Papadimitriou, and Vazirani's book]
- Jan 31: Dynamic programming. Example: line break problem.
[Ref: Jeff's book]
- Feb 2: Longest common subsequence (LCS), with linear space.
[Ref: see Sec D.1 of Jeff's notes on Chowdhury and Ramachandran's space saving trick]
- Feb 7: LCS, with slightly subquadratic time. Max-perimeter L-gon.
[Ref: Sec D.2 of Jeff's notes; F. Yao's paper; and for those curious, Schieber's paper]
- Feb 9: Optimal binary search trees. Knapsack.
[Ref: Jeff's book and Sec D.4 of Jeff's notes]
- Feb 14: Randomized algorithms.
- Feb 16: Optional midterm 1 review (no lecture). (We will go over some selected questions from here.)
- Feb 21: Primality testing (Rabin-Miller).
[Ref: Sec 14.6 of Motwani and Raghavan's book; Chris Caldwell's PrimePages; the AKS paper]
- Feb 23: String matching (Rabin-Karp).
[Ref: Ch7 of Motwani and Raghavan's book, or Jeff's notes]
- Feb 28: Hashing (universal, perfect, ...).
[Ref: Sec 8.4 of Motwani and Raghavan, or Jeff's notes]
- Mar 2 and Mar 7: Smallest 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 9: Median finding (Floyd-Rivest and random sampling, Chernoff bounds). Optimization.
[Ref: Sec 3.3 and 4.1 of Motwani and Raghavan]
- Mar 14 and Mar 16: Spring break.
- Mar 21: Bipartite matching (Hungarian method, and Hopcroft-Karp (briefly)).
[Ref: Sariel's notes]
- Mar 23: Max flow (Ford-Fulkerson, max-flow/min-cut theorem).
[Ref: Jeff's book]
- Mar 28: Max flow cont'd (Edmonds-Karp), and min-cost flow.
[Ref: Jeff's notes on min-cost flow; and for your amusement, the over-100-pages breakthrough paper by Chen, Kyng, Liu, Peng, Gutenberg, and Sachdeva (2022)]
- Mar 30: Optional midterm 2 review (no lecture). (We will go over some selected questions from here.)
- Apr 4: Linear programming (standard form, simplex algorithm).
[Ref: Ch 20 and Ch 21 Sariel's notes]
- Apr 6: Linear programming (Duality).
[Ref: Ch 21 Sariel's notes]
- Apr 11: NP Completeness-I.
[Ref: Ch 1 and Ch 2 Sariel's notes, Chapter 8 (Section 8.2) in Kleinberg and Tardos (Algorithm Design)]
- Apr 13: NP Completeness-II.
[Ref: Chapter 8 (Sections 8.6 and 8.8) in Kleinberg and Tardos (Algorithm Design)] [Timothy's tips on NP-completeness proofs with examples (from 374)]
- Apr 18: Approximation Algorithms-I.
[Ref: Chapter 11 (Sections 11.1, 11.3, 11.8) in Kleinberg and Tardos (Algorithm Design)]
- Apr 20: Approximation Algorithms-II.
[Ref: Chapter 11 (Sections 11.6, 11.7) in Kleinberg and Tardos (Algorithm Design)]
- Apr 25: Approximation Algorithms-III.
[Williamson and Shmoys (The Design of Approximation Algorithms), 1.7,5.1,5.3,5.4,5.5 ]
- Apr 27: Approximation Algorithms-IV.
[Vazirani (Approximation Algorithms), Chapters 9 and 10 ]
- May 2: Final review. (Timothy will go over some selected questions from here.)