Daniel Dominic Kaplan Sleator (born 10 December 1953) is a professor of

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institu ...

Pittsburgh Pittsburgh ( ) is a city in Allegheny County, Pennsylvania, United States, and its county seat. It is the List of municipalities in Pennsylvania#Municipalities, second-most populous city in Pennsylvania (after Philadelphia) and the List of Un ...

, United States. In 1999, he won the

ACM ACM or A.C.M. may refer to: Aviation * AGM-129 ACM, 1990–2012 USAF cruise missile * Air chief marshal * Air combat manoeuvring or dogfighting * Air cycle machine * IATA airport code for Arica Airport in Amazonas Department, Colombia Computing ...

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 theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees a ...

) for the

splay tree A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal ...

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 The move-to-front (MTF) transform is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually j ...

heuristic, and

s. He invented many

data structures In computer science, a data structure is a data organization 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, and the functi ...

with

, such as

link/cut tree A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations: * Add a tree consisting of a single node to the forest. * Given a node in one of the trees, disconnect it (and its subtr ...

s, 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 cons ...

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 of ...

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 ...

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 symptoms of inattention, hyperactivity, impulsivity, and emotional dysregulation that are excessive and pervasive, impairing in multiple con ...

(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 The American Internet Chess Server, commonly known as Internet Chess Server (ICS) was a telnet-based chess server which allowed users to play live chess over the internet. History In the 1970s, one could play correspondence chess in a PLAT ...

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. It was the first Internet chess server and was the largest p ...

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. ...

with

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 Sleator

The Internet Chess Club

Paris Kanellakis Theory and Practice Award

Left Out radio show
{{DEFAULTSORT:Sleator, Daniel Carnegie Mellon University faculty Living people 1953 births American theoretical computer scientists University of Illinois Urbana-Champaign alumni Stanford University alumni Competitive programmers