| Date | Reading | Class | Assignments | ||
|---|---|---|---|---|---|
| Introduction | 08/25 | Introduction | |||
| 08/27 | p. 30 [ch. 1] | Abstract data types and complexity analysis | |||
| Unit 1: Sequences | 09/01 | pp. 87, 216 [ch. 2–4] | Dynamic arrays; classes and copy control | HW1 | |
| 09/03 | 5.1–2, 5.5–6, 6.1–5 | Linked lists; templates | |||
| 09/08 | 7.1–3, 8.1–3 | Stacks, queues, and deques | |||
| 09/10 | An RPN calculator with undo | PG1 | |||
| Unit 2: Sorting and priority queues | 09/15 | 10.1–2, 11.1–2, 11.4, handout | Priority queues: binary heaps | HW2 | 09/17 | 13.1, 13.3 | Sorting: insertion, selection, heap |
| 09/22 | [9], 13.2, 13.4 | Sorting: merge, quick | |||
| 09/24 | Where is the nearest food? | PG2 | |||
| Unit 3: Searching and search trees | 09/29 | 12.1, [10.3–4], 10.5 | Binary search and binary search trees | HW3 | |
| 10/01 | 11.3 | B-trees | |||
| 10/06 | 11.5, handout | Red-black trees | |||
| 10/08 | Where is the nearest food, continued | PG3 | |||
| 10/13 | Project presentations | ||||
| 10/15 | Midterm exam | ||||
| Fall break | |||||
| Unit 4: Hash tables | 10/27 | 12.2–4 | Separate chaining, hash functions | HW4 | |
| 10/29 | pages 601, 618–619 again | Open addressing, rehashing | |||
| 11/03 | handout | Bucket sort | |||
| 11/05 | Geocoding in South Bend | PG4 | |||
| Unit 5: Graphs | 11/10 | 15.1–2 | Graph representations | HW5 | |
| 11/12 | 15.3 | Breadth-first, depth-first search | |||
| 11/17 | 15.4 | Dijkstra's algorithm | |||
| 11/19 | Navigating around South Bend | PG5 | |||
| Advanced topics | 11/24 | Handout | Very small data structures | ||
| 11/26 | Thanksgiving | ||||
| 12/01 | Handout | Very big data structures | |||
| 12/03 | Project presentations | ||||
| 12/08 | Project presentations | ||||
| 12/10 | Project presentations | ||||
| 12/15 10:30am | Final exam | ||||
Readings in square brackets cover review topics. They are optional, but you are expected to be familiar with the concepts in them.