Randomized algorithm - Revision history

imported>OAbot: Open access bot: url-access=subscription updated in citation with #oabot.

2025-08-25T04:56:43Z

Open access bot: url-access=subscription updated in citation with #oabot.

← Previous revision		Revision as of 04:56, 25 August 2025
Line 4:		Line 4:
	A '''randomized algorithm''' is an [[algorithm]] that employs a degree of [[randomness]] as part of its logic or procedure. The algorithm typically uses [[Uniform distribution (discrete)\|uniformly random]] bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.		A '''randomized algorithm''' is an [[algorithm]] that employs a degree of [[randomness]] as part of its logic or procedure. The algorithm typically uses [[Uniform distribution (discrete)\|uniformly random]] bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

	There is a distinction between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite ([[Las Vegas algorithm]]s, for example [[Quicksort]]<ref>{{Cite journal\|last=Hoare\|first=C. A. R.\|date=July 1961\|title=Algorithm 64: Quicksort\|journal=Commun. ACM\|volume=4\|issue=7\|pages=321–\|doi=10.1145/366622.366644\|issn=0001-0782}}</ref>), and algorithms which have a chance of producing an incorrect result ([[Monte Carlo algorithm]]s, for example the Monte Carlo algorithm for the [[Minimum feedback arc set\|MFAS]] problem<ref>{{Cite journal\|last=Kudelić\|first=Robert\|date=2016-04-01\|title=Monte-Carlo randomized algorithm for minimal feedback arc set problem\|journal=Applied Soft Computing\|volume=41\|pages=235–246\|doi=10.1016/j.asoc.2015.12.018}}</ref>) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem.<ref>"In [[primality test\|testing primality]] of very large numbers chosen at random, the chance of stumbling upon a value that fools the [[Fermat primality test\|Fermat test]] is less than the chance that [[cosmic radiation]] will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." [[Hal Abelson]] and [[Gerald J. Sussman]] (1996). ''[[Structure and Interpretation of Computer Programs]]''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>		There is a distinction between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite ([[Las Vegas algorithm]]s, for example [[Quicksort]]<ref>{{Cite journal\|last=Hoare\|first=C. A. R.\|date=July 1961\|title=Algorithm 64: Quicksort\|journal=Commun. ACM\|volume=4\|issue=7\|pages=321–\|doi=10.1145/366622.366644\|issn=0001-0782}}</ref>), and algorithms which have a chance of producing an incorrect result ([[Monte Carlo algorithm]]s, for example the Monte Carlo algorithm for the [[Minimum feedback arc set\|MFAS]] problem<ref>{{Cite journal\|last=Kudelić\|first=Robert\|date=2016-04-01\|title=Monte-Carlo randomized algorithm for minimal feedback arc set problem\|journal=Applied Soft Computing\|volume=41\|pages=235–246\|doi=10.1016/j.asoc.2015.12.018}}</ref>) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem.<ref>"In [[primality test\|testing primality]] of very large numbers chosen at random, the chance of stumbling upon a value that fools the [[Fermat primality test\|Fermat test]] is less than the chance that [[cosmic radiation]] will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." [[Hal Abelson]] and [[Gerald J. Sussman]] (1996). ''[[Structure and Interpretation of Computer Programs]]''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2] {{Webarchive\|url=https://web.archive.org/web/20060903155101/http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 \|date=2006-09-03 }}.</ref>

	In common practice, randomized algorithms are approximated using a [[pseudorandom number generator]] in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator.		In common practice, randomized algorithms are approximated using a [[pseudorandom number generator]] in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator.
Line 67:		Line 67:

	=== Sorting ===		=== Sorting ===
	[[Quicksort]] was discovered by [[Tony Hoare]] in 1959, and subsequently published in 1961.<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 64: Quicksort \|url=https://dl.acm.org/doi/10.1145/366622.366644 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321 \|doi=10.1145/366622.366644 \|issn=0001-0782\|url-access=subscription }}</ref> In the same year, Hoare published the [[Quickselect\|quickselect algorithm]],<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 65: find \|url=https://dl.acm.org/doi/10.1145/366622.366647 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321–322 \|doi=10.1145/366622.366647 \|issn=0001-0782\|url-access=subscription }}</ref> which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.<ref>{{Cite journal \|last1=Blum \|first1=Manuel \|last2=Floyd \|first2=Robert W. \|last3=Pratt \|first3=Vaughan \|last4=Rivest \|first4=Ronald L. \|last5=Tarjan \|first5=Robert E. \|date=August 1973 \|title=Time bounds for selection \|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339 \|journal=Journal of Computer and System Sciences \|language=en \|volume=7 \|issue=4 \|pages=448–461 \|doi=10.1016/S0022-0000(73)80033-9}}</ref>		[[Quicksort]] was discovered by [[Tony Hoare]] in 1959, and subsequently published in 1961.<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 64: Quicksort \|url=https://dl.acm.org/doi/10.1145/366622.366644 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321 \|doi=10.1145/366622.366644 \|issn=0001-0782\|url-access=subscription }}</ref> In the same year, Hoare published the [[Quickselect\|quickselect algorithm]],<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 65: find \|url=https://dl.acm.org/doi/10.1145/366622.366647 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321–322 \|doi=10.1145/366622.366647 \|issn=0001-0782\|url-access=subscription }}</ref> which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.<ref>{{Cite journal \|last1=Blum \|first1=Manuel \|last2=Floyd \|first2=Robert W. \|last3=Pratt \|first3=Vaughan \|last4=Rivest \|first4=Ronald L. \|last5=Tarjan \|first5=Robert E. \|date=August 1973 \|title=Time bounds for selection \|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339 \|journal=Journal of Computer and System Sciences \|language=en \|volume=7 \|issue=4 \|pages=448–461 \|doi=10.1016/S0022-0000(73)80033-9\|url-access=subscription }}</ref>

	=== Number theory ===		=== Number theory ===
Line 78:		Line 78:
	Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<ref name=":0" /> In 1979, Carter and Wegman introduced [[Universal hashing\|universal hash functions]],<ref>{{Cite journal \|last1=Carter \|first1=J. Lawrence \|last2=Wegman \|first2=Mark N. \|date=1979-04-01 \|title=Universal classes of hash functions \|journal=Journal of Computer and System Sciences \|language=en \|volume=18 \|issue=2 \|pages=143–154 \|doi=10.1016/0022-0000(79)90044-8 \|issn=0022-0000\|doi-access=free }}</ref> which they showed could be used to implement chained hash tables with constant expected time per operation.		Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<ref name=":0" /> In 1979, Carter and Wegman introduced [[Universal hashing\|universal hash functions]],<ref>{{Cite journal \|last1=Carter \|first1=J. Lawrence \|last2=Wegman \|first2=Mark N. \|date=1979-04-01 \|title=Universal classes of hash functions \|journal=Journal of Computer and System Sciences \|language=en \|volume=18 \|issue=2 \|pages=143–154 \|doi=10.1016/0022-0000(79)90044-8 \|issn=0022-0000\|doi-access=free }}</ref> which they showed could be used to implement chained hash tables with constant expected time per operation.

	Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the [[Bloom filter]].<ref>{{Cite journal \|last=Bloom \|first=Burton H. \|date=July 1970 \|title=Space/time trade-offs in hash coding with allowable errors \|journal=Communications of the ACM \|volume=13 \|issue=7 \|pages=422–426 \|doi=10.1145/362686.362692 \|s2cid=7931252 \|issn=0001-0782\|doi-access=free }}</ref> In 1989, [[Raimund Seidel]] and [[Cecilia R. Aragon]] introduced a randomized balanced search tree known as the [[treap]].<ref>{{Cite book \|last1=Aragon \|first1=C.R. \|last2=Seidel \|first2=R.G. \|title=30th Annual Symposium on Foundations of Computer Science \|chapter=Randomized search trees \|date=October 1989 ~~\|chapter-url=https://ieeexplore.ieee.org/document/63531~~ \|pages=540–545 \|doi=10.1109/SFCS.1989.63531\|isbn=0-8186-1982-1 }}</ref> In the same year, [[William Pugh (computer scientist)\|William Pugh]] introduced another randomized search tree known as the [[skip list]].<ref>[[William Pugh (computer scientist)\|Pugh, William]] (April 1989). ''[http://drum.lib.umd.edu/handle/1903/542 Concurrent Maintenance of Skip Lists]'' (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.</ref>		Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the [[Bloom filter]].<ref>{{Cite journal \|last=Bloom \|first=Burton H. \|date=July 1970 \|title=Space/time trade-offs in hash coding with allowable errors \|journal=Communications of the ACM \|volume=13 \|issue=7 \|pages=422–426 \|doi=10.1145/362686.362692 \|s2cid=7931252 \|issn=0001-0782\|doi-access=free }}</ref> In 1989, [[Raimund Seidel]] and [[Cecilia R. Aragon]] introduced a randomized balanced search tree known as the [[treap]].<ref>{{Cite book \|last1=Aragon \|first1=C.R. \|last2=Seidel \|first2=R.G. \|title=30th Annual Symposium on Foundations of Computer Science \|chapter=Randomized search trees \|date=October 1989 \|pages=540–545 \|doi=10.1109/SFCS.1989.63531\|isbn=0-8186-1982-1 }}</ref> In the same year, [[William Pugh (computer scientist)\|William Pugh]] introduced another randomized search tree known as the [[skip list]].<ref>[[William Pugh (computer scientist)\|Pugh, William]] (April 1989). ''[http://drum.lib.umd.edu/handle/1903/542 Concurrent Maintenance of Skip Lists]'' (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.</ref>

	=== Implicit uses in combinatorics ===		=== Implicit uses in combinatorics ===
Line 157:		Line 157:

	==Derandomization==		==Derandomization==
	{{~~Unreferenced~~\|section\|date=~~September 2023~~}}		{{More citations needed\|section\|date=August 2025}}

	Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible).<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|last1=Luby \|first1=Michael \|last2=Wigderson \|first2=Avi \|date=July 1995 \|publisher=University of California at Berkeley \|location=USA}}</ref> It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time.<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref> For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]],<ref name=":2" /> i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.		Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible).<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|last1=Luby \|first1=Michael \|last2=Wigderson \|first2=Avi \|date=July 1995 \|publisher=University of California at Berkeley \|location=USA}}</ref> It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time.<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref> For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]],<ref name=":2" /> i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

Line 164:		Line 163:
	* the [[method of conditional probabilities]], and its generalization, [[pessimistic estimator]]s		* the [[method of conditional probabilities]], and its generalization, [[pessimistic estimator]]s
	* [[discrepancy theory]] (which is used to derandomize geometric algorithms)		* [[discrepancy theory]] (which is used to derandomize geometric algorithms)
	* the exploitation of limited independence in the random variables used by the algorithm, such as the [[pairwise independence]] used in [[universal hashing]]		* the exploitation of limited independence in the random variables used by the algorithm, such as the [[pairwise independence]] used in [[universal hashing]]<ref>{{Cite journal \|last1=Chazelle \|first1=B. \|last2=Friedman \|first2=J. \|date=1990-09-01 \|title=A deterministic view of random sampling and its use in geometry \|url=https://doi.org/10.1007/BF02122778 \|journal=Combinatorica \|language=en \|volume=10 \|issue=3 \|pages=229–249 \|doi=10.1007/BF02122778 \|issn=1439-6912\|url-access=subscription }}</ref>
	* the use of [[expander graph]]s (or [[disperser]]s in general) to ''amplify'' a limited amount of initial randomness (this last approach is also referred to as generating [[pseudorandom]] bits from a random source, and leads to the related topic of pseudorandomness)		* the use of [[expander graph]]s (or [[disperser]]s in general) to ''amplify'' a limited amount of initial randomness (this last approach is also referred to as generating [[pseudorandom]] bits from a random source, and leads to the related topic of pseudorandomness)
	* changing the randomized algorithm to use a [[hash function]] as a source of randomness for the algorithm's tasks, and then derandomizing the algorithm by [[brute-force search\|brute-forcing]] all possible parameters (seeds) of the hash function. This technique is usually used to exhaustively search a sample space and making the algorithm deterministic (e.g. randomized graph algorithms)		* changing the randomized algorithm to use a [[hash function]] as a source of randomness for the algorithm's tasks, and then derandomizing the algorithm by [[brute-force search\|brute-forcing]] all possible parameters (seeds) of the hash function. This technique is usually used to exhaustively search a sample space and making the algorithm deterministic (e.g. randomized graph algorithms)

imported>Nubzor: Reverted edits by 2409:40F2:2016:1A91:181D:F5FF:FE51:B916 (talk) (HG) (3.4.13)

2025-06-21T17:33:04Z

Reverted edits by 2409:40F2:2016:1A91:181D:F5FF:FE51:B916 (talk) (HG) (3.4.13)

← Previous revision	Revision as of 17:33, 21 June 2025
(No difference)

imported>OAbot: Open access bot: url-access updated in citation with #oabot.

2025-06-19T20:53:12Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 20:53, 19 June 2025
Line 67:		Line 67:

	=== Sorting ===		=== Sorting ===
	[[Quicksort]] was discovered by [[Tony Hoare]] in 1959, and subsequently published in 1961.<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 64: Quicksort \|url=https://dl.acm.org/doi/10.1145/366622.366644 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321 \|doi=10.1145/366622.366644 \|issn=0001-0782}}</ref> In the same year, Hoare published the [[Quickselect\|quickselect algorithm]],<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 65: find \|url=https://dl.acm.org/doi/10.1145/366622.366647 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321–322 \|doi=10.1145/366622.366647 \|issn=0001-0782}}</ref> which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.<ref>{{Cite journal \|last1=Blum \|first1=Manuel \|last2=Floyd \|first2=Robert W. \|last3=Pratt \|first3=Vaughan \|last4=Rivest \|first4=Ronald L. \|last5=Tarjan \|first5=Robert E. \|date=August 1973 \|title=Time bounds for selection \|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339 \|journal=Journal of Computer and System Sciences \|language=en \|volume=7 \|issue=4 \|pages=448–461 \|doi=10.1016/S0022-0000(73)80033-9}}</ref>		[[Quicksort]] was discovered by [[Tony Hoare]] in 1959, and subsequently published in 1961.<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 64: Quicksort \|url=https://dl.acm.org/doi/10.1145/366622.366644 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321 \|doi=10.1145/366622.366644 \|issn=0001-0782\|url-access=subscription }}</ref> In the same year, Hoare published the [[Quickselect\|quickselect algorithm]],<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 65: find \|url=https://dl.acm.org/doi/10.1145/366622.366647 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321–322 \|doi=10.1145/366622.366647 \|issn=0001-0782\|url-access=subscription }}</ref> which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.<ref>{{Cite journal \|last1=Blum \|first1=Manuel \|last2=Floyd \|first2=Robert W. \|last3=Pratt \|first3=Vaughan \|last4=Rivest \|first4=Ronald L. \|last5=Tarjan \|first5=Robert E. \|date=August 1973 \|title=Time bounds for selection \|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339 \|journal=Journal of Computer and System Sciences \|language=en \|volume=7 \|issue=4 \|pages=448–461 \|doi=10.1016/S0022-0000(73)80033-9}}</ref>

	=== Number theory ===		=== Number theory ===
Line 74:		Line 74:

	=== Data structures ===		=== Data structures ===
	One of the earliest randomized data structures is the [[hash table]], which was introduced in 1953 by [[Hans Peter Luhn]] at [[IBM]].<ref name=":0">{{Cite book \|last=Knuth \|first=Donald E. \|url=https://dl.acm.org/doi/10.5555/280635 \|title=The art of computer programming, volume 3: (2nd ed.) sorting and searching \|date=1998 \|publisher=Addison Wesley Longman Publishing Co., Inc. \|isbn=978-0-201-89685-5 \|location=USA \|pages=536–549 }}</ref> Luhn's hash table used chaining to resolve collisions and was also one of the first applications of [[Linked list\|linked lists]].<ref name=":0" /> Subsequently, in 1954, [[Gene Amdahl]], [[Elaine M. McGraw]], [[Nathaniel Rochester (computer scientist)\|Nathaniel Rochester]], and [[Arthur Samuel (computer scientist)\|Arthur Samuel]] of [[IBM Research]] introduced [[linear probing]],<ref name=":0" /> although [[Andrey Ershov]] independently had the same idea in 1957.<ref name=":0" /> In 1962, [[Donald Knuth]] performed the first correct analysis of linear probing,<ref name=":0" /> although the memorandum containing his analysis was not published until much later.<ref>[[Donald Knuth\|Knuth, Donald]] (1963), ''[https://web.archive.org/web/20160303225949/http://algo.inria.fr/AofA/Research/11-97.html Notes on "Open" Addressing]'', archived from the original on 2016-03-03</ref> The first published analysis was due to Konheim and Weiss in 1966.<ref>{{Cite journal \|last1=Konheim \|first1=Alan G. \|last2=Weiss \|first2=Benjamin \|date=November 1966 \|title=An Occupancy Discipline and Applications \|url=http://dx.doi.org/10.1137/0114101 \|journal=SIAM Journal on Applied Mathematics \|volume=14 \|issue=6 \|pages=1266–1274 \|doi=10.1137/0114101 \|issn=0036-1399}}</ref>		One of the earliest randomized data structures is the [[hash table]], which was introduced in 1953 by [[Hans Peter Luhn]] at [[IBM]].<ref name=":0">{{Cite book \|last=Knuth \|first=Donald E. \|url=https://dl.acm.org/doi/10.5555/280635 \|title=The art of computer programming, volume 3: (2nd ed.) sorting and searching \|date=1998 \|publisher=Addison Wesley Longman Publishing Co., Inc. \|isbn=978-0-201-89685-5 \|location=USA \|pages=536–549 }}</ref> Luhn's hash table used chaining to resolve collisions and was also one of the first applications of [[Linked list\|linked lists]].<ref name=":0" /> Subsequently, in 1954, [[Gene Amdahl]], [[Elaine M. McGraw]], [[Nathaniel Rochester (computer scientist)\|Nathaniel Rochester]], and [[Arthur Samuel (computer scientist)\|Arthur Samuel]] of [[IBM Research]] introduced [[linear probing]],<ref name=":0" /> although [[Andrey Ershov]] independently had the same idea in 1957.<ref name=":0" /> In 1962, [[Donald Knuth]] performed the first correct analysis of linear probing,<ref name=":0" /> although the memorandum containing his analysis was not published until much later.<ref>[[Donald Knuth\|Knuth, Donald]] (1963), ''[https://web.archive.org/web/20160303225949/http://algo.inria.fr/AofA/Research/11-97.html Notes on "Open" Addressing]'', archived from the original on 2016-03-03</ref> The first published analysis was due to Konheim and Weiss in 1966.<ref>{{Cite journal \|last1=Konheim \|first1=Alan G. \|last2=Weiss \|first2=Benjamin \|date=November 1966 \|title=An Occupancy Discipline and Applications \|url=http://dx.doi.org/10.1137/0114101 \|journal=SIAM Journal on Applied Mathematics \|volume=14 \|issue=6 \|pages=1266–1274 \|doi=10.1137/0114101 \|issn=0036-1399\|url-access=subscription }}</ref>

	Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<ref name=":0" /> In 1979, Carter and Wegman introduced [[Universal hashing\|universal hash functions]],<ref>{{Cite journal \|last1=Carter \|first1=J. Lawrence \|last2=Wegman \|first2=Mark N. \|date=1979-04-01 \|title=Universal classes of hash functions \|journal=Journal of Computer and System Sciences \|language=en \|volume=18 \|issue=2 \|pages=143–154 \|doi=10.1016/0022-0000(79)90044-8 \|issn=0022-0000\|doi-access=free }}</ref> which they showed could be used to implement chained hash tables with constant expected time per operation.		Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<ref name=":0" /> In 1979, Carter and Wegman introduced [[Universal hashing\|universal hash functions]],<ref>{{Cite journal \|last1=Carter \|first1=J. Lawrence \|last2=Wegman \|first2=Mark N. \|date=1979-04-01 \|title=Universal classes of hash functions \|journal=Journal of Computer and System Sciences \|language=en \|volume=18 \|issue=2 \|pages=143–154 \|doi=10.1016/0022-0000(79)90044-8 \|issn=0022-0000\|doi-access=free }}</ref> which they showed could be used to implement chained hash tables with constant expected time per operation.

imported>WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2025-02-19T18:46:59Z

v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

Show changes