15-859 Advanced Data Structures

CMU, Fall 2007, Professor Danny Sleator

General Information

This course will focus on beautiful and theoretically (or practically) 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 4615A.

Instructor: Danny Sleator. Office: Wean Hall 4128. Phone: x87563. Office Hours by arrangement -- just call me.

Assistants: Jon Derryberry

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) (20%), homework (60%), And a class presentation of a paper (20%).

Homework Assignments

Homework 1 Due Mon, Oct 1 in class.
Homework 2 Due Mon, Oct 22 in class.
Homework 3 Due Wed, Dec 5 in class.

Lectures So Far

September 11 -- Amortized analysis and the list update problem pdf
September 14 -- Splay Trees I [txt]
September 17 -- Splay Trees II [txt]
September 19 -- Dynamic Optimality, Tango Trees [pdf]
September 24 -- Rabin-Karp string matching [Wikipedia][pdf], Intro to Suffix Trees and Suffix Arrays
September 26 -- Computing Suffix Arrays in linear time [pdf]
October 1 -- Range-Min Queries and Least Common Ancestor Queries [pdf]
October 3 -- Quick kth Ancensor Finding (aka Level Ancestor) [pdf]
October 8 -- Link-Cut Trees I [pdf]
October 10 -- Link-Cut Trees II
October 15 -- Dynamic Connectivity I [pdf]
October 17 -- Dynamic Connectivity II
October 22 -- Point Location I: Kirkpatrick's Algorithm [html]
October 24 -- Point Location II: Persistence [pdf]
October 29 -- Perfect Hashing [pdf]
October 31 -- Cuckoo Hashing [see pdf above]
November 5 -- Fibonacci Heaps [txt]
November 7 -- Soft Heaps [pdf]
November 12 -- Soft heaps contd.
November 14 -- Derryberry and Sleator's algorithm for non-meldable soft-heaps
November 19 -- The Order Maintenance Problem [Dietz Sleator] [MIT Lecture Notes]


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


splay trees
exploring dynamic optimality

string search

suffix trees
suffix arrays
computing in linear time

dynamic algorithms

dynamic trees (link-cut trees), Euler tour trees
dynamic connectivity
lower bound for dynamic connectivity

Hashing topics:

cuckoo hashing
polynomial method to get high-independence
(highly independent hashing functions)

Persistent Data Structures

partial persistence
point location
full persistence
catenable lists
order maintenance data structures

integer dictionaries

van emde boas
y-fast trees

memory models

External memory model
cache oblivious model


Pettie/Ramachandran optimal MST
Heaps (see 2005 course)


Advanced Data Structures, Danny Sleator et. al. 2005

Advanced Data Structures, Erik Demaine (2003) (2005) (2007)

Danny Sleator
Last modified: Wed Nov 28 13:09:42 2007