Randomized Algorithms

Question 1

What are randomized algorithms?

Answer 1

Randomized algorithms are algorithms that make random decisions during their process to solve computational problems.

Question 2

What is the primary benefit of randomized algorithms?

Answer 2

Randomized algorithms may handle worst-case scenarios effectively and can simplify complex deterministic solutions.

Question 3

How do randomized algorithms differ from average-case analysis?

Answer 3

Randomized algorithms make random internal decisions

Question 4

What is the contention resolution problem?

Answer 4

A problem where multiple processes compete for a single shared resource and need to resolve conflicts to access it.

Question 5

What is the randomized algorithm for contention resolution?

Answer 5

Each process independently decides to attempt accessing the resource with a probability p in each round.

Question 6

What is the probability of success for a process in contention resolution?

Answer 6

The probability is ( p(1-p)^{n-1} ) for n processes.

Question 7

How is p optimized in contention resolution algorithms?

Answer 7

Set ( p = 1/n ) to maximize the success probability.

Question 8

What is the expected time for a process to succeed in contention resolution?

Answer 8

( O(n \log n) ) rounds for all processes to succeed with high probability.

Question 9

What is the contraction algorithm for finding minimum cuts?

Answer 9

A randomized algorithm that repeatedly contracts edges in a graph until only two nodes remain.

Question 10

What is the probability that the contraction algorithm finds the minimum cut?

Answer 10

At least ( \frac{1}{n^2} ) for a graph with n nodes.

Question 11

What is linearity of expectation?

Answer 11

The property that ( E[X+Y] = E[X] + E[Y] ) for any random variables X and Y

Question 12

How is linearity of expectation used in randomized algorithms?

Answer 12

It allows breaking complex random variables into simpler ones and summing their expectations.

Question 13

What is the coupon collector’s problem?

Answer 13

A problem asking how many trials are needed to collect all n types of coupons.

Question 14

What is the expected number of trials in the coupon collector’s problem?

Answer 14

( nH(n) )

Question 15

What is the probabilistic method?

Answer 15

A technique showing the existence of a structure by proving a random construction produces it with positive probability.

Question 16

What is the approximation factor of the random assignment for MAX 3-SAT?

Answer 16

A random assignment satisfies at least ( \frac{7}{8} ) of the clauses in expectation.

Question 17

How can the randomized algorithm for MAX 3-SAT be turned into a high-probability algorithm?

Answer 17

Repeat the random assignment process until a ( \frac{7}{8} ) satisfaction rate is achieved.

Question 18

What does the union bound state?

Answer 18

The probability of the union of events is at most the sum of their probabilities.

Question 19

How is the union bound applied in contention resolution?

Answer 19

It provides an upper bound for the probability that not all processes succeed.

Question 20

What is the harmonic number ( H(n) )?

Answer 20

The sum ( H(n) = 1 + 1/2 + 1/3 + … + 1/n )

Question 21

What does it mean for events to be independent?

Answer 21

Two events E and F are independent if ( Pr[E \cap F] = Pr[E] \cdot Pr[F] ).

Question 22

What is the expected value of the number of trials to get the first success?

Answer 22

( 1/p )

Question 23

What is the role of randomization in symmetry breaking?

Answer 23

Randomization allows processes to independently make decisions

Question 24

How is the contraction algorithm’s success probability amplified?

Answer 24

Run the algorithm ( O(n^2 \log n) ) times and take the best result to achieve high probability of finding the minimum cut.

Question 25

Explain the term ‘expected value’ in probability.

Answer 25

The average value a random variable takes over many trials

Question 26

How is probability used to analyze algorithm performance?

Answer 26

By calculating the likelihood of events and their expected outcomes under random choices.

Question 27

Why is randomization beneficial in distributed systems?

Answer 27

It reduces explicit communication and coordination while managing contention among processes.

Question 28

Explain the MAX 3-SAT problem.

Answer 28

An optimization problem where the goal is to satisfy the maximum number of clauses in a 3-SAT formula.

Question 29

What is the probabilistic guarantee for random assignment in MAX 3-SAT?

Answer 29

It satisfies at least ( \frac{7}{8} ) of the clauses in expectation.

Question 30

Give an example of using the probabilistic method in algorithms.

Answer 30

Proving that a random assignment satisfies ( \frac{7}{8} ) of the clauses in any 3-SAT instance.