Please note that some topics may take more/less time than planned and may not be covered in exactly this order.
| Week | Date | Topic | Reading |
|---|---|---|---|
| Week1 | 7/2 | Introduction, analyzing running times, O, Omega, Theta notation, short math review | Chapter 1: 1.2.2,1.2.3; Chapter 2: 2.1 |
| 7/3 | Recursion and runtime analysis: binary search, gcd, Towers of Hanoi | Chapter 2: 2.4.4 | |
| 7/5 | Sorting: bubble sort, insertion sort | Chapter 7: 7.2 | |
| 7/6 | Sorting: lowerbound on simple sorting, mergesort, comparison with quicksort | Chapter 7: 7.3, 7.6 | |
| Week2 | 7/9 | Sorting: quicksort, runtime analysis, special case: bucket sort | Chapter 7: 7.7, 7.9 |
| 7/10 | List ADT, array and linked list implementation, hw1 due | Chapter 3: 3.1,3.2,3.4,3.5 | |
| 7/11 | Generic classes and Iterator interface, Stack ADT, implementation overview | Chapter 3: 3.4,3.5,3.6 | |
| 7/12 | Stack applications: balancing symbols, evaluating postfix expressions. Queue ADT, array and link list implementation | Chapter 3: 3.6,3.7 | |
| Week3 | 7/16 | Trees: introduction, terminology, tree properties, traversals, Binary Search Trees | Chapter 4: 4.1,4.3 |
| 7/17 | BST implementation. Balanced trees: AVL trees, hw2 due | Chapter 4: 4.3, 4.4 | |
| 7/18 | Wrap up trees, midterm review | Chapter 4: 4.3 | |
| 7/19 | MIDTERM | ||
| Week4 | 7/23 | Heaps | Chapter 6: 6.1-6.3 |
| 7/24 | Leftist heaps, heapsort, hw3 due | Chapter 6: 6.6; Chapter 7: 7.5 | |
| 7/25 | Hashing: introduction, examples, collision resolution with chaining | Chapter 5: 5.1-5.3 | |
| 7/26 | Hashing: other collision resolution strategies, rehashing | Chapter 5: 5.4,5.5 | |
| Week5 | 7/30 | Introduction to graphs, terminology, different graph representations | Chapter 9: 9.1 |
| 7/31 | Topological sort, Depth First Search, hw4 due | Chapter 9: 9.2, 9.6.1 | |
| 8/1 | Unweighted shortest paths: Breadth First Search | Chapter 9: 9.3.1 | |
| 8/2 | Minimum Spanning Trees: Prim's and Kruskal's algorithms | Chapter 9: 9.5 | |
| Week6 | 8/6 | Weighted shortest paths: Dijkstra's algorithm | Chapter 9: 9.3.2 |
| 8/7 | Dijkstra runtime analysis, final review, hw5 due | Chapter 9: 9.3.2 | |
| 8/8 | Final review, course evaluations | ||
| 8/9 | FINAL |