Probabilistic algorithms

Question 1

Probabilistic quick sort algorithm (idea)

Answer 1

Pick a random index as the pivot point of the algorithm. Recursively do this until the sorting is done.

Question 2

Probabilistic quick sort algorithm (run time)

Answer 2

We got a runtime that in the bad case in avarage is O(nlogn) where the bad cases are negligible. Inn the regular sort the bad case of O(n^2) is not negligible.

Question 3

Random min cut (idea)

Answer 3

Choose a random edge, and combine the two vertices into one. Do this until you are left with only two nodes. (The graph will include multiple edges going from one node to the other, that will be the min cut)

Question 4

Random min cut (accuracy)

Answer 4

In one run the algorithm has a (2/(n^2)) chance of getting it right. if you run it ((n^2)/2) times, it has a a chance of being wrong that is smaller than 1/e .

Question 5

Las Vegas algorithm

Answer 5

A probabilistic algorithm, that is never wrong and the run time is calculated by the expectation (תוחלת)

Question 6

Monte Carli algorithm

Answer 6

A probabilistic algorithm that might be wrong. You can mitigate this by running multiple times. The run time isn’t random.

Question 7

Matrix multiplication determinition (idea and run time)

Answer 7

Choose a random 1d vector x and multiply both sides ABx=Cx. If ABx≠Cx the for sure AB≠C. But if ABx=Cx then there is a 50% chance that AB=C. Run this multiple times each time choosing a new random vector. Runtime is O(n^2)

Question 8

AKS algorithm

Answer 8

Ann algorithm for accurately determining if a number is prime in O(n^6)

Question 9

Fermat’s Little Theorem

Answer 9

If p is a prime number, for any integer a: a^p = a%p

Question 10

The Miller Rabin primality test

Answer 10

Given a number p, pick a random integer a, and test if a^p = a%p. If not then p is for sure not prime else it might be. do this k times to control the mistake probability. There is a 4^(-k) probability for false positive. O(n^3) time (n number of digits)