Questions tagged [randomized-algorithms]
Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.
351
questions
25
votes
1answer
6k 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 ...
23
votes
7answers
9k 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 ...
22
votes
4answers
3k 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 ...
20
votes
3answers
604 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 \...
20
votes
1answer
550 views
Algorithm to chase a moving target
Suppose that we have a black-box $f$ which we can query and reset. When we reset $f$, the state $f_S$ of $f$ is set to an element chosen uniformly at random from the set $$\{0, 1, ..., n - 1\}$$ where ...
18
votes
2answers
8k views
What is the advantage of Randomized Quicksort?
In their book Randomized Algorithms, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set ...
18
votes
4answers
4k views
Simulate a fair die with a biased die
Given a biased $N$-sided die, how can a random number in the range $[1,N]$ be generated uniformly? The probability distribution of the die faces is not known, all that is known is that each face has a ...
asked Aug 25 '14 at 15:24
Gilles 'SO- stop being evil'
40.1k7 gold badges108 silver badges171 bronze badges
18
votes
1answer
370 views
Is there an O(n log n) algorithm for 4D line simplification?
The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are ...
16
votes
1answer
351 views
Lost in a “one directional” concert
You and a friend lost each other on the line to a concert, and neither is sure which of you is further ahead. Formally, each is at some integer coordinate and may only walk towards a higher coordinate ...
15
votes
2answers
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 ...
14
votes
4answers
2k views
Are there any algorithms or data structures that need to find the median value of a set?
I have been reading this book for my class, Randomized Algorithms. In this particular book, there is a whole section dedicated to finding the median of an array using random selection, that leads to a ...
14
votes
1answer
7k 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 ...
12
votes
3answers
2k views
Discrepancy between heads and tails
Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=\text{max}_i H_i$. Show ...
12
votes
2answers
473 views
Is this special case of a scheduling problem solvable in linear time?
Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number,...
11
votes
1answer
186 views
Sharp concentration for selection via random partitioning?
The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is:
Sample $n^{3/4}$ elements from $A$ with replacement into $B$
Sort $B$ and find the rank $|B|\pm \sqrt{n}$ ...
10
votes
3answers
2k 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 ...
10
votes
0answers
167 views
(Slightly) faster simulation of quantum Fourier transform
Suppose I want to write a classical software simulator of a quantum circuit with $N$ qubits. When it comes time to simulate the quantum Fourier transform I can evaluate all $2^N$ states to determine ...
9
votes
4answers
418 views
How to devise an algorithm to generate a random but valid train track layout?
I am wondering if I have quantity C of curved tracks and quantity S of straight tracks, how I could devise an algorithm, (computer assisted or not), to design a "random" layout using all of those ...
9
votes
2answers
979 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 ...
9
votes
1answer
220 views
Randomized Meldable Heap - Expected Height
Randomized Meldable Heaps have an operation "meld", which we then use to define all other operations, including insert.
The question is, what is an expected height of that tree with $n$ nodes?
...
8
votes
3answers
2k views
Problem with the pseudo random number generator One-Time-Pad
I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $...
8
votes
1answer
5k views
Algorithm to find all 2-hop neighbors lists in a graph
Given a graph $G = (V,E)$, where $|V| = n$. What is a fast algorithm for generating the collection of all 2-hop neighborhood lists of all nodes in $V$.
Naively, you can do that in $O(n^3)$. With ...
8
votes
2answers
285 views
Are randomized algorithms constructive?
From , the proofs by the probabilistic method are often said to be non-constructive.
However, a proof by probabilistic method indeed designs a randomized algorithm and uses it for proving existence. ...
8
votes
1answer
262 views
Is it possible to simulate a fair coin with a finite number of tossing of a biased one?
It is a classic problem to simulate a fair coin with a biased one.
According to Fair Coin (wiki),
John von Neumann gave the following procedure:
Toss the coin twice.
If the results match, start over,...
8
votes
3answers
468 views
Isn't polynomial identity testing over arithmetic *expressions* trivial?
Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
8
votes
1answer
738 views
Does a coin tossing algorithm terminate? [duplicate]
Suppose we have an algorithm like:
n = 0
REPEAT
c = randomInt(0,1)
n = n + 1
UNTIL (c == 0)
RETURN n
(Assumuing the random number generator produces "good" ...
8
votes
2answers
220 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 ...
8
votes
1answer
798 views
Randomized algorithm for 3SAT
There is a very simple randomized algorithm that, given a 3SAT, produces an assignment satisfying at least 7/8 of the clauses (in expectation): choose a random assignment. A random assignment ...
8
votes
1answer
184 views
Finding a maximal independent set in parallel
On a graph $G(V,E)$, we do the following process:
Initially, all nodes in $V$ are uncolored.
While there are uncolored nodes in $V$, each uncolored node does the following:
Selects a random real ...
8
votes
0answers
130 views
Compute the expected size of an approximation of vertex cover
Consider the following randomized approximation algorithm of vertex cover:
Input: A graph G = (V, E).
Output: A set $C_G \subseteq V$ a vertex cover of $G$.
The algorithm:
Set $C_G := \emptyset$.
...
7
votes
2answers
719 views
How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits?
A shuffling algorithm is supposed to generate a random permutation of a given finite set. So, for a set of size $n$, a shuffling algorithm should return any of the $n!$ permutations of the set ...
7
votes
2answers
241 views
Why is randomness a problem? (i.e. why do we care about derandomization?)
I'm reading Aaronson's survey on P vs. NP, and I've come to understand that in CS theory, people really care about derandomization results like P vs. BPP etc. My question is, what's the problem with ...
7
votes
1answer
680 views
Random restarts for unsatisfiable instances
In the worst case, Boolean satisfiability (assuming P!=NP) takes exponential time. Nonetheless, modern SAT solvers using variants of DPLL, are able to solve enough instances to be useful in practice.
...
7
votes
3answers
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 ...
7
votes
1answer
753 views
Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution
Let G = (V,E) be a unit-capacity graph with n vertices and m edges.
Let T denote all the spanning trees in G.
If we run Karger's algorithm, we will get a random spanning tree in T formed by the ...
7
votes
1answer
2k views
What does the “principle of deferred decisions” formally mean
I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my ...
7
votes
1answer
193 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 ...
7
votes
1answer
176 views
Why does PCP theorem imply that NP problems are hard to approximate?
What I only got currently from PCP theorem is that it needs at most $O(\log n)$ randomness and $O(1)$ query of proof to approximate. So how does this result relate to the fact that solution to NP ...
6
votes
4answers
2k views
The physical implementation of quantum annealing algorithm
From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum ...
6
votes
3answers
973 views
Relationship between Las Vegas algorithms and deterministic algorithms
I'm wondering why the following argument doesn't work for showing that the existence of a Las Vegas algorithm also implies the existence of a deterministic algorithm:
Suppose that there is a Las ...
6
votes
2answers
881 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 ...
6
votes
2answers
664 views
Randomized Rounding of Solutions to Linear Programs
Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global ...
6
votes
1answer
258 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 ...
6
votes
2answers
992 views
Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?
I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether
$$AB = C$$
and be correct with high probability.
The algorithm choose a random $r$ n-...
6
votes
1answer
1k views
Why does the Count-Min Sketch require pairwise independent hash functions?
The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream. Intuitively, it works by picking a variety of hash functions, hashing each ...
6
votes
1answer
106 views
Completeness of formal definition of 'hardness on the average'
While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for ...
6
votes
1answer
928 views
Generate a random graph with geometrical degree distribution
I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper.
We are talking about generating an undirected graph in a slightly different way ...
6
votes
2answers
194 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 ...
6
votes
1answer
165 views
Streaming algorithm and random access
Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least
one duplicate number, i.e., a number that appears at least twice. I want output some duplicate ...
6
votes
1answer
494 views
The Power of Randomized Reduction
I try to figure out a redundant power of two-sided error randomized Karp - reduction.
It's well known fact and it is relatively hard to show that BPP is reducible by a one-sided error randomized Karp-...
