| Week | Dates | Day | Topics | Readings | Homework |
|---|---|---|---|---|---|
| 1 | Nov. 27- Dec. 1 | 1 | Course introduction
Definition of Datastructure Doubly linked lists Information hiding Inner classes | 6.5.2-6.5.4 17.1, 17.3 | |
| 2 | Generics
Functors Iterators | 4.7.1, 4.8.0, 4.8.1,
4.8.4, 6.2.0, 6.2.1 6.3.2, 6.4.0, 15.2 | Not collected: Linked lists - part 1 | ||
| 3 | Remove in iterator
Fail-fast iterators Stacks Queues | 6.6, 16.2 | Not collected: Linked lists - part 2 | ||
| 2 | Dec. 4-8 | 4 | Trees
Binary trees Binary search trees (BST) The Comparable interface Inserting elements into a BST | 4.7.2 - 4.7.4, 6.4.1
18.0-18.3, 19.0, 19.1 | 23:59: LinkedList |
| 5 | Review of analysis of algorithms
Tree traversal Tree Iterators | 5.1, 5.2 18.4 | Not collected: BST - part 1 | ||
| 6 | Parameter passing by value
Removing nodes from a tree Thread safety | 2.2.5 | Not collected: BST - part 2 | ||
| 3 | Dec. 11-15 | 7 | Removal in iterators
Analysis of algorithms Bounds Big-Oh | 5.4-5.7, 6.4.3 | Not collected: BST - part 3
BC: Runtimes homework |
| 8 | Comprehensive Analysis of BinarySearchTrees | 5.8, 19.2, 19.3 | 23:59: BST - part 4 | ||
| 9 | AVL trees
Inserting into an AVL Tree | 19.4 | |||
| 4 | Dec. 18-22 | 10 | Removing from an AVL Tree
Induction | 7.2 | BC: Big-Oh analysis homework |
| 11 | Analysis of AVL trees
Review for exam 1 | ||||
| Evening exam 1 | |||||
| 12 | No class, to compensate for evening exam. | ||||
| 5 | Jan. 8-12 | 13 | Ammortized analysis
ADTs Binary Heaps | 2.4.2, 2.4.3,
21.0 - 21.3, 22.1.1 | BC: Induction proofs |
| 14 | Priority Queues
Heapsort | 6.9, 21.5 | 23:59: AVL Trees | ||
| 15 | Hashtables
Maps and HashMaps Sets and HashSets | 6.7, 6.8, 8.0, 8.1, 20 | BC: Amortization HW | ||
| 6 | Jan. 15-19 | 16 | Red Black Trees
Bottom-up and Top Down Insertion | 19.5.0 - 19.5.2 | |
| 17 | Analysis of Red-Black Trees
Proof of log height of RB trees | 23:59: PriorityQueue | |||
| 18 | Mergesort
Ethical codes | 8.5 | |||
| 7 | Jan. 22-26 | 19 | Red Black Tree Top Down Removal and analysis | 19.5.4 | 23:59: TDRBTree Insertion |
| 20 | Skiplists
Review for exam 2 | Skiplists
14.1 | BC: Professional codes of conduct | ||
| 21 | Exam 2 | ||||
| 8 | Jan. 29- Feb. 2 | 22 | Lower bound on comparison based sorting
Linear sorting Constant time sorting | 8.8 | |
| 23 | Graphs
Representation of graphs Graph search: Dijkstra's algorithm | 14.2-14.3 | 23:59: TDRBTree Removal | ||
| 24 | AA Trees | 19.6 | |||
| 9 | Feb. 5-9 | 25 | Graph algorithms | 23:59: Extra Credit: Skiplists | |
| 26 | Quicksort, Recurrence Relations | 8.6 | |||
| 27 | Average case of Quicksort
Master Theorem File Compression | BC: Analysis HW | |||
| 10 | Feb. 12-16 | 28 | B-trees | BC: Recurrence homework
23:59: Extra Credit: AA Trees | |
| 29 | Comparison of Tree data structures
Relationship among classes implementing the Collections interface Course evals | Analysis 2 homework, and Analysis 3 homework | |||
| 30 | ChatGPT coding exercise
Review for final exam | 5pm: MST pair programming assignment |