CS 261, Spring 2021: Data Structures

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.

Tentative schedule of topics

Week 1:

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

Lectures:

Lecture notes

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:

Lecture notes

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:

Lecture notes

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:

Lecture notes

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:

Lecture notes

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:

Lecture notes

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:

Lecture notes

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:

Lecture notes

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

Week 9:

Readings: Persistence, retroactivity

Lectures:

Lecture notes

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

Week 10:

Readings: Tries and suffix trees.
Union-find and dynamic graph algorithms.

Lectures:

Lecture notes

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.