Dsgn & Analysis Of Algorithms
Dsgn & Analysis Of Algorithms CS 4310
Popular in Course
verified elite notetaker
verified elite notetaker
verified elite notetaker
Yi xian soo
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in ComputerScienence
This 29 page Class Notes was uploaded by Lisette Hodkiewicz on Wednesday September 30, 2015. The Class Notes belongs to CS 4310 at Western Michigan University taught by Ajay Gupta in Fall. Since its upload, it has received 5 views. For similar materials see /class/216879/cs-4310-western-michigan-university in ComputerScienence at Western Michigan University.
Reviews for Dsgn & Analysis Of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/30/15
Summations and Recurrence Relations1 CS331 and 08531 Design and Analysis of Algorithms Ajay Gupta Don Nelson Version 1 January 3 1992 June 26 2003 1Note These are informal notes that are to be used only as a supporting mate rial Use them at your own risk Please report any errors and typographical mis takes to Ajay Gupta guptacswmichedu or Don Nelson nelsoncswmichedu 1 Math Preliminaries Below you will nd some formulae that are useful for analysis of algorithms The list is by no means exhaustive7 rather it is designed to give you a avor of di erent ideas we may need Conventions 0 V ltgt for all symbol 0 3 ltgt there exists symbol 0 0 1 o 0 1 o loga1 07 for all a gt 0 o logy ltgt base two log ofy when no explicit base is indicated Vy 2 1 o ifz 0ifxgty o rm m Logarithms o logmy 2 ltgt yVx gt1 0 zlogwy yVx gt1 0 logma gtlt b logma logm bVx gt1 and ab gt 0 o logm logo 7 logm bVx gt1 and ab gt 0 logy a logy m 7 o logma Vzygt1 o alogwb blogw V gt1 0 logm ab b logm 1 Powers o 117 gtlt ac ab ab 177039 o abc a1 0 ac gtlt be ab 2 Series Sums In this section we will consider a number of examples of various series that occur often during solutions of recurrence relations and frequency counting The sum 2 notation is often used to denote a series in more succinct form and hence let7s rst start by understanding this notation ln general7 2 fz denotes the longer form u fz 1 fz 2 fy 71lmfy where yx are integers7 y gt z and is some function Observe that terms occur y 7 m 1 number of times and 239 is called a running variable of the sum Here are some useful facts about the sum notation o i z 2 y 2 In other words uj k are simply dummy 397 7m k 17m 77 variables Pause Compare the longer forms of the sums z o If is a constant function as far as its dependence on the running 2 2 variable goes eg uj and k7 then Z a fa 1 y 7 z 1fa7 for any a 31 239 x x y o 92 if ig for some functions f and g Pause ls f2 1 9 90 m Long 1s ice x 92 fro x jam 239z ygj gtlt f2 97 gtlt if2 whenever 97 is not a function of the erimnning variable 2 2 Z 2 o Zf2f2 Z fkVz such thatzgzgy im 239m z1 21 ArithmeticLike Series 71 Lets consider the series of the form 22k for some positive constant k and 21 V L try to establish closed forrns77 represented by these We know that 1 72 21 why How about 2 7 This series represents sum of the rst 72 natural numbers Let7s rst lcolnsider the case when n is an even integer If we add the rst and last number we get 1 n7 add the second and the second last number we get 2 n 7 1 1 n and add the third and the third last number we get 3 n 7 2 1 Continuing in this fashion7 it is easy to see that we need to add a total ofnnQ pairs each one resulting in a sum 7272 1 2 of 1 Hence7 one can say that 2 for even 72 21 Pause What happens when we use a similar strategy but 72 is odd 1 Now7 suppose that we claim 2 W for all n gt 0 How can we 21 be sure that in fact our claim is correct One way to make sure is to use rnathernatical induction So7 lets try it For n 12 we can easily verify that our claim is true and hence our claim holds for the base case Now by induction hypothesis 1H assume that k 22 kk 1 i1 holds for k n We know that Zr Z n i1 for all values of k lt n We need to prove that our claim i1 anl useleithkn71 nn1 I 2 V L Let us now consider the series 22 In order to nd a closed form for i1 this series7 we illustrate a method which is also applicable for nding closed V L forms for the series 22 for k gt 2 It is easy why to verify that 13 3n1371 1 We rst expand the left hand side LHS of equation 1 so that terms involving only 2392 239 and 1 remain We thus have Z 13 7 23 22393 3 23 1 7 23 i1 i1 i1 Z 33Z 23Z 2172 3 i1 i1 i1 i1 i1 32 23Z Zl 2 i1 i1 i1 H Now7 using equation 2 and the right hand side RHS of equation 17 we obtain 32 232 Zln1371 3 i1 i1 i1 gt 3i 2n137173i 7i1 4 i1 s 22 n13 717 3nn12 7703 nn12n16 I Break Try to generalize above strategy to rzd a closed form for 23 i1 Long Break Try to rzd a closed form for Ztk for k gt 3 i1 22 GeometricLike Series 2 Suppose that we have a series of the form 01 for some constant C These im kind of series are known as geometric series Following is one way to nd a closed form for these Let S denote the closed forrn7 then S 20139 5 egtltS 20139 6 im1 Subtracting equation 5 from equation 67 we obtain 21 2 e71S E 01172011 im1 iz Cy1 7 cm gt S CZ1 7 eme 71 I Let k be a positive constant and e be a constant How about a series of V L the form gtlt Ci which looks similar to a combination of an arithmetic i1 like and a geometric series We now describe a method which helps us in nding a closed form when k 1 ie7 closed form for the series n Etc 7 i1 We can rst use a strategy which is similar to the one for geometric series and then strategy similar to the one for arithmetic like series Let S again denote the closed form for the series 7 We have n S EM 8 11 0 gtlt S c gtlt 22H i1 2261471 i1 n1 I cgtltS 223971CZ 9 12 Subtracting equation 8 from equation 97 we obtain 0 71S z397 1w 72390139 ncn z39 7 1w 7 23 c no 1 7 c 7 1ci 7 22H i2 13972 no 1 7 c 7 l 7 ZCi i2 no 1 7 c 7 Ci i2 no 1 7 c 7 0 1 7 02c 7 1 gt S ncn 7 cc 71 7c 1 7 02c 712 I Long Break Try nding closed form for 2220i 11 3 Recurrence Relations Suppose that Tn represents the cost of performing an algorithm on a data set of size n Often Tn7 when originally constructed7 will not be in some closed form77 representing a function of 717 rather7 it will be given in terms of one or more values of Tk for values of k smaller than 71 Consider the following examples 1 ifn01 Tn71Tn72 ifngt1 10 1 ifn01 Tn2n ifngt1 11 c if n 1 TM c ETU if 71 gt1 12 i1 Equation 10 is given in terms of the previous two terms equation 11 is given in terms of the value of T at 712 and equation 12 is given in terms of all the preceding values of T The last equation is referred to as a full history recurrence relation Whenever such recurrence relations represent the cost of performing an algorithm7 it becomes important to establish a bound on T as a function of 717 the size of the problem For example7 can we establish a bound on Tn if T is given by equation 10 It is easy to show using mathematical induction that 2 is a bound First observe that T0 S 20 and T1 S 21 Thus7 we have the basis for an inductive proof Now suppose that Tk 3 2k for all k lt n Then Tn Tn 1 Tn 7 2 g 2 1 2 lt 2 1 2 1 13 2n Note that in the inequality expressed in 13 the value of 2 was over estimated by 2 1 a factor of 2 This is a rather coarse estimate7 and it might lead one to suspect that a better bound could be found In fact that is the case It can be shown that there is a constant c such that Tn lt CA where A1618 Next we will look at equation 11 and try an upper bound on Tn7 say 712 In this case we will restrict our values of n to powers of 2 In other words7 can it be shown that T2P S 22 for p 0172 7 Here we can use induction on p Observe that T1 T20 207 so it is true for p 0 Assume that it is true for p k Then T2k1 T2k2k1 S 22k2k1 lt 22k22k 14 22k1 lt 22W 15 22k1 Again7 notice in the inequalities 14 and 15 that extremely coarse over estimates were made As was the case with the estimate for equation 107 this might lead one to suspect that the bound we are considering is much too large Let7s try a smaller bound Can we show that Tn 3 2n 7 1 It is certainly true for n 1 20 Assume that it is true for n 2k Then T2k1 T2k 2k1 2 gtlt 2k 71 2 1 l 2x2k171 As a nal observation about this last bound7 note that it is easy to show that Tn 2n 7 1 ie7 we can nd an exact solution for powers of 2 instead of merely nding an upper bound In each of the examples that we have considered7 an upper bound was proposed7 and then shown to work Other guesses can also be made7 but it may be dif cult or impossible to establish that the proposed bound is actually a bound For example7 could you show for equation 11 that Tn S cgtlt log2 n 31 The Iteration Method Establishing whether or not a given function represents a bound for a re currence relation is one thing7 but coming up with a reasonable bound is another In the following material we will use the method of expanding a recurrence relation in order to arrive at a solution or a bound To see how this method works7 let7s consider again the recurrence relation given in 11 Suppose that n 2 for some integer p To expand the relation7 we will start with n and work our way down step by step until a pattern can be seen T71 T712 71 T7122 712 71 T7123 7122 712 71 T712 71 12i p71 1 1 712127 70 1712 12711 7 127172 27171 Next we will illustrate another expansion to solve the following recurrence relation T71 c ifn1 16 2T712 0712 if 71 gt1 As was the case with the rst expansion above we will assume that 71 2 for some integer p Then the expansion proceeds as follows T01 2T712 C712 22T7122 col2 6712 22T7122 071214 1 222T7123 col22 071214 1 10 23Tn23 0712116 14 1 232Tn24 4 071282 4 0712116 14 1 24Tn24 0712164 116 14 1 p71 2PTn2P 0712 2 14139 i0 1 14 34 cn 4cn231 7 14 on 4cn231 71712 1771 I 02 0712 214l 43970 on 0712 on 403012 71 C4n23 n 7 43 Note that in each of the above expansions we continued to apply the recurrence relation until a recognizable pattern was reached and at that point we jumped all the way to the pth step It would take an inductive argument to prove that such a jump is legitimate To actually verify that the expressions we derived are solutions one should really show by induction that the solution is valid for all powers 2 The induction can be done on p 32 The Master Method For an another expansion consider the following recurrence relation ifn1 T01 aTnb cnk if 71 gt1 11 This relation is similar to those expanded above however we observe that it is expressed in terms of the general parameters a b c and k We will proceed to expand this in the same way however we will obtain only upper bounds rather than exact solutions At one point in the expansion we will nd it necessary to consider cases which depend on the parameters ab and k Let n 1forsornepgt0 Tn aTnb an a2Tnb2 acnkbk cnk a2Tnb2 cnkabk 1 a2aTnb3 cnkbZk cnkabk 1 a3Tnb3 cnkabk2 abk 1 apT1 CH abky 10 17 cap cnk 201ka i0 The sum in the last equation above represents a geometric series so its growth is dependent on the ratio abk To estimate the growth of Tn we will consider three cases for the ratio Case 1 a lt bk 17a 1771 In this case 2abky is bounded by 1M which we will denote by G Thus we can write Tn 3 cap Gcnk cabng Gcnk onlogb Gcnk lt cnk Gcnk 0nk Case 2 a bk 1771 In this case 201ka p logbn and we can write i0 Tn caZ7 cnk logbn onlogb cnk logbn cnk cnk logbn 0nk10gbn Case 3 a gt bk In this case ablkil is a positive constant7 which we will denote by H Then p71 139 a bk p galbk ab211 and hence Tn cabng Cabk 7171nka nk 71 Unlong CHn10Eba 7 Can 0n10gba Given a recurrence equation in the form of equation 87 we now can quickly nd the order of growth by considering abk and applying the ap propriate case This7 of course7 only gives the order of growth and does not produce an exact solution 33 Full History Recurrence Relation We will now consider one nal example7 namely that of a full history recur rence relation This particular equation will arise when we study the average case performance of quicksor t The equation is 2 n71 I Tn n 71 E Z TZ 18 i1 with T1 0 We rst eliminate the summation in the following way First consider equation 18 and multiplying both sides by n we obtain n71 nTn nn 71 2 Z Tz39 19 i1 Now7 replacing n by 71 1 in equation 18 and then multiplying both sides by n 1 we get 2 n 71 1Tn 1 nn 1 2im 20 i1 Subtracting equation 19 from equation 20 and solving for Tn 1 yields 71 1Tn 1 7 nTn 2n 2Tn 2n n2 Tltn1 n1 n1 Tn 21 Notice that Equation 21 now gives Tn 1 in terms of As before we will attempt to expand based on 21 only the method will be somewhat di erent than that used for the previous recurrence relations We rst make an observation about the term 2nn 1 in equation 21 It is bounded above by 2 and as 71 becomes large it is very close to 2 By replacing 2nn 1 with 2 we can convert the equation to an inequality and have a system that is much simpler to solve Since our main concern will ultimately be to nd a bound on the growth of Tn this substitution will not defeat our goal n2 T 1 T 2 m lt n1ltngt n2n1 T 71 2 2 n1lt n n gt gt 2 2 2 n n1 n2 n 2n2 T 72 2 7 2 n 717101 n1 n2 2 1 T 72 2 2 717101 1 1 n27 n2n71 2 1 T 73 2 2 2 71719172 0quot 1 1 1 n272 n2 3 1 T 73 2 2 717201 1 n1 n272 o l 0n27 i Tnip2n2 n2 n7p1 Letting p n 7 1 we obtain n71 Tuy nm j 0n27 i n2 2 S Tn 1 n71 2n2 Z 0n27 i 2n2lt gt n2 n1 1 1 Zgm 1 g 0n 2 log2n 2 n 1 log2n 1 Exercises 1 Find an exact solution for c ifn0 T01 2Tn2cn ifngt1 2 Expand and nd a bound for the following recurrence relation Then check how your answer compares with the solution to the general case we derived 0 if n lt 2 TM 7 7Tn2 0712 if n gt 2 For each of the recurrence relation given below7 rst using the expan sioniteration rnethod nd a close upper bound7 and then prove by induction that your solution is correct Assume c and k are constants 3 c if n 1 TM clogn ifn 2 2 4 c if n 17 2 TM 2Tg clogn2 if n 2 3 5 ck if n 1 TM 4T clogn if n 2 2 6 c if1 n 2 T01 T12Lcnifn23 17 TnC 3T 071 ifn 2 2 ifn1 ifn1 2T cnlogn if n 2 2 ifn1 c 7 3T cnlogn ifn 2 2 ifn1 Tltngt C T cnlogn ifn 2 2 Tn C ifn1234 777 TTcn E7125 Minimum Spanning Trees De nition of MST Generic MST algorithm Kruskal s algorithm Prim s algorithm De nition ofMST Let GVE be a connected undirected giaph For each edge icy in E we have aweight wuv specifying the cost length oredge to connect u and v We wish to find a acyclic subset r of E that connects all of the Vertices in Vand whose total weight is minimized since the total weight is minimized the subset T must be acyclic no circuit Thus Tis atree We call it aspanning tree The problem of determining the tree T is called the in in mumspanningtree problem Application ofMST an example I In the design of electronic circuitry it is o en necessary to make a set ofpins electrically equivalent by Wiring them together To interconnect n pins We can use nl Wires each connecting two pins I We Want to minimize the total length of the Wires I Minimum Spanning Trees can be used to model this problem CS4310 spring08 lecture notes on MCST by Mahmoud Said Electronic Circuits om 2603201 Electronic Circuits Here is an example of a connected graph and its minimum spanning tree Notice that the tree is not unique replacing bc with ah yields another spanning tree with the same minimum weight CS4310 spring08 lecture notes on MCST by Mahmoud Said Growing a MSTGeneric Algorithm 2 3 4 5 GENERICMSTGW l A while A does not form aspannmg tree do ind an edge uv that is safe forA AA uv return A Set A is always a subset ofsome minimum spanning tree This property is called the invariant propeit An edge uv is a safe edge for A ifadding the edge to A does not destroy the invariant AsafeedgeisJ39 L r T A L T 4 How to nd a safe edge We need some de nitions and a theorem A cut SNS of an undirected graph GVE is a partition of V An edge crosses the cut SNS if one ofiw endpoints is in S and the other is in VS An edge is a light edge crossing a cut if its Weight is the minimum of any edge crossing the cut This gure shows a cut SVS ofthe graph The edge do is the unique light edge crossing the cut CS4310 spring08 lecture notes on MCST by Mahmoud Said Theorem 1 I Let GVE be a connected undirected graph with a realvalued weight function w define I Let A be a subset ofE that is included in some minimum spanning tree for G I Let SVS be any cut ofG such that for 811y edge u V inA u v Q S or u v vs I Let uv be a light edge crossing SVS I Then edge uv is safe for A l Corollary 2 Let GVE be a connected undirected graph with areal valued weight function w de ned on E Let Abe a subset ofE that is included in some minimum spanning tree or Let c be a connected component tree in the forest GAVA Let uvbealight edge shortestamong all ed es connecting with at ers components connecting c to ome other component in A Then edge uv is safe for A For Kmskal s algorithm Yl r The algorithms of Kruskal and Prim I The two algorithms are elaborations of the generic algorithm I They each use a speci c rule to determine a safe edge in line 3 of GENERIC MST I In Kmskal39s algorithm 7 The set A is aforest e The safe edge added to A is always a leastweight edge in the grap that connects two distinct components I In Prim39s algorithm A The set A forms asingle tree The s edge added to A is always a leastweight edge connecting the tree to avertex not in the tree l2 CS4310 spring08 lecture notes on MCST by Mahmoud Said Kruskal s a1 g0rithmltbasic part 1 Sort the edges in an increasing order 2 3 while E is not empty do 3 take an edge 11 V that is shortest in E and delete it from E 4 if u and V are in different componenw then add n V to A Note each time a shortest edge in E is considered Kruskal s algorithm Fun Part not required MSTiKRUSKALGw 1 A 2 for each Vertex V in VG 3 do MAKEisETV 4 sort the edges of E by nondecreasing Weight W 5 for each edge uV in E in or e y nondecreasmg wel t 6 do if FINDis ETu l FINDisETV 7 then AADuV 8 UNIONuV return A Disj oint set is discussed in Chapter 21 Page 498 14 DisjointSet Chapter 21 Page 498 Keep a collection ofsets s1 s2 so 7 Each s is aset eg sv1 v2 v8 Three operations 7 MakeSetxcreates anew set whose only member is x e Unionx y runites the sets that contain x and y say SK and ST into anew set that is the union ofthe two sets 7 FindSetxretums apointerto the representative ofthe set containing x 7 Each operation takes Olog n time CS4310 spring08 lecture notes on MCST by Mahmoud Said I Our implementation uses a disj ointset data struc e to maintain several disjoint sew of elements Each set contains the Vertices in a tree of the current forest The operation FINDis ETu returns a representative element from the set that contains u Thus We can determine Whether two Vertices u and V belong to the same tree by testing Whether FINDisETu equals FIND7SETV The combining of trees is accomplished by the UNION procedure Running time OOE lg OED The execution of Kruskal39s algorithm Moderatepart The edges are considered by the a1gorithrn in sorted order by weig t The edge under consideration at eaeh step is shown with ared weight number 4 2 11 4 14 e 1 2 l7 8 7 4 9 11 2 6 4 14 8 10 1 2 8 7 4 9 11 2 14 4 7 6 8 10 1 2 18 CS4310 spring08 lecture notes on MCST by Mahmoud Said 8 7 4 9 11 2 14 4 7 6 8 10 1 2 8 7 4 9 11 2 14 7 6 4 8 10 1 2 19 8 7 4 9 11 2 14 1 4 6 8 10 1 2 8 7 4 9 2 11 6 4 14 8 10 1 2 21 CS4310 spring08 lecture notes on MCST by Mahmoud Said 4 9 11 2 14 a 4 7 6 8 10 1 2 8 7 4 9 2 a 11 6 4 14 8 10 1 2 Prim s algorithmeastepm MSTPRIMGwr 1 40 2 8r r is an arbitrary node in V 3 QVr 4 while Q is not empty do 5 take an edge u v such that 1 u es and v e Q vs S and u v 15 the shortest edge satisfying 1 6 add n V to A add V to S and delete V from Q Prlm s algorlthmeunpartnereth MSTPRIMGwr 1 for each u in Q do keyuao 3 parentuNIL 4 keyr0 0 then parentv 1 1 keyvwuv CS4310 spring08 lecture notes on MCST by Mahmoud Said I Grow the minimum spanning tree from the root Vertex r Q is a priority queue holding all Vertices that are not in the tree now I keyV is the minimum Weight of any edge connecting V to a Vertex in the tree parentV names the parent ofV in the tree When the algorithm terminates Q is empty the th minimum spanning tree A for G is AVparentvv V r I Running time OEHVng VD The execution of Prim39s algOrthIHmodemte part 8 7 the root 4 9 vertex 2 11 4 14 e 6 8 10 1 2 8 7 4 J 9 6 a 11 6 4 14 8 10 1 2 26 8 7 4 9 11 2 14 4 7 6 s 1 1 2 8 7 4 9 11 2 14 4 7 6 8 10 1 2 27 CS4310 spring08 lecture notes on MCST by Mahmoud Said 8 7 4 9 11 2 14 1 4 7 6 8 10 1 2 39 8 7 4 9 11 2 14 l 4 6 8 10 1 2 39 22 8 7 4 9 11 2 14 1 4 6 8 10 A I 4 1 9 11 2 14 1 4 7 6 8 10 1 39 2 29 8 A 7 I 4 l 9 11 2 14 1 4 7 6 8 10 1 39 2 c 1 largest edge weight is minimum over all spahhlhg trees ofG The value ofthe bottleneck spahhlhg tree is the weight ofthe maximumweight edge h T Theorem Amlhlmum spahhlhg tree is also abottleneck spahhlhg tree Challenge problem CS4310 spring08 lecture notes on MCST by Mahmoud Said
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'