# Questions tagged [randomized-algorithms]

Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.

36 questions
Filter by
Sorted by
Tagged with
7k views

### How to prove correctness of a shuffle algorithm?

I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased). The first method I use is to construct the entire list of elements and ...
• 1,538
4k views

### Sorting algorithms which accept a random comparator

Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the ...
• 1,538
1k views

### Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
• 4,895
384 views

### Why is the probability used in the definition of RP complexity classes, arbitrary?

I was looking at the following wikipedia article on the RP complexity class: https://en.wikipedia.org/wiki/RP_(complexity) In its definition it states: If the correct answer is NO then it always ...
344 views

### FPT algorithm for a variant of Feedback Vertex Set

I am interested in a variant of the Feedback Vertex Set (FVS) problem. For an undirected graph $G$ and $k\in \mathbb{N}$ we need to decide if there is a subset $S \subseteq V(G)$ of size at most $k$ s....
• 203
743 views

• 143
1 vote
688 views

### Is there a software algorithm that can generate a non-deterministic chaos pattern?

Is there a software algorithm can generate a non-deterministic pattern or sequence? In Chaos theory, simple processes can create deterministic patterns, and psudo-random number generators can generate ...
• 121
1 vote
222 views

### General approach to randomized algorithm for equality problem

Using randomized approach we can guarantee that the equality problem has O(1) complexity (in communication). With other definitions of of equality (not strictly equal), is there a general approach to ...
1 vote
468 views

### Can BPP be bounded around any constant other than 1/2?

A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. ...
• 1,299
Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...