Daniel Sleator

From Wikipedia, the free encyclopedia

Daniel Dominic Kaplan Sleator (born 10 December 1953 in St. Louis)^[1] is a Professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 1999, he won the ACM Paris Kanellakis Award (jointly with Robert Tarjan) for the splay tree data structure.^[2]

He was one of the pioneers in amortized analysis of algorithms, early examples of which were the analyses of the move-to-front heuristic,^[3] and splay trees.^[4] He invented many data structures with Robert Tarjan, such as splay trees, link/cut trees, and skew heaps.

The Sleator and Tarjan paper on the move-to-front heuristic^[3] first suggested the idea of comparing an online algorithm to an optimal offline algorithm, for which the term competitive analysis was later coined in a paper of Karlin, Manasse, Rudolph, and Sleator.^[5] Sleator also developed the theory of link grammars, and the Serioso music analyzer for analyzing meter and harmony in written music.

Personal life

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.

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.

References

↑ American Men and Women of Science, Thomson Gale, 2004
↑ Citation for Sleator and Tarjan Kanellakis Award
↑ 3.0 3.1 Sleator, Daniel D.; Tarjan, Robert E. (1985), "Amortized efficiency of list update and paging rules", Communications of the ACM (Association for Computing Machinery) 28 (2): 202–208, doi:10.1145/2786.2793
↑ Sleator, Daniel D.; Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees", Journal of the ACM (Association for Computing Machinery) 32 (3): 652–686, doi:10.1145/3828.3835
↑ Karlin, Anna R.; Manasse, Mark S.; Rudolph, Larry; Sleator, Daniel D. (1988), "Competitive snoopy caching", Algorithmica 3 (1): 79–119, doi:10.1007/BF01762111, MR 925479

External links

Winners of the Paris Kanellakis Theory and Practice Award

Adleman, Diffie, Hellman, Merkle, Rivest, Shamir (1996)
Lempel, Ziv (1997)
Bryant, Clarke, Emerson, McMillan (1998)
Sleator, Tarjan (1999)
Karmarkar (2000)
Myers (2001)
Franaszek (2002)
Miller, Rabin, Solovay, Strassen (2003)
Freund, Schapire (2004)
Holzmann, Kurshan, Vardi, Wolper (2005)
Brayton (2006)
Buchberger (2007)
Cortes, Vapnik (2008)
Bellare, Rogaway (2009)
Mehlhorn (2010)
Samet (2011)
Broder, Charikar, Indyk (2012)

Persondata
Name	Sleator, Daniel
Alternative names
Short description	American computer scientist
Date of birth	10 December 1953
Place of birth
Date of death
Place of death

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.