Tagged Questions

An algorithm whose behaviour is determined by its input and a source of random numbers.

learn more… | top users | synonyms (1)

1
vote
1answer
24 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 ...
-1
votes
0answers
15 views

Markov Chain Monte Carlo Simulator Not Working [closed]

I'm trying to run a MC simulator for a Markov Chain that is uniformly distributed among all 50x50 matrices that have no neighboring 1's. My algo is supposed to fill up the state space by running the ...
2
votes
0answers
118 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 ...
7
votes
1answer
451 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
26 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
15 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 ...
0
votes
0answers
24 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.) Are nondeterministic algorithm algorithms on a deterministic Turing machine? ...
1
vote
1answer
31 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
30 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
28 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
2answers
65 views

Which type of randomized algorithm is best suited for web crawling?

I have decided to implement a web crawler for my CS major project. The project is focused towards adaptive search. I want the pages to be as user specific as possible and time efficiency is not much a ...
0
votes
0answers
71 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 ...
3
votes
0answers
36 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 ...
12
votes
4answers
206 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 ...
5
votes
2answers
101 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
60 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
59 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. ...
-4
votes
1answer
71 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
46 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
70 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
35 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
96 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 ...
1
vote
1answer
100 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
votes
1answer
36 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
46 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 ...
1
vote
1answer
111 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 ...
7
votes
0answers
64 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
130 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
42 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 ...
0
votes
0answers
24 views

Expected time taken to spread message in gossip-based protocol [closed]

A town has $N$ people. At Day 0, a person has a secret. At Day 1, he calls a random person and tells him the secret. At Day 2, every person who knows the secret calls a person at random to tell the ...
2
votes
2answers
49 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 ...
4
votes
1answer
364 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 ...
4
votes
3answers
239 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
168 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
67 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
98 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
39 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
32 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 ...
4
votes
1answer
149 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
140 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 ...
-1
votes
2answers
104 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
85 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
105 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 ...
2
votes
1answer
141 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
175 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 ...
5
votes
1answer
66 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 ...
2
votes
1answer
102 views

Interpretation of “expected cost” of an algorithm

I'm studying randomized algorithms and I sometimes come across results like (1) The algorithm has an expected $O(f(n))$ cost. and (2) With constant probability, the cost is bounded by ...
5
votes
0answers
77 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 ...
2
votes
1answer
57 views

BPP upper bound

does $BPP\subseteq P^{NP}$ ? it seems reasonable but I don't know if there is a proof of this!could any one post a proof or any material that discusses the statement or something that look like this . ...
4
votes
2answers
273 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 ...