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 practical disciplines (includi ...

at Carnegie Mellon University,

Pittsburgh Pittsburgh ( ) is a city in the Commonwealth of Pennsylvania, United States, and the county seat of Allegheny County. It is the most populous city in both Allegheny County and Western Pennsylvania, the second-most populous city in Pennsylva ...

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

) 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

, 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 age-inap ...

(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 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 American computer scientists Carnegie Mellon University faculty Living people 1953 births Theoretical computer scientists Stanford University alumni Competitive programmers