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
6
votes
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-...
5
votes
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 ...
5
votes
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 ...
5
votes
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 ...
5
votes
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 ...
5
votes
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 ...
5
votes
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, ...
5
votes
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 ...
5
votes
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 ...
5
votes
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. ...
5
votes
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 ...
5
votes
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?
5
votes
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 ...
5
votes
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 ...
5
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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. ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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$ ...
4
votes
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: ...
4
votes
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 ...
4
votes
2answers
65 views

Why is tabulated hashing 3-wise independent but not 4-wise independent?

Tabulated hashing uses tables of random numbers to compute hash values. Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $...
4
votes
1answer
47 views

How to approach analysis of randomized algorithm

Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any ...
4
votes
1answer
53 views

Speaking of “randomness” in computing terms, to what sense can any extant digital processor make “random” results?

From a very strictly adhering sense to the hardware and circuit-level operations of any standard (non-specialized, DSPs, or supercomputing systems, etc.) microprocessor follow very similar, almost ...
4
votes
1answer
64 views

Las Vegas algorithm for finding 00000 in bit string

Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). ...
4
votes
1answer
51 views

Marginal Probability of Generating a Tree

Fix some finite graph $G = (V, E)$, and some vertex $x$. Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows: Let $T_0 = \{ x \}$. For $0 < n \leqslant N$ i. Let ...
4
votes
3answers
927 views

Algorithms for procedural generated mazes

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important). There are many Maze generation algorithms, but they only work on a ...
4
votes
1answer
503 views

Comparing A* search to Simulated Annealing

Good Afternoon, I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my ...
4
votes
1answer
111 views

Using Chebyshev to derive an upper bound for Coupon Collecter's Problem

I'm TA'ing a course and have trouble solving an exercise. Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E[...
4
votes
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 ...
4
votes
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. ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ~...
4
votes
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 ...
3
votes
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 ...
3
votes
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: ...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...

1
2
3 4 5
8