49 votes

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 ...
user avatar
28 votes

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.
user avatar
  • 25.2k
25 votes

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 ...
user avatar
  • 616
18 votes
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 ...
user avatar
17 votes
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 ...
user avatar
  • 9,612
17 votes
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 ...
user avatar
13 votes

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 ...
user avatar
12 votes
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 ...
user avatar
12 votes
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$...
user avatar
  • 141k
11 votes

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 ...
user avatar
  • 1,582
11 votes
Accepted

Generating random words by grammar

Your process is a textbook example of a branching process. Starting with one $E$, we have an expected $3/2$ many $F$s, $9/4$ many $T$s, and so $9/8$ many remaining $E$s in expectation. Since $9/8 > ...
user avatar
10 votes

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

Computing medians is particularly important in randomized algorithms. Quite often, we have an approximation algorithm that, with probability at least $\tfrac34$, gives an answer within a factor of $1\...
user avatar
9 votes
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,...
user avatar
9 votes
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 ...
user avatar
  • 4,747
9 votes
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 ...
user avatar
9 votes

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$....
user avatar
9 votes
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 ...
user avatar
  • 7,843
8 votes
Accepted

Can someone explain LazySelect?

$\DeclareMathOperator{\rank}{rank}$Given a set $S$ of $n = 2k$ elements, the algorithm is aimed at finding the median of $S$ in linear time, with high probability. The idea is to find two elements $a,...
user avatar
8 votes
Accepted

Why is the probability used in the definition of RP complexity classes, arbitrary?

Yes, the constant is entirely arbitrary. Call an algorithm a $p$-algorithm if: When the correct answer is NO, it always answers NO. When the correct answer is YES, it answers YES with probability at ...
user avatar
8 votes

Are there adversarial inputs for randomized quicksort?

There are implementations of Quicksort (the partitioning algorithm, specifically) which deal badly with duplicates. No matter how much you randomize -- shuffling the input, random choice of the pivot, ...
user avatar
  • 70.9k
8 votes

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

tl;dr: You can make a rough probabilistic judgement in $O(1)$ time Let's assume you are willing to settle on a test which differentiates "good" matrices $A,B$ from "pretty bad" $A,...
user avatar
  • 936
7 votes
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 ...
user avatar
7 votes
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 ...
user avatar
  • 141k
7 votes

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 ...
7 votes
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 ...
user avatar
7 votes

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 ...
user avatar
7 votes

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$ ...
user avatar
  • 141k
7 votes
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 ...
user avatar
  • 141k
7 votes
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 ...
user avatar
7 votes

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

A pseudorandom generator is a deterministic algorithm, which given a short random seed returns a pseudorandom string fooling certain adversaries (i.e. such adversaries will not be able to distinguish ...
user avatar
  • 13.2k

Only top scored, non community-wiki answers of a minimum length are eligible