Here is this semester's tentative schedule; we will update it as the semester
progresses.
Please note that lecture notes are provided as a supplement, and are NOT a
substitute for attending lecture. In particular, these are not guaranteed, so
expect technical difficulties to prevent them from being posted at least a few
times in the semester; they also will not contain exercises whose solutions are
worked out on the board in class. Please plan accordingly to either take notes or get them
from a friend if necessary.
| Date |
Topic |
Reading |
Lecture Notes |
Supplemental Code |
| Monday, Jan. 13 |
Syllabus
Union-Find intro |
|
Lecture Notes |
|
| Wednesday, Jan. 15 |
Union-Find analysis |
Wikipedia article
Reading with O(log*n) amortized analysis
Extra reading
|
Lecture Notes |
Implementations in C++, Java, Python, and C#
|
| Wednesday, Jan. 22 |
Union-Find analysis |
Writeup with O(log*n) amortized analysis
|
Lecture Notes |
Implementations in C++, Java, Python, and C#
|
| Friday, Jan. 24 |
Union-Find: final notes |
Writeup with O(log*n) amortized analysis
|
Lecture Notes |
|
| Monday, Jan. 27 |
Skip lists
binary search trees |
Notes by Jeff Erickson (see 3.2)
Skiplist intro/anlysis in java by Pat Morin
|
Lecture Notes |
|
| Wednesday, Jan. 29 |
Scapegoat Trees
Fractional cascading (if time) |
Intro and analysis
Wikipedia intro
Chapter in Open Data Structures
Fractional cascading
|
Lecture Notes |
|
| Friday, Jan. 31 |
Sub: Strassen's algorithm |
|
coming soon |
|
| Friday, Feb. 8 |
Splay Trees |
References notes
Alternate reference
|
Lecture Notes |
|
| Monday, Feb. 10 |
Splay Trees: analysis |
References notes
|
Lecture Notes |
|
| Wednesday, Feb. 12 |
Splay Trees: analysis (cont) |
References notes
|
Lecture Notes |
|
| Friday, Feb. 14 |
Sub: Strassen's algorithm (cont) |
|
coming soon |
|
| Monday, Feb. 17 |
External Memory: B-trees |
References notes
Additional Notes
Textbook on this topic
|
Lecture Notes |
|
| Wednesday, Feb. 19 |
B-trees (cont) |
References notes
|
Lecture Notes |
|
| Friday, Feb. 21 |
Bit vectors |
|
Lecture Notes |
|
| Monday, Feb. 24 |
Tiered bitvectors |
Bitvectors and van Emde Boas trees
Solving recurrences (or use your favorite discrete math book!)
|
Lecture Notes |
|
| Wednesday, Feb. 26 |
Van Emde Boas Trees |
Bitvectors and van Emde Boas trees
|
Lecture Notes |
|
| Monday, March 2 |
Binomial Heaps |
Textbook (CLRS)
Jeff Erickson's overview
Extra notes reference
|
Lecture Notes |
|
| Wednesday, March 4 |
Binomial Heaps (cont.) |
Extra notes reference
|
Lecture Notes |
|
| Friday, March 6 |
Fibonacci Heaps |
Jeff Erickson's overview
Extra notes reference
|
Lecture Notes |
|