Online Schedule
The rest of our semester will be divided into topic sections. Each topic section will have a set of lecture recordings (a lecture package) to watch and a given watch-by date.
Dynamic Programming
March 23 - Review and Gerrymandering
- Exam Review - Video
- Exam Algorithm Design - Video
- Longest Common Subsequence - Horton’s video - Slides
- DP Review - Video - Slides - Written Notes
- Gerrymandering - Video - Slides - Ch 16
- Horton’s 3/23 3:30 pm class discussion in Zoom Video
- Hott’s 3/23 5 pm class discussion in Zoom Video
Greedy Algorithms
March 25 - Greedy Algorithms Introduction
- Greedy Introduction - Ch 16 Video - Slides
- Interval Scheduling - Video - Slides - Ch 16
- Hott’s 3/25 2 pm class discussion in Zoom Video
- Horton’s 3/25 3:30 pm class discussion in Zoom Video
March 30 - Huffman Coding
- Huffman Coding - Ch 16 - Video - Slides - Marked-up Slides
- Hott’s 3/30 5 pm class discussion in Zoom Video
- Horton’s 3/30 3:30 pm class discussion in Zoom Video: discussion of pseudo-polynomial time at 00:49:30; discussion of HW6 P1 at 01:02:08.
April 1 - Belady Cache Replacement
- Belady Cache Replacement - Ch 16 - Video - Slides - Marked-up Slides
- Horton’s 4/1 3:30 pm class discussion in Zoom Video: discussed Huffman encoding, how to approach HW6 P2 (starting at 00:15:38)
- Hott’s 4/1 2 pm class discussion in Zoom Video: discussed similar problems to the homework
Graph Algorithms
April 6 - Graph Introductions
- Graph Review - Ch 23
- Minimum Spanning Trees - Ch 23
- Lecture, April 6 - Video - Slides
- Horton’s 4/6 3:30 pm class discussion in Zoom Video
- Hott’s 4/6 pm class discussion in Zoom Video
April 8 - Shortest Paths
- Dijkstra’s Algorithm - Ch 24
- Lecture, April 8 - Video - Slides
- Hott’s 4/8 2 pm class discussion in Zoom Video: discussed shortest path algorithms and proof of Dijkstra’s algorithm
- Horton’s 4/8 3:30 pm class discussion in Zoom Video
April 10 - Shortest Paths
- Bellman-Ford and Floyd-Warshall - Ch 24 - Video - Slides - Marked-up Slides
April 13 - Max Flow
- Max Flow / Min Cut - Ch 26 - Video - Slides - Marked-up Slides
- Hott’s 4/13 5 pm class discussion in Zoom Video
Reductions
April 15 - Introduction
- Reductions and Bipartite Matching - Ch 34 - Video - Slides - Marked-up Slides
April 20 - Additional Reductions, Intro to NP-Completeness
- Slides for both parts, updated 4/22 4pm
- Part 1: Reductions, Lower Bounds - Ch 34 - Video
- Part 2: Intro to NP-Completeness etc - Ch 34 - Video
NP-Completeness
April 22 - NP-Completeness
- NP-Completeness Slides for both parts, updated on 4/23 11 am, slides 16 and 55
- Part 1: NP-Completeness Video
- Part 2: Proving NP-Completeness with reductions, Wrap-up on NP-C Video
Finale
April 27 - Join us for a live course finale
- Hott’s 2pm
- Horton’s 3:30pm
- Slides with markup
- Video. Due to error, only recorded final 10 minutes, “wrap up” of course. Apologies! Dang, I even wore a nice shirt for the last class too. :-(
- Hott’s 5pm
In-Person Schedule
This is a tentative full-semester schedule of topics addressed. As we go through the semester, we will add homework dates and adjust topics slightly as needed.
| Date | Topic | Slides/Notes | Readings | Homework |
|---|---|---|---|---|
| Jan 13 | Introduction | Horton, Hott | - | HW0 out |
| Jan 15 | Divide and Conquer | Horton, Hott | Ch 3, 4 | |
| Jan 20 | MLK Day - No class | |||
| Jan 22 | Karatsuba, Tree Method | Horton, Hott, math | Ch 4 | |
| Jan 27 | Guess and Check | Horton, Hott, math | Ch 4 | |
| Jan 29 | Master Theorem | Horton, Hott, math | ||
| Feb 3 | Master Theorem, Substitution | Horton, Brunelle/Hott | Ch 4 | |
| Feb 5 | Closest Pair of Points, Strassen’s Algorithm | Horton, Hott | Ch 4, 33 | |
| Feb 10 | Quicksort, Quickselect, Median of Medians | Horton, Brunelle/Hott | Ch 7, 9 | |
| Feb 12 | Median of Medians, Randomized Quicksort, Sorting | Horton, Hott | Ch 7, 8 | |
| Feb 17 | Average-case Quicksort, Lower Bounds Sorting | Horton, Hott | Intro II, Ch 4, 6, 8 | |
| Feb 19 | Linear Time Sorting, MSCS | Horton, Hott | 6, 8 | |
| Feb 24 | Dynamic Programming | Horton, Hott | Ch 15 | |
| Feb 26 | Matrix Chain Multiplication | Horton, Hott | Ch 15 | |
| Mar 2 | Seam Carving, Longest Common Subsequence | Horton, Hott | Ch 15 | |
| Mar 4 | Midterm Exam | |||
| Mar 9 | Spring Break | |||
| Mar 11 | Spring Break |