CS 473 (or CS 498DL1), Fall 2017: Algorithms
Instructor
Timothy Chan
(tmc, Siebel 3230,
office hours: Tue 2:00-3:00 & Fri 11:00-12:00 or by appointment)
TAs
Shalmoli Gupta (sgupta49,
office hours: Mon 2:00-3:00 at the theory lounge (Siebel 3rd floor))
Mitchell Jones (mfjones2,
office hours: Tue 11:00-12:00 at the theory lounge)
Graders
Xiyao Shi (xshi27),
Sam Stephens (scsteph2),
Qiwen Wang (qwang70)
Meeting time/place
Wed & Fri 9:30-10:45, DCL 1310
Administrivia
Homework
- Homework 0 (out Aug 30, due Sep 6 Wed 8pm)
[solutions]
- Homework 1 (out Sep 6, due Sep 13 Wed 8pm)
[solutions]
- Homework 2 (out Sep 13, due Sep 20 Wed 8pm)
[note: a typo in problem 2 has been fixed;
solutions]
- Homework 3 (out Sep 20, due Sep 27 Wed 8pm)
[solutions]
- Homework 4 (out Oct 4, due Oct 11 Wed 8pm)
[solutions]
- Homework 5 (out Oct 11, due Oct 18 Wed 8pm)
[solutions]
- Homework 6 (out Oct 18, due Oct 25 Wed 8pm)
[solutions]
- Homework 7 (out Oct 25, due Nov 1 Wed 8pm)
[solutions]
- Homework 8 (out Nov 8, due Nov 15 Wed 8pm)
[solutions]
- Homework 9 (out Nov 15, due Nov 29 Wed 8pm)
[solutions]
- Homework 10 (out Nov 29, due Dec 6 Wed 8pm)
[solutions]
Exams
- Midterm 1 (Oct 3 Tue 7pm-9pm):
[solutions]
- location: DCL 1320
- you may bring one double-sided 8.5"x11" cheat sheet (with your name and netID written on the upper right corner), but otherwise no additional material is allowed
- the exam covers everything up to and including Sep 22's lecture (in particular, content related to HW0-HW3)
- here are some sample midterm questions
- I will have an extra office hour on Oct 2 Monday 3:00-4:00
(in addition to my Tuesday 2:00-3:00 office hour)
- Midterm 2 (Nov 7 Tue 7pm-9pm)
[solutions]
- location: MSEB 100
- you may bring one double-sided 8.5"x11" cheat sheet (with your name and netID written on the upper right corner), but otherwise no additional material is allowed
- the exam covers everything from Sep 29 to
Nov 1 Oct 27 lectures (inclusively)
- here are some sample midterm questions
- I will have an extra office hour on Nov 6 Monday 3:00-4:00
(in addition to my Tuesday 2:00-3:00 office hour)
- Final exam (Dec 15 Fri 7pm-10pm)
- location: Siebel 0216
- you may bring two double-sided 8.5"x11" cheat sheets (with your name and netID written on the upper right corner), but otherwise no additional material is allowed
- the final exam is comprehensive, with greater emphasis on post-midterm
material
- here are some sample questions on NP-completeness and approximation algorithms
(which do not reflect the length or comprehensiveness of the actual final exam)
- I will have an extra office hour on Dec 14 Thursday 3:00-4:00
(in addition to my usual Tuesday 2:00-3:00 and Friday 11:00-12:00 office hours)
Course outline
- (Advanced) divide-and-conquer (such as FFT)
- (Advanced) dynamic programming
- Randomized algorithms
- Optimization: matching, network flow, linear programming
- NP-completeness and reductions
- Approximation algorithms
Lectures
There is no required textbook. I will provide notes written in class
(and some links to relevant resources) below. There are already excellent lecture notes/slides/videos from previous versions of CS473 by
Jeff
and
Chandra/Ruta
and
Sariel (though the specific topics may vary from semester to semester). You can also find
links to other useful resources
here.
- Aug 30: Divide-and-conquer. SMAWK (searching in totally monotone matrices).
[my notes; other refs:
the original paper or
Sec D.4-D.6 of Jeff's notes]
- Sep 1: FFT (polynomial multiplication, i.e., convolution).
[my notes (and
more); other refs: Ch 30 of
Cormen et al.'s book or Jeff's notes]
- Sep 6: FFT cont'd (applications to string matching with "don't cares"). Matrix multiplication.
[my notes; other ref:
Clifford and Clifford's paper]
- Sep 8: Matrix multiplication cont'd (Strassen, and application to triangle finding).
[my notes (and more); other ref: see Sec 4.2 of Cormen et al.'s book]
- Sep 13: Dynamic programming. LCS.
[my notes; other refs: Sec 15.4
of Cormen et al.'s book; see Sec D.1 of Jeff's notes for Hirschberg's space-saving trick]
- Sep 15: APSP.
[my notes; other ref: Ch 25 of
Cormen et al.'s book]
- Sep 20: More DP (max convex k-gon (with SMAWK), min length triangulation,
subset sum, TSP).
[my notes]
- Sep 22: Randomized algorithms. Primality testing (Rabin-Miller).
[my notes; other refs: Chris
Caldwell's
Prime Pages and
AKS paper]
- Sep 27: No class.
- Sep 29: String matching (Rabin-Karp).
[my notes; other refs: Sec 32.2 of Cormen et al. or Ch7 of Motwani and Raghavan's book]
- Oct 4: Hashing (universal, perfect, etc.).
[my notes; other refs: Sec 8.4 of Motwani and Raghavan, or
Jeff's notes]
- Oct 6: Smallest enclosing circle (Seidel-Welzl and randomized incremental algorithms).
[my notes; other refs:
Welzl's paper
(and Sec 5.1 of Cormen et al. on the "hiring problem")]
- Oct 11: Median finding (Floyd-Rivest and random sampling, Chernoff bounds).
[my notes; other refs: Sec 3.3 and 4.1 of
Motwani and Raghavan]
- Oct 13: SAT (Papadimitriou's algorithm and random walks).
[my notes; other refs:
Sec 6.1 of Motwani-Raghavan, and
Schoening's paper]
- Oct 18: Optimization. Bipartite matching (Hungarian method).
[my notes]
- Oct 20: Bipartite matching cont'd (Hopcroft-Karp). Max flow.
[my notes; other ref: see
Hopcroft and Karp's original paper]
- Oct 25: Max flow (Ford-Fulkerson, max-flow/min-cut theorem, integrality theorem).
[my notes; other refs:
Sec 26.1-26.2 of Cormen et al., or more concisely, Sec 8.1 of
Tarjan's book]
- Oct 27: Max flow cont'd (Edmonds-Karp). LP.
[my notes; see above refs]
- Nov 1: LP (simplex method).
[my notes; see Ch 29 of
Cormen et al. or Sariel's notes, or books on LP such as
Matousek-Gartner]
- Nov 3: LP cont'd (duality etc.).
[my notes]
- Nov 8: NP-completeness. P, NP, and NP-complete problems.
[my notes; Sec 34.1-34.3 of Cormen et al.
(or find
Garey and Johnson's book in the library)]
- Nov 10: NP-completeness of (Circuit-)SAT and 3SAT.
[my notes; Sec 34.4 of Cormen et al.]
- Nov 15: NP-completeness of independent set/vertex cover/clique.
[my notes]
- Nov 17: NP-completeness of Hamiltonian cycle/TSP, and subset sum.
[my notes]
- Nov 29: Approximation algorithms. Vertex cover.
[my notes; Sec 35.1 of Cormen et al.]
- Dec 1: Metric TSP (by MST and Christofides).
[my notes; Sec 35.2 of Cormen et al.,
Sec 3.2 of
Vazirani's book]
- Dec 6: Disjoint squares (Hochbaum-Maass).
[my notes;
see original paper]
- Dec 8: MAX-SAT (Goemans-Williamson, by LP relaxation + randomized rounding).
[my notes;
Ch 16 of
Vazirani's book]
- Dec 13: Review
