Links to within this page:

- What remains to be done this Fall
- What has already been taught this Fall
- What was taught last Spring

Who's teaching?

- Sep. 21 --- Heaps, the sorting lower bound, and possibly some counting sort and radix sort. Homework 2 due
- Sep. 26 --- Counting and radix sort, and various problems involving sorting and searching
- Sep. 28 --- Review and more practice for first exam. Homework 3 due
- Oct. 03 --- Intro to expected values, and hashing
- Oct. 05 --- Exam 1 (covering September's lectures)
- Oct. 10 --- More about random variables (especially IRV) and hashing. (also the drop deadline)
- Oct. 12 --- Randomized Selection and Quicksort
- Oct. 17 --- Amortization (last lecture included in Exam 2)
- Oct. 19 --- Intro to binary search trees and red-black trees
- Oct. 24 --- More about red-black trees if necessary, and some review if time permits
- Oct. 26 --- Exam 2 (covering hashing, randomized algorithms and amortization)
- Oct. 31 --- Augmented trees
- Nov. 02 --- Dynamic programming

Nov. 07 --- No class - Nov. 09 --- More dynamic programming
- Nov. 14 --- Intro to graphs, BFS, DFS
- Nov. 16 --- Exam 3 (on BSTs and dynamic programming)
- Nov. 21 --- Topological sort, and strongly connected components

Nov. 23 --- No class - Nov. 28 --- Minimum spanning trees (intro and Kruskal's algorithm).
- Nov. 30 --- More MST (Prim's algorithm), and intro to single-source shortest paths
- Dec. 05 --- A little more SSSP, and then some NP-completeness
- Dec. 07 --- More on NP-completeness if necessary, and some computational geometry

- Dec. 15 --- Exam 4 (graphs), and cumulative final (tentatively 6-9pm, location TBD)

- Greg covered: the last bit of recurrences by substitution, and the master method.
- Reading: Section 3.1 and 3.2

- Greg covered: solving recurrences by substitution
- Reading: Section 3.1 (all but the last two pages of the condensed pdf; or last 15 pages of full slideshow)

- Greg covered: more about big-O, then mergesort and its recurrence
- Reading: All of Section 2, Section 4.2, and the beginning of Section 3.1 (up to determining the time complexity of mergesort with a tree)

- Prof. Blumer covered: Intro, Insertion sort, and brief definition of big-O and Omega
- Reading: Section 4.1 and the start of Section 2.

- NP-completeness reductions. Review of course. Constructing convex hulls.
- Reading: section 14. Nothing for convex hulls.

- SSSP for DAGs and Dijkstra's algorithm. NP-completeness (up to defining reductions)
- Reading: Sections 12.3 and 12.4, and part of section 14

- Prim's MST algorithm, intro to SSSP and the Bellman-Ford algorithm.
- Reading: section 11.3 and sections 12.1, 12.2

- Minimum spanning trees: intro and Kruskal's algorithm. Also a short recap of SCC.
- Reading: section 11.1 and 11.2

- Greg covered topological sort, and strongly connected components (except for the second example and final recap of proof of correctness)
- Reading: section 10.3 and 10.4

- Greg covered an intro to graphs, BFS, and DFS.
- Reading: section 10.1 and 10.2 (except the part on planar graphs)

- Prof. Blumer did a review for exam 3.

- Prof. Blumer covered more dynamic programming (LCS, LIS, rod cutting)
- Reading: section 8

- Prof. Blumer covered augmented trees, and introduced dynamic programming.
- Reading: Sections 7 and 8.1

- Prof. Blumer did a review for exam 2.

- Prof. Blumer covered intro to BSTs, and red-black trees.
- Reading: Sections 6.1, 6.2, and 6.3

- Prof. Blumer covered amortization.
- Reading: Section 9. There is no video for multipop and binary counter, but there is a video introducing amortization using array doubling.

- Prof. Blumer covered randomized selection, and quicksort.
- Reading: Section 5.2 and section 4.4

- Prof. Blumer covered the rest of the notes on hashing (open addressing, etc).
- Reading: Section 13.1. Also, see Theorems 11.1 and 11.2 in CLRS, which provide more detail than the course notes.
- You should practice IRVs in section 15. This will help for homework 5, and for the upcoming lecture on randomized selection and quicksort.

- Prof. Blumer covered intro to expectation, and hashing with chaining (including more details than what's in my course notes)
- Reading: Section 13.1 and the beginning of section 15 are related. You could also take a look at my old comp61 notes on probability. Not all of it has to do with this class though.

- Greg posted a new video on counting sort and radix sort. The example used is better than the one from last semester.
- Reading: Section 4.6

- Greg covered: heaps, and the sorting lower bound
- Reading: Sections 4.3 and 4.5

- Greg covered: deterministic selection (median-finding)
- Reading: section 5.1

- Greg covered: the master method
- Reading: Section 3.2 (and 3.3.d)

- Greg covered: more examples of solving recurrences by substitution
- Reading: Section 3.1

- Prof. Blumer covered: big-O proofs, mergesort and its recurrence
- Reading: All of Section 2, Section 4.2, and the beginning of Section 3.1 (up to determining the time complexity of mergesort)

- Prof. Blumer covered: Intro, Insertion sort, and brief definition of big-O and Omega
- Reading: Section 4.1 and the start of Section 2.