This course is taught by David Eppstein. There will be an online discussion forum on Ed Discussion, accessed through Canvas. Lectures will be held physically, Tuesdays and Thursdays, 11:00–12:20, in the Anteater Learning Pavilion, room 2200. Lecture notes will be linked from this page prior to each lecture. Except for students with special arrangements through the UCI Disability Services Center, all exams will be in person only.
I will assign weekly practice problem sets at the start of each week, covering that week's material, and I strongly recommend that all students do these, but they will not be collected and graded. Instead, solutions will be posted at the end of the week to the course web site, and you can expect to see similar problems (or even in some cases the same problems) on the exams. There will be three exams (two midterms and a non-comprehensive final) each covering the material from roughly one third of the class, each equally weighted in the overall course grade. Exams will be closed book, closed notes, and closed friends.
There is no required textbook; however, much of the course material will be drawn from the Wikipedia articles collected together in the Wikipedia “book” Fundamental Data Structures. Additionally, suggested internet readings for the topics covered here will be linked from the schedule of topics.
Office hours: Tuesdays and Fridays 2:30 – 3:30, Bren Hall 4082.
This course may be used as part of the comprehensive exam in the computer science masters program. To pass the comprehensive exam, students must earn at least an overall grade of A- in the course. If you are enrolled in the course, you will be automatically considered eligible for the comprehensive exam.
Following US ADA regulations and UCI policy, I am working to make all online course content accessible. However, external sites linked from here might not follow the same accessibility guidelines. If you notice any issues with the accessibility of course materials, or need assistance with their accessibility, please contact me.
Tentative schedule of topics
- Week 1 (March 31 – April 2):
- The potential method of amortized analysis. Dynamic arrays. Double-ended queues.
- Lecture notes: Course overview
- Lecture notes: Amortized analysis and dynamic arrays
- Practice problem set 1
- Week 2 (April 7–9):
- The dictionary problem and hash tables.
- Hash functions: cryptographic hash functions, k-independent hashing, and tabulation hashing.
- Hash chaining, linear probing, and cuckoo hashing.
- Week 3 (April 14–16):
- Representing sets by bitmaps and dictionaries.
Bloom filters and cuckoo filters.
Disjointness and the exponential time hypothesis. - Week 4 (April 21–23):
- Midterm Tuesday, April 21
- Tries and suffix trees.
- Week 5 (April 28–30):
- Priority queues. Binary heaps. k-ary heaps. Fibonacci heaps.
- Integer priority queues: Bucket queues. Priority queues vs integer sorting. Flat trees.
- Week 6 (May 5–7):
- Binary
search trees and successor
queries.
B-trees and external memory data structures.- Splay trees, competitive analysis, and the dynamic optimality conjecture.
- Week 7 (May 12–14):
- Range searching, augmented binary search trees, and Dynamic prefix sums.
Ranking and unranking.- Midterm Thursday, May 14
- Range searching, augmented binary search trees, and Dynamic prefix sums.
- Week 8 (May 19–21):
- Range
minima, Cartesian
trees, and lowest
common ancestors.
Level ancestors. Maintaining order in a list. - Week 9 (May 26–28):
- Streaming
data structures, reservoir sampling, and MinHash.
- Frequent item detection, the Boyer–Moore majority voting, the count-min sketch, and Invertible Bloom filters.
- Week 10 (June 2–4):
- Persistence and retroactivity.
- Union-find and dynamic graph algorithms.
- Exam week:
- Final exam, Tuesday June 9, 10:30 – 12:30PM in the same room as the lectures.
See also Erik Demaine's open courseware class on similar material.