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.


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


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


[ 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


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

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

Advanced Data Structures Home Page
Danny Sleator
Last modified: Mon Nov 7 13:02:45 2005