Randomized algorithms

Question 1

Why might it be useful to design an algorithm that is allowed to make random decisions?

Answer 1

• by allowing randomization we make our underlying model more powerful*
• It may be conceptually much simpler*
• it may allow the algorithm to function while maintaining very little internal state or memory of the past*

Question 2

Matrix Identification problem

You are given 3 matrices A,B,C: nxn

• Decide whether AB!=C
• Trivial solution: compute and validate - O(n^3)
• What is the randomized approach?

Answer 2

• The algorithm is based on the fact that if AB=C then for any vector v, (AB)v=Cv.*
• We randomize a boolean vector {n}, and validate the equality.*
• For a vector to mislead us, we need to have Dv=(AB-C)v=0, where D!=0. For that to happen we need to check how many vectors at most might possibly nullify D.*
• the proof for the probability of at least 1/2 for success is attached.*
• We can further improve the algorithm by perfoming it k times. Having the chance of failure to drop from at most 1/2 to at most (1/2)^k*

Question 3

Important point

• when we consider the running-time of arithmetic operations we must ask ourselves how many bits require to hold the input.*
• If the input is a sequence of n bits, AKA, a number within the interval [0,2^n-1], we need O(n) bits/registers to hold the number. Thus it takes O(n) for each arithmetic operation.*

Question 4

Two useful facts:

First:

• Let w<2^n be a natural number.
• the number of primes dividing w does not exceed..

Second:

• For any natural number t, the number of primes smaller than t is not less than…

Answer 4

First fact

• The answer is n.
• The smallest prime is 2. If w is the prodcut of 2^n we reach 2^n>w.

Second fact

• The answer is t/logt

Question 5

• Representing natural number i requires [log(i)] bits
• Arithmatic operations for number which can be represented in 64bit register take O(1)
• There exists a randomized algorithm which outputs prime q in O(log^4(n), where n is the length of the interval.

Answer 5

Question 6

we perform mod q after each multiplication

Horner’s method tell us we can compute polynomial in O(n) step.

Thus the total time of the following computation is O(n), where the length of the input is log(q).

That is, we perform O(n) operations that take log(q), which is O(1) because the size of the input is O(log(q)).