CS 261, Fall 2011: Data Structures

This course meets Monday, Wednesday, and Friday, 10:00 - 10:50 in MSTB 118. I will also have office hours Mondays and Tuesdays from 2:00 - 3:00 in my office, Bren 4214. Coursework will consist of weekly homeworks, one midterm and a comprehensive final exam. Grading will be based 20% on homework, 35% for the midterm, and 45% for the final. The reader assigned to the course is Leila Jalali .

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.

• Friday, September 23: No lecture.
• Week 1 (Sept. 26-28-30):
  • Introduction: priority queues in selection sort; dynamic arrays and the potential method of amortized analysis.
  • Dijkstra's algorithm, binary heaps, D-ary heaps
  • Fibonacci heaps.
  • Homework 1, due Wednesday, Oct. 5 -- Solutions
• Week 2 (Oct. 3-5-7):
  • Integer priority queues.
  • Hashing: hash chaining, open addressing (double hashing, linear probing, linear probing analysis). See also this blog post.
  • Cuckoo hashing (see also: cuckoo hashing with a stash).
  • Homework 2, due Wednesday, Oct. 12 -- Solutions
• Week 3 (Oct. 10-12-14):
  • Bloom filters, and invertible Bloom filters.
  • Min-wise hashing
  • Hash functions: cryptographic hashing, universal hashing, tabulation hashing.
  • Homework 3, due Wednesday, Oct. 19 -- Solutions
• Week 4 (Oct. 17-19-21):
  • Overview of balanced binary search trees.
  • B-trees and cache-oblivious B-trees.
  • Splay trees.
  • The dynamic optimality conjecture. (Additional reading on non-splay-tree approaches to dynamic optimality.)
  • Homework 4, due Wednesday, Oct. 26 -- Solutions
• Week 5 (Oct. 24-26-28):
  • Range sums, prefix sums, and decomposable searching problems.
  • Logarithmic lower bounds for dynamic prefix sums.
  • Binary search trees; augmented binary search trees and range searching.
• Week 6 (Oct. 31, Nov 2-4):
  • Midterm, Monday, October 31 -- Solutions.
  • Succinct representation of trees and fast navigation in succinct trees. Level ancestors.
  • Lowest common ancestors, range minima, and the Bender-Farach algorithm.
  • Homework 5, due Wednesday, Nov. 9 -- Solutions
• Week 7 (Nov. 7-9-11):
  • Veteran's day holiday, November 11.
  • Persistence. Closures and fully-persistent stacks.
  • Persistent search trees, point location, Voronoi diagrams, and the post office problem.
  • The node-copying and fat node techniques for making data structures persistent.
  • Homework 6, due Friday, Nov. 18 -- Solutions
• Week 8 (Nov. 14-16-18):
  • Fractional cascading and halfspace range reporting.
  • Range trees and kD-trees.
  • Quadtrees and approximate nearest neighbors.
  • Homework 7, due Wednesday, Nov. 23 -- Solutions
• Week 9 (Nov. 21-23-25):
  • Segment trees and interval trees
  • Dynamic closest pairs.
  • Thanksgiving holiday, November 25.
• Week 10 (Nov. 28-30, Dec. 2):
  • Homework 8, due Friday, Dec. 2
  • Tries, compressed tries, and suffix trees
  • Dynamic graph algorithms and dynamic subgraph statistics
  • Union-find

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

David Eppstein, ICS, UC Irvine.