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 (eppstein@uci.edu), with Hadi Khodabande (khodabah@uci.edu) 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.

**Week 1**:Readings: The potential method of amortized analysis. Dynamic arrays. Double-ended queues.

Lectures:

- 1a: Introduction (17:24)
- 1b: Data structures (10:10)
- 1c: Amortization (30:14)
- 1d: Dynamic arrays (19:44)
- 1e: Stacks, deques, and queues (7:20)
- 1f: Summary (2:29)

Homework 1 and HW1 solution template, due Monday, April 5

**Week 2**: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.Lectures:

- 2a: Dictionaries (11:04)
- 2b: Hashing (12:36)
- 2c: Probability (14:27)
- 2d: Collisions and hash chaining (12:07)
- 2e: Linear probing (16:01)
- 2f: Cuckoo hashing (25:18)
- 2g: k-independence and tabulation hashing (15:08)
- 2h: Summary (2:32)

Homework 2 and HW2 solution template, due Monday, April 12

**Week 3**:Readings: Representing sets by bitmaps and dictionaries.

Bloom filters and cuckoo filters.

Disjointness and the exponential time hypothesis.Lectures:

- 3a: Sets (6:17)
- 3b: Bitmaps (12:02)
- 3c: Filters (13:26)
- 3d: Bloom filters (11:51)
- 3e: Cuckoo filters (14:24)
- 3f: Disjointness (10:07)
- 3g: Summary (2:46)

Homework 3 and HW3 solution template, due Monday, April 19

**Week 4**:Readings: Streaming data structures and frequent item detection.

Boyer–Moore majority voting, MinHash, and the count-min sketch.

Invertible Bloom filters.Lectures:

- 4a: Streaming and sketching (9:03)
- 4b: Medians and reservoir sampling (8:41)
- 4c: Majority and heavy hitters (19:29)
- 4d: MinHash (13:55)
- 4e: Count-min sketch (15:32)
- 4f: Set reconciliation (17:25)
- 4g: Summary (3:43)

Homework 4 and HW4 solution template, due Monday, April 26

**Week 5**:Readings: Priority queues. Binary heaps.

k-ary heaps. Fibonacci heaps.

Integer sorting. Flat trees.Lectures:

- 5a: Priority queues (11:54)
- 5b: Binary heaps (23:35)
- 5c:
*k*-ary heaps (10:48) - 5d: Fibonacci heaps (33:05)
- 5e: Integer priority queues (10:28)
- 5f: Flat trees (13:46)
- 5g: Summary (4:15)

Homework 5 and HW5 solution template, due Monday, May 3

**Week 6**:Readings: 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.Lectures:

- 6a: Binary search (16:18)
- 6b: Balanced search trees (24:20)
- 6c: B-trees (14:06)
- 6d: Optimal search trees (22:36)
- 6e: Splay trees (23:52)
- 6f: Summary (4:34)

Homework 6 and HW6 solution template, due Monday, May 10

**Week 7**:Readings:Range searching, augmented binary search trees, and Dynamic prefix sums.

Ranking and unranking. Fractional cascading.Lectures:

- 7a: Ranking and unranking (11:44)
- 7b: Range search (18:25)
- 7c: Lower bound (29:44)
- 7d: Multi-level range search (7:07)
- 7e: Fractional cascading (15:59)
- 7f: Summary (4:19)

Homework 7 and HW7 solution template, due Monday, May 17

**Week 8**:Readings: Range minima, Cartesian trees, and lowest common ancestors.

Level ancestors. Maintaining order in a list.Lectures:

- 8a: Succinct representation of trees (7:13)
- 8b: Applications of common ancestors (8:15)
- 8c: From ancestors to range minima (5:56)
- 8d: Cartesian trees (11:47)
- 8e: LCA and range minimum solutions (12:42)
- 8f: Maintaining order in a list (20:29)
- 8g: Level-ancestors (15:19)
- 8h: Summary (2:10)

Homework 8 and HW8 solution template, due Monday, May 24

**Week 9**:Readings: Persistence, retroactivity

Lectures:

- 9a: Persistence (9:12)
- 9b: Persistent stacks (11:39)
- 9c: Path copying (17:32)
- 9d: Fat nodes (12:08)
- 9e: Persisent search trees (23:41)
- 9f: Retroactivity (10:50)
- 9g: Summary (4:31)

Homework 9 and HW9 solution template, due Monday, May 31

**Week 10**:Readings: Tries and suffix trees.

Union-find and dynamic graph algorithms.Lectures:

- 10a: Tries (19:18)
- 10b: Suffix trees (10:46)
- 10c: Union-find (14:50)
- 10d: Union-find analysis (26:31)
- 10e: Dynamic graph algorithms (5:28)
- 10f: Summary (2:43)

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.