(This schedule is tentative and may change slightly as the course progresses.)
| Day | Date | Topic(s) | Section of Book (Homework Problems) |
| Wed | Sep 5 | Introduction Asympototic Notation Common Functions |
3.1 (HW: Ex. 3.1-2, 3.1-3, 3.1-4) 3.2 (HW: Ex. 3.2-3, Pr. 3-2 (not part c), 3-3a) |
| MON | Sep 10 | More Common Functions Substitution Method LAST DAY TO DROP A CLASS WITHOUT RECEIVING A "W" |
3.2 4.1 (HW: Ex. 4.1-1, 4.1-2, 4.1-6) |
| TUE | Sep 11 | LAST DAY TO ADD A CLASS | |
| Wed | Sep 12 | Recursion-Tree Method Master Method Quiz 1 |
4.2 (HW: Ex. 4.2-1) 4.3 (HW: Ex. 4.3-1, 4.3-3) 3.1, 3.2, 4.1 |
| Mon | Sep 17 | Heaps Maintaining the Heap Property |
6.1 (HW: Ex. 6.1-6) 6.2 (HW: Ex. 6.2-1) |
| Wed | Sep 19 | Building a Heap Heapsort Quiz 2 |
6.3 (HW: Ex. 6.3-1) 6.4 (HW: Ex. 6.4-1, 6.4-3) 4.1, 4.2, 4.3, 6.1 |
| Mon | Sep 24 | Priority Queues | 6.5 (HW: Ex. 6.5-1, 6.5-2, 6.5-7 (write pseudocode)) |
| Wed | Sep 26 | Quicksort Quiz 3 |
7.1 (HW: Ex. 7.1-1), 7.2 (HW Ex. 7.2-1) 6.2, 6.3, 6.4, 6.5 |
| Mon | Oct 1 | Lower Bounds for Sorting Counting Sort |
8.1 (HW: Ex. 8.1-1) 8.2 (HW: Ex. 8.2-1) |
| Wed | Oct 3 | Radix Sort Bucket Sort |
8.3 (HW: Ex. 8.3-1, 8.3-2) 8.4 (HW: Ex. 8.4-1) |
| MON | Oct 8 | EXAM 1 | On the material covered to date |
| Wed | Oct 10 | Direct-Address Tables Hash Tables |
11.1 (HW: Ex. 11.1-1, 11.1-2 (write pseudocode, as on p. 222)) 11.2 (HW: Ex. 11.2-2) |
| Mon | Oct 15 | Hash Functions Quiz 4 |
11.3 (HW: Ex. 11.3-3 (consider case: string of 2 chars only), 11.3-4) 11.1, 11.2 |
| Wed | Oct 17 | Open Address Tables Binary Search Trees |
11.4 (HW: Ex. 11.4-1, 11.4-2) 12.1 (HW: 12.1-1, 12.1-3) |
| Mon | Oct 22 | Querying a Binary Search Tree Insertion in Binary Search Trees Quiz 5 |
12.2 (HW: Ex. 12.2-1(Hint: draw the tree), 12.2-2,
12.2-3) 12.3 (HW: Ex. 12.3-1, 12.3-3) 11.3, 11.4 |
| Wed | Oct 24 | Deletion in Binary Search Trees Red-Black Trees |
12.3 (HW: extra
problems) 13.1 (HW: Ex. 13.1-1, 13.1-2) |
| Mon | Oct 29 | Rotation Insertion in Red-Black Trees Quiz 6 |
13.2 (HW: Ex. 13.2-1, 13.2-3) 13.3 (HW: Ex. 13.3-2, 13.3-5) 12.1, 12.2, 12.3 |
| Wed | Oct 31 | Deletion in Red-Black Trees | 13.4 (HW: Ex. 13.4-3) |
| MON | Nov 5 | Matrix-Chain Multilication Longest Common Subsequence Quiz 7 LAST DAY TO DROP A CLASS AND RECEIVE A "W" |
15.2 (HW: Ex. 15.2-1, 15.2-2, 15.2-3) 15.4 (HW: Ex. 15.4-1, 15.4-2, 15.4-5) 13.1, 13.2, 13.3 |
| Wed | Nov 7 | Huffman Codes | 16.3 (HW: 16.3-2, extra problem: Find an optimal Huffman code for the data: p:50 q:22 r:6 s:15 t:4 u:10 v:3) |
| MON | Nov 12 | EXAM 2 | On the material covered since Exam 1 |
| Wed | Nov 14 | Representations of Graphs Breadth-First Search |
22.1 (HW: Ex. 22.1-2, 22.1-6) 22.2 (HW: Ex. 22.2-1, 22.2-2) |
| Mon | Nov 19 | Depth-First Search Topological Sort Quiz 8 |
22.3 (HW: Ex. 22.3-2, 22.3-3, 22.3-10) 22.4 (HW: Ex. 22.4-1) 15.2 |
| Wed | Nov 21 | No class (Wed, 11/21, follows a Friday class schedule) |
|
| Mon | Nov 26 | Strongly Connected Components | 22.5 (HW: Ex. 22.5-2, 22.5-5) |
| Wed | Nov 28 | Growing a Minimal Spanning Tree The Algorithms of Kruskal and Prim Quiz 9 |
23.1 (HW: Ex. 23.1-1) 23.2 (HW: extra problems) 15.4, 16.3 |
| Mon | Dec 3 | The Bellman-Ford Algorithm | 24.1 |
| Wed | Dec 5 | Single-Source Shortest Paths in Acyclic
Digraphs Dijkstra's Algorithm Quiz 10 |
24.2 24.3 22.1, 22.2, 22.3 |
| Mon | Dec 10 | Shortest Paths and Matrix Multiplication The Floyd-Warshall Algorithm |
25.1 25.2 |
| Wed | Dec 12 | Johnson's Algorithm for Sparse Graphs Review for the Final Exam Quiz 11 |
25.3 - 22.4, 22.5, 23.1 |
| MON | DEC 17 | FINAL EXAM 3:00-6:00pm Smith 234 |
The final is comprehensive, but will emphasize the material since
Exam 2: 15.2, 15.4, 16.3, 22.1, 22.2, 22.3, 22.4, 22.5, 23.1, 23.2 |