Talk:Randomized algorithm - Revision history

Cewbot: Maintain {{WPBS}}: 2 WikiProject templates. Remove 1 deprecated parameter: field.

2024-03-09T04:02:11Z

Maintain {{WPBS}}: 2 WikiProject templates. Remove 1 deprecated parameter: field.

← Previous revision		Revision as of 04:02, 9 March 2024
Line 2:		Line 2:
	{{WikiProject banner shell\|class=C\|		{{WikiProject banner shell\|class=C\|
	{{WikiProject Computer science\|importance=High}}		{{WikiProject Computer science\|importance=High}}
	{{WikiProject Mathematics\|priority=Mid~~\|field=discrete~~}}		{{WikiProject Mathematics\|priority=Mid}}
	}}		}}
	{{todo}}		{{todo}}

Qwerfjkl (bot): Implementing WP:PIQA (Task 26)

2024-02-20T14:35:04Z

Implementing WP:PIQA (Task 26)

← Previous revision		Revision as of 14:35, 20 February 2024
Line 1:		Line 1:
	{{Talk header\|search_term=(randomized OR probabilistic) (algorithm OR algorithms)}}		{{Talk header\|search_term=(randomized OR probabilistic) (algorithm OR algorithms)}}
	~~{{WikiProjectBannerShell\|~~{{WikiProject ~~Computer~~ ~~science~~\|class=C\|~~importance=High}}~~		{{WikiProject banner shell\|class=C\|
			{{WikiProject Computer science\|importance=High}}
	{{~~maths~~ ~~rating\|class=C~~\|priority=Mid\|field=discrete}}}}		{{WikiProject Mathematics\|priority=Mid\|field=discrete}}
			}}
	{{todo}}		{{todo}}

David Eppstein: /* First algorithm */ r

2022-04-19T05:20:28Z

First algorithm: r

← Previous revision		Revision as of 05:20, 19 April 2022
Line 96:		Line 96:
	::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)		::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)
	:::I'm honestly pretty out of my depth here. I only came across this on recent changes patrol and saw someone doing their own research and replacing what looked like a well-sourced statement with an unsourced one. Sadly it's looking like this was probably a falsely sourced bit of content. I won't object to any further changes any of you implement.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 03:45, 19 April 2022 (UTC)		:::I'm honestly pretty out of my depth here. I only came across this on recent changes patrol and saw someone doing their own research and replacing what looked like a well-sourced statement with an unsourced one. Sadly it's looking like this was probably a falsely sourced bit of content. I won't object to any further changes any of you implement.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 03:45, 19 April 2022 (UTC)
			::::I restored the pointer to [[Pocklington's algorithm]], with a proper source (the one cited in the forum link). The other comments at the forum make me wary of stating outright that it is the first known randomized algorithm, but I did include a quote from the source suggesting that it may be. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 05:20, 19 April 2022 (UTC)

Fyrael: /* First algorithm */

2022-04-19T03:45:00Z

First algorithm

← Previous revision		Revision as of 03:45, 19 April 2022
Line 95:		Line 95:
	:Thanks for your help [[User:Swordyfish\|Swordyfish]] ([[User talk:Swordyfish\|talk]]) 22:11, 18 April 2022 (UTC)		:Thanks for your help [[User:Swordyfish\|Swordyfish]] ([[User talk:Swordyfish\|talk]]) 22:11, 18 April 2022 (UTC)
	::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)		::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)
			:::I'm honestly pretty out of my depth here. I only came across this on recent changes patrol and saw someone doing their own research and replacing what looked like a well-sourced statement with an unsourced one. Sadly it's looking like this was probably a falsely sourced bit of content. I won't object to any further changes any of you implement.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 03:45, 19 April 2022 (UTC)

David Eppstein: /* First algorithm */ 2c

2022-04-19T00:36:25Z

First algorithm: 2c

← Previous revision		Revision as of 00:36, 19 April 2022
Line 94:		Line 94:
	:So what should we do?		:So what should we do?
	:Thanks for your help [[User:Swordyfish\|Swordyfish]] ([[User talk:Swordyfish\|talk]]) 22:11, 18 April 2022 (UTC)		:Thanks for your help [[User:Swordyfish\|Swordyfish]] ([[User talk:Swordyfish\|talk]]) 22:11, 18 April 2022 (UTC)
			::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)

Swordyfish: /* First algorithm */ Reply

2022-04-18T22:11:09Z

First algorithm: Reply

← Previous revision		Revision as of 22:11, 18 April 2022
Line 87:		Line 87:

	{{ping\|Swordyfish}} after looking some myself, I see what you may be talking about on this stackexchange question: [https://cstheory.stackexchange.com/questions/12568/probabilistic-randomized-algorithms-before-modern-computer-science-appeared]. It seems like some actual qualified author is making the case for Pocklington. The problem is that it's rather difficult to cite. If we could find this "Factoring Integers before Computers" book then we'd be in business, but so far I can only find mentions of the publication. It would also help if anyone was able to verify what's in the "Closest point problems in computational geometry" source that we currently reference. Sadly that ref was added by an IP editor almost a decade ago.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 21:46, 18 April 2022 (UTC)		{{ping\|Swordyfish}} after looking some myself, I see what you may be talking about on this stackexchange question: [https://cstheory.stackexchange.com/questions/12568/probabilistic-randomized-algorithms-before-modern-computer-science-appeared]. It seems like some actual qualified author is making the case for Pocklington. The problem is that it's rather difficult to cite. If we could find this "Factoring Integers before Computers" book then we'd be in business, but so far I can only find mentions of the publication. It would also help if anyone was able to verify what's in the "Closest point problems in computational geometry" source that we currently reference. Sadly that ref was added by an IP editor almost a decade ago.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 21:46, 18 April 2022 (UTC)

			:Let me make two points in response:
			:(1) There is already a Wikipedia page for the Pocklington algorithm, and the Wikipedia page includes a trial-and-error step, which succeeds with 50% probability on each attempt (although that page could do a better job calling that out). So there is already clear precedent on Wikipedia for the history of the algorithm I am referring to.
			:(2) Regardless, it's just not okay to have the history in its current form, since nobody can reasonably claim that the first randomized algorithm was in the 1970s. (Rabin's algorithm was 1976, if it's the algorithm that is referred to on the Wikipedia page for the Closest Pair of Points problem). At the very least, Quicksort comes earlier (1961).
			:As I see it, the current form of the page is clearly wrong. And my proposed edit is backed up by the Wikipedia page for Pocklington's algorithm. But, no matter what, we need to do something about the current page.
			:So what should we do?
			:Thanks for your help [[User:Swordyfish\|Swordyfish]] ([[User talk:Swordyfish\|talk]]) 22:11, 18 April 2022 (UTC)

Fyrael: /* First algorithm */ new section

2022-04-18T21:46:23Z

First algorithm: new section

← Previous revision		Revision as of 21:46, 18 April 2022
Line 83:		Line 83:
	[[File:Information.svg\|30px]]		[[File:Information.svg\|30px]]
	A discussion is taking place to address the redirect [[:Adversarial input]]. The discussion will occur at [[Wikipedia:Redirects for discussion/Log/2021 May 13#Adversarial input]] until a consensus is reached, and readers of this page are welcome to contribute to the discussion. <!-- from Template:RFDNote --> [[User:KnowledgeablePersona\|KnowledgeablePersona]] ([[User talk:KnowledgeablePersona\|talk]]) 04:56, 13 May 2021 (UTC)		A discussion is taking place to address the redirect [[:Adversarial input]]. The discussion will occur at [[Wikipedia:Redirects for discussion/Log/2021 May 13#Adversarial input]] until a consensus is reached, and readers of this page are welcome to contribute to the discussion. <!-- from Template:RFDNote --> [[User:KnowledgeablePersona\|KnowledgeablePersona]] ([[User talk:KnowledgeablePersona\|talk]]) 04:56, 13 May 2021 (UTC)

			== First algorithm ==

			{{ping\|Swordyfish}} after looking some myself, I see what you may be talking about on this stackexchange question: [https://cstheory.stackexchange.com/questions/12568/probabilistic-randomized-algorithms-before-modern-computer-science-appeared]. It seems like some actual qualified author is making the case for Pocklington. The problem is that it's rather difficult to cite. If we could find this "Factoring Integers before Computers" book then we'd be in business, but so far I can only find mentions of the publication. It would also help if anyone was able to verify what's in the "Closest point problems in computational geometry" source that we currently reference. Sadly that ref was added by an IP editor almost a decade ago.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 21:46, 18 April 2022 (UTC)

KnowledgeablePersona: Notification: listing of :Adversarial input at WP:Redirects for discussion.

2021-05-13T04:56:30Z

Notification: listing of Adversarial input at WP:Redirects for discussion.

← Previous revision		Revision as of 04:56, 13 May 2021
Line 80:		Line 80:
	If not, exactly what is the difference between a probabilistic algorithm and a randomized algorithm?		If not, exactly what is the difference between a probabilistic algorithm and a randomized algorithm?
	--[[User:DavidCary\|DavidCary]] ([[User talk:DavidCary\|talk]]) 03:43, 26 December 2020 (UTC)		--[[User:DavidCary\|DavidCary]] ([[User talk:DavidCary\|talk]]) 03:43, 26 December 2020 (UTC)
			== "Adversarial input" listed at [[Wikipedia:Redirects for discussion\|Redirects for discussion]] ==
			[[File:Information.svg\|30px]]
			A discussion is taking place to address the redirect [[:Adversarial input]]. The discussion will occur at [[Wikipedia:Redirects for discussion/Log/2021 May 13#Adversarial input]] until a consensus is reached, and readers of this page are welcome to contribute to the discussion. <!-- from Template:RFDNote --> [[User:KnowledgeablePersona\|KnowledgeablePersona]] ([[User talk:KnowledgeablePersona\|talk]]) 04:56, 13 May 2021 (UTC)

DavidCary: /* probabilistic algorithm */ new section

2020-12-26T03:43:53Z

probabilistic algorithm: new section

← Previous revision		Revision as of 03:43, 26 December 2020
Line 70:		Line 70:

	However, this citation was misunderstood. The end of the paragraph is an example of a "non-algorithmic method" in the words of Cohen. It explains a ''pseudo-primality test'' (to test whether ''N'' is prime, test whether ''2<sup>N-1</sup> = 1 mod N'') which fails for ''N = 341'' for instance. This ''method'' indeed is not an algorithm. But it has nothing to do with a Monte Carlo algorithm! It uses no randomness, and consistently fails for some input. -- [[User:B!Gre\|B!Gre]] ([[User talk:B!Gre\|talk]]) 15:02, 2 September 2019 (UTC)		However, this citation was misunderstood. The end of the paragraph is an example of a "non-algorithmic method" in the words of Cohen. It explains a ''pseudo-primality test'' (to test whether ''N'' is prime, test whether ''2<sup>N-1</sup> = 1 mod N'') which fails for ''N = 341'' for instance. This ''method'' indeed is not an algorithm. But it has nothing to do with a Monte Carlo algorithm! It uses no randomness, and consistently fails for some input. -- [[User:B!Gre\|B!Gre]] ([[User talk:B!Gre\|talk]]) 15:02, 2 September 2019 (UTC)

			== probabilistic algorithm ==

			Today [[probabilistic algorithm]] is a redirect to [[randomized algorithm]].

			I feel that to comply with the [[WP:R#ASTONISH]] guideline,
			this article needs to specifically spell out the relationship between probabilistic algorithms and randomized algorithms.
			Are they the same (interchangeable synonyms)?
			If not, exactly what is the difference between a probabilistic algorithm and a randomized algorithm?
			--[[User:DavidCary\|DavidCary]] ([[User talk:DavidCary\|talk]]) 03:43, 26 December 2020 (UTC)

ProcBot: Task 7: Implement TfD

2020-12-01T09:23:28Z

Task 7: Implement TfD

← Previous revision		Revision as of 09:23, 1 December 2020
Line 1:		Line 1:
		⚫	{{Talk header\|search_term=(randomized OR probabilistic) (algorithm OR algorithms)}}
	{{WikiProjectBannerShell\|{{WikiProject Computer science\|class=C\|importance=High}}		{{WikiProjectBannerShell\|{{WikiProject Computer science\|class=C\|importance=High}}
	{{maths rating\|class=C\|priority=Mid\|field=discrete}}}}		{{maths rating\|class=C\|priority=Mid\|field=discrete}}}}
	{{todo}}		{{todo}}
⚫	{{~~findsourcesnotice~~\|(randomized OR probabilistic) (algorithm OR algorithms)}}

	==Comment on "Motivation"==		==Comment on "Motivation"==

← Previous revision		Revision as of 05:20, 19 April 2022
Line 96:		Line 96:
	::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)		::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)
	:::I'm honestly pretty out of my depth here. I only came across this on recent changes patrol and saw someone doing their own research and replacing what looked like a well-sourced statement with an unsourced one. Sadly it's looking like this was probably a falsely sourced bit of content. I won't object to any further changes any of you implement.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 03:45, 19 April 2022 (UTC)		:::I'm honestly pretty out of my depth here. I only came across this on recent changes patrol and saw someone doing their own research and replacing what looked like a well-sourced statement with an unsourced one. Sadly it's looking like this was probably a falsely sourced bit of content. I won't object to any further changes any of you implement.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 03:45, 19 April 2022 (UTC)
			::::I restored the pointer to [[Pocklington's algorithm]], with a proper source (the one cited in the forum link). The other comments at the forum make me wary of stating outright that it is the first known randomized algorithm, but I did include a quote from the source suggesting that it may be. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 05:20, 19 April 2022 (UTC)

← Previous revision		Revision as of 03:45, 19 April 2022
Line 95:		Line 95:
	:Thanks for your help [[User:Swordyfish\|Swordyfish]] ([[User talk:Swordyfish\|talk]]) 22:11, 18 April 2022 (UTC)		:Thanks for your help [[User:Swordyfish\|Swordyfish]] ([[User talk:Swordyfish\|talk]]) 22:11, 18 April 2022 (UTC)
	::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)		::At the very least, not counting sampling methods for estimating statistical information, the idea of approximately solving optimization problems by randomly sampling solutions and keeping the best sample found appears explicitly in "Algorithms for solving production-scheduling problems", Giffler & Thompson, 1960. (There's also much earlier work on algorithms with random data and on algorithms for generating random numbers, but that's different from the idea of using random methods for nonrandom inputs.) —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:36, 19 April 2022 (UTC)
			:::I'm honestly pretty out of my depth here. I only came across this on recent changes patrol and saw someone doing their own research and replacing what looked like a well-sourced statement with an unsourced one. Sadly it's looking like this was probably a falsely sourced bit of content. I won't object to any further changes any of you implement.[[User:Fyrael\| -- Fyrael]] ([[User talk:Fyrael\|talk]]) 03:45, 19 April 2022 (UTC)