CSD Home | Research Home

 

 

Acar
Andersen
Balcan
Blelloch
Blum, A.
Blum, L.
Blum, M.
Brookes
Brunskill
Bryant
Carbonell
Christel
Clarke
Crary
Dannenberg
Datta
Erdmann
Fahlman
Faloutsos
Fatahalian
Fink
Garlan
Gibson
Goldstein
Gupta
Guruswami
Haeupler
Harchol-Balter
Harper
Hauptmann
Hodgins

Kanade
Kolter

Lee, T.
Mason
Maxion

Miller
Mitchell
Morris
Mowry
O'Donnell
O'Hallaron
Pavlo
Pfenning
Platzer
Pollard
Procaccia
Reddy
Rudich
Rudnicky
Sandholm
Satyanarayanan
Schmerl
Seshan
Shaw
Siewiorek
Simmons
Sleator
Steenkiste
Touretzky
Treuille
Veloso
Von Ahn
Wactlar
Wing
Zhang
 
Affiliated Faculty
Aldrich
Brumley
Durand
Ganger
Hoe
Mutlu
Perrig
Schwartz
Stern
Xing
Yang

DANIEL D. SLEATOR
Professor, Computer Science
www

I have worked in a variety of different areas of computer science, including amortized analysis of algorithms, self-adjusting data structures, competitive algorithms, natural language parsing, computer game playing, synthesis of musical sounds, and persistent data structures.

Natural Language: I (jointly with co-author Davy Temperley) wrote a parser for English. The system (which we call a link grammar) is unlike phrase structure parsing or context free parsing. The scheme is elegant and simple, and our grammar captures a very wide variety of complex phenomena in English. We (John Lafferty and I) plan to use this as a basis for a new statistical model of language. This work on language is described in two technical reports: CMU-CS-91-196, CMU-CS-92-181.

Competitive Algorithms: Consider the idealized problem of deciding whether to rent or buy skis. You're about to go skiing. The cost of renting skis is $20, the cost of buying them is $400. Clearly if you knew that you were going to go skiing more than twenty times, then you could save money by immediately buying skis. If you knew that you would go skiing fewer than twenty times, then it would be prudent to always rent skis. However, suppose that you cannot predict the future at all, that is, you never know until after one ski trip ends if you will ever go skiing again. What strategy would you use for deciding whether to rent or buy skis? Your goal is to minimize the ratio of the cost that you incur to the cost you would incur if you could predict the future. (Hint: you can come within a factor of two.)

Since the simple principle behind this example turns out to be very useful we have given it a name. A competitive algorithm is an on-line algorithm (it must process a sequence of requests, and it must process each request in the sequence immediately, without knowing what the future requests will be), whose performance is within a small constant factor of the performance of the optimal off-line algorithm for any sequence of requests. (In the skiing example, there is only one type of request, and the only uncertainty is in knowing how long the request sequence will be.)

My collaborators and I have discovered a surprising variety of practical problems for which there exist very efficient competitive algorithms. We have also developed a partial theory of competitive algorithms. However there remain many interesting open problems, from discovering competitive algorithms for specific problems, to answering general questions about when such algorithms exist.

Data Structures: Data structure problems are typically formulated in terms of what types of operations on the data are required, and how fast these operations should take place. A worst-case analysis of the performance of a data structure is a bound on the performance of any operation. An amortized analysis of a data structure bounds the performance of the structure on a sequence of operations, rather than a single operation. It turns out that by only requiring amortized efficiency (rather than worst-case), a variety of new and elegant solutions to old data structure design problems become possible. My collaborators and I have devised a number of such solutions (splay trees, skew heaps, fibonacci heaps, self-adjusting lists, persistent data structures, etc.), and I continue to have a strong interest in data structures and amortized analysis.


 

 

      CSD Home   Webteam  ^ Top   SCS Home