15-859 Advanced Data Structures

CMU, Fall 2005, Professor Danny Sleator

General Information

This course will focus on beautiful and motivated data structures that are typically not presented in undergraduate or graduate algorithms courses. (See the list of topics below for more information.)

Class Meetings: Monday and Wednesday from 1:30 to 2:50 in Wean 4623.

Instructor: Danny Sleator. Office: Wean Hall 4128. Phone: x87563. Office Hours: 3-4 Monday and Wednesday.

Assistants: Jon Derryberry and Chris Wang.

There is a class mailing list that will be used sprodically. The address is sleator+ds@cs.cmu.edu. If you're taking or auditing the class, please let me know, and I'll add you to the list.

Knowledge of algorithms and data structures at the level of a typical undergraduate course (i.e. CMU's 15-451) will be assumed.

Grading

The grading for the class will be based on class participation (i.e. coming to class and paying attention) (10%), homework (40%), a takehome midterm exam (20%), and a class project (30%).

On the projects, you can work in groups of up to two people. Around mid-semester you will submit a project proposal. We'll be developing a web page with ideas for projects as the semester continues.

Homework Assignments

Homework 1 Due Wed. Sept. 21 in class
Homework 2 Due Mon. Oct. 24 in class

Lectures So Far

September 12 -- Amortized analysis and the list update problem
September 14 -- Splay Trees I
September 19 -- Splay Trees II
September 21 -- link-cut trees I
September 26 -- link-cut trees II
September 28 -- solving max flow with link-cut trees
October 3 -- Off-line Least Common Ancestors & Min Range Query & Cartesian Trees
October 5 -- Applications of Suffix trees and suffix arrays
October 10 -- Linear Construction of Suffix trees and suffix arrays
October 12 -- Leftist Heaps
October 17 -- Self-adjusting heaps
October 19 -- Soft Heaps I
October 24 -- (cancelled due to FOCS)
October 26 -- Soft Heaps II
October 31 -- Lower Bound on heaps with increase key
November 2 -- Analysis of Union/Find
November 7 -- Planar Point Location using Persistent Search Trees

Syllabus

Here are some topics that will (may?) be covered. Look for more details (papers and lecture notes, etc) here as the semester progresses.

• Amortized analysis and the list update problem [1]

• Splay Trees [2] [25]

  • Centroid Potential analysis and its consequences
  • Dynamic Optimality Conjecture
  • Sequential Access Lemma [17]
  • Rotation Distance Upper Bound [23]
  • Binary Search Tree Lower Bounds (new material)
  • (Multi-Splay trees [18])

• Link-Cut Trees and computing the maximum flow in O(n m log n) time ([2] and pages 387 and 388 of [3]). Also see my handwritten notes.

• Off-line Least Common Ancestors [4]

• Min Range Query & Cartesian Trees [4]

• Suffix Trees (indexing) [5]

• Heaps

  • Skew Heaps [6]
  • Leftist Heaps, and computing the MST [7]
  • Randomized Complexity of Maintaining the Minimum [24]
  • Pairing Heaps [8]
  • (Soft Heaps and the best known deterministic MST algorithm [9])

• van Emde-Boas priority queue [10]

• Maintaining Disjoint Sets [11]

  • Inverse Ackermann upper bound (for weighted union and path compression)
  • (Inverse Ackermann lower bound for maintaining disjoint sets [12])

• Persistent Data Structures [13]

• Maintaining Order in a List [14]

• Fully Persistent Lists with Catenation [15]

• Y-Fast Trees [16]

• PQ Trees and linear-time planarity testing [19]

• Succinct Data Structures (Jacobson, Munro, etc) [22]

• Data Compression Algorithms [20]

  • Huffman Codes
  • Arithmetic Coding
  • Burrows-Wheeler

• The Cache-Oblivious Model and results [21]

  • linked lists
  • divide-and-conquer
  • median/select
  • static search trees
  • sorting

References

[ 1]: Amortized Efficiency of List Update and Paging Rules,Sleator and Tarjan
[ 2]: Self-Adjusting Binary Search Trees, Sleator and Tarjan
[ 3]: A Data Structure for Dynamic Trees, Sleator and Tarjan
[ 4]: Lecture 10 from Demaine's Advanced Data Structures course, 2003
[ 5]: Lecture 11 from Demaine's Advanced Data Structures course, 2003
[ 6]: Self-Adjusting Heaps, Sleator and Tarjan
[ 7]: (to be added)
[ 8]: Pairing Heaps: A New Form of Self-Adjusting Heap, Fredman, Sleator, and Tarjan
[ 9]: The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, Chazelle
[10]: (to be added)
[11]: Data Structures and Network Algorithms, Chapter 2. [12]: (to be added)
[13]: Making Data Structures Persistent, Driscoll, Sarnak, Sleator, and Tarjan
[14]: Two Algorithms for Maintaining Order in a List, Dietz and Sleator
[15]: Fully Persistent Lists with Catenation, Driscoll, Sleator, and Tarjan
[16]: Lecture 2 from Demaine's Advanced Data Structures course, 2003
[17]: (to be added)
[18]: Dynamic Optimality and Multi-Splay Trees, Sleator and Wang
[19]: (to be added)
[20]: Lecture 13 from Demaine's Advanced Data Structures course, 2003
[21]: Lecture 16 from Demaine's Advanced Data Structures course, 2003
[22]: (to be added)
[23]: Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan, and Thurston
[24]: (to be added)
[25]: Graduate Algorithms Lecture Notes

Resources

Advanced Data Structures, Eric Demaine (2003) (2005)

The following books have been put on reserve in the Engineering Library:

• Data Structures and Network Algorithms by Robert Tarjan