This is a tentative forecast of class contents, exam dates, and dates for homeworks and labs. The forecast is subject to revision as necessary and has often been considerably revised in past years based on how quickly we get through the material.
| Date | Class Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Mon Aug 24 |
Which algorithm is best? Finding the closest pair of points | Sections 1.1 - 2.3 | Lab 0, Homework 0 | |
| Wed Aug 26 |
Fast algorithm for finding closest pair of points | Section 33.4 | Lab 1 | |
| Mon Aug 31 |
Asymptotic notation | Chapter 3 | Homework 1 | |
| Wed Sep 2 |
Divide-and-conquer algorithms | Section 4.4 | Homework 0, Lab 0 | |
| Mon Sep 7 |
Labor Day; No class | |||
| Wed Sep 9 |
Solving recurrences | Section 4.5 | ||
| Mon Sep 14 |
Dictionary ADT, hashing | Sections 10.2, 11.1-11.2 | Lab 1 | |
| Wed Sep 16 |
Hashing analysis | Section 11.3.1 and Appendix C.3 | Homework 1 | Homework 2 |
| Mon Sep 21 |
Quicksort worst-case analysis | Sections 7.1 & 7.2 | Lab 2 | |
| Wed Sep 23 |
Quicksort: randomized version | Sections 7.3 & 7.4 | ||
| Mon Sep 28 |
Sorting lower bound | Sections 8.1 & 8.2 | ||
| Wed Sep 30 |
catchup | Homework 2 | ||
| Mon Oct 5 |
EXAM 1 | |||
| Wed Oct 7 |
Counting sort and radix sort | Section 8.3 | Lab 2 | Homework 3 |
| Mon Oct 12 |
Binary search trees | Sections 12.1 - 12.3 | ||
| Wed Oct 14 |
Skip lists | handout | ||
| Mon Oct 19 |
Skip list analysis | Lab 3 | ||
| Wed Oct 21 |
B-trees | Sections 18.1 - 18.3 | Homework 3 | Homework 4 |
| Mon Oct 26 |
B-trees analysis | handout | ||
| Wed Oct 28 |
Priority Queue ADT, binary heaps | Sections 6.1 & 6.2 | ||
| Mon Nov 2 |
Graph problems, representing graphs | Section 22.1 | Lab 3 | |
| Wed Nov 4 |
catchup | Homework 4 | ||
| Mon Nov 9 |
EXAM 2 | |||
| Wed Nov 11 |
Breadth-first search (BFS), introduce Dijkstra | Section 22.2 | Homework 5, Lab 4 | |
| Mon Nov 16 |
Dijkstra's shortest path algorithm | Sections 24.3 & 24.5 | ||
| Wed Nov 18 |
Analysis of Dijkstra's algo; Prim's Minimum Spanning Tree (MST) | Sections 23.1 & 23.2 | ||
| Mon Nov 23 |
DFS and topological sort | Sections 22.3 & 22.4 | ||
| Nov 25-27 | Thanksgiving break; No class | |||
| Mon Nov 30 |
TBA | Homework 5 | ||
| Wed Dec 2 |
EXAM 3 | Lab 4 due Fri, 12/4 |