The following schedule is very tentative. Topics will take more/less time, and some topics will only be covered if time permits. I will adjust the schedule as we go along and post the relevant reading from the book.
| Date | Topic | Relevant Reading |
|---|---|---|
| 1/17 | course overview, asymptotic notation, short math review | Chapter 1: 1.2.2,1.2.3 Chapter 2: 2.1 |
| 1/22 | recursion and runtime analysis: binary search, gcd, Towers of Hanoi | Chapter 2: 2.4.4 |
| 1/24 | bubble sort, insertion sort, lowerbound on simple sorting, mergesort overview | Chapter 7: 7.2,7.3 |
| 1/29 | comparing objects in java, the merge routine, quicksort | Chapter 7: 7.6, 7.7 |
| 1/31 | quicksort runtime analysis, comparing mergesort and quicksort, hw1 due | Chapter 7: 7.7, 7.9 |
| 2/5 | go over hw, bucket sort | Chapter 7: 7.9 |
| 2/7 | abstractions, list ADT, array list implementation | Chapter 3: 3.1,3.2,3.4 |
| 2/12 | link list implementation | Chapter 3: 3.5 |
| 2/14 | iterator for link list, stack ADT and (generic) array implementation, stack applications, hw2 due | Chapter 3: 3.5, 3.6 |
| 2/21 | queue ADT and (generic) list implementation | Chapter 3: 3.7 |
| 2/26 | mathematical induction, trees: introduction, terminology, properties, traversals, binary search trees | Chapter 4: 4.1, 4.2 |
| 2/28 | BST implementation, hw3 due | Chapter 4: 4.3 |
| 3/4 | go over VList and CStack (from the homework), remove method of BST implementation | Chapter 4: 4.3 |
| 3/6 | MIDTERM; look over practice midterm to prepare | |
| 3/18 | go over midterm, balanced trees: motivation, AVL trees | Chapter 4: 4.4 |
| 3/20 | heaps | Chapter 6: 6.1-6.3 |
| 3/25 | leftist heaps, heapsort | Chapter 6: 6.6, Chapter 7: 7.5 |
| 3/27 | hashing: overview, collision resolution strategies, hw4 due | Chapter 5: 5.1 - 5.3 |
| 4/1 | go over homework, more collision resolution, rehashing, intro to graphs: motivation for topological sort | Chapter 5: 5.4 -5.6 |
| 4/3 | graph terminology, modeling problems as graphs, different graph representations | Chapter 9: 9.1 |
| 4/8 | topological sort (naive and efficient implementation), depth-first search (DFS), dfs-based topological sort | Chapter 9: 9.2, 9.6.1 |
| 4/10 | using Java Collections to represent a graph, dfs application: finding strongly connected components (SCCs) | Chapter 9: 6.6.5 |
| 4/15 | correctness of finding SCCs (and dfs-based topological sort), breadth first search, hw5 due | Chapter 9: 9.3.1 |
| 4/17 | minimum spanning trees: greedy MST algorithms (Kruskall and Prim) | Chapter 9: 9.5 |
| 4/22 | efficient implementation of MST algorithms | Chapter 9: 9.5 |
| 4/24 | weighted shortest paths: Dijkstra | Chapter 9: 9.3.2 |
| 4/29 | 2-approximation for Traveling Salesman Problem (TSP), course evaluations | |
| 5/1 | final review, hw6 due | |
| 5/6 | FINAL (9-11 a.m., same room), practice final |