Talk:Randomized algorithm

Computer science Start‑class High‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Start

This article has been rated as Start-class on Wikipedia's content assessment scale.

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

Comment on "Motivation"

"Find an 'a' in the array" is not an output. Possible outputs would be a boolean (" 'a' found") or 'a' itself.

"findingA_LV(array A, n)" has no output.

The behaviour of "findingA_MC(array A, n, k)" is independent of 'a'.

I am not editing because I do not know what is intended, am ignorant of the subject, which is why I looked this up.

Merger proposal

Needs to be merged with randomized algorithms. Fredrik 09:33, 10 Mar 2004 (UTC)

Possible minor mistake in the Miller-Rabin primality test ?

Shouldn't the probability in the article: (3/4)¹⁰⁰ be (1/4)¹⁰⁰, according to the 3 propositions of the Miller-Rabin test, since the probability of not picking a witness each iteration is 1/4?

Yes, it should have been (1/4)¹⁰⁰. Corrected now. Andris 15:29, Jun 28, 2004 (UTC)

Nonterminating "algorithm"?

I am told by my theoretical Computer Science teacher that an algorithm is not an algorithm if it doesn't end (please see the wikipedia page about Algorithm: "given an initial state, will terminate in a corresponding recognizable end-state". So the side-note "(possibly nonterminating) algorithm" doesn't make sense. But I don't know enough about this to make an edit.

No, algorithms that do not terminate are still algorithms.

There are two possible definitions of the term 'probabilistic algorithm'. See my addition to the intro section and cited books. Qwertyus (talk) 00:50, 28 April 2009 (UTC)[reply]

pseudorandom number generator?

In the first paragraph, the sentence: this means that the machine implementing the algorithm has access to a pseudorandom number generator. - does it really matter if the random number generator is pseodorandom? Would an algorithm which used a Hardware random number generator, not be classed as a randomized algorithm? If so, then this line should be changed to ' a source of random numbers'...

The statement was oddly placed and unclear; it said "in common practice" and is describing how they're typically implemented, as opposed to defining "randomized algorithm." In fact, a program based on a PRNG isn't a randomized algorithm at all but a deterministic approximation of one, so this was quite misleading. Dcoetzee 04:30, 4 December 2008 (UTC)[reply]

Where randomness helps

Another example that could be added to the list Randomized algorithm#Where randomness helps: Symmetry breaking in distributed computing. As a trivial example, leader election in a symmetric, anonymous network is impossible without randomness. — Miym (talk) 00:04, 29 November 2009 (UTC)[reply]

Relevance of Prisoner's Dilemma

I don't pretend to have a deep understanding of randomized algorithms, but the invocation of the Prisoner's Dillema in the "Motivation" section makes little sense to me: "Randomized algorithms are particularly useful when faced with a malicious "adversary" or attacker who deliberately tries to feed a bad input to the algorithm (see worst-case complexity and competitive analysis (online algorithm)) such as in the Prisoner's dilemma." I don't think the Prisoner's Dilemma is at all an example of what the sentence is talking about (another party passing particular data to an algorithm, hoping to make it work as hard as possible). Am I missing something? Dindon (talk) 04:58, 16 December 2009 (UTC)[reply]

Motivation

I don't understand why the Monte Carlo algorithm does not care about finding an 'a' and how we'd use it in practice. Should we always run it k times in a row and then have a look at what has been found (after each iteration? or just at the k^th)? Or is a stop condition based on the value selected at each iteration missing?134.58.45.79 (talk) 15:27, 22 September 2010 (UTC)[reply]