We’re rewarding the question askers & reputations are being recalculated! Read more.

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
2
votes
1answer
119 views

Using Yao's principle to find a lower bound

This is a HW question, so I'm not expecting any answers, just a general guidance/help. Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\...
0
votes
1answer
340 views

Hiring problem from CLRS

Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions. However, for Exercise question 5.2-2 my solution deviates from the one given in the ...
0
votes
1answer
39 views

Monte-Carlo Algorithm for counting 'on' bits in a binary array

Given a Monte-Carlo algorithm (called A) that given a binary array with b 'on' bits (one-bits) returns a, where in a probability of 1/2: $\frac b 3 \leq a \leq 3b$ How can I use A to build an ...
1
vote
0answers
55 views

Finding subset of integer summing up above threshold

Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such ...
1
vote
1answer
57 views

Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle. We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
2
votes
1answer
117 views

Show that RP is closed under concatenation

I'm trying to prove the following problem: Show that $RP$ is closed under concatenation Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the ...
6
votes
1answer
176 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 ...
5
votes
1answer
695 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 ...
1
vote
1answer
46 views

number of random sets needed to generate subset

Let $A\subseteq \{1\ldots n\}$ with $|A|=\alpha n, 0<\alpha\leq1$. Now we start generating random sets $B_i \subseteq \{1\ldots n\}$ with $|B_i|=\beta n$ where $0<\beta\leq\alpha$. How many $...
2
votes
1answer
519 views

Average case of simple algorithm like binary search

These questions is about one of my research. As I am not a computer scientist, formal answering is difficult to me. I have a special search algorithm which the explanation here will take a lot of ...
1
vote
0answers
35 views

Generate a random tree population

Given a unbalanced k-ary tree base (with internal nodes that represent operators and leafs representing values) from the space of all unbalanced k-ary trees ...
1
vote
0answers
93 views

Generate higher dimensional pink noise

1D Pink noise, is easy enough to generate. See https://www.dsprelated.com/showarticle/908.php for example. What about higher-dimensional pink noise, such as 2D or 3D pink noise? Is there an algorithm ...
2
votes
2answers
60 views

Question about Morris' algorithm

I am reading the lecture notes. I am trying to understand Morris' algorithm on page 2. The Morris' algorithm is as follows. Problem: Given an input stream $\sigma$, compute (or approximate) its ...
0
votes
2answers
100 views

Defining decision-problem complexity classes by counting branches of a polynomial-time NTM

This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) ...
2
votes
0answers
33 views

Sorting Algorithm: Probability Bound For Randomized Inversion Swapping

Let $A = (a_1, a_2, \dots, a_n)$ denote an array of distinct values with an order defined. Consider the following randomized sorting algorithm. Let $m := 0$. Select a pair $(i, j)$ with $1 \le i < ...
2
votes
1answer
203 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 ...
2
votes
1answer
165 views

Weighted probability using Huffman Tree

I want to produce a value from a set, where each value has an associated weight. Eg: [(1, 4), (2, 3), (3, 3)] should give me a 40% chance of picking 1, and a 30%...
4
votes
1answer
35 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 ...
2
votes
0answers
316 views

How much better are conservative updates for count-min sketch?

I've been reading about count-min sketch and I'm interested in the performance of this data structure when doing conservative updates. To my understanding from the Wikipedia article, conservative ...
2
votes
2answers
53 views

Limit repetitions in randomized list with each unique element occurring n times

I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row. So with elements [0,1,2] n = ...
2
votes
1answer
330 views

Generating uniformly random bits from a stream of arbitrarily biased bits

Say we have a function called GenBiasedBit. This function returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. How could I ...
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 $...
3
votes
1answer
64 views

How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?

I'm considering the following definition of one-way functions: Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is ...
-1
votes
1answer
516 views

Applying a Chernoff bound with Only an Upper Bound of the Expectation

First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case. The ...
4
votes
1answer
36 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 ...
2
votes
2answers
607 views

What is the difference between Simulated Annealing and Monte-Carlo Simulations?

What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?
0
votes
1answer
41 views

Probability that a leaf with 1 will be selected in game tree evaluation

I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar). ...
3
votes
2answers
265 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 ...
1
vote
1answer
40 views

Coloring a cubic-graph with 2 colors

Given a cubic graph, I want to color its vertices in 2 colors (Say A & B). A vertex is considered "Good" iff the majority of its neighbors is colored differently than that vertex. (For example, ...
3
votes
1answer
140 views

non-binary locality-sensitive hashing with random projections

I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to ...
3
votes
2answers
516 views

how to bound the probability that quicksort takes greater than n lg n time?

I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed) Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > ...
2
votes
1answer
90 views

Why doesn't this put $BPP$ in $NP$?

From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$ From Adleman we know $x\in L(M)...
1
vote
0answers
57 views

Randomized Algorithm for determining items with rank $\geq n/16$

Problem: We say that an item $x$ is of rank $m$ if there are $m$ items in the set less than $x$. Design a randomized algorithm to find all of the items in a set of size $n$ with rank greater than $\...
2
votes
0answers
173 views

How do I do a biased shuffling of a deck of cards?

I currently have a deck of cards (in fact this deck is an array of sorted elements in descending order as indicated by the picture above), that I want to shuffle. However, the caveat is that I want ...
2
votes
1answer
365 views

Randomized vs deterministic approach for multiset equality

Let $S_1$ and $S_2$ are two multi sets. We want to find, Is $S_1 =S_2$? Algo 1: Sort $S_1$ and $S_2$ and then check $S_1 = S_2$ Running time : $O(n \log {n})$, where $n$ is the size of the multi ...
1
vote
3answers
120 views

Finding one of 2/3 of all array elements in constant expected time

How do I go about designing a constant time algorithm which satisfies the following I/O requirements: Input: an array $A$ of length $3n$, containing $2n$ values of the symbol $X$ and $n$ of the ...
2
votes
2answers
408 views

Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes

I want to compute the median in an array of size $m$ which consists of distinct integers from $\{0, 1, ..., n-1\}$, I have $m<n$. By median I mean the middle element (rounding up/down if the array ...
1
vote
0answers
46 views

Proving a randomized algorithm that sums array elements

I am trying to prove the following algorithm to be correct: ...
0
votes
2answers
64 views

Quick sort analysis confusion

Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input? Let say A1 = [1,2,3,4,5] , A2 = [5,2,3,4,1] A3 = [5,4,3,2,1] , Will the randomized ...
3
votes
1answer
64 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. ...
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 ...
4
votes
1answer
308 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 ...
2
votes
1answer
59 views

Choosing $n$ points to get the closest sum

Let's say there is a set of $N$ real numbers, $x_i, i\in\{1,2,...,N\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, ...
0
votes
0answers
238 views

How to prove the correctness of inside-out shuffle algorithm

I've read this similar question How to prove correctness of a shuffle algorithm? and I understand the answer. However I still couldn't figure out how to apply that inductive proof to a similar shuffle ...
1
vote
1answer
111 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 ...
1
vote
1answer
39 views

Algorithm to estimate the probability that a “0 and 1 matrix” fills up following the bootstrap percolation rules

Presentation of the model: we consider the regular lattice created from $\mathbb{Z}^2$ (It's no more, no less a square lattice). At $t=0$, each site is said "active" independently with a probability $...
8
votes
1answer
530 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 ...
0
votes
1answer
218 views

Randomized linear search — Why does reducing the sample size make the running time constant?

I have two search algorithms (for determining if an element $x$ is in a list $A$ of length $n$): (1) Pick a random index $i$ from $L = [1, \ldots n]$. If $A[i] = x$, terminate. Otherwise, pick a new ...
1
vote
1answer
364 views

Algorithm to distribute elements evenly among a population

Algorithm to distribute elements evenly among a population In the software I am doing I have three different categories: ...
2
votes
1answer
210 views

Alternative definitions of ZPP and probabilistic Turing Machines

There are two ways to define a probabilistic Turing Machine: A Turing Machine that can toss coins during its computation. A deterministic Turing Machine that takes two inputs: $(x,r)$, where $x$ is ...