# Tag Info

## Hot answers tagged randomized-algorithms

### Can we generate random numbers using irrational numbers like π and e?

For any reasonable definition of perfect, the mechanism you describe is not a perfect random number generator. Non-repeating isn't enough. The decimal number $0.101001000100001\dots$ is non-repeating ...
• 80.2k

### Can we generate random numbers using irrational numbers like π and e?

It is cryptographically useless because an adversary can predict every single digit. It is also very time consuming.
• 25.2k

### How can I quickly judge whether matrix A is the inverse matrix of B?

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random ...
• 616
Accepted

### Can we generate random numbers using irrational numbers like π and e?

The most obvious disadvantage is the unnecessary complexity of PRNG algorithms based on irrational numbers. They require much more computations per generated digit than, say, an LCG; and this ...
Accepted

### Are there any algorithms or data structures that need to find the median value of a set?

if there are any practical applications of this algorithm in the domain of computer science besides being a theoretical improvement The application of this algorithm is trivial - you use it whenever ...
• 9,612
Accepted

### Problem with the pseudo random number generator One-Time-Pad

You seem to have misunderstood what the key is. In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver. For OTP, the key is the ...
• 80.2k

### Are there any algorithms or data structures that need to find the median value of a set?

Median filtering is common in reduction of certain types of noise in image processing. Especially salt and pepper noise. It works by picking out the median value in each color channel in each local ...
• 231
Accepted

### Does a coin tossing algorithm terminate?

The formal, unambiguous way to state this is “terminates with probability 1” or “terminates almost surely”. In probability theory, “almost” means “with probability 1”. For a probabilistic Turing ...
Accepted

### Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$...
• 141k

### Problem with the pseudo random number generator One-Time-Pad

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator No, no and once again no. I'm concerned that this is what you're being taught. The absolutely fundamental ...
• 1,582
Accepted

• 80.2k
Accepted

### Choosing a random bit from a bitmap

There is a simple $O(n)$ algorithm using the technique of reservoir sampling. Keep a currently selected element $x$ (initially, none). Go over all bits in the file in order. When seeing the $m$th zero,...
• 270k
Accepted

### Why is ZPP = RP ∩ co-RP?

The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though. Markov's inequality ...
• 4,747
Accepted

### Why is randomness a problem? (i.e. why do we care about derandomization?)

Complexity theory is a mathematical theory which aims at addressing one shortcoming of computability theory, namely, it takes into account the use of resources. While it is true that in its early days ...
• 270k

### Why shuffling by picking random position in all array instead of a part is not correct

Suppose that the array has length $n$. Since you are making $n$ random choices of numbers from 1 to $n$, the probability to obtain any specific permutation is of the form $A/n^n$, for some integer $A$....
• 270k
Accepted

### Random restarts for unsatisfiable instances

There is some research in this area. In The Effect of Restarts on the Efficiency of Clause Learning Jinbo Huang shows empirically that restarts improve a solver's performance over suites of both ...
• 7,843
Accepted

• 936
Accepted

### Understanding Expected Running Time of Randomized Algorithms

There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time ...
• 270k
Accepted

### Random algorithm termination

The question "Does it terminate?" isn't well-formed. You need to define more precisely what you mean by that question before it can be answered. Is it guaranteed to terminate on all possible ...
• 141k

### Choosing error rates for probabilistic algorithms

This is the arithmetic for Juho's answer. (Run it for the length of time it takes to make the algorithm failure probability equal the hardware failure probability). Suppose it takes time $t$ seconds ...
Accepted

### Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution

You should show that at each step, both algorithms select an edge with the same probability distribution. For example, the first edge that is contracted by Karger's algorithm is a uniformly random ...
• 270k

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

No, there is no algorithm that shuffles an array of length $n > 2$ using a bounded number of random Booleans. This is because given an algorithm that uses $m$ random bits (at most), each outcome ...
• 270k

### Isn't polynomial identity testing over arithmetic *expressions* trivial?

For a univariate polynomial $p(x)$, yes, it's that easy. For a multivariate polynomial $p(x_1,x_2,\dots,x_k)$, no, no such algorithm works. In particular, when you write "a polynomial of degree $d$ ...
• 141k
Accepted

### How can Karger's algorithm (and other randomized algorithms) be used in practice?

Karger's algorithm is a randomized algorithm. It has a small probability of error, but that probability can be made arbitrarily (exponentially) small simply by repeating the approach. If we do one ...
• 141k
Accepted

### Randomized algorithm for 3SAT

The random assignment algorithm can be derandomized (made deterministic) using the method of conditional expectations. Let the 3SAT instance consist of clauses $C_1,\ldots,C_m$. During the algorithm ...
• 270k