| Week | Day | Topics | Readings | Homework |
|---|---|---|---|---|
| Nov.28 - Dec.2 | 1 | Course introduction
Definition of Datastructure Trees Binary trees | ||
| 2 | Tree traversal
Iterators Tree Iterators Inner Classes | 18.1 - 18.4, 6.2, 6.3 | BST, Part 1 | |
| 3 | Binary search trees (BST)
The Comparable interface Inserting elements into a BST | 15.2, 19.0, 19.1. | BST, Part 2 | |
| Dec.5 - Dec.9 | 4 | Review of analysis of algorithms
Best, worst, and average case analysis Removing nodes from a tree | 19.2, 19.3 | BC: BST, Part 3 |
| 5 | Big-Oh
Bounds Polymorphism | 5.0-5.4 | BST Removal | |
| 6 | Analysis of Algorithms
AVL trees Inserting into an AVL Tree | 19.4 | BC: BST Polymorphism | |
| Dec.12 - Dec.16 | 7 | removing from an AVL Tree
Initial analysis of AVL trees Induction | BC: Analysis Homework | |
| 8 | Analysis of AVL trees
Ammortized analysis | 22.1.1, 2.4.2. | BC: Induction HW | |
| 9 | ADTs
Priority Queues Binary Heaps | 6.9, 21.0 - 21.3 | BC: AVL Trees | |
| Dec. 19 - 20, Jan. 5 | 10 | Debugging strategies
Heapsort | 21.5 | |
| 11 | Hashtables
Maps and HashMaps Sets and HashSets Functors | 20, 6.7.2, 6.8 | ||
| 12 | Mergesort
B Trees | 8.5, 19.8 | BC: Priority queue | |
| Jan.9 - Jan.13 | 13 | Red Black Trees
Bottom-up and Top Down Insertion | 19.5.0 - 19.5.2 | |
| 14 | Skiplists
Quicksort | Skiplists, 8.6 | ||
| 15 | No class, to compensate for evening exam | |||
| Jan.16 - Jan.20 | 16 | Red Black Tree Top Down Removal | 19.5.4 | BC: TDRBTrees Insertion |
| 17 | Detailed analysis of the performance of Red Black and AVL Trees
Graphs Representation of graphs | 14.1 | ||
| 18 | Proof of log height of RB trees
Graph search: breadth-first, depth-first Analysis of graph search | BC: Extra Credit: Skiplists | ||
| Jan.23 - Jan.27 | ||||
| 19 | A* and sliding 8 puzzle
Analysis of A* Average case analysis of Quicksort | A* | BC: TDRBTree removal | |
| 20 | More graph algorithms
Ethical codes | 14.2, 14.3 | ||
| 21 | Lower bound on sorting
Relationship among classes implementing the Collections interface Team project kick-off | 8.8 | 9 am: Team preference form
BC: Analysis Homework | |
| Jan.30 - Feb.3 | 22 | AA Trees | 19.6 | BC: Professional Code of Ethics |
| 23 | Evaluation of AA trees
Review for exam 2 | BC: Homework on AA trees | ||
| 24 | No class, to compensate for evening exam | |||
| Feb.6 - Feb.10 | 25 | Splay trees | 22.0-22.3 | BC: Design documents |
| 26 | Splay trees cont'd | 22.5 | BC: Field Guide to Data structures | |
| 27 | Linear sorting: Bucket and Radix sort
Constant time sorting. | 8.4 | Friday 5pm: Extra credit: AA Tree Project
BC: Project update | |
| Feb.13 - Feb.17 | 28 | File compression | 12.1 | BC: Extra credit: Splay Trees project |
| 29 | Randomization | 9, 6.8 | ||
| 30 | Project demos
Review for final exam Course evals | Final Info | Friday 5pm, w/ 48h grace period: Team
project documents
Friday 5pm: Extra credit: Top-down splay tree applet |