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 Paris Kanellakis Award (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 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 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 splay trees, link/cut trees, and skew heaps. 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 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. From 2003 to 2008, Sleator co-hosted the progressive talk show ''Left Out'' on WRCT-FM with

School of Computer Science faculty member Bob Harper. He is also an active member of the competitive programming platform Codeforces.

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