| Date | Lecture Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Thur, Aug 26 | Which algorithm is best? Finding the closest pair of points. | Sections 1.1-1.4 | Homework 0 Lab 1 |
|
| Tue, Aug 31 | Fast algorithm for finding closest pair of points | Section 35.4 | Homework 0 | |
| Thur, Sept 2 | Asymptotic notation | Chapter 2 | ||
| Tue, Sept 7 | Divide-and-conquer algorithms | Section 4.2 | ||
| Thur, Sept 9 | Solving recurrences | Section 4.3 | Lab 1 | Homework 1 |
| Tue, Sept 14 | Dictionary ADT, hashing | Sections 11.2, 12.1-12.2 (through page 225) | ||
| Thur, Sept 16 | Hashing analysis (and probability review) | Section 12.3.1 and 6.3 (through middle of pg 113) | Homework 1 | Homework 2 | Tue, Sept 21 | Quicksort worst-case analysis, introduce randomized quicksort | Sections 8.1-8.2 | Thur, Sept 23 | Analysis of randomized quicksort | Sections 8.3-8.4 | Homework 2 | Lab 2 |
| Tue, Sept 28 | EXAM 1 | |||
| Thur, Sept 30 | Sorting lower bound | Sections 9.1-9.2 | ||
| Tue, Oct 5 | Sorting lower bound (cont) | |||
| Thur, Oct 7 | Counting sort and radix sort | Section 9.3 | Lab 2 | Homework 3 |
| Tue, Oct 12 | Review search trees, introduce skip lists | Sections 13.1-13.3 | ||
| Thur, Oct 14 | Skip lists | handout | Homework 3 | Lab 3 |
| Tue, Oct 19 | Skip list analysis | |||
| Thur, Oct 21 | B-trees | Sections 19.1-19.3 | ||
| Tue, Oct 26 | B-trees (cont) | |||
| Thur, Oct 28 | Priority Queue ADT, binary heaps | Sections 7.1-7.2 | Lab 3 | |
| Tue, Nov 2 | EXAM 2 | Homework 4 | ||
| Thur, Nov 4 | Graph problems, representing graphs | Section 23.1 | ||
| Tue, Nov 9 | Breadth-first search (bfs), introduce MST | Section 23.2 | Lab 4 | |
| Thur, Nov 11 | Prim's Minimum Spanning Tree (MST) Alg | Sections 24.1-24.2 | Homework 4 | |
| Tue, Nov 16 | Analysis of Prim's algorithm | |||
| Thur, Nov 18 | Dijkstra's shortest path algorithm | Sections 25.1-25.2 | ||
| Tue Nov 23 | DFS and topological sort | Sections 23.3-23.4 | Lab 4 suggested | |
| Thur Nov 25 | Thanksgiving Break | |||
| Tues, Nov 30 | Garbage collection algorithms | handout | Lab 4 | Homework 5 |
| Thurs, Dec 2 | Garbage collection algorithms | |||
| Tue, Dec 7 | Overview and review for the final | Homework 5 | ||
| Tue, Dec 14 | Final Exam 1:00pm-3:00pm (location TBA) |