CS 261, Spring 2024: Data Structures

UPDATE FOR THURSDAY, MAY 16: The lecture will be online. Go to the Zoom tab of Canvas for connection details.

This course is taught by David Eppstein, with Shion Fukuzawa as teaching assistant. There will be an online discussion forum on Ed Discussion, accessed through Canvas. Lectures will be held physically, Tuesdays and Thursdays, 2:00–3:20pm, in SSL 248. 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 "Resources" in Ed Discussion, and you can expect to see similar problems (or even in some cases the same problems) on the exams. There will be two exams (a midterm and a non-comprehensive final) each covering the material from roughly half of the class, each equally weighted in the overall course grade. Exams will be closed book, closed notes, and closed friends. Because of the late timing of the exam, regrade requests will not be accepted on the final exam.

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: Shion Fukuzawa, Mondays 1:00 - 1:50 in ICS 458A and Thursdays 1:00 - 1:50 in ICS 458B; David Eppstein, Tuesdays 4:00 - 4:50 in Bren 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.

Tentative schedule of topics

Week 1:
The potential method of amortized analysis. Dynamic arrays. Double-ended queues.
 
Practice problem set 1
Lecture notes: Tuesday, Thursday
 
Week 2:
The dictionary problem and hash tables.
Hash functions: cryptographic hash functions, k-independent hashing, and tabulation hashing.
Hash chaining, linear probing, and cuckoo hashing.
 
Practice problem set 2
Lecture notes: Tuesday, Thursday
 
Week 3:
Representing sets by bitmaps and dictionaries.
Bloom filters and cuckoo filters.
Disjointness and the exponential time hypothesis.
 
Practice problem set 3
Lecture notes: Tuesday, Thursday
 
Week 4:
Streaming data structures and frequent item detection.
Boyer–Moore majority voting, MinHash, and the count-min sketch.
Invertible Bloom filters.
 
Practice problem set 4
Lecture notes: Tuesday, Thursday
 
Week 5:
Priority queues. Binary heaps. k-ary heaps. Fibonacci heaps.
Bucket queues. Priority queues vs integer sorting. Flat trees.
 
Practice problem set 5
Lecture notes: Tuesday, Thursday
 
Week 6:
Midterm Tuesday, May 7.
Binary search trees and successor queries.
Splay trees, competitive analysis, and the dynamic optimality conjecture.
 
No problem set this week
Lecture notes: Thursday
 
Week 7:
Range searching, augmented binary search trees, and Dynamic prefix sums.
Ranking and unranking. Fractional cascading.
 
Practice problem set 6
Lecture notes: Tuesday, Thursday
 
Week 8:
Range minima, Cartesian trees, and lowest common ancestors.
Level ancestors. Maintaining order in a list.
 
Practice problem set 7
Lecture notes: Tuesday, Thursday
 
Week 9:
Memorial day holiday, Monday, May 27
Persistence
Retroactivity.
 
Practice problem set 8
Lecture notes: Tuesday, Thursday
 
Week 10:
Tries and suffix trees.
Union-find and dynamic graph algorithms.
 
Practice problem set 9
Lecture notes: Tuesday, Thursday
 
Exam week:
Final exam, Thursday June 13, 1:30PM – 3:30PM in the same room as the lectures.

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.