CS 261, Winter 2011: Data Structures

This course meets Monday, Wednesday, and Friday, 2:00 - 2:50 in Bren 1200. 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, you may find the following helpful for some of the material:

• Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein. I don't recommend that you buy the book for this course (it is expensive and only covers part of the material) but many of you are likely to have it from undergraduate CS courses and it includes useful material on several topics from this course. Other algorithms texts are also likely to be helpful; the one I use in my undergraduate algorithms courses is "Algorithm Design" by Goodrich and Tamassia.
• Lecture notes from similar courses here and elsewhere:
  • ICS 261, UCI, Fall 2003
  • 6.897, MIT, Spring 2003
  • COS226, Princeton, Spring 2008
  • External memory data structures, Aarhus, Fall 2000
• When possible I will try to include more specific links to Wikipedia or other related online reading from the schedule of topics below.

Below is a tentative schedule of topics and readings. Dates for specific topics are subject to change, but the exam schedule is firm.

• Week 1 (Jan 3-5-7):
  • Introduction: priority queues in selection sort; binary heaps.
  • Dijkstra's algorithm and D-ary heaps; amortized analysis and variable-sized arrays.
  • Potential functions for amortization.
  • Homework 1, due Wednesday, Jan 12 (solutions)
• Week 2 (Jan 10-12-14):
  • Fibonacci heaps.
  • Integer priority queues.
  • Homework 2, due Wednesday, Jan 19 (solutions)
• Week 3 (Jan 17-19-21):
  • HOLIDAY January 17 (Martin Luther King, Jr. Day).
  • Hashing: hash chaining, open addressing (double hashing, linear probing). See also this blog post.
  • Cuckoo hashing (see also: cuckoo hashing with a stash).
  • Homework 3, due Wednesday, Jan 26 (solutions)
• Week 4 (Jan 24-26-28):
  • Min-wise hashing, Bloom filters, and invertible Bloom filters.
  • Hash functions: cryptographic hashing, finding collisions using cycle detection algorithms, universal hashing, tabulation hashing.
  • Overview of balanced binary search trees.
  • Homework 4, due Wednesday, Feb 2 (solutions)
• Week 5 (Jan 31, Feb 2-4):
  • Splay trees.
  • The dynamic optimality conjecture. (Additional reading on non-splay-tree approaches to dynamic optimality.)
  • MIDTERM, Friday, February 4. (solutions)
• Week 6 (Feb 7-9-11):
  • 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.
  • Homework 5, due Wednesday, Feb 16 (solutions)
• Week 7 (Feb 14-16-18):
  • Succinct representation of trees and fast navigation in succinct trees. Level ancestors.
  • Lowest common ancestors, range minima, and the Bender-Farach algorithm.
  • Homework 6, due Wednesday, Feb 23 (solutions)
• Week 8 (Feb 21-23-25):
  • HOLIDAY February 21 (Presidents' Day).
  • 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 7, due Wednesday, Mar 2 (solutions)
• Week 9 (Feb 28, Mar 2-4):
  • Quadtrees and approximate nearest neighbors
  • Segment trees and interval trees
  • Tries, compressed tries, and suffix trees
  • Homework 8, due Friday, Mar 11 (solutions)
• Week 10 (Mar 7-9-11):
  • Dynamic graph algorithms and dynamic subgraph statistics
  • Union-find
• FINAL EXAM, Friday, March 18, 1:30-3:30pm.

Several exams from past offerings of this course are online: Midterm, Winter 1999 (solutions); Final, Fall 2003; Final, Fall 2004; Midterm, Winter 2006 (solutions); Final, Winter 2006.

For additional course-related information see the syllabus from my previous offering in Winter 2010 and previous quarters linked from there.

David Eppstein, ICS, UC Irvine.