CS 261, Spring 2013: Data Structures

This course meets Tuesdays and Thursdays, 2:00 - 3:20 in Bren 1500. 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. Homeworks will usually be assigned Thursdays and due on the following Thursday. Grading will be based 20% on homework, 35% for the midterm, and 45% for the final.

Instructor office hours are Tuesdays and Wednesdays from 4:00 to 5:00, in DBH 4214. The reader for the course is Wei Ping; Wei's office hours are Fridays from 3:30 to 4:30, in DBH 4069.

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: Algorithms + Data Structures. The potential method of amortized analysis. Dynamic arrays.
  Homework 1, due Tuesday, April 16 — Solutions.
• Week 2. No class.
• Week 3: 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 Thursday, April 25 — Solutions.
• Week 4: Bloom filters, invertible Bloom filters, MinHash, streaming data structures, and frequent item detection.
  Homework 3, due Thursday, May 2 — Solutions.
• Week 5: Priority queues. Binary heaps and k-ary heaps. Fibonacci heaps.
  Homework 4, due Thursday, May 9 — 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 Thursday, May 16 — Solutions.
• Week 7: Midterm Tuesday — Solutions.
  Tries and suffix trees.
  Homework 6, due Thursday, May 23 — Solutions.
• Week 8: Range searching, Dynamic prefix sums and augmented binary search trees.
  Homework 7, due Thursday, May 30 — Solutions.
• Week 9: Range minima, Cartesian trees, and lowest common ancestors. Persistence.
  Homework 8, due Thursday, June 6 — Solutions.
• Week 10: Integer searching. Union find.

See also: the Fall 2011 syllabus including sample homeworks and exams with their solutions, and additional information linked from that page.

David Eppstein, ICS, UC Irvine.