| Week | Dates | Day | Topics | Readings | Homework |
|---|---|---|---|---|---|
| 1 | Mar. 10-14 | 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
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 | Mar. 17-21 | 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 | Mar. 24-28 | 7 | Removal in iterators
Analysis of algorithms Bounds Big-Oh | 5.4-5.7, 6.4.3 | Not collected: BST - part 3 |
| 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 | BC: Runtimes homework | ||
| 4 | Mar. 31 - Apr. 4 | 10 | Review for exam 1 | 7.2 | BC: Big-Oh analysis homework |
| 11 | Removing from an AVL Tree
Initial analysis of AVL trees | ||||
| Evening exam 1 | |||||
| 12 | No class, to compensate for evening exam. | ||||
| 5 | Apr. 7-11 | 13 | Induction
Analysis of AVL trees | ||
| 14 | Ammortized analysis
ADTs | 23:59: AVL Trees | |||
| 15 | Binary Heaps
Priority Queues Heapsort | 2.4.2, 2.4.3, 6.9, 21.5, 21.0 - 21.3, 22.1.1 | BC: Induction proofs | ||
| 6 | Apr. 21-25 | 16 | AA trees
Inserting into an AA tree Initial analysis of AA trees | 19.6 | 23:59: Amortization HW |
| 17 | Removal from AA tree
Continue analysis of AA trees | 23:59: PriorityQueue | |||
| 18 | Hashtables
Maps and HashMaps Sets and HashSets Adding a hashtable to BSTs Implementing find() through hashtable Ethical codes | 6.7, 6.8, 8.0, 8.1, 20, 8.5 | |||
| 7 | Apr. 28 - May 2 | 19 | Mergesort
Review for exam 2 | 8.5 | |
| 20 | Skiplists
Analysis of Skiplists | Skiplists
14.1 | BC: Professional codes of conduct | ||
| Evening exam 2 | |||||
| 21 | No class, to compensate for evening exam. | ||||
| 8 | May 5-9 | 22 | Graphs
Representation of graphs Graph search: Dijkstra's algorithm | 14.2-14.3 | 23:59: AA Trees |
| 23 | Graph algorithms | ||||
| 24 | Tree shapes
Complexity proofs for graphs Prompt engineering | ||||
| 9 | May 12-16 | 25 | Quicksort
Evaluation of sorting algorithms Recurrence relationships | 8.6 | 23:59: Extra Credit: Skiplists |
| 26 | Average case of Quicksort
Master Theorem File Compression | ||||
| 27 | Lower bound on comparison based sorting
Linear sorting Constant time sorting | 8.8 | BC: Graph analysis homework
BC: Recurrence homework | ||
| 10 | May 19-23 | 28 | B-trees
Course evals | ||
| 29 | Debugging | ||||
| 30 | Experiences with ChatGPT exercise
Review for final exam | BC: Analysis 3 homework 5pm: MST pair programming assignment |