This course will be online-only. I will be providing online lecture material in the form of videos, together with the slides (updated to fix minor mistakes from the versions of the slides from which the videos were made). The material is arranged into weekly sets of topics. Coursework will consist of weekly homeworks (including homework from the last week of lectures, due in finals week), turned in online through Gradescope. Collaboration on homeworks, or asking people outside the class for assistance with the homeworks, is not permitted. Each homework set will have one of the assigned problems graded, and will be scored 50% for that problem and 50% for whether it included an answer for each other problem.
The course will be led by David Eppstein (firstname.lastname@example.org), with Hadi Khodabande (email@example.com) as teaching assistant. For general questions and discussions on course material, we will set up a Piazza forum, and we will also have regular online office hours (TBA). For questions about your individual performance and grading, requests to set up a private Zoom meeting, or other material of a confidential nature, please contact us by our UCI email addresses.
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.
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.
Readings: The potential method of amortized analysis. Dynamic arrays. Double-ended queues.
Homework 1 and HW1 solution template, due Monday, April 5
Readings: The dictionary problem and hash tables.
Hash chaining, linear probing, and cuckoo hashing.
Hash functions: cryptographic hash functions, k-independent hashing, and tabulation hashing.
Homework 2 and HW2 solution template, due Monday, April 12
Readings: Representing sets by bitmaps and dictionaries.
Bloom filters and cuckoo filters.
Disjointness and the exponential time hypothesis.
Homework 3 and HW3 solution template, due Monday, April 19
data structures and frequent item detection.
Boyer–Moore majority voting, MinHash, and the count-min sketch.
Invertible Bloom filters.
Homework 4 and HW4 solution template, due Monday, April 26
k-ary heaps. Fibonacci heaps.
Integer sorting. Flat trees.
Homework 5 and HW5 solution template, due Monday, May 3
search trees and predecessor
WAVL trees and B-trees.
Optimality and the Garsia–Wachs algorithm.
Splay trees, competitive analysis, and the dynamic optimality conjecture.
Homework 6 and HW6 solution template, due Monday, May 10
trees, and Dynamic prefix sums.
Ranking and unranking. Fractional cascading.
Homework 7 and HW7 solution template, due Monday, May 17
trees, and lowest
Level ancestors. Maintaining order in a list.
Homework 8 and HW8 solution template, due Monday, May 24
Readings: Persistence, retroactivity
Homework 9 and HW9 solution template, due Monday, May 31
Readings: Tries and suffix trees.
Union-find and dynamic graph algorithms.
Homework 10 and HW10 solution template, due Monday, June 7
See also syllabi from Winter 2018, Spring 2013 and Fall 2011 including sample homeworks and exams with their solutions, and Erik Demaine's open courseware class on similar material.
David Eppstein, ICS, UC Irvine.