CS 261, Spring 2023: Data Structures

This course is taught by David Eppstein, with Daniel Frishberg as teaching assistant. There will be an online discussion forum on Canvas. Lectures will be held physically, Mondays, Wednesdays, and Fridays, 4:00–4:50pm, in Steinhaus Hall, Room 134. Lectures will only be in-person. Lecture notes will be posted on 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.

Coursework will consist of weekly homeworks (to be turned in through GradeScope), a midterm, and a comprehensive final exam. The course grade will be weighted as 10% from homeworks, 40% from the midterm, and 50% from the final. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks. 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: Daniel Frishberg, Thursdays 2:00 - 3:30, Bren Hall 4013. David Eppstein, Fridays 2:00 - 3:00, 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.

Tentative schedule of topics

Week 1:
The potential method of amortized analysis. Dynamic arrays. Double-ended queues.
 
Lecture notes: Monday, Wednesday, Friday
Homework 1, due Friday, April 14
 
Week 2:
The dictionary problem and hash tables.
Hash chaining, linear probing, and cuckoo hashing.
Hash functions: cryptographic hash functions, k-independent hashing, and tabulation hashing.
 
Lecture notes: Monday, Wednesday, Friday
Homework 2, due Friday, April 21
 
Week 3:
Representing sets by bitmaps and dictionaries.
Bloom filters and cuckoo filters.
Disjointness and the exponential time hypothesis.
 
Lecture notes: Monday, Wednesday, Friday
Homework 3, due Friday, April 28
 
Week 4:
Streaming data structures and frequent item detection.
Boyer–Moore majority voting, MinHash, and the count-min sketch.
Invertible Bloom filters.
 
Lecture notes: Monday, Wednesday, Friday
Homework 4, due Friday, May 5
 
Week 5:
Priority queues. Binary heaps.
k-ary heaps. Fibonacci heaps.
Bucket queues. Priority queues vs integer sorting. Flat trees.
 
Lecture notes: Monday, Wednesday, Friday
No homework because of next week's midterm
 
Week 6:
Midterm Monday, May 8
 
Binary search trees and predecessor queries.
WAVL trees and B-trees.
Optimality and the Garsia–Wachs algorithm.
Splay trees, competitive analysis, and the dynamic optimality conjecture.
 
Lecture notes: Wednesday, Friday
Homework 5, due Friday, May 19
 
Week 7:
Range searching, augmented binary search trees, and Dynamic prefix sums.
Ranking and unranking. Fractional cascading.
 
Lecture notes: Monday, Wednesday, Friday
Homework 6, due Friday, May 26
 
Week 8:
Range minima, Cartesian trees, and lowest common ancestors.
Level ancestors. Maintaining order in a list.
 
Lecture notes: Monday, Wednesday, Friday
Homework 7, due Friday, June 2
 
Week 9:
Memorial day holiday, Monday, May 29
Persistence
 
Lecture notes: Wednesday, Friday
Homework 8, due Friday, June 9
 
Week 10:
Retroactivity.
Tries and suffix trees.
Union-find and dynamic graph algorithms.
 
Lecture notes: Monday, Wednesday, Friday
There will be no additional homework assignment this week.
 
Exam week:
Final exam, Thursday June 15, 4:00 – 6:00 in the same room as the lectures. If you have another exam in this time slot, please contact me before the exam to arrange a later make-up exam.

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.