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.