Daniel Sleator
Encyclopedia
Daniel Dominic Kaplan Sleator is a professor of computer science
at Carnegie Mellon University
. He discovered amortized analysis
and he invented many data structures with Robert Tarjan
, such as splay tree
s, link/cut tree
s, and skew heap
s. He also pioneered the theory of link grammar
s and developed the technique of competitive analysis
for online algorithm
s. Because of his contribution in computer science, he won the Paris Kanellakis Award
in 1999.
into the Internet Chess Club
despite outcry from fellow volunteers. The ICS has since become one of the most successful internet-based commercial chess servers.
He is the brother of William Sleator
, who wrote science fiction for young adults.
Sleator has hosted the progressive talk show Left Out on WRCT-FM
with fellow host and School of Computer Science faculty member Bob Harper
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
. He discovered amortized analysis
Amortized analysis
In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
and he invented many data structures with Robert Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
, such as splay tree
Splay tree
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O amortized time. For many sequences of nonrandom operations, splay trees perform...
s, link/cut tree
Link/cut tree
A link/cut tree is a type of data structure that can merge and split data sets in O amortized time, and can find which tree an element belongs to in O amortized time. In the original publication, Sleator and Tarjan referred to link/cut trees as "dynamic trees"....
s, and skew heap
Skew heap
A skew heap is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heaps, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic...
s. He also pioneered the theory of link grammar
Link grammar
Link grammar is a theory of syntax by Davy Temperley and Daniel Sleator which builds relations between pairs of words, rather than constructing constituents in a tree-like hierarchy. There are two basic parameters: directionality and distance...
s and developed the technique of competitive analysis
Competitive analysis (online algorithm)
Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance...
for online algorithm
Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
s. Because of his contribution in computer science, he won the Paris Kanellakis Award
Paris Kanellakis Award
The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing...
in 1999.
Personal life
Sleator commercialized the volunteer-based Internet Chess ServerInternet chess server
An Internet chess server is an external server that provides the facility to play, discuss, and view the board game of chess over the Internet...
into the Internet Chess Club
Internet Chess Club
The Internet Chess Club is a commercial Internet chess server devoted to the play and discussion of chess and chess variants. ICC currently has over 30,000 subscribing members...
despite outcry from fellow volunteers. The ICS has since become one of the most successful internet-based commercial chess servers.
He is the brother of William Sleator
William Sleator
William Warner Sleator III , known as William Sleator, was an American science fiction author who wrote primarily young adult novels but also wrote for younger readers. His books typically deal with adolescents coming across a peculiar phenomenon related to an element of theoretical science, then...
, who wrote science fiction for young adults.
Sleator has hosted the progressive talk show Left Out on WRCT-FM
WRCT
WRCT is a non-commercial freeform radio station based in Pittsburgh, Pennsylvania. The station, which is hosted in the basement of Carnegie Mellon's University Center, is run by students, staff, faculty, and community members. WRCT broadcasts on 88.3 MHz with an ERP of 1.75 kW, from atop...
with fellow host and School of Computer Science faculty member Bob Harper
Robert Harper (computer scientist)
Robert "Bob" William Harper, Jr. is a computer science professor at Carnegie Mellon University who works in programming language research. He made major contributions to the design of the Standard ML programming language and the LF logical framework....
.