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