Editing Ron Rivest (section)

===Algorithms===
In 1973, Rivest and his coauthors published the first [[selection algorithm]] that achieved [[linear time]] without using [[randomization]].{{ran|A1}}<ref>{{cite conference
 | last = Paterson | first = Mike | author-link = Mike Paterson
 | editor1-last = Karlsson | editor1-first = Rolf G.
 | editor2-last = Lingas | editor2-first = Andrzej
 | contribution = Progress in selection
 | doi = 10.1007/3-540-61422-2_146
 | pages = 368–379
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithm Theory – SWAT '96, 5th Scandinavian Workshop on Algorithm Theory, Reykjavík, Iceland, July 3–5, 1996, Proceedings
 | volume = 1097
 | year = 1996| isbn = 978-3-540-61422-7 }}</ref> Their algorithm, the [[median of medians]] method, is commonly taught in algorithms courses.<ref>{{cite journal
 | last = Gurwitz | first = Chaya
 | doi = 10.1109/13.144650
 | issue = 3
 | journal = IEEE Transactions on Education
 | pages = 230–232
 | title = On teaching median-finding algorithms
 | volume = 35
 | year = 1992| bibcode = 1992ITEdu..35..230G
 }}</ref> Rivest is also one of the two namesakes of the [[Floyd–Rivest algorithm]], a randomized selection algorithm that achieves a near-optimal number of comparisons.{{ran|A2}}<ref>{{cite journal
 | last1 = Cunto | first1 = Walter
 | last2 = Munro | first2 = J. Ian | author2-link = Ian Munro (computer scientist)
 | doi = 10.1145/62044.62047
 | issue = 2
 | journal = [[Journal of the ACM]]
 | mr = 1072421
 | pages = 270–279
 | title = Average case selection
 | volume = 36
 | year = 1989| s2cid = 10947879
 | doi-access = free
 }}</ref>

Rivest's 1974 doctoral dissertation concerned the use of [[hash table]]s to quickly match [[partial word]]s in documents; he later published this work as a journal paper.{{ran|A3}} His research from this time on [[self-organizing list]]s{{ran|A4}} became one of the important precursors to the development of [[Competitive analysis (online algorithm)|competitive analysis]] for [[online algorithm]]s.<ref>{{cite journal
 | last1 = Sleator | first1 = Daniel D. | author1-link = Daniel Sleator
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | doi = 10.1145/2786.2793
 | issue = 2
 | journal = [[Communications of the ACM]]
 | mr = 777385
 | pages = 202–208
 | title = Amortized efficiency of list update and paging rules
 | volume = 28
 | year = 1985| s2cid = 2494305 | doi-access = free
 }}</ref> In the early 1980s, he also published well-cited research on two-dimensional [[bin packing problem]]s,{{ran|A5}} and on [[channel routing]] in [[VLSI design]].{{ran|A6}}

He is a co-author of ''[[Introduction to Algorithms]]'' (also known as ''CLRS''), a standard textbook on algorithms, with [[Thomas H. Cormen]], [[Charles E. Leiserson]] and [[Clifford Stein]]. First published in 1990, it has extended into four editions, the latest in 2022.{{ran|A7}}