Randomized Algorithms Flashcards
What are randomized algorithms?
Randomized algorithms are algorithms that make random decisions during their process to solve computational problems.
What is the primary benefit of randomized algorithms?
Randomized algorithms may handle worst-case scenarios effectively and can simplify complex deterministic solutions.
How do randomized algorithms differ from average-case analysis?
Randomized algorithms make random internal decisions
What is the contention resolution problem?
A problem where multiple processes compete for a single shared resource and need to resolve conflicts to access it.
What is the randomized algorithm for contention resolution?
Each process independently decides to attempt accessing the resource with a probability p in each round.
What is the probability of success for a process in contention resolution?
The probability is ( p(1-p)^{n-1} ) for n processes.
How is p optimized in contention resolution algorithms?
Set ( p = 1/n ) to maximize the success probability.
What is the expected time for a process to succeed in contention resolution?
( O(n \log n) ) rounds for all processes to succeed with high probability.
What is the contraction algorithm for finding minimum cuts?
A randomized algorithm that repeatedly contracts edges in a graph until only two nodes remain.
What is the probability that the contraction algorithm finds the minimum cut?
At least ( \frac{1}{n^2} ) for a graph with n nodes.
What is linearity of expectation?
The property that ( E[X+Y] = E[X] + E[Y] ) for any random variables X and Y
How is linearity of expectation used in randomized algorithms?
It allows breaking complex random variables into simpler ones and summing their expectations.
What is the coupon collector’s problem?
A problem asking how many trials are needed to collect all n types of coupons.
What is the expected number of trials in the coupon collector’s problem?
( nH(n) )
What is the probabilistic method?
A technique showing the existence of a structure by proving a random construction produces it with positive probability.
What is the approximation factor of the random assignment for MAX 3-SAT?
A random assignment satisfies at least ( \frac{7}{8} ) of the clauses in expectation.
How can the randomized algorithm for MAX 3-SAT be turned into a high-probability algorithm?
Repeat the random assignment process until a ( \frac{7}{8} ) satisfaction rate is achieved.
What does the union bound state?
The probability of the union of events is at most the sum of their probabilities.
How is the union bound applied in contention resolution?
It provides an upper bound for the probability that not all processes succeed.
What is the harmonic number ( H(n) )?
The sum ( H(n) = 1 + 1/2 + 1/3 + … + 1/n )
What does it mean for events to be independent?
Two events E and F are independent if ( Pr[E \cap F] = Pr[E] \cdot Pr[F] ).
What is the expected value of the number of trials to get the first success?
( 1/p )
What is the role of randomization in symmetry breaking?
Randomization allows processes to independently make decisions
How is the contraction algorithm’s success probability amplified?
Run the algorithm ( O(n^2 \log n) ) times and take the best result to achieve high probability of finding the minimum cut.
Explain the term ‘expected value’ in probability.
The average value a random variable takes over many trials
How is probability used to analyze algorithm performance?
By calculating the likelihood of events and their expected outcomes under random choices.
Why is randomization beneficial in distributed systems?
It reduces explicit communication and coordination while managing contention among processes.
Explain the MAX 3-SAT problem.
An optimization problem where the goal is to satisfy the maximum number of clauses in a 3-SAT formula.
What is the probabilistic guarantee for random assignment in MAX 3-SAT?
It satisfies at least ( \frac{7}{8} ) of the clauses in expectation.
Give an example of using the probabilistic method in algorithms.
Proving that a random assignment satisfies ( \frac{7}{8} ) of the clauses in any 3-SAT instance.
