ANNOUNCEMENT MAY 18: Because of the inability of the campus to supply working internet to our classroom, all remaining lectures will be online (through Zoom) until further notice. See the Canvas Zoom tab for the link. The final exam will still be in-person, in the classroom, at the scheduled time (we will not need internet access for it). See links below for replacement content for the May 18 lecture, which was disrupted by the internet outage.

This course is taught by David Eppstein, with Hadi Khodabande (khodabah@uci.edu) and Nitya Raju (nraju1@uci.edu) as teaching assistants (office hours TBA). Office hours:

- David Eppstein: Wednesdays 2:00-2:50 in Bren Hall 4082, jointly with CS 164 and CS 266
- Hadi Khodabande: Thursdays 11:00-11:50 in ICS-1, room 415
- Nitya Raju: Tuesdays 11:00-11:50, in Bren Hall 4011

There is an online discussion forum on Canvas. Lectures will be held physically, Mondays, Wednesdays, and Fridays, 4:00–4:50pm, in the Social Science Lab, SSL 140. Lectures will also be simultaneously streamed on Zoom, and recorded for later viewing through the Zoom tab of Canvas. 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.

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.

**Week 1**:- The potential method of amortized analysis. Dynamic arrays. Double-ended queues.
- Lecture notes: Monday, Wednesday, Friday.
- Homework 1, due Friday, April 8.
**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 15.
**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 22.
**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, April 29.
**Week 5**:- Priority
queues. Binary
heaps.

k-ary heaps. Fibonacci heaps.

Integer sorting. Flat trees. - Lecture notes: Monday, Wednesday, Friday.
- No new homework assignment this week because of the midterm
**Week 6**:- Midterm Monday, May 2
- 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 13.
**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 20.
**Week 8**:- Range
minima, Cartesian
trees, and lowest
common ancestors.

Level ancestors. Maintaining order in a list. - Lecture notes: Monday, Wednesday, Friday.
- Recorded videos from 2020 covering the same material as Wednesday's lecture:
- Applications of common ancestors (8:15)
- From ancestors to range minima (5:56)
- Cartesian trees (11:47)
- LCA and range minimum solutions (12:42)

- Homework 7, due Friday, May 27.
**Week 9**:- Persistence, retroactivity
- Lecture notes: Monday, Wednesday, Friday.
- Homework 8, due Friday, June 3.
**Week 10**:- Memorial day holiday, Monday, May 30
- Tries and suffix trees.

Union-find and dynamic graph algorithms. - Lecture notes: Wednesday, Friday.
- Sample homework on week 10 material

(From last year. This year, we do not have a homework on this material.) **Exam week**:- Final exam, Thursday June 9, 10:30am–12:30pm (same room)

See also syllabi from Winter 2018, Spring 2013 and Fall 2011 including sample homeworks and exams with their solutions, final exams from Fall 2003, Fall 2004, and Winter 2006, and Erik Demaine's open courseware class on similar material.