The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
3
votes
1answer
211 views

Proof of Randomized Self-Adjusting Binary Search Tree

I developed a randomized self-adjusting binary search tree years ago, which I called a shuffle tree, but was unable to ever have it published because my proofs were rejected (with little explanation). ...
3
votes
2answers
3k views

Turn biased random number generator into uniform

I'm looking at a problem in the book Introduction to Algorithms by Cormen et al. It says that if we are given a random number generator rand() which satisfies the distribution: $P(X = 0) = p,\;\;P(X=...
1
vote
2answers
1k views

Genetic Algorithm Minimum Population Size

Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.
2
votes
0answers
68 views

Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
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 ...
3
votes
1answer
211 views

Asymptotic expected runtime of Randomized Algorithm

I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties: Given input size $n$, with probability $3/4$ it moves on to solve an ...
5
votes
1answer
144 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 ...
7
votes
1answer
678 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 ...
2
votes
0answers
127 views

Message protocol to probabilistically infer missing object from Union of two subsets of a larger set

This was a challenge problem I read some time ago and just remembered it: Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect sets ...
8
votes
1answer
728 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" ...
-1
votes
1answer
41 views

Algorithm for random generation of two connected partitions of a finite set [closed]

Given the set $X=\{1,2,\ldots,n\}$; $\,\,$ $n=mp=kq$ where $m,k,p,q$ are positive integers. Please help me to programme an algorithm that realizes random generation of the following two partitions of ...
1
vote
1answer
247 views

Average Case runtime for random choice search

Assuming we have an array with $n$ Elements and want to find an unique element by randomly (uniformly) choosing. What would be the average case runtime? My thoughts so far: The chance to find the ...
3
votes
2answers
546 views

Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?

An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.) However, there are different kind of algorithms, such as deterministic, non-...
1
vote
1answer
73 views

Randomized agorithm for selecting a $m$-subset out of a $n$-set

The question has been discussed here but unfortunately is closed. Reference : m-element random sample being equally likely ...(CLRS 5.3-7)? My question is as follows. Suppose $n = 5, m = 3$. This ...
3
votes
1answer
71 views

Understanding the flaw in a proof attempt of the Communication Complexity of Equality

I'm new to communication theory and I've been wondering where the following simple argument fails: Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
1
vote
0answers
64 views

Using “incremental algorithms” to find the $k^{th}$ smallest number

This is what I vaguely understand of what an "incremental algorithm" is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the ...
0
votes
0answers
166 views

Randomized algorithm to make a Binary Search Tree from an array of $n$ distinct elements

An array $\mathcal{A}$ of $n$ distinct integers $\{a_1,a_2,\ldots,a_n\}$ is given. I'm asked to design a randomized (esp. Las Vegas) algorithm to make a Binary Search Tree out of these elements, such ...
4
votes
0answers
53 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 ~...
17
votes
4answers
3k 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 ...
2
votes
2answers
349 views

Choosing error rates for probabilistic algorithms

Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ ...
1
vote
1answer
75 views

Name for class of algorithms preserving accuracy/confidence

I am considering the following class of algorithms: The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input. The answer of procedure $f$ (we may assume it is ...
1
vote
1answer
98 views

Understanding Property Testing with a toy example

I am newbie with this property testing and I am trying to understand it with a few examples. I first dealt with a toy example. I did not understand the first step of the test in the following slide. ...
-3
votes
1answer
776 views

m-element random sample being equally likely …(CLRS 5.3-7)? [closed]

I am trying to understand the following solution to CLRS 5.3-7: http://clrs.skanev.com/05/03/07.html Question description is on the page. I understood the part where m-element subset is constructed ...
-3
votes
1answer
694 views

Can someone explain LazySelect?

The LazySelect algorithm is given in these slides as follows. We have a set $S$ of $n = 2k$ distinct numbers and want to find the $k$th smallest element. Let $R$ be a set of $n^{3/4}$ elements ...
0
votes
2answers
84 views

Randomized Algorithm with matrices [closed]

We have two computers, Comp1 and Comp2, which hold binary matrices A and B of size $n\times n$. We want to check if the matrices of the computers are identical except for exactly 1 entry. Comp1 has ...
-1
votes
1answer
130 views

checking if there're equal bits in binary string [closed]

We have two binary strings, $X$ and $Y$, in two different computers. Both of them in length $n$. The computers can communicate by sending bits to each other. We have to build randomized algorithm to ...
0
votes
1answer
192 views

Do RP algorithms exist?

I think I understand the RP complexity class (along with coRP, BPP, and ZPP). However, I can't seem to think of how an RP algorithm might be formulated. How can the random coin flip possibilities ...
3
votes
1answer
217 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 ...
1
vote
2answers
384 views

Is there a software algorithm that can generate a non-deterministic chaos pattern?

Is there a software algorithm can generate a non-deterministic pattern or sequence? In Chaos theory, simple processes can create deterministic patterns, and psudo-random number generators can generate ...
2
votes
1answer
4k 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
1answer
748 views

Understanding Monte Carlo Probabilities

I am trying to get a good grasp on Monte Carlo (MC) algorithms, but I feel I am missing something fundamental. What I don't understand is how MC improves its confidence of giving the correct solution ...
18
votes
1answer
303 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 ...
2
votes
1answer
751 views

Expected maximum bin load, for balls in bins with equal number of balls and bins [closed]

Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is $\Theta(\ln n/\ln\ln n)$. How can we ...
2
votes
1answer
159 views

Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS?

In section 9.2 of CLRS (Introduction to Algorithms; page 185 in the 2nd edition and page 215 in the 3rd edition), a randomized selection algorithm is presented. For its analysis, $T(n)$ is a random ...
2
votes
2answers
103 views

Why can't we derandomize the PCP theorem by iterating over all possible $\log n$ random strings?

Let's say I can solve problem $A$ in polynomial time using only $\log n$ bits of randomness, with a $\ge \frac{2}{3}$ chance of a correct answer. Then surely I can solve $A$ determistically by ...
5
votes
1answer
407 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 ...
6
votes
3answers
853 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 ...
3
votes
3answers
220 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 ...
2
votes
1answer
123 views

Advantage of the Monte Carlo method over a regular periodic sampling [closed]

I am unclear on when to use the Monte Carlo random sampling method for algorithm design. The classic example that I keep seeing is using random points within some bounding rectangle to determine the ...
3
votes
1answer
549 views

Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG

I am somewhat confused with the running time analysis of a program here which has recursive calls which depend on a RNG. (Randomly Generated Number) Let's begin with the pseudo-code, and then I will ...
1
vote
1answer
67 views

Randomised Median [closed]

I have tried hard , but i'm unable to come up with the expected running time for the number of comparisons to find the Randomized Median (find the median of an unsorted array). Also i wanted to make ...
1
vote
1answer
35 views

Interpreting probabilistic time turning machines

I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better: $$ Pr_{r \in \{0,1\}^l}[A(r) = \text{"yes"}]$$ Where r is ...
5
votes
1answer
532 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 ...
2
votes
1answer
779 views

Chernoff bounds and Monte Carlo algorithms

One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to ...
0
votes
2answers
991 views

Algorithm for sorting with constraints

I've got 30 elements which has to be grouped/sorted into 10 ordered 3-tuple. There are several rules and constraints about grouping/sorting. For example: Element $A$ must not be in the same tuple ...
6
votes
2answers
163 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 ...
0
votes
1answer
194 views

FFT for expanded form of equation multiplication

I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying? For example, if you are multiplying $...
3
votes
1answer
656 views

Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?

In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
6
votes
2answers
609 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 ...
6
votes
1answer
97 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 ...