Daniel Dominic Kaplan Sleator (born 10 December 1953) is a Professor of
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
at
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
,
Pittsburgh
Pittsburgh ( ) is a city in the Commonwealth (U.S. state), Commonwealth of Pennsylvania, United States, and the county seat of Allegheny County, Pennsylvania, Allegheny County. It is the most populous city in both Allegheny County and Wester ...
, United States. In 1999, he won the
ACM Paris Kanellakis Award The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". It wa ...
(jointly with
Robert Tarjan
Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's off-line lowest common ancestors algorithm, and co-inventor of both splay trees a ...
) for the
splay tree data structure.
He was one of the pioneers in
amortized analysis
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case ...
of algorithms, early examples of which were the analyses of the
move-to-front heuristic,
and
splay trees.
He invented many
data structures
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
with
Robert Tarjan
Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's off-line lowest common ancestors algorithm, and co-inventor of both splay trees a ...
, such as
splay trees,
link/cut trees, and
skew heap A skew heap (or self-adjusting 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 constr ...
s.
The Sleator and Tarjan paper on the move-to-front heuristic
first suggested the idea of comparing an
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 o ...
to an optimal offline algorithm, for which the term
competitive analysis was later coined in a paper of
Karlin, Manasse, Rudolph, and Sleator.
Sleator also developed the theory of
link grammar
Link grammar (LG) is a theory of syntax by Davy Temperley and Daniel Sleator which builds relations between pairs of words, rather than constructing constituents in a phrase structure hierarchy. Link grammar is similar to dependency grammar, but d ...
s, and the Serioso music analyzer for analyzing meter and harmony in written music.
Personal life
Sleator was born to William Warner Sleator, Jr., a professor of physiology and
biophysics
Biophysics is an interdisciplinary science that applies approaches and methods traditionally used in physics to study biological phenomena. Biophysics covers all scales of biological organization, from molecular to organismic and populations. ...
, and Esther Kaplan Sleator, a pediatrician who did pioneering research on
attention deficit disorder
Attention deficit hyperactivity disorder (ADHD) is a neurodevelopmental disorder characterised by excessive amounts of inattention, hyperactivity, and impulsivity that are pervasive, impairing in multiple contexts, and otherwise Development ...
(ADD).
He is the younger brother of
William Sleator
William Warner Sleator III (February 13, 1945 – August 3, 2011), 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 adolescent ...
, who wrote science fiction for young adults.
Sleator commercialized the volunteer-based
Internet Chess Server
An Internet chess server (ICS) is an external server that provides the facility to play, discuss, and view the board game of chess over the Internet. The term specifically refers to facilities for connecting players through a variety of graphical c ...
into the
Internet Chess Club
The Internet Chess Club (ICC) is a commercial Internet chess server devoted to the play and discussion of chess and chess variants. ICC had over 30,000 subscribing members in 2005.John Black, Martin Cochran, Martin Ryan Gardner"Lessons Learned ...
despite outcry from fellow volunteers. The ICS has since become one of the most successful internet-based commercial chess servers.
From 2003 to 2008, Sleator co-hosted the progressive talk show ''Left Out'' on
WRCT-FM
WRCT (88.3 FM) is a non-commercial freeform radio station based in Pittsburgh, Pennsylvania. The volunteer-run station has a studio in the basement of Carnegie Mellon's University Center. WRCT broadcasts throughout the city with an ERP of 1.75 ...
with
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
School of Computer Science faculty member
Bob Harper.
He is also an active member of the competitive programming platform
Codeforces
Codeforces is a website that hosts competitive programming contests. It is maintained by a group of competitive programmers from ITMO University led by Mikhail Mirzayanov. Since 2013, Codeforces claims to surpass Topcoder in terms of active co ...
.
References
External links
The CMU home page of Daniel SleatorThe Internet Chess ClubParis Kanellakis Theory and Practice AwardLeft Out radio show
{{DEFAULTSORT:Sleator, Daniel
American computer scientists
Carnegie Mellon University faculty
Living people
1953 births
Theoretical computer scientists
Stanford University alumni
Competitive programmers