Seminar On RANDOMIZED ALGORITHMS
Computer Science Clay Active In SP Posts: 712 Joined: Jan 2009 
14062009, 01:20 AM
Seminar On RANDOMIZED ALGORITHMS Prepared by Shamseena K S1 M.Tech Software Engineering CUSATPage 2 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 2 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. First and foremost reason for using randomized algorithms is simplicity. An easy randomized algorithm can match the performance of a deterministic algorithm. For some problems, the bestknown randomized algorithms are faster than the bestknown 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 or may take very long time. Two types of Randomized Algorithms: 1. Las Vegas Algorithm 2. Monte Carlo Algorithm Las Vegas Algorithm: The randomized algorithm always outputs the correct answer, it is just that there is a small probability of taking long to execute. Monte Carlo Algorithm: The algorithm always completes quickly, but allow a small probability of error. Quicksort is probably the most familiar "realworld" algorithm in which randomness is very useful. The deterministic version of this algorithm requires O(n 2 ) time to sort n numbers for some degenerate inputs  such as the array elements being already in sorted order! However, if the algorithm randomly permutes elements before starting, it finishes in O(n log n) time with a high probability, for any input. The difference between the two is crucial when sorting large datasets.Page 3 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 3 CONTENTS 1. INTRODUCTION 1.1 DETERMINISTIC ALGORITHM 1.2 RANDOMIZED ALGORITHM 1.3 WHY RANDOMIZED ALGORITHMS? 2. LAS VEGAS AND MONTE CARLO 2.1 LAS VEGAS ALGORITHM 2.2 MONTE CARLO ALGORITHM 3. RANDOMIZED QUICK SORT ALGORITHM 3.1 TRADITIONAL QUICKSORT 3.2 RANDOMIZED QUICKSORT 4. RANDOMIZED MINCUT ALGORITHM 5. COMPLEXITY CLASSES 5.1 CLASS RP 5.2 CLASS ZPP 5.3 CLASS PP 5.4 CLASS BPP 6. ADVANTAGES 7. DISADVANTAGES 8. SCOPE 9. CONCLUTION 10.REFERENCESPage 4 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 4 1. INTRODUCTION An algorithm is any welldefined 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 the output. A problem can be represented as a tuple, problem (instances, solutions). Where instances are the inputs to the problem and solutions are the outputs to the problem. To solve a problem we can use different algorithms. These algorithms differ dramatically in their efficiency. 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". 1.1 DETERMINISTIC ALGORITHM Goal is to solve the problem correctly (always) and quickly. Typically the number of steps should be polynomial in the size of the input. Input Output 1.2 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 random bits to influence its computation. Input Output Random bits Algorithm AlgorithmPage 5 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 5 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. 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 which one assumes a distribution on the inputs and analyses an algorithm that may itself be deterministic. 1.3 WHY RANDOMIZED ALGORITHMS ? Simplicity :  This is the first and foremost reason for using randomized algorithms. There are numerous examples where an easy randomized algorithm can match (or even surpass) the performance of a deterministic algorithm. Example: Sorting algorithms. The MergeSort algorithm is asymptotically best deterministic algorithm. It is not too hard to describe. However, the same asymptotic running time can be achieved by the simple randomized Quicksort algorithm. The algorithm picks a random element as a pivot and partitions the rest of the elements: those smaller than the pivot and those bigger than the pivot. Recurse on these two partitions. We will give the analysis of the running time later. Speed : 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 or may take very long time. Example: Checking if a multivariate polynomial is the zero polynomial. There is no known deterministic polynomialtime algorithm that determines if the given multivariate polynomial is the zero polynomial. On the other hand, there is a very simple and efficient randomized algorithm for this problem: just evaluate the givenPage 6 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 6 polynomial at random points. Note that such a polynomial could be represented implicitly. e.g., as a determinant of a matrix whose entries contain different variables.Page 7 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 7 2. LAS VEGAS AND MONTE CARLO There are two types of Randomized Algorithms: 1) Las Vegas Algorithm 2) Monte Carlo Algorithm 2.1 LAS VEGAS ALGORITHM:  Las Vegas Algorithm: The randomized algorithm always produces the correct answer,but its runtime for each input is a random variable whose expectation is bounded. Example: Quicksort algorithm 2.2 MONTE CARLO ALGORITHM:  The randomized algorithm runs for a fixed number of steps for each input and produces an answer that is correct with a bounded probability. That is it may produce incorrect solution .It has a fixed deterministic running time. If the algorithm is run repeatedly with independent random choices each time, the failure probability can be made arbitrarily small, at the expense of running time. For decision problems (problems for which the answer to an instance is YES or NO), there are two kinds of Monte Carlo algorithms: those with onesided error, and those with twosided error. A Monte Carlo algorithm is said to have twosided error if there is a nonzero probability that it errs when it outputs either YES or NO. It is said to have onesided error if the probability that it errs is zero for at least one of the possible outputs (YES / NO) that it produces. Example: MinCut Algorithm. Which is better, Monte Carlo or Las Vegas? The answer depends on the application. In some applications an incorrect solution may be catastrophic. A Las Vegas algorithm is by definition a Monte Carlo algorithm with error probability zero. It is possible to derive a Las Vegas algorithm from a Monte Carlo algorithm. The efficiencyPage 8 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 8 of the derivation procedure depends on the time taken to verify the correctness of a solution to the problem. We say that a Las Vegas algorithm is an efficient Las Vegas algorithm if on any input its expected running time is bounded by a polynomial function of the input size. Similarly a Monte Carlo algorithm is an efficient Monte Carlo algorithm if on any input its worstcase running time is bounded by a polynomial function of the input size.Page 9 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 9 3. RANDOMIZED QUICKSORT 3.1 TRADITIONAL QUICKSORT Consider sorting a set S of n numbers into ascending order. Pick the first element as the pivot element, say y. Partition the set S{y} into two sets S 1 and S 2 , where S 1 consists of those elements of S that are smaller than y, and S 2 has the remaining elements. Recursively sort S 1 and S 2 , then output the elements of S 1 in ascending order , followed by y ,and then the elements of S 2 in ascending order. Analysis:  If we could find y in cn steps for some constant c, we could partition S {y} in n1 additional steps by comparing each element of S with y; thus the total number of steps in our sorting procedure would be given by the recurrence T (n) <= 2T(n/2) + (c+1) n, Where T(k) represents the time taken by this method to sort k numbers on the worstcase input. This recurrence has the solution T(n)<= c n log n for a constant c. The difficulty with the above scheme in practice is finding the element y that splits S{y} into two sets of the same size. One simple solution is to choose an element of S at random. This does not always ensure a splitter giving a roughly even split. However, it is reasonable to hope that in the recursive algorithm we will be lucky fairly often. The result is an algorithm we call RandQS, for Randomized Quicksort.Page 10 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 10 3.2 RANDOMIZED QUICKSORT Randomized Quicksort algorithm makes random choices during execution. Algorithm RandQS: Input: A set of numbers S. Output: The elements of S sorted in increasing order. 1.Choose an element y uniformly at random from S: every element in S has equal probability of being chosen. 2.By comparing each element of S with y, determine the set S 1 of elements smaller than y and the set S 2 of elements larger than y. 3.Recursively sort S 1 and S 2 .Output the sorted version of S 1 , followed by y, and then the sorted version of S 2 . Analysis:  As for any sorting algorithms, we measure the running time of RandQS in terms of the number of comparisons it performs .Our goal is to analyze the expected number of comparisons in an execution of RandQS. All the comparisons are performed in Step 2. Let S(i) be the i th smallest element in the input list S. Define the random variable X ij to assume the value 1 if S(i) and S(j) are compared in an execution, and the value 0 otherwise. Thus X ij is a count of comparisons between S(i) and S(j), and so the total number of comparisons is Expected runtime t of RandQS is ?? = = n i i j ij X 1 ?? ?? = = = = = = n i i j ij n i i j ij X E X E t 1 1 ] [ ] [Page 11 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 11 Let P ij denote the probability that S(i) and S(j) are compared in an execution. Since X ij only assumes the values 0 and 1, E[X ij ] = P ij *1 + (1 P ij ) * 0 = P ij To compute P ij , we make two observations. 1. There is a comparison between S(i) and S(j) if and only if S(i) or S(j) occurs earlier in the permutation ? than any element S(l) such that i<l<j. To see this, let S(k) be the earliest in ? from among all elements of rank between i and j. If k = i or j then S(i) will belong to the left subtree of S(k) while S(j) will belong to the right subtree of S(k), implying that there is no comparison between S(i) and S(j). Conversely, when k=I or j there is an ancestor descendent relationship between S(i) and S(j), implying that the two elements are compared by RandQS. 2. Any of the elements S(i),S(I+1),Â¦,S(j) is equally likely to be the first of these elements to be chosen as a partitioning element, and hence to appear first in ? . Thus, the probability that this first element is either S(i) or S(j) is exactly 2/(ji+1). Therefore, the expected runtime t: Note that 1+ 1/2 + 1/3 + Â¦ + 1/n ? ln n Randomized Quicksort is a Las Vegas Algorithm. n n j n i j p X E t n j n i i j n i i j ij n i i j ij ln 2 2 1 2 ] [ 1 1 1 1 ? = +  = = = ? ?? ?? ?? = = = = = = =Page 12 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 12 The expected running time holds for every input. It is an expectation that depends only on the random choices made by the algorithm, and not on any assumptions about the distribution of the input. The behavior of a randomized algorithm can vary even on a single input, from one execution to another. The running time becomes a random variable, and the running time analysis involves understanding the distribution of this random variable.Page 13 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 13 4. RANDOMIZED MINCUT ALGORITHM Let G = (V,E) be a connected , undirected multigraph with n vertices.A multigragh may contain multiple edges between any pair of vertices.A cut in G is a set of 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, and we want to know how robust it is in the sense of the the minimum number of links whose failure causes the network to become disconnected.The minimum cut problem is to find a cut of minimum size. Mincut algorithm Algorithm MinCut Input: Connected, undirected multigragh G(V,E). Output: Size of the mincut. 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 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 14Page 15 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 15 Analysis: Look at what happens to the edges after they are contracted. They become self loops and are removed. After the ith iteration of the while loop, or the ith contraction, how many nodes remain: n  i. Let us assume that no minimumcut edge got contracted. (We want to know what is the probability of this â„¢lucky eventâ„¢ happening) Each node in the contracted graph has degree>= k (Why? Because contractions do not decrease the mincut). Thus after the ith iteration, the total number of edges in the graph is >= k(ni)/2 . The probability q 1 of picking one of those k edges in the first merging step = k/(kn/2) = n/2 The probability p 1 of not picking any of those k edges in the first merging step = (12/n) Repeat the same argument for the first n2 merging steps. Probability p of not picking any of those k edges in all the merging steps = (12/n)(12/(n1))(12/(n2))Â¦(12/3) Therefore, the probability of finding the mincut: If we repeat the whole procedure n 2 /2 times, the probability of not finding the mincut is at most )1 ( 2 3 )... 1 ( )1 )...( 3 )( 2 ( ) 3 2 1 )...( 1 2 1)( 2 1(  =    =     = n n n n n n n n p e n n /1 ) /2 1( 2/ 2 2 ? Page 16 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 16 By this process of repetition, we have managed to reduce the probability of failure from 12/(n**2) to a more respectable 1/e. Further execution of the algorithm will make the failure probability arbitrarily smallthe only consideration being that repetitions increase the running time. Randomized Mincut is a Monte Carlo Algorithm.Page 17 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 17 5.COMPLEXITY CLASSES A complexity class is a collection of languages all of whose recognition problems can be solved under prescribed bounds on the computational resources. A language recognition problem is to decide whether a given string x in ?* belongs to L. An algorithm 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 string not 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 has polynomial running time if it halts within n O(1) time on any input of length n. Some basic complexity classes focusing on those involving randomized algorithms are 1) Randomized Polynomial time (RP) 2) Zeroerror Probabilistic Polynomial time(ZPP) 3) Probabilistic Polynomial time(PP) 4) Boundederror Probabilistic Polynomial time (BPP) 5.1 CLASS RP The class RP (for randomized polynomial time) consists of all languages L that have 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 was observed in the case of the mincut algorithm, independent repetitions of the algorithm can be used to go from the case where the probability of success is polynomially small to the case where the probability of error is exponentially small while changing only thePage 18 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 18 degree of the polynomial that bounds the running time . Thus , the success probability can be changed to an inverse polynomial function of the input size without significantly affecting the definition of RP. Observe that an RP algorithm is a Monte Carlo algorithm that can err only when x ?L. this is referred to as onesided error. The class coRP consists of languages that have polynomial time randomized algorithms erring only in the case when x ? L.A problem belonging to both RP and coRP can be solved by a randomized algorithm with zerosided error, ie a Las Vegas algorithm. 5.2 CLASS ZPP The class ZPP is the class of languages which have Las Vegas algorithms running in expected polynomial time. ZPP = RP n coRP 5.3 CLASS PP The class PP (for probabilistic polynomial time ) consists of all languages L that have 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] < Ã‚Â½ To reduce the error probability of a twosided error algorithm, we can perform several independent iterations on the same input and produce the output that occurs in the majority of these iterations. Unfortunately, the definition of the class PP is rather weak: because we have no bound on how far from Ã‚Â½ the probabilities are, it may not be possible to use a small number of repetitions of an algorithm A with such twosided error probability to obtain an algorithm with significantly small error probability.Page 19 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 19 5.3 CLASS BPP The class BPP (for bounded error probabilistic polynomial time) consists of all languages L that have 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] <= Ã‚Â¼. For this class of algorithms the error probability can be reduced to 1/2 n with only a polynomial number of iterations. In fact the probability bounds Ã‚Â¾ and Ã‚Â¼ can be changed to Ã‚Â½ + 1/p(n) and Ã‚Â½ 1/p(n), respectively, for any polynomially bounded function p(n) without affecting this error reduction property or the definition of the class BPP to a significant extent.Page 20 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 20 6.ADVANTAGES There are two principal advantages to randomized algorithms. The first is performance. For many problems, randomized algorithms run faster than bestknown deterministic algorithms. Second, many randomized algorithms are simpler to describe and implement than deterministic algorithms of comparable performance. Randomized Quicksort is an example.Page 21 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 21 7.DISADVANTAGES Difficulty to sample the distributions using only random bits:For example, consider an algorithm that picks a random real number from some interval. This requires infinitely many random bits. There is sometimes a nontrivial computational overhead associated with sampling from a seemingly wellbehaved distribution. For example, consider the program of using a source of unbiased random bits to sample uniformly from a set S whose cardinality is not a power of 2.Page 22 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 22 8.SCOPE Â¢ Number theoretic algorithms: Primality testing (Monte Carlo) Â¢ Data structures: Sorting, order statistics, searching, and computational geometry. Â¢ Algebraic identities: Polynomial and matrix identity verification and Interactive proof systems. Â¢ Mathematical programming: Faster algorithms for linear Programming, Rounding linear program solutions to integer program solutions, Â¢ Graph algorithms: Minimum spanning trees, shortest paths and minimum cuts. Â¢ Counting and enumeration: Matrix permanent and Counting combinatorial structures. Â¢ Parallel and distributed computing: Deadlock avoidance, distributed Consensus. Â¢ Probabilistic existence proofs: Show that a combinatorial object arises with nonzero probability among objects drawn from a suitable probability space.Page 23 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 23 9.CONCLUSION The ideas underlying randomized algorithms can be traced back to Monte Carlo methods used in numerical analysis, statistical physics, and simulation . 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. 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. Zeroerror Probabilistic Polynomial time (ZPP) 3. Probabilistic Polynomial time (PP) 4. Boundederror Probabilistic Polynomial time (BPP).Page 24 Seminar Report2005 Randomized Algorithms Department of Computer Science CUSAT 24 10.REFERENCES Books: Rajeev Motwani and Prabhakar Raghavan: Randomized Algorithms, Cambridge University Press 1995. Thomas H Cormen, Charles E Leiserson,Ronald L Rivest and Clifford Stein: Introduction to Algorithms Websites: en.wikipediawiki/Probabilistic_algorithm en.wikipediawiki/Las_Vegas_algorithm nist.gov/dads/HTML/LasVegas.html nist.gov/dads/HTML/monteCarlo.htm Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



Guest Thinking To Register 
01082013, 04:20 PM
source code and algorithm,problem definition,list of validation,technique apply in the project and implimentation of reischuk's randomized algorithm



