Questions tagged [randomized-algorithms]

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

Filter by
Sorted by
Tagged with
25 votes
1 answer
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 ...
edA-qa mort-ora-y's user avatar
22 votes
4 answers
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 ...
edA-qa mort-ora-y's user avatar
16 votes
2 answers
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 ...
Tim's user avatar
  • 4,895
6 votes
1 answer
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 ...
user1070241's user avatar
4 votes
0 answers
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....
JoshHalas's user avatar
  • 203
20 votes
3 answers
743 views

Problems in P with provably faster randomized algorithms

Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \...
aelguindy's user avatar
  • 1,797
14 votes
1 answer
8k views

Randomized Selection

The randomized selection algorithm is the following: Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$ Output: The the "rank $k$ element" of $A$ (i.e., the one in ...
Amumu's user avatar
  • 431
9 votes
2 answers
1k views

Is there a "sorting" algorithm which returns a random permutation when using a coin-flip comparator?

Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's ...
Joe's user avatar
  • 4,107
5 votes
1 answer
805 views

NP-complete decision problems - how close can we come to a solution?

After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
352 views

Random algorithm termination

Suppose I have an algorithm that works as follows when invoked: it calls itself recursively with probability $0 < p < 1$ and terminates with probability $1-p$. Does this algorithm terminate? On ...
hesson's user avatar
  • 151
3 votes
2 answers
534 views

Choosing error rates for probabilistic algorithms

Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ ...
David Richerby's user avatar
2 votes
2 answers
919 views

Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?

An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.) However, there are different kind of algorithms, such as deterministic, non-...
Tim's user avatar
  • 4,895
0 votes
2 answers
139 views

About the properties of the coresets in k-median clustering

I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is ...
user avatar
24 votes
7 answers
10k views

Can we generate random numbers using irrational numbers like π and e?

Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times ...
Abhradeep Sarkar's user avatar
10 votes
3 answers
3k views

Concrete understanding of difference between PP and BPP definitions

I am confused about how PP and BPP are defined. Let us assume $\chi$ is the characteristic function for a language $\mathcal{L}$. M be the probabilistic Turing Machine. Are the following definitions ...
DurgaDatta's user avatar
8 votes
3 answers
2k views

Constructing a random Hamiltonian Cycle (Secret Santa)

I was programming a little Secret Santa tool for my extended family's gift exchange. We had a few constraints: No recipients within the immediate family Nobody should get who they got last year The ...
Mark Peters's user avatar
8 votes
2 answers
255 views

Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square ...
Charlie Parker's user avatar
7 votes
1 answer
213 views

Sorting an unordered pile of items into drawers with minimal drawer movements

A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away. My wardrobe is set up as follows: My drawers are categorized by the type of ...
JesseTG's user avatar
  • 325
6 votes
2 answers
216 views

Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator

C++11 has a convenient Bernoulli RNG, illustrated at http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution . However, distilling an entire random integer into a single random bit ...
Igor Markov's user avatar
6 votes
2 answers
1k views

Example for a non-trivial PCP verifier for an NP-complete problem

During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating $\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$. I understand the ...
Raphael's user avatar
  • 72.4k
5 votes
1 answer
306 views

Existence of suitable pseudo-random number generators to derandomize BPP to P

I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other. My understanding is that if there is a suitably strong ...
PPenguin's user avatar
  • 327
4 votes
1 answer
496 views

Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
Juho's user avatar
  • 22.6k
4 votes
2 answers
897 views

Online generation of uniform samples

A source provides a stream of items $x_1, x_2,\dots$ . At each step $n$ we want to save a random sample $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ of size $k$, i.e. $S_n$ should be a uniformly chosen ...
user1374864's user avatar
4 votes
3 answers
1k views

Why shuffling by picking random position in all array instead of a part is not correct

There is a famous problem to generate a random permutation of elements in an array - it's called shuffling. My understanding of that problem is that I have to put every element in an array into a ...
Max Koretskyi's user avatar
3 votes
1 answer
141 views

Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement). On ...
chausies's user avatar
  • 532
2 votes
1 answer
992 views

Can an algorithm be truly non-deterministic?

I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the ...
Ajoy Bhatia's user avatar
2 votes
1 answer
1k views

Chernoff bounds and Monte Carlo algorithms

One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to ...
zpavlinovic's user avatar
  • 1,654
2 votes
0 answers
77 views

Using the random forest algorithm to predict vectors [duplicate]

I know this might sound like a newbie question, but bear with me. I have read a paper where researchers use a random forest to predict species distribution, but in their study, they only predict a ...
jeshaitan's user avatar
  • 173
1 vote
2 answers
3k views

Genetic Algorithm Minimum Population Size

Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.
Declan Murphy's user avatar
1 vote
1 answer
246 views

Color coding to get an FPT algoirthm for $k$ disjoint triangles

Consider the following problem: Input: A graph $G=(V,E)$ and an integer $k \in \mathbb{N}$ Output: Are there $k$ vertex-disjoint triangles in $G$? Assume we want to use color coding to develop an FPT ...
securitymensch's user avatar
1 vote
1 answer
198 views

Expected linear-time algorithm for finding MST with probability for sampling an edge other than 1/2

I'm trying to understand this algorithm : https://en.m.wikipedia.org/wiki/Expected_linear_time_MST_algorithm As described in the wiki article, it works in 5 steps to find the MSF for a graph $G = (V, ...
Baksel's user avatar
  • 143
1 vote
2 answers
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 ...
Chloe's user avatar
  • 121
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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. ...
e_noether's user avatar
  • 1,299
0 votes
1 answer
243 views

Random uniform sampling of position restricted permutations

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 ...
michal's user avatar
  • 103
-3 votes
1 answer
1k views

m-element random sample being equally likely ...(CLRS 5.3-7)? [closed]

I am trying to understand the following solution to CLRS 5.3-7: http://clrs.skanev.com/05/03/07.html Question description is on the page. I understood the part where m-element subset is constructed ...
Azfar Hussain's user avatar