CS 261, Spring 2017: Data Structures

This course meets Mondays, Wednesdays, and Fridays, 10:00 - 10:50 in Steinhaus Hall 134. Coursework will consist of weekly homeworks, turned in online 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.

Rather than setting specific office hours, I will be trying an open door policy: I will be available in my office most afternoons, and if my door is open you are welcome to interrupt me with course questions. If this becomes too problematic I will set more specific office hours, and if you need me to be available at a more predictable time please email me for an appointment.

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 (April 3-7):
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 11:59PM Friday, April 14Solutions
Week 2 (April 10-14):
The dictionary problem and hash tables. Hash chaining, linear probing, and cuckoo hashing.
Homework 2, due 11:59PM Friday, April 21Solutions
Week 3 (April 17-21):
Hash functions: cryptographic hash functions, k-independent hashing, and tabulation hashing.
Representing sets by bitmaps, dictionaries, and Bloom filters.
Cuckoo filters and invertible Bloom filters.
Homework 3, due 11:59PM Friday, April 28Solutions
Week 4 (April 24-28):
Streaming data structures and frequent item detection.
Boyer–Moore majority voting, MinHash, and the count-min sketch.
Homework 4, due 11:59PM Friday, May 5Solutions
Week 5 (May 1-5):
Priority queues. Binary heaps and k-ary heaps. Fibonacci heaps.
Homework 5, due 11:59PM Friday, May 12Solutions
Week 6 (May 8-12):
Binary search trees and predecessor queries. WAVL trees and B-trees.
Splay trees, static optimality, competitive analysis, and the dynamic optimality conjecture.
Week 7 (May 15-19):
Review session Monday, May 15
Midterm Wednesday, May 17
Tries and suffix trees.
Week 8 (May 22-26):
Range searching, Dynamic prefix sums and augmented binary search trees. Fractional cascading.
Homework 6, due 11:59PM Friday, June 2Solutions
Week 9 (May 29-June 2):
Memorial day holiday Monday, May 29
Range minima, Cartesian trees, and lowest common ancestors.
Homework 7, due 11:59PM Friday, June 9Solutions
Week 10 (June 5-9):
Integer searching.
Finals Week
Final exam, Monday June 12, 10:30–12:30.

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

David Eppstein, ICS, UC Irvine.