19-08-2014, 12:46 PM
REISCHUK’S RANDOMIZED ALGORITHM SEMINAR REPORT
REISCHUK’S RANDOMIZED.docx (Size: 26.38 KB / Downloads: 39)
ABSTRACT
A randomized algorithm is defined as an algorithm that typically uses the random bits as an auxiliary input to guide its behavior. It achievs good performance in the "average case". Formally, the algorithm's performance will be a random variable determined by the random bits, with (hopefully) good expected value. The "worst case" is typically so unlikely to occur that it can be ignored.
We describe a probabilistic parallel algorithm to sort n keys drawn from some arbitrary total ordered set. This algorithm can be implemented on a parallel computer consisting of n RAMs, each with small private memory, and a common memory of size O(n) such that the average runtime is bounded by O(log n). Hence for this algorithm the product of time and number of processors meets the information theoretic lower bound for sorting.
An easy randomized algorithm can match the performance of a deterministic algorithm. For some problems, the best-known randomized algorithms are faster than the best-known deterministic algorithms. This is achieved by requiring that the correct answer be found only with high probability or that the algorithm should run in expected polynomial time.This means that the randomized algorithm may not find a correct answer in some cases ormay take very long time.Two types of Randomized Algorithms:
1. Las Vegas Algorithm
2. Monte Carlo Algorithm
MONTE CARLO ALGORITHM
The randomized algorithm runs for a fixed number of steps for each input andproduces an answer that is correct with a bounded probability. That is it may produceincorrect solution .It has a fixed deterministic running time. If the algorithm is runrepeatedly with independent random choices each time cision problems (problems for which the answer to an instance is YES orNO), there are two kinds of Monte Carlo algorithms: those with one-sided error, andthose with two-sided error. A Monte Carlo algorithm is said to have two-sided error ifthere is a non-zero probability that it errs when it outputs either YES or NO. It is said tohave one-sided error if the probability that it errs is zero for at least one of the possibleoutputs (YES / NO) that it produces
INTRODUCTION
An algorithm is any well-defined computational procedure that takes some values,
or set of values as input and produces some values or set of values as output. An
algorithm is thus a sequence of computational steps that transform the input into theoutput. A problem can be represented as a tuple, problem (instances, solutions). Whereinstances are the inputs to the problem and solutions are the outputs to the problem. Tosolve a problem we can use different algorithms. These algorithms differ dramatically intheir efficiency
RANDOMIZED ALGORITHM
A randomized algorithm is defined as an algorithm that is allowed to access a
source of independent, unbiased random bits, and it is then allowed to use these randombits to influence its computation.
Formally, the algorithm's performance will be a random variable determined by
the random bits, with (hopefully) good expected value. The "worst case" is typically sounlikely to occur that it can be ignored. Bounds on the performances of random
algorithms depend on their random choices and not on any assumptions about the inputs.It is important to distinguish this form of probabilistic analysis of an algorithm, in whichone assumes a distribution on the inputs and analyses an algorithm that may itself bedeterministic
SIMPLICITY OF RANDOMIZED ALGORITHM
This is the first and foremost reason for using randomizedalgorithms. There are numerous examples where an easy randomized algorithm canmatch (or even surpass) the performance of a deterministic algorithm.
Example: Sorting algorithms.
The Merge-Sort algorithm is asymptotically best deterministic algorithm. It is not
too hard to describe. However, the same asymptotic running time can be achieved by thesimple randomized Quick-sort algorithm. The algorithm picks a random element as apivot and partitions the rest of the elements: those smaller than the pivot and those biggerthan the pivot. Recurse on these two partitions. We will give the analysis of the runningtime later
RANDOMIZED MIN-CUT ALGORITHM
Let G = (V,E) be a connected , undirected multigraph with n vertices.Amultigragh may contain multiple edges between any pair of vertices.A cut in G is a setof edges whose removal results in G being broken into two or more components. A min-
cut is a cut of minimum cardinality. For instance, say this graph represents a network, andwe want to know how robust it is in the sense of the the minimum number of linkswhose failure causes the network to become disconnected.The minimum cut problem isto find a cut of minimum size.Min-cut algorithmAlgorithmMin-Cut
Input: Connected, undirected multigragh G(V,E).
Output: Size of the min-cut.
1. while |V| >= 2 do
2.Pick an edge e randomly and contract it.
3.Remove Self Loops.
4. end while
5. Return |E| ;
Once we have collapsed the first random edge, the rest of the algorithm proceeds
recursively on the remaining (n - 1)-node graph. Here is a lucky example.Page 14
Analysis
Look at what happens to the edges after they are contracted. They become selfloops and are removed. After the i-th iteration of the while loop, or the i-thcontraction,how many nodes remain: n - i. Let us assume that no minimum-cut edge got contracted.(We want to know what is the probability of this ™luckyevent™ happening) Each node inthe contracted graph has degree>= k (Why? Because contractions do not decrease themin-cut). Thus after the i-th iteration, the total number of edges in the graph is >=k(n-i)/2 .The probability q1of picking one of those k edges in the first merging step = k/(kn/2)= n/2 .The probability p1of not picking any of those k edges in the first merging step = (1-2/n)Repeat the same argument for the first n-2 merging steps.Probability p of not picking any of those k edges in all the merging steps= (1-2/n)(1-2/(n-1))(1-2/(n-2))¦(1-2/3)
Therefore, the probability of finding the min-cut:If we repeat the whole procedure n2/2 times, the probability of not finding themin-cut is atmost)1(23)...1()1)...(3)(2()321)...(121)(21(-=---=----=nnpenn/1)/21(2/22?.By this process of repetition, we have managed to reduce the probability of failurefrom 1-2/(n*2) to a more respectable 1/e. Further execution of the algorithm will makethe failure probability arbitrarily small-the only consideration being that repetitionsincrease the running time.Randomized Min-cut is a Monte Carlo Algorithm
COMPLEXITY CLASSES
A complexity class is a collection of languages all of whose recognition problemscan be solved under prescribed bounds on the computational resources. A languagerecognition problem is to decide whether a given string x in ?* belongs to L. Analgorithm solves a language recognition problem for a specific language L by accepting(output YES) any input string contained in L , and rejecting (output NO)any input stringnot contained in L.We are primarily interested in various forms of efficient algorithms,where efficient is defined as being polynomial time. Recall that an algorithm haspolynomial running time if it halts within nO(1)time on any input of length n.
CLASS RP
The class RP (for randomized polynomial time) consists of all languages L thathave a randomized algorithm A running in worst case polynomial time such that for any
input x in ?*,¢ x ?L ? Pr[A(x) accepts] >= ½¢ x ? L ?Pr[A(x) accepts] = 0.The choice of the bound on the error probability ½ is arbitrary. In fact , as wasobserved in the case of the min-cut algorithm, independent repetitions of the algorithmcan be used to go from the case where the probability of success is polynomially small tothe case where the probability of error is exponentially small while changing only degree of the polynomial that bounds the running time . Thus , the success probabilitycan be changed to an inverse polynomial function of the input size without significantlyaffecting the definition of RP.Observe that an RP algorithm is a Monte Carlo algorithm that can err only whenx ?L. this is referred to as one-sided error. The class co-RP consists of languages thathave polynomial time randomized algorithms erring only in the case when x ? L.Aproblem belonging to both RP and co-RP can be solved by a randomized algorithm withzero-sided error, ie a Las Vegas algorithm
CONCLUSION
The ideas underlying randomized algorithms can be traced back to Monte Carlo
methods used in numerical analysis, statistical physics, and simulation .A randomizedalgorithm is defined as an algorithm thattypically uses the random bits as an auxiliary inputto guide its behavior. It achievs good performance in the "average case". Formally, thealgorithm's performance will be a random variable determined by the random bits, with(hopefully) good expected value. The "worstcase" is typically so unlikely to occur that itcan be ignored. Randomized algorithms take a random bit to randomize the algorithm.
For randomized quick sort expected running time holds for every input.
There are some interesting complexity classes involving randomized algorithms:
1. Randomized Polynomial time (RP)
2. Zero-error Probabilistic Polynomial time (ZPP)
3. Probabilistic Polynomial time (PP)
4. Bounded-error Probabilistic Polynomial time (BPP).Page 24