Questions tagged [randomized-algorithms]

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

362 questions
Filter by
Sorted by
Tagged with
1answer
518 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-...
2answers
356 views

randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$

I'm trying to practice myself with random algorithms. Lets call a CNF formula over n variables s-formula if it is either unsatisable or it has at least $\frac{2^n}{n^{10}}$ satisfying assignments. I ...
1answer
431 views

Is this method really uniformly random?

I have a list and want to select a random item from the list. An algorithm which is said to be random: When you see the first item in the list, you set it as the selected item. When you see the ...
4answers
329 views

Is there a random shuffle algorithm using only true /false?

Is there a way to randomly shuffle an array using only a source of random boolean values? SO to clarify, shuffle using true /false only, and not integers or decimals. For this question, I'm ...
1answer
659 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 ...
1answer
86 views

Uniformly Random Nested Subset Pairs

Main Question We can represent subsets of a vector using, say, a bit mask. Let's say a nested subset is a pair of masks, for example ...
2answers
2k views

Optimal pivot selection for quick-sort

The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots. It is well known that picking a random pivot does not work as good as taking the median of three, ...
1answer
294 views

Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property: for every subset $W\subset V$ such ...
1answer
188 views

Why does a polytime hitting set generator derandomize RP?

I am reading Goldreich, Vadhan, Wigderson: Simplified Derandomization of BPP Using a Hitting Set Generator and trying to understand the result that polytime hitting set generators (HSGs) would not ...
2answers
203 views

Random generator considerations in the design of randomized algorithms

It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. Perfect random sources are unavailable in practice. ...
1answer
38 views

Is there a name for “yield first result parallel map”?

Context In randomized algorithms two schemes of computation are common: Las Vegas algorithms with random running time Randomized algorithms that have a probability of success, and have to be ...
1answer
77 views

Can we derandomize subexponential algorithms given P=BPP?

Under $BPP=P$ conjecture randomization does not have much power for poly time algorithms. Can we say the same about randomized subexp algorithms like number field sieve?
1answer
218 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 ...
1answer
264 views

Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to ...
1answer
1k views

Randomized quicksort expected running time analysis

I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis. Setting in CLRS First let $Z = \{z_1, ..., z_n\}$ be the set of elements of ...
2answers
1k views

Generating random words by grammar

A bit of context I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
3answers
742 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 ...
1answer
301 views

Choosing a random bit from a bitmap

Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so. I have quite a large bitmap (~100 Million bits) (e.g. ...
3answers
265 views

Book recommendations on the analysis of randomized algorithms

I would like to read some books (or any other material) that cover the design of randomized algorithms with a particular focus on the analysis. My main goal is to develop the rigour needed to ...
2answers
734 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 ...
2answers
315 views

Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers. A test solution is the sequence of answers $S\in[k]^N$. Given is a black box which receives a solution as input ...
2answers
688 views

From Whence the Randomization in Randomized Quicksort

Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph): Using a random number generator to choose the positions is ...
1answer
420 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 ...
1answer
36 views

Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?

Let $n, k > 0$ and $0 < m < nk$. I want to fill an $n$-length array $A$ with random integer values in the range $[0,k]$ such that $\sum_{i=0}^{n -1} A[i] = m$. Furthermore, all such arrays ...
2answers
99 views

On certificates in BPP (avoiding majority vote)

Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output. However if the problem $\Pi$ is also in $NP$ ...
1answer
470 views

What is the approximation ratio of this randomized algorithm for finding matchings?

I would like to analyze the following algorithm in terms of its approximation ratio. Here is the algorithm: ...
1answer
146 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
2answers
65 views

1answer
78 views

Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
1answer
108 views

Pseudo-random role assignment

I have a number of players, ranging from [0..N]. Each round every player is assigned a specific role, either 1, 2 or 3. ...
1answer
45 views

Logarithmic guarantees for randomized search trees

In this paper [1], "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being ...
1answer
761 views

Building ideal skip lists

I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list. The definition of an “ideal skip list” is that in the first level we'll have all the ...
0answers
48 views

Karger's min-cut (contraction): Combinatorial argument for success probability?

The contraction algorithm for min-cut is: pick an edge $(u,v)$ uniformly at random, and "contract" it by merging $u$ and $v$ into a single vertex, deleting self-loops. Continue until two vertices ...
0answers
57 views

Randomized algorithm to compute cover radius?

I am self-study the book "Geometric Approximation Algorithms" by Sariel Har-Peled. And I stuck on a problem and don't know how to start it. Let $C$ and $P$ be two sets of point in the plane , such ...
0answers
190 views

Data structures for ordering noisy data

In a certain robotics application, I encountered a problem in which we need to determine the order of positions of several robots on $\mathbb{R}$. Each measurement that we take of robot positions is ...
0answers
56 views

Status of Research Problems in Motwani and Raghavan

One nice aspect of Motwani and Raghavan's classic textbook, Randomized Algorithms, is that the notes for many chapters include open questions marked as "research problems." However, the textbook is ~...
1answer
102 views

How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
3answers
2k views

Efficient n-choose-k random sampling

Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)? I have read this question but it asks for generations of all combinations, not ...
1answer
687 views

Expected length of a random walk on a line

I am given the following randomized algorithm for SAT, Input: A satisfiable CNF-formula $\varphi$. Output: An assignment $\rho$, such that $\rho \models \varphi$. The algorithm works as follow: ...
2answers
266 views

Shuffling a file on disk using $O(\log n)$ memory

How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place? If the file had size $2^m$, then we can first split the file ...
1answer
263 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 ...
1answer
6k views

Understanding Expected Running Time of Randomized Algorithms

I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random ...
3answers
226 views

Selecting random points at general position

How will you find a random collection of $n$ points in the plane, all with integer coordinates in a specified range (e.g. -1000 to 1000), such that no 3 of them are on the same line? The following ...