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
24
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 ...
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 ...
21
votes
6answers
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 ...
20
votes
3answers
552 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
510 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 ...
19
votes
1answer
341 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 ...
18
votes
2answers
7k 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 ...
16
votes
1answer
345 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 ...
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
2answers
988 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
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
439 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
181 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}$ ...
9
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 ...
9
votes
4answers
392 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
910 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
209 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? ...
9
votes
0answers
163 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 ...
8
votes
1answer
4k 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
277 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
3answers
455 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
733 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
211 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
712 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
181 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
118 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
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 $...
7
votes
2answers
658 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
1answer
203 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,...
7
votes
2answers
218 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
632 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
1answer
714 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
181 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
168 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
897 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
796 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
606 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
230 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
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 ...
6
votes
2answers
848 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
102 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
872 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
184 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
157 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
447 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-...

1
2 3 4 5
7