CS 261, Winter 2016: Data Structures

This course meets Mondays, Wednesdays, and Fridays, 2:00 - 2:50 in Steinhaus Hall 128. Coursework will consist of weekly homeworks, turned in at the start of lecture and returned at the reader's office hours, one midterm, and a comprehensive final exam. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks. Homeworks will usually be assigned Fridays and due on the following Friday. Grading will be based 20% on homework, 35% for the midterm, and 45% for the final.

Instructor office hours are TBA. The reader for the course is Maral Amir; office hours TBA.

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 score at least 66% of the possible points on the final examination for the course. Students who wish to take the comprehensive exam but are not enrolled in the course should contact me by email before the end of week 8 of the quarter to reserve a place in the exam.

Tentative schedule of topics

Week 1:
Introduction: Abstract data types versus data structures. Worst case versus amortized complexity.
The potential method of amortized analysis. Dynamic arrays. Stacks, queues, and deques.
Homework 1, due Friday, January 15.
Homework 1 solutions
Weeks 2–3:
No class Monday Jan. 11 or Wednesday Jan. 13; Martin Luther King, Jr. holiday Monday Jan. 18.
The dictionary problem and hash tables. Hash chaining, linear probing, and cuckoo hashing.
Hash functions: cryptographic hash functions, k-independent hashing, and tabulation hashing.
Homework 2, due Friday, January 29.
Homework 2 solutions
Week 4:
Bloom filters, invertible Bloom filters, MinHash, streaming data structures, and frequent item detection.
Homework 3, due Friday, February 5.
Homework 3 solutions
Week 5:
Priority queues. Binary heaps and k-ary heaps. Fibonacci heaps.
Homework 4, due Friday, February 12.
Homework 4 solutions
Week 6:
Binary search trees and predecessor queries. Random binary search trees, AVL trees, and rank-balanced trees.
Splay trees, static optimality, competitive analysis, and the dynamic optimality conjecture.
Homework 5, due Friday, February 19.
Homework 5 solutions
Week 7:
President's Day holiday Monday, Feb. 15.
Midterm Wednesday, Feb. 17
Tries and suffix trees.
Week 8:
Range searching, Dynamic prefix sums and augmented binary search trees. Fractional cascading.
Homework 6, due Friday, March 4.
Homework 6 solutions
Week 9:
Range minima, Cartesian trees, lowest common ancestors, and level ancestors.
Van Emde Boas trees.
Week 10:
Guest lectures by Will Devanney (Monday and Wednesday, on persistence) and Mike Goodrich (Friday, on union-find).

See also: Spring 2013 syllabus and Fall 2011 syllabus including sample homeworks and exams with their solutions.

David Eppstein, ICS, UC Irvine.