Editing Daniel Sleator (section)

{{short description|American computer scientist}}

{{Infobox scientist
| name              = Daniel Sleator
| image             =
| caption           = 
| birth_date        = {{birth-date and age|10 December 1953}}
| birth_place       = [[St. Louis]],<ref>''American Men and Women of Science'', Thomson Gale, 2004</ref> [[Missouri]]
| children          = Leon Sleator
| death_date        = 
| death_place       = 
| citizenship       = 
| nationality       = 
| ethnicity         = 
| fields            = [[Computer science]]
| workplaces        = [[Carnegie Mellon University]]
| alma_mater        = [[University of Illinois at Urbana–Champaign]], [[Stanford University]]
| doctoral_advisor  = [[Robert Tarjan]]
| academic_advisors = 
| doctoral_students = 
| notable_students  = 
| thesis_url        = 
| thesis_title      = 
| thesis_year       = 
| known_for         = 
| author_abbrev_bot = 
| author_abbrev_zoo = 
| influences        = 
| influenced        = 
| awards            = [[Paris Kanellakis Award]] {{small|(1999)}}
| religion          = 
| signature         = 
| footnotes         =  
}}
'''Daniel Dominic Kaplan Sleator''' (born 10 December 1953) is a professor of [[computer science]] at [[Carnegie Mellon University]], [[Pittsburgh]], United States. In 1999, he won the [[Association for Computing Machinery|ACM]] [[Paris Kanellakis Award]] (jointly with [[Robert Tarjan]]) for the [[splay tree]] data structure.<ref>[http://www.acm.org/announcements/pk_award_1999.html Citation for Sleator and Tarjan Kanellakis Award] {{webarchive|url=https://web.archive.org/web/20120211141406/http://www.acm.org/announcements/pk_award_1999.html |date=2012-02-11}}</ref>

He was one of the pioneers in [[amortized analysis]] of algorithms, early examples of which were the analyses of the [[Move-to-front transform|move-to-front]] heuristic,<ref name="MTF">{{Citation |first1=Daniel D. |last1=Sleator |first2=Robert E. |last2=Tarjan |title=Amortized efficiency of list update and paging rules |url=https://www.cs.cmu.edu/~sleator/papers/amortized-efficiency.pdf |journal=[[Communications of the ACM]] |volume=28 |issue=2 |pages=202–208 |year=1985 |doi=10.1145/2786.2793|citeseerx=10.1.1.367.6317 |s2cid=2494305 }}</ref> and [[splay tree]]s.<ref name="splay">{{Citation |first1=Daniel D. |last1=Sleator |first2=Robert E. |last2=Tarjan |title=Self-Adjusting Binary Search Trees |url=https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf |journal=[[Journal of the ACM]] |volume=32 |issue=3 |pages=652–686 |year= 1985 |doi=10.1145/3828.3835|s2cid=1165848 }}</ref> He invented many [[data structures]] with [[Robert Tarjan]], such as [[splay tree]]s, [[link/cut tree]]s, and [[skew heap]]s.

The Sleator and Tarjan paper on the move-to-front heuristic<ref name="MTF" /> first suggested the idea of comparing an [[online algorithm]] to an optimal offline algorithm, for which the term [[Competitive analysis (online algorithm)|competitive analysis]] was later coined in a paper of [[Anna Karlin|Karlin]], Manasse, Rudolph, and Sleator.<ref name="snoopy">{{citation |last1=Karlin |first1=Anna R. |last2=Manasse |first2=Mark S. |last3=Rudolph |first3=Larry |last4=Sleator |first4=Daniel D. |doi=10.1007/BF01762111 |issue=1 |journal=[[Algorithmica]] |mr=925479 |pages=79–119 |title=Competitive snoopy caching |volume=3 |year=1988|s2cid=33446072 }}</ref> Sleator also developed the theory of [[link grammar]]s, and the Serioso music analyzer for analyzing meter and harmony in written music.