| Date | Lecture Topic | Reading | Assigned | Due |
|---|---|---|---|---|
| Tues, Jan 12 | Which algorithm is best? Finding the closest pair of poitnts. | Sections 1.1-1.4 | Homework 0 | |
| Thurs, Jan 14 | Fast algorithm for finding closest pair of points | Section 35.4 | Lab 1 | Homework 0 |
| Mon, Jan 18 | No Help Session | |||
| Tues, Jan 19 | Asymptotic notation | Chapter 2 | ||
| Thurs, Jan 21 | Divide-and-conquer algorithms | Section 4.2 | ||
| Mon, Jan 25 | Practice with divide-and-conquer algs | |||
| Tues, Jan 26 | Solving recurrences | Homework 1 | Lab 1 (suggested) | |
| Thurs, Jan 28 | Quicksort worst-case analysis, introduce randomized quicksort | Sections 8.1-8.2 | Lab 1 | |
| Mon, Feb 1 | Practice with exactly solving recurrences, induction to prove a solution correct | |||
| Tues, Feb 2 | Probability background, analysis of randomized quicksort | Sections 6.3 (through middle of 113), 8.3,8.4 | ||
| Thurs, Feb 4 | Sorting lower bound | Sections 9.1-9.2 | Homework 2 | Homework 1 |
| Mon, Feb 8 | Very basic C++ tutorial | |||
| Tues, Feb 9 | Sorting lower bound (cont) | |||
| Thurs, Feb 11 | Counting sort and radix sort | Section 9.3 | Homework 2 | |
| Mon, Feb 15 18 | Review session for Exam 1 | |||
| Tues, Feb 16 | EXAM 1 | Lab 2 | ||
| Thurs, Feb 18 | Dictionary ADT, hashing | Sections 11.2, 12.1-12.2 (through page 225) | ||
| Mon, Feb 22 | Guidance on "A" portion of lab | |||
| Tues, Feb 23 | Hashing analysis | Section 12.3.1 | Homework 3 | Lab 2 (suggested) |
| Thurs, Feb 25 | Review search trees, introduce skip lists | Sections 13.1-13.3 | Lab 2 | |
| Mar 1 - Mar 5 | Spring Break | |||
| Mon, Mar 8 | Lower bounds and whatever else is requested | |||
| Tues, Mar 9 | Skip lists | handout | ||
| Thurs, Mar 11 | Skip list analysis | Lab 3 | Homework 3 | |
| Mon, Mar 15 | Lab 3 help session | |||
| Tues, Mar 16 | B-trees | Sections 19.1-19.3 | ||
| Thurs, Mar 18 | B-trees (cont) | Lab 3 | ||
| Mon, Mar 22 | Review session for Exam 2 | Lab 3 accepted until 4:00pm without penalty | ||
| Tues, Mar 23 | EXAM 2 | Homework 4 | ||
| Thurs, Mar 25 | Priority Queue ADT, binary heaps | Sections 7.1-7.2 | ||
| Mon, Mar 29 | B-tree practice problems | |||
| Tues, Mar 30 | Graph problems, representing graphs | Section 23.1 | ||
| Thurs, Apr 1 | Breadth-first search (bfs), introduce MST | Section 23.2 | Lab 4 | Homework 4 |
| Mon, Apr 5 | Implementing a graph ADT | |||
| Tues, Apr 6 | Prim's Minimum Spanning Tree (MST) Alg | Sections 24.1-24.2 | ||
| Thurs, Apr 8 | Dijkstra's shortest path algorithm | Sections 25.1-25.2 | ||
| Mon, Apr 12 | Help Session for Lab 4 | |||
| Tues, Apr 13 | Analysis of Prim's and Dijkstra's algorithms | Homework 5 | Lab 4 (suggested) | |
| Thurs, Apr 15 | DFS and topological sort | Sections 23.3-23.4 | Lab 4 | |
| Mon, Apr 19 | Additional graph algorithm problems/examples | |||
| Tues, Apr 20 | Garbage collection algorithms | handout | ||
| Thurs, Apr 22 | Garbage collection algorithms, review for Final Exam | Homework 5 | ||
| Mon, Apr 26 | Study session for final | |||
| Tue, May 4 | Final Exam 3:30pm-5:30pm (location TBA) |