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.

- 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.