CMU, Fall 2007, Professor Danny Sleator
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 1 Due Mon, Oct 1 in class.
Homework 2 Due Mon, Oct 22 in class.
Homework 3 Due Wed, Dec 5 in class.
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.
self-adjustment
lists
splay trees
exploring dynamic optimality
tango/multi-splay-trees
string search
suffix trees
suffix arrays
applications
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
Possible:
Pettie/Ramachandran optimal MST
Heaps (see 2005 course)
Advanced Data Structures, Danny Sleator et. al. 2005
Advanced Data Structures, Erik Demaine (2003) (2005) (2007)