[note: my Oct 24 Tuesday office hour will be moved to Oct 25 Wednesday 11:00-12:00]

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)

- 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)
- Final exam (TBA)

- (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 (with 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 (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 (and random sampling, Chernoff bounds).

[my notes; other refs: Sec 3.3 and 4.1 of Motwani and Raghavan] - Oct 13: SAT (and random walks).

[my notes; other refs: Sec 6.1 of Motwani-Raghavan, and Schoening's paper] - Oct 18:
*Optimization*. Bipartite matching.

[my notes] - Oct 20: Bipartite matching (cont'd). Max flow...