CS 261, Winter 2018: Data Structures

This course meets Mondays, Wednesdays, and Fridays, 3:00 - 3:50 in Social Ecology II, room 1304. Coursework will consist of weekly homeworks, turned in online and returned at the reader's office hours, one midterm, and a comprehensive final exam. No books or notes are permitted for the exams. 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. If you are enrolled in the course, you will be automatically considered eligible for the comprehensive exam. 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 (January 8–12):

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 Monday, January 22 (11:55pm) – Solutions

 

Week 2 (January 15–19):

Holiday Monday, January 15: Martin Luther King Day

The dictionary problem and hash tables. Hash chaining, linear probing, and cuckoo hashing.

Homework 2, due Monday, January 29 (11:55pm) – Solutions

 

Week 3 (January 22–26):

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 Monday, February 5 (11:55pm) – Solutions

 

Week 4 (January 29 – February 2):

Streaming data structures and frequent item detection.

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

Homework 4, due Monday, February 12 (11:55pm) – Solutions

 

Week 5 (February 5 – 9):

Priority queues. Binary heaps and k-ary heaps. Fibonacci heaps.

Homework 5, due Tuesday, February 20 (11:55pm) – Solutions

 

Week 6 (February 12 – 16):

Binary search trees and predecessor queries. WAVL trees and B-trees.

Splay trees, static optimality, competitive analysis, and the dynamic optimality conjecture.

 

Week 7 (February 19 – 23):

Holiday Monday, February 19: Presidents' Day

Midterm Wednesday, February 21 – Solutions

Integer searching.

 

Week 8 (February 23 – March 2):

Range searching, Dynamic prefix sums and augmented binary search trees. Fractional cascading.

Homework 6, due Friday, March 9 (11:55pm) – Solutions

 

Week 9 (March 5 – 9):

Range minima, Cartesian trees, lowest common ancestors, and level ancestors.

Homework 7, due Friday, March 16 (11:55pm) – Solutions

 

Week 10 (March 12 – 16):

Tries and suffix trees.

Persistence.

Union-find.

 

Finals Week

Final exam, Monday March 19, 4:00–6:00.

See also syllabi from 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.