Lecture Topics Calendar
| No. | Date | Topic Reading Assignment |
|---|---|---|
| 1 | Th Sept 25 | Syllabus, Trees Chap.1 (skim to review as needed), Section 4.1 |
| 2 | Tu Sept 30 | Tries, Huffman codes Section 5.4 |
| 3 | Th Oct 2 | Java I/O, bit manipulation, Assignment #1 Java API docs (for I/O) |
| 4 | Tu Oct 7 | Tree traversals, Heap/Priority Queue Section 4.1-4.3 |
| 5 | Th Oct 9 | Storing Heaps in an Array, Heapsort Algorithm, Binary Search Trees Section 9.1 Priority Queue (up to not including "Leftist Trees"), Section 11.3 Heapsort, Section 6.4 BST |
| 6 | Tu Oct 14 | Quick Review of Big-O Order Notation, BST Average Case Analysis, AVL Trees and Rotations Chapter 1 (for Order Notation review), Section 6.4 (for BSTs), Chapter 7 (for AVL) |
| 7 | Th Oct 16 | BST Average Case Analysis, Treaps, Assignment #2 Section 6.4, Aragon and Seidel paper (PDF) |
| 8 | Tu Oct 21 | Analysis of Treaps, Assignment #2: Java Iterators, Doing Traversal Without Recursion, Java Comparator/Comparable Section 6.4, Aragon and Seidel paper (PDF), Java documentation |
| 9 | Th Oct 23 | Red-Black Trees, Skip Lists Section 7.2 (starting with page 233 Red-Black Tree), Section 6.3 (starting with page 187 Skip List) |
| 10 | Tu Oct 28 | Graphs, Assignment #3 Chapter 12 (Graphs) |
| Th Oct 30 | MIDTERM | |
| 11 | Tu Nov 3 | More Graphs - Shortest Path(s) Chapter 12 (Graphs) |
| 12 | Th Nov 5 | More Graphs - Minimum Spanning Tree Chapter 12 (Graphs) |
| Tu Nov 11 | VETERAN'S DAY HOLIDAY | |
| 13 | Th Nov 13 | NP-Complete Graph Problems, Union-Find Chapter 2 (very last section on NP Completeness), Chapter 12 (Graphs), Section 9.2 (Union-Find) |
| 14 | Tu Nov 18 | Hashing, Amortized Analysis Chapter 8 (Hashing) |
| 15 | Th Nov 20 | More Hashing Chapter 8 (Hashing) |
| 16 | Tu Nov 25 | Time costs in memory hierarchy NOTE: As indicated on the lecture slides, the reading for this lecture is not in the book. The book does contain information about B-trees and 2-3-trees, but uses a slightly different method of key bookkeeping than described in class. It is recommended to only study the lecture slides in order to avoid confusion. |
| Th Nov 25 | THANKSGIVING HOLIDAY | |
| 17 | Tu Dec 2 | Self-organizing lists, Splay tree, k-d Tree Section 7.3 (Splay Tree), Section 9.3 (starting with page 321 k-d Tree) |
| 18 | Th Dec 4 | Review for final exam |
| Wed Dec 10 | FINAL EXAM |