Mitchell Jones (mfjones2, office hours: Tue 11:00-12:00 at the theory lounge)

- About this course
- Policies
- Academic integrity
- Gradescope for homework submissions and grades (self-enrollment code: MV8822; tell us your Gradescope identity on this form on Moodle)
- Moodle for exam grades
- Piazza for discussions and announcements

- 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]

- 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)

- location:
- 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)

- location:
- 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)

- location:

- (Advanced) divide-and-conquer (such as FFT)
- (Advanced) dynamic programming
- Randomized algorithms
- Optimization: matching, network flow, linear programming
- NP-completeness and reductions
- Approximation algorithms

- 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