### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DATA STRUCTR&ALGORITHMS CSCE 350

GPA 3.61

### View Full Document

## 5

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 82 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 350 at University of South Carolina - Columbia taught by Staff in Fall. Since its upload, it has received 5 views. For similar materials see /class/229586/csce-350-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for DATA STRUCTR&ALGORITHMS

### 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: 10/26/15

Lecture 1 Introduction to Algorithms Analysis I m assuming you ve all had CSCE 350 or the equivalent I ll assume some basic things from there and sometimes quickly review the more importantsubtle points We ll start with Appendix A in CLRS 7 Summations Why They are essential tools in analyzing the complexity of algorithms A First Example Consider the following two C code fragments Fragment 1 sum O for i1 iltn i2 for j0 jlti j sum and Fragment 2 sum O for i1 iltn i2 for ji jltn j sum Note the subtle difference Is there a difference in running time order of magnitude as a function of 71 Yes there is Sample 1 runs in time n and Sample 2 runs in time n log n so Sample 2 runs signi cantly longer Recall o f 09 means fn is at most a constant times 9n for all 71 large enough 0 f 99 means fn is at least a positive constant times 9n for all 71 large enough Equivalently 9 Of o f 99 means both 1 09 and f f 9977 is an equivalence relation between 1 and 9 Also logn means log2 Here s the intuition in both fragments the variablei does not run from 1 to n at an even pace Since it doubles each time it spends most of its time being very small compared to n which makes the rst j loop run faster and the second j loop run slower Let s analyze the running times more rigorously We generally don t care about constant factors so it is enough to nd for each fragment an upper bound and a lower bound that are within a constant factor of each other This looseness usually makes life a lot easier for us since we don t have to be exact Claim 1 The runn1ng t1me for Fragment 2 1s Onlog Proof The body of the inner loop j loop takes 01 time Each time it runs the j loop iterates 71 71 g 71 times for a time of 071 per execution The outer 1 loop runs about log71 many times actually exactly log 71 many times So the total time for the fragment including initialization loop testing and increment is O7110g71 D Claim 2 The runn1ng t1me for Fragment 2 1s Qnlog Proof Note that for all iterations of the 1 loop except the last one the j loop iterates at least 712 times because 1 lt 712 and thus 71 71 gt 71 7 712 Thus the sum variable is incremented at least x log71 7 1 times total which is clearly 9nlog D Claim 3 The runn1ng t1me for Fragment 1 1s Proof To get a lower bound we only need to look at the last iteration of the 1 loopI Digression the late Paul Erdos arguably the greatest mathematician of the 20th century once described the art of mathematical analysis as knowing what information you can throw away The value of 1 in the last 1 loop iteration must be at least 712 In this iteration as in all iterations j runs from 0 through 1 7 1 so the sum variable is incremented 1 2 712 times But maybe we threw too much away in ignoring the previous 1 loop iterations so that our lower bound of is not tight enough Actually it is tight Claim 4 The runn1ng t1me for Fragment 1 1s Proof Now we must be more careful the simple analysis that worked for Fragment 2 is not good enough here We must bite the bullet and take a sum of the running times of the j loop as 1 increases For all 0 g k lt log 71 during the k 1st iteration of the 1 loop we clearly have1 2k For this 11 1st iteration of the 1 loop the j loop iterates 1 2k times so it takes time at most C 2k for some constant C gt 0 So the total time for the fragment is log 71 71 T g 2 0211 110 This is a nite geometric series see below whose exact value is 2mg 7 7 1 C2T10gn1 2 7 1 But log 71 lt log71 1 so T g C 21 71 lt C210gn1 2071 which is 071 as claimed Even if we add the extra bits initialization loop testing incrementing these can be absorbed into the 071 bound D headSeries Geometric Series Geometric series come in two avors nite and in nite A nite geometric series is of the form n71 Z 10 where r is a constant real7 but could also be complex7 and n is a nonnegative integer If r 17 then this sum is clearly equal to 11 To nd a closed form when r 31 17 let S be the value of the sum above Then n71 n71 S715 1171 1 10 10 n71 n71 2717276141 10 10 n71 n T1472Ef 10 11 71 The last equation holds because most ofthe terms in the two sums cancel This is called telescoping Dividing by 1 7 1 which is not zero7 we get 171 S 171 An in nite geometric series has the form M8 H o 139 which is the limit of the nite geometric series as n 7 00 We have 1 7L lim E 1 1 Hoe 10 Mg 1 H o n lim wam 147 7 7 lim 1 171 17111700 This last limit exists if and only if M lt 17 in which case it is zero So for M lt 17 the in nite geometric series above has value 11 7 1 Lecture 2 More About Sums Arithmetic Series How to compute a closed form for 212 This method is attributed to Gauss as a child Let S 2122 Then reversing the terms we see that S 2101 1 1 7 Then adding these two sums term by term we get V L V L 2SZin17i Zn 1 nn1 i1 i1 so S nn 12 Notice that this means that Elli nz Higher Powers Closed forms can be computed for ELI ik for any integer k 2 0 We have 2212 nn 12n 16 and 212 3 71271 124 More generally we know that M 2 9M 1 for all integers k 2 0 Supplement Finding Closed Forms for 22231241 The sum 2201 ik has a closed form for every integer k 2 O The closed form is always a polynomial in n of degree k 1 Here s how to nd it using induction on k For each i and k 2 0 de ne ii 7 7 2 7 k 1 k many factors First we ll nd a closed form for the sum 2201 ii and from this we can easily get a closed form for 2201 Consider the sum H n SZi1 7i l i0 This sum telescopes in two different ways First of all we clearly have that S nkil7 011i1 nkil Second each term of the sum can be factored l H n n71 i1 7i l Zi1ii71i7k17ii71i7k1i7k i0 Zllti17i7ki 71 k1 l k1ZiE l H o Equating these two expressions for S and dividing by k 1 we get 1 k1 k n7 1 1 2 7k 02 M1 MW M gt n gt7 which is a closed form for 2201 ii Now to get a closed form for 2012 we rst expand the product ii completely For example for k 2 we would get i2 7 1 i2 7 i We then sum this for i going from 0 to n 7 1 and use the closed form we got above k n71 I I I 1 nn71n72 222 72 22 2 17171 1n 2 The left hand side is equal to 2201 7201 i We already know the second term7it is 71717 12 and so we move it to the other side 1 1 i2 71717 1n7 2 717171 71717 12n7 1 3 2 6 H 0 So we have a closed form for the sum of squares For more general k when we expand 2E and sum we ll get some combination where the other terms all involve sums of smaller powers of 2 Assuming by induction that we have closed forms for all the smaller power sums we then get a closed form for As an exercise apply the ideas above to nd a closed form for 2201 23 Harmonic Series What about k 71 We show that 211i log n more accurately ELI 1i lnnO1 We use the technique of nested sums Assume n 2 1 and let m llogn 1 that is m is the largest integer such that 2 g n 1 Then 1 1 1 22 2bi 239 1 The inner sum on the right hand side gives a block of contiguous terms in the sum on the left hand side The last sum on the right gives the terms left over after all the complete blocks are counted We use 1 to get both lower and upper bounds on the harmonic series For the upper bound we see that m712b71 1 lt m712b71 1 m11 4 m 21 2 7 21 7 70 10 70 10 70 and n n 1 1 Z E Z 27 17 1201 1201 since there are at most 2 terms in this sum Thus 2112 m 1 Ologn We do something similar for the lower bound 4251 12b1 1 W Z 1 gt m 1 7 m 1 m b 4 7 W 7 7 10 10 2 J 120 0 2 170 2 2 so 211i m2 Qlogn U Differentiating and Integrating Series Closed forms for some series can be obtained by differentiating or integrating term by term another series with a known closed form For example consider the series 2m 2 11 for some xed 1 7 1 There are at least two ways for nding a closed form for Direct Method Set S 2111 Then as in the case of the geometric series we have S7 TS 11 7 2141111 1 1 1 1 TL TL 211 1 7 2141141 11 10 n n1 11 7 7 1 11 11 n n1 n1 21117 14111717211 11 11 11 771 11 n1 1 21 10 n 1T 1 1 T Tn1gt7 V L I 1 7 n1 1 n1 Zir1r T 7 71 T t 3 1 7 12 1 7 1 11 Differentiation Method Differentiate both sides of the equation i 1 7 Tn1 Zr 7 17 10 7 T with respect to 1 By linearity of ddr we get 7ltn 1gtwlt17 r lt17 W1 1 7 T 39 M H o Multiplying both sides by r ignoring the 1 0 term on the left and rearranging the right gives 3 Taking the limit as n 7 oo in 3 we get for all r such that M lt 1 11 11 Note that n Urn tends to zero because 71 1 increases only linearly in 71 but VH1 decreases exponentially in n lntegrating a series term by term can also be useful 0 N where M lt 1 Hint integrate the in nite Exercise Find a closed form for the series 21 geometric series term by term Doing this is legal because the series zi i 7 converges uniformly l for z in some neighborhood of 72 Lecture 3 More Math Products A product is like a sum but the terms are multiplied instead of added For example 71 ml H i i1 By convention an empty sum has value 0 and an empty product has value 1 So in particular There are tricks for getting a closed form for a product but a good fall back method is to just take the logarithm to any convenient base 1 This turns the product into a sum Simplify the sum then take I to the power of the result then simplify further if possible For example suppose 7L 5123139 i0 Taking the log to base two of both sides we have we want to evaluate n logS Zlog2 3i i0 7L log2 ilog3 i0 V L n 1 log3 i0 1 n 1 log 3 Taking 2 to the power of each side we get S 7 2n1 2log 3nn12 2n1 2log3nn12 2n1 3nn1239 A quicker but essentially equivalent way to get the same closed form is to split the product then use the fact that the product of b to the power of some term is equal to b to the power of the sum of the terms So we have r L r L r L H2 nil 3i i0 39 2n1 3nn127 as we had before Bounding Sums 9M for all We ve already done a few of these Here s one more we show that ELI ik 7 xed k 2 0 For the upper bound we have 71 Zik lt nk nk1 H For the lower bound we have iik 2 2 it i1 lira21 Z 316 in2i 2 k 2 33 nk1 W lntegral Approximation Sums can be approximated closely by integrals in many cases De nition 5 Let I Q R be an interval with endpoints a lt b a could be foo and I could be 00 A function f I H R is monotone increasing on I if for all zy E I if x g y then x The function f is monotone decreasing on I if we have x g y implies x 2 Theorem 6 Let I a and b be in De nition 5 and let 1 I gt R be some function integrable on I For any integers c and at such that a g c 71lt d 1 b we have a d d1 mm 2m mm 071 ic c if f is monotone increasing on I and d1 d d mm 2m 71 mm if f is monotone decreasing on I Proof De ne gx and hx Assume rst that f is monotone increasing Then gx x hx for all of 1 g x 11 Thus we have A mm mm gxdx d g 1 mm which proves the rst two inequalities in the theorem Now if f is monotone decreasing7 then gx 2 x 2 hx7 and so we get the same chain of inequalities as above but with the sense of the inequalities reversed This proves the second two inequalities in the theorem D It is sometimes useful to know how tight the integral approximation is This is done by comput ing the difference between the upper and lower bounding integrals For the monotone increasing case the decreasing case is similar7 we have A mm 7 mm 11 fwd mm d 071 fd 1 027 1 This is usually tight enough for our purposes Let s redo our estimation of 21 ik using the integral approximation method We can get our two constants much closer together in this case Since x xk is monotone increasing on 07 00 for k 2 07 we use the rst inequalities of Theorem 6 to get k1 n k1 n k n1 71 7lt lt 1 12 k1 So we get not only that ELI ik nkH but also that we can choose our constants 01 1k 1 and 62 to be anything greater than 1k17 provided we then choose our threshold no large enough Math Odds and Ends More Asymptotic Notation We ve seen 0 7 9 and notation There are two more 0 little oh and w little omega notation n ogn means that n grows strictly more slowly than any positive constant times That is7 for any 0 gt 0 there is an no such that lt 0 901 for all n 2 no Equivalently7 n J om039 9 fn ogn implies fn Ogn and fn 7 Qgn7 but is strictly stronger than both combined fn wgn means that fn grows strictly faster than any positive constant times That is7 for any 0 gt 0 there is an no such that 1 gt 0 901 for all n 2 no Equivalently7 h m 30 901 00 or equivalently7 gn ofn fn wgn implies fn and fn 7 Ogn7 but is strictly stronger than both combined Modular Arithmetic For integers a and n with n gt 07 we de ne a mod n to be the remainder after dividing a by 71 That is7 a mod n a 7 lanln If a mod n 1 mod n then we may write a E 1 mod This is true if and only if n is a divisor of a 7 b Exponentials for any real constants a and b with a gt 1 That is7 nb 0a 132 133 13139 e 71z2lgl ln particular7 em 2 1 z for any real m We also have em lim 1 5 Hoe n Two useful identities are 01z emforallz R o 5mg1mm2forallz Rsuchthat lzlgl Logarithms Forallrealagt0 bgt0 cgt0andn a blogba7 logcab loge L logo I logl7 a n logl7 a log a 10gb a c 7 logo I 10gb1a 7 logy lo 1 a 7 gb loga b7 alogb c Clogb 17 where we assume none of the logarithm bases are 1 The natural logarithm lnz loge z ff drr satis es 0 ln1 z z 7 z22 z33 7 m44 7 7 Taylor series olnm z71forallzgt0 ln mathematics lnz is often denoted as log m We will use lgz to denote log2 m Lecture 4 Starting Algorithms Problems Algorithms and the RAM Model Types of problems decision search arrangement optimization We have examples for each and there can be overlap An algorithm is a careful step by step procedure for performing some task It should allow no room for judgment or intuition To analyze algorithms rigorously we must express them concretely as programs on a completely speci ed mathematical model of computation One such popular model which is essentially equiva lent to several others is the RAM Random Access Machine model De ning this model rigorously would be too tedious so we ll only describe it A RAM algorithm is a sequence of RAM instructions that act on read and write individual registers in a one way in nite array indexed O 1 2 Each register is a nite sequence of bits Typical allowed instructions include arithmetic addition substraction multiplication and division on registers both integer and oating point loading and storing values from in registers indirect addressing testing equality comparison of registers both integer and oating point and branching Thus the RAM model looks like some generic assembly language We count each instruction execution as costing one unit of time This is only realistic however if we limit the range of possible values that can be stored in a register A restriction that is commonly agreed upon is that for problems of size 71 each register is allowed to be only clog 71 bits where c 2 1 is some constant that we can choose as big as we need for the problem at hand so long as it is independent of 71 If we didn t restrict the size of registers then we could manipulate huge amounts of data in a single register in a single time step say by repeated squaring This is clearly unrealistic Sometimes it is unclear whether or not we should allow a particular operation as a primitive instruction in the RAM model For example exponentiation Generally exponentiation is not considered a primitive operation however most architectures allow arithmetic shifts by k bits which is essentially multiplication by 2k Provided k is small we ll sometimes treat this as a primitive operation Data Structures Data structures support algorithms making them faster Algorithms support data structures as basic operations making them more efficient We ll look at algorithms on simple data structures linear arrays at rst then later we ll look at more sophisticated data structures and the algorithms that support them Lecture 4 A Tale of Two Algorithms lnsertion Sort and MergeSort in pseudocode MergeSort uses the Divide and Conquer tech nique with Merge as the combining subalgorithm Analysis lnsertionSort takes nz quadratic time to sort 71 numbers in the worst case In the best case when the list is already sorted or almost sorted the running time is n linear time The average case over all possible arrangements of the initial data is nz sort of because each item is inserted about half way into the sorted list to its left on average Merge takes time m n to merge a sorted list of m items with a sorted list of 71 items Since the total input size is m n this makes Merge linear time Since MergeSort is recursive we cannot do a direct tally of the total running time like we did with lnsertionSort Instead we let Tn be the worst case time to MergeSort an array of 71 items Then we do a direct tally of the time for each line of code and we get the relation Tn 2Tn2 This is an example of a recurrence relation We ll see how to solve this and other recurrence relations soon Lecture 6 Recurrences When an algorithm is recursive we cannot just add up the component times directly since we don t know how long the recursive calls take lnstead if we let Tn be the worst case time of a given recursive algorithm A then adding up the times gives us an equation expressing Tn in terms of Tm for m lt n For example suppose A takes a list of 71 numbers and o in the base case n 1 say runs in constant time and 0 otherwise calls itself recursively twice each time on a list of size 712 as well as taking n time outside of the recursive calls Then we know that T1 01 TM 2Tln2l9n7 where the second equation assumes n gt 1 This is an example of a recurrence relation lt uniquely determines the asymptotic growth rate of The time for Mergesort roughly satis es this recurrence relation More accurately it satis es T1 01 TM Tln2lTTn2l9n To get a relation that uniquely de nes values not just the asymptotics of a function bounding the run time we supply constants in place of the asymptotic notation T1 d M 2Tltln2lgtcn where c and d are positive constants This uniquely determines the value of Tn for all positive integers n and allows us to manipulate it more directly When we only care about asymptotics we often omit c tacitly assuming 0 1 as well as omitting the base case which is always of the form if n is bounded by some constant then Tn is bounded by some constant77 The actual choice of these constants does not affect the asymptotic growth rate of Tn so we can just ignore this case altogether Solving Recurrence Relations We now concentrate on techniques to solve recurrence relations There are three main ap proaches the substitution method the tree method and the master method The Substitution Method This method yields a rigorous proof by induction that a function given by a recurrence relation has a given asymptotic growth rate It is in some sense the nal word in the analysis of that function A drawback is that you have to guess what the growth rate is before applying the method Consider the relation T0 1 Tm 3Tn4jn2 forngt0 where c gt 0 is a constant Clearly Tn 9n2 because Tn 2 n2 for all n gt 0 We guess that this is tight that is Tn 0n2 Guessing the asymptotic growth rate is the rst step of the method Now we try to prove our guess we must show by induction that there is an no and constant c gt 0 such that Tn cnz 4 for all n 2 n0 For the inductive step we assume that 4 holds for all values less than n and show that it therefore holds for n where n is large enough We have M 3TltW41gt n 3cln4JZ n2 inductive hyp 3cn42 n2 7 3 2 7 ltEc1gtn We re done with the inductive case if we can get the right hand side to be cnz This will be the case provided 1A 1A 3 E 0 1 g c or equivalently c 2 1613 Thus so far we are free to choose 0 to be anything at least 1613 The base case might impose a further constraint though Now the base case where we decide no Note that TO 1 gt 0 02 for any 0 so we cannot choose no 0 We can choose no 1 though as long as we establish 4 for enough initial values of n to get the induction started We have Tl 4 T2 7 T3 12 All higher values of n reduce inductively to these three so it suffices to pick no 1 and c 4 so that 4 holds for n E 1 23 Since 4 2 1613 our choice of c is consistent with the constraint we established earlier By this we have shown that Tn 0n2 and hence Tn nz In the future we will largely ignore oors and ceilings This almost never gets us into serious trouble but doing so make our arguments less than rigorous Thus after analyzing a recurrence by ignoring the oors and ceilings if we want a rigorous proof we should use our result as the guess in an application of the substitution method on the original recurrence Changing Variables Sometimes you can convert an unfamiliar recurrence relation into a familiar one by changing variables Consider Tn 2Tn lg n 5 Let S be the function de ned by Sm T2m for all m Then from 5 we get Sm T2m 2T2m2 lg 2m 2Sm2 m 6 So we get a recurrence on S without the square root This is essentially the same recurrence as that for MergeSort By the tree or master methods later we can solve this recurrence for S to get Sm mlgm Thus Tn Slgn lgnlglgn The Tree Method The execution of a recursive algorithm can be visualized as a tree Each node of the tree corresponds to a call to the algorithm the root being the initial call and the children of a node 14 being the recursive calls made at that node Each node is labeled with the time taken in that node We can often solve a recurrence by looking at the structure of the corresponding tree Consider the recurrence Tn Tn3 T2n3 n The root is labeled n with two children the left labeled n3 and the right labeled 2n3 etc The shallowest leaf in the tree that is when the argument is about 1 is along the leftmost path at depth log3 n The deepest leaf is along the rightmost path at depth logg2 n Now we add up the labels level by level starting at the root level 0 To get a lower bound on Tn we only count full levels so we go down to the level of the shallowest leaf Each of these levels is found to add up to n so the rst log3n 1 levels give a total of nlog3n 1 Thus Tn Qnlg For an upper bound we continue counting all the levels in the tree as if they were full and thus added up to We thus get an upper bound of nlog32n 1 Onlgn Thus Tn nlg Lecture 7 Recurrences continued The Master Method The master method solves recurrences of the form T01 nb H for a wide variety of functions f and values of a and b It derives directly from the following theorem Theorem 7 Master Theorem Let fn be a function and let a and b be real with a 2 1 and b gt 1 Suppose Tn is giuen by the recurrence Tltngt armb M where we interpret nb to be either or Then letting t logba Z 0 N if there is an 6 gt 0 such that 0nt75 then Tn nt N if nt then Tn ntlgn 93 A if there is an 6 gt 0 such that Q ntg and there is a c lt 1 such that afnb for all su iciently large n then Tn Proof We will prove the theorem without worrying about oors and ceilings Also we ll only prove the most important special cases of the theoremithose in which fn nd for some real 1 2 0 The general theorem including oorsceilings can be reduced rather easily to these cases Let fn nd for d 2 0 lf 1 lt t then we are in Case 1 lf 1 t then Case 2 otherwise if d gt t then it is Case 3 In any case using the tree method we get a completely balanced tree of depth logbn7 where the total for level i is ai nbi Thus7 10gb n M 7 Zai nbi l H Sm Sm M M 1 A El 1 where r abd This is clearly a nite geometric series Noting that bd 017 7 and thus logbr logba7 d t 7 d7 we see that r gt1r 17 or r lt 1 just as t gt d7 25 d7 or t lt d7 respectively We consider the three possibilities t gt d This corresponds to Case 1 of the theorem We have7 log n1 7 nd lt7 b 1 r 7 1 1 ndr Tlogb 71 r 7 1 T nd Tlogbn 7 r 7 1 r T nd nlogbr 7 r 7 1 r T d t7d l r 7 1n lt71 r d r t n r71ltn 7 nt Tn as in Case 1 Note that nd 001 t lt d This corresponds to Case 3 of the theorem We rst verify the regularity property of fn di 71 a nb de T 1 T 1 and thus we can take 0 r lt 1 to make the regularity property hold Next7 since 0 lt r lt 17 we see that for all n 2 1 and thus Tn nd fn as in Case 3 t d This corresponds to Case 2 of the theorem We have T 1 so logbn Tn nd 2 1 ndlogbn 1 ndlgn i0 as in Case 3 D Remark In Case 1 of the theorem the tree is bottom heavy that is the total time is dominated by the time spent at the leaves In Case 3 the tree is top heavy and the time spent at the root dominates the total time Case 2 is in between these two In this case the tree is rectangular that is each level gives about the same total time Thus the total time is the time spent at level 0 the root ie nt times the number of levels ie lg The Master Method Use the master theorem to solve the following recurrences 1 T n 2Tn2 71 Case 2 2 T n 8Tn3 712 Case 3 9Tn3 712 Case 2 Tn 3 Tn 10Tn3 712 Case 1 5 T n 2T2n3 712 Case 3 6 Tn T9n10 1 Case 2 The rst recurrence is that of MergeSort The Master Theorem gives a time of n lg In each case go through the following steps 1 What is a 2 What is b 3 Compare logba with the exponent of 4 Determine which case of the Master Theorem applies if any 5 Read off the asymptotic expression for Tn from the Theorem Fast Integer Multiplication To see a good example of divide and conquer with an analysis using the Master method we look at the task of multiplying large integers Let s assume we have two integers b c 2 0 represented in binary with 71 bits each Here n is assumed to be large so we cannot assume as we usually do that b and c can be added subtracted or multiplied in constant time We imagine that the b and c are both represented using arrays of 71 bits I bn1 b0 and c arkl 00 where the bi and oi are individual bits leading 0s are allowed Thus n71 b 2 1222 i0 n71 c Z c i i0 Addition The usual sequential binary add with carry algorithm that we all learned in school takes time n since we spend a constant amount of time at each column from right to left The sum is representable by n 1 bits at most This algorithm is clearly asymptotically optimal since the produce the correct sum we must at least examine each bit of b and of c Subtraction Similar to addition the usual subtract and borrow algorithm takes n time which is clearly asymptotically optimal The result can be represented by at most 71 bits Multiplication Now the interesting bit If we multiply b and c using the naive grade school algorithm then it takes quadratic 9012 time Essentially this algorithm is tantamount to expanding the product be according to the expressions above n71 n71 bc 12 20 Ema2W i0 j0 13739 then adding everything up term by term There are n2 Multiplying with Divideand Conquer If n 1 then the multiplication is trivial so assume that n gt 1 Let s further assume for simplicity n is even In fact we can assume that n is a power of 2 If not pad each number with leading Us to the next power of 2 this doubles the input size at worst Let m 712 Split 1 and 0 up into their m least and m most signi cant bits Let bl and b be the numbers given by the low m bits and the high m bits of b respectively Similarly let Cl and C be the low and high halves of 0 Thus 0 bbbh 010 lt 2 and many terms I blbh2m7 c clch2m 18 We then have be bl bh2mcz ch27quot bzcz bzch bhcz m bhchQW This suggests that we can compute be with four recursive multiplications of pairs of m bit numbersi blag blah bhcg and bhchias well as n time spent doing other things namely some additions and multiplications by powers of two the latter amounts to arithmetic shift of the bits which can be done in linear time The time for this divide and conquer multiplication algorithm thus satis es the recurrence Tn 4Tm n 4Tn2 The Master Theorem Case 1 then gives Tn nz which is asymptotically no better than the naive algorithm Can we do better Yes Split 1 and 0 up into their low and high halves as above but then recursively compute only three products m 3 b501 y 3 thh7 Z 3 bl bhcl Ch Now you should verify for yourself that bcmziy7z2my2n which the algorithm then computes How much time does this take Besides the recursive calls there s a linear time s worth of overhead additions subtractions and arithmetic shifts There are three recursive callsicomputing z y and 2 The numbers z and y are products of two m bit integers each and z is the product of at most two m 1 bit integers Thus the running time satis es Tn 2Tn2 Tn2 1 It can be shown that the 1 doesn t affect the result so the recurrence is effectively Tltngt 3Tn2 901 which yields Tn nlgs by the Master Theorem1 Since lg3 i 1585 lt 2 the new approach runs signi cantly faster asymptotically This approach dates back at least to Gauss who discovered using the same trick that multi plying two complex numbers together could be done with only three real multiplications instead of the more naive four Lecture 8 Sorting and Order Statistics Heapsort 11f you re really worried about the 1 you should verify that Tn nlga directly using the substitution method Alternatively you can modify the algorithm a bit so that only 771bit numbers are multiplied recursively and the overhead is still Finally we look at algorithms for some speci c problems Note that we are skipping Chapter 5 although we will use some of its techniques eventually The Sorting Problem Input A sequence of 71 numbers 011012 an Output A permutation reordering a3 2 a of the input sequence such that 1 g 2 g g 04 Items usually stored in an array or a linked list perhaps as keys of records with additional satellite data Ifthe amount of satellite data in each record is large we usually only include a pointer to it with the key in order to minimize data movement while sorting These are programming details rather than algorithmiciie methodologicaliissues so we usually consider the array to consist of numbers only Sorting is fundamental in the study of algorithms with a wide variety of applications We ve seen Insertion Sort nz time in the worst case but sorts in place and MergeSort nlgn time but the Merge subroutine does not rearrange data in place We ll see two other in place sorting routines HeapSort nlg n worst case time and Quick Sort nz worst case time but nlg n averagecase time Both sort in place 01 extra space used The Order Statistics Problem The ith order statistic of a multiset of 71 numbers is the ith smallest number in the set We can nd the ith order statistic by sorting the numbers in the set then indexing the ith element This takes time asymptotically equal to that of sorting eg nlg n for MergeSort But there is actually a linear time algorithm for nding the ith order statistic Heaps A heap is used to implement a priority queue and is also used in Heapsort Heaps are collections of objects with keys taken from a totally ordered universe There are two types of heap min heap and max heap Min heaps support the following operations Insertion Adding an element to the heap Deletion Removing an element with minimum key value Finding the minimum Returing an object with minimum key value the heap is unchanged Decrease key Decreasing the key value of an element of the heap Max heaps support the same operations with minimum replaced with maximum and decrease replaced with increase An Implementation Binary Heap array A with two attributes lengthA and heap sizeA which is at most lengthA The elements of the heap reside in A1 heap sizelAH and can be pictured as an almost full binary tree A binary tree is almost full if all its leaves are either on the same level or on two adjacent levels with the deeper leaves as far left as possible The correspondance between node locations on the tree and array indices is obtained by travers ing the tree in level order left to right within each level The root is at index 1 The left and right children of the node with index i have indices 2i and 2i 1 respectively and for any nonroot note 20 with indexi gt 1 the index of its parent is So for example the rightmost leaf on the bottom level has index heap sizeA Thus we have the following functions running in 01 time Parent return 2j Lefti return 2i Right2 return 2i 1 1 The elements of the heap are kept in either max heap order or mm heap order depending on the type of heap Max heap order means that for any 2 g i heap si2eA we have ALparenti 2 the inequality is reversed for min heaps Lecture 9 Heaps and Heapsortc0ntinued Recall A1 lengthA holds heap items numbers The actual heap is kept in A1 heap si2eA where heap si2eA is always less than lengthA Now we show how to take an arbitrary array A1 and put it into max heap order This uses MaxHeapify an important subroutine for other heap operations The idea is that we make each subtree a max heap starting from the bottom of the tree and working up toward the root This means that when we make the tree rooted at index i into a heap we can assume that the subtrees rooted at Lefti and Righti are heaps already Each leaf is already a max heap so we start with the nonleaf with highest index that is Parentheap sz392eA BuildMaxHeapA n Makes a max heap out of the rst 71 elements of A Precondition 1 g n lengthA fori eParentn downto 1 do MaxHeapifyA n heap si2eAltn MaxHeapifyA n Makes the subtree of A1 n rooted at i into a max heap Precondition 1 g i g n Precondition the subtrees rooted at Lefti and Righti are in max heap order Method cascade the root down into the tree 21 mejez repeat forever if Leftj n and ALeftj gt Am then meLeftj if Righw n and ARightj gt Am then meRigth m is index of largest item among Am Aileftm Alrightjl if m j then return else swap Aljl H Alml jem this doublesj at least We need to show that these algorithms are correct We leave that for later but now just mention that if MaXHeapify correctly does what it is supposed to then clearly MakeMaXHeap is correct as well We now look at the run time of MaXHeapify and MakeMaxHeap ln MaXHeapify each iteration of the repeat loop takes 01 time as well as all the stuff outside the repeat loop Thus the time for MaXHeapifyA n is asymptotically equal to the number of iterations of the repeat loop This is clearly equal to one plus the depth of the subtree rooted at index 2 Clearly a longest path from the root in this tree is down the left spine and the length of this path is the largest k such that k applications of Right to i is g 71 That is the largest k such that i2k n Thus k llgnij and the number of iterations of the repeat loop is thus 1 Therefore the time for MaXHeapifyA mi is lgni To get the total time Tn for MakeMaXHeapAn rst we note that clearly Tn 971 since it has at least loop iterations To get an upper bound we take a sum and split it Let m be least such that n lt 2 Note that 2 g 271 By the analysis of MaXHeapify we get that lnzl TM 9 Z llgnil i1 So for large enough n7 there is a constant C such that lnZl Tltngt 0 Ugom i1 A 2quot1 S C llg2mil 2quot711 0 Z milgij 11 2771 0 2 me ngm 11 m712k71 0 2W llg2kjl k0 j0 022071710 k j CZOnik k k m 0 2 72m 71 m 02 quot 2 727 71 0 g 02 quot Z r2T 71 We know that this last sum converges to some constant D exercise what is D7 Thus for all sufficiently large n Tn CD27quot 2CDn Thus MakeMaxHeapA7 71 takes time We now implement other heap operations We do this for max heaps FindMaXA Precondition heap sizeA 2 1 return AH DeleteMaXA Precondition heap sizeA 2 1 A1ltAheap sizeA heap sizeAltheap si26A 7 1 MaxHeapifyA7 heap sizeA 1 Finally7 HeapSort HeapSortA n Sort A1n Precondition n lengthA MakeMaXHeapA 71 while heap sizelA gt 0 do save eFindMaxA DeleteMaXA also decrements heap sizelA Aheap sz39zeA 1 esave As we ve seen MakeMaXHeapA 71 takes n time The while loop iterates n times and the bulk of the work of each iteration is done by DeleteMax We ve seen that DeleteMaX called with a heap of size i takes time lgi in the worst case so the total time taken by the calls to DeleteMaX in the while loop is asymptotically equal to 7L Dn Z lgi i1 The fact that Dn nlgn follows from the following inequalities which hold for n gt 0 nlgn71 E 2 7 2 l A E 3 1A R4 an 3 Lecture 10 Quicksort Quicksort is a divide and conquer sort that takes nz time in the worst case but nlg n time in the average case Like Mergesort it splits the list in two sorts both sublists recursively then recombines the results Unlike Mergesort the major work is in splitting the list while the recombination is trivial Quicksort uses a Partition subroutine to split the lists PartitionA p r takes a list Alp r assuming p g r and rearranges its elements so that there is an index q such that p q r and Aq AM for all ij such that p g i lt q lt j g r The index q is returned by the Partition procedure The value AM is called the pivot Once Partition returns q we simply sort the sublists Alp q 7 1 and Aq 1 r recursively When the recursive sorting is done it is clear that the list is entirely sorted so there is no recombining step needed 24 QuicksortA p r Sorts Abnml if p lt r then q ePartitionAp r QuicksortAp q 7 1 QuicksortA q 1 r Quicksort runs fastest when the list is split into roughly equal sized sublists each time Thus the Partition procedure should choose the partition to be at least reasonably close to the median If we expect randomly arranged initial data then any element of Ap r is just as likely to be near the median as any other so we could naively just choose Abe as the pivot Let s call this value x The partitioning procedure described here is closer to Hoare s original partitioning procedure than the one given in the textbook It is not particularly better or worse than the textbooks just different We start from the extremes of the list and work towards the middle whenever we come upon a pair of indices i lt j for which gt z gt AM we swap with AM and continue We end up somewhere in the array and this index is the return value q We move z into AM and return Verifying the correctness of this procedure is a tricky business so the pseudocode includes several assertions to help with this You should verify that all assertions are true each time they occur PartitionA p r Precondition p g r 714M z is the pivot ilt7p jlt7r 1 Abe z throughout the following loop repeat iltj and1M gm repeat j7j 7 1 until j g i or Aj jZiaHdAljl 96 All elements of AU 1 1 r are 2 m repeat 7271 1 until i Zj or gt z All elements of Ap i 7 1 are m ifi lt j then AM gt z gt Am swapltAiiLAijigt until i Zj pjrandj21 Actually either i j or i j 1 141le z All elements ofAj1r are 2 m All elements of Ap i 7 1 are m Thus all elements of Ap j are m swapltAipiAijigt ltz AU z and Abel g z Thus all elements of Ap j are m qej Alql 90 return q The time taken by Partition is clearly asymptotically dominated by the number of times i is incremented and j is decremented in the inner repeat loops since each happens at least once in any iteration of the outer repeat loop But i p and j r 1 initially and afterwards j g i g j 1 so the total number of incrementdecrement operations is between r 7p 1 and r 7p 2 Letting n r 7 p 1 be the number of elements in the list we see that Partition takes time linear in n ie In this version of Partition the pivot is always the rst element of the sublist If the initial n element list is already sorted then the rst element is also the least so the partition is into an empty list and a list of size n 7 1 which is also sorted Thus if Tn is the time for Quicksort in this case we have Tn Tn 71 n which is easily solved to get Tn nz This is the worst case behavior of Quicksort The best case is when the pivot is always close to the median Then we get essentially the same recurrence as with Mergesort yielding Tn nlg Assuming a uniformly random input distribution one can also show that the average time for Quicksort over all possible input arrangements is also n lg n the pivot is close enough to the median most of the time on average This analysis is done in the textbook Unfortunately it is often not reasonable to assume a completely random distribution For example the list may be almost sorted which leads in our case behavior close to the worst case Some alternative deterministic partition strategies can help with some of these cases for example choosing the pivot to be the median of Abe AM and Alpr2j the so called median of three strategy which gives good behavior when the list is almost sorted Still there are initial arrangments rather contrived that make the median of 3 strategy exhibit worst case behavior Another approach is to choose the pivot at random from ALP r This procedure is no longer deterministic but randomized We assume a procedure Randomp r that returns an integer in the range p r uniformly at random ie so that each integer in the range has an equal probability of being returned We also assume that successive calls to Random return independently random7 ie uncorrelated7values Finally it is reasonable to assume that Random runs in constant time for reasonable values of p and q RandomPartitionA p r m 7Random p r swapltAipiAimigt return PartitionA p r When analyzing a randomized algorithm we usually do not average over different inputs but rather over the random choices made in the algorithm for any xed input We now see that for any initial arrangement of Ap r the expected running time of RandomizedQuicksortAp r averaged over all possible sequences of return values of Random is nln n where n r 7 26 p 1 and RandomizedQuicksort is the same as Quicksort except that we replace Partition with RandomPartition Consider the rst call to RandomizedQuicksortAp7 r Since the pivot is chosen uniformly at random from Ap r the return value of the rst call to RandomlartitionAp7 r is distributed uniformly at random in the range p 7 Thus if k is the size of the left hand list the size of the right hand list then being 71 7 k 7 17 its possible values range from 0 to n 7 17 inclusive7 with each size occurring with probability 171 Let be the expected time for RandomizedQuicksort of n elements Then we see that is an average over the expected running times for each possible value of k Thus for all n 2 2 that is7 when partition occurs and recursive calls are made7 E01 900 EkEn7k71 an 1 2 Ek7 n k0 where a is some constant such that an bounds the running time of the initial call to RandomPar tition We get an upper bound for using the substitution method We guess that g on lg n1 for some constants b7 0 gt 07 since we guess we hope that the average case should act like n lg The additive term I is important for the base case Since lg1 0 and OlgO 0 by convention7 the equation above cannot hold for n 0 or n 1 unless I is big enough7 ie7 b 2 maxE0E1 So we x n 2 2 and assume that Em cmlnm b for all m lt n where lnn is the natural logarithm to base 5 of n We wish to show that cnlnn b We use the natural logarithm here because we will use an integral approximation We have 2 n71 Em an 219k k0 2 n71 lt 7 7 an n Zcklnkb k0 2Cn71 an2b7Zklnk 71 k71 7L lt an2bE mlnmdm n 1 a n 2 4 4 2 cnlnn7cltn 1gtan2b 2n Cn71 2 cnlnnb7 l A cnlnn7 an2b l A 27 with the last inequality holding provided Cgt 2anb39 7 7171 Sincen 2 2 we have 2anb S 4anb 4a2b 7171 n and therefore it su ices rst to let I maXE0 to handle the case where n lt 2 then to let 0 4a 2b This proves that 0nln n 0nlgn as desired Putting it all together we see that RandomizedQuicksort runs in expected time nlg Lecture 11 ComparisonBased Sorting Lower Bounds Selection Problem A comparison based sorting algorithm is one which only inspects the data when comparing two elements There are other sorting algorithms that take advantage of certain properties of the data such as the data are integers in a certain range or each datum is given in binary for example These are not comparison based since they look at and manipulate the data in ways other than simple comparisons All the sorting algorithms we ve seen so far lnsertion Sort MergeSort HeapSort QuickSort are comparison based Today we show that any deterministic eg not randomized comparison based sorting algo rithm requires 9nlg n time to sort 71 items in the worst case In particular in the worst case such an algorithm makes 9nln n comparisons This shows that MergeSort and HeapSort are asymptotically optimal worst case comparison based sorting algorithms One can also show we won t that any deterministic or randomized comparison based sorting algorithm must also take 9nlg n time in the average case so QuickSort is optimal in the average case For the proof we model the behavior of a comparison based algorithm by a decision tree Each nonleaf node of our decision tree is labeled with a comparison and its subtrees represent the alternative computations based on the answer to the comparison Our comparisons are binary eg ls A17 lt A147 so our decision tree is a binary tree A particular execution of the algorithm corresponds to a path through the tree from the root to a leaf Each intermediate node along the path corresponds to the algorithm making the corresponding comparison and the path continues according to the answer to the comparison The leaf represents the end of the computation Let P be any deterministic comparison based algorithm that correctly sorts any initial arrange ment of n distinct items Let T be its corresponding decision tree Claim 8 T has at least nl leaves Proof There are nl ways of arranging n distinct items in the input array Each path through T effects a permutation of the items in the array to get it sorted Since any two different initial arrangements of the array must be permuted differently to sort them the algorithm cannot take the same path through the tree on both initial arrangements otherwise that would lead to the same permutation of the two different arrangements so at least one of them would not be sorted in the end Thus by the pigeon hole principle the number of distinct root leaf paths in the treeiand hence the number of leavesimust be at least the number of possible initial arrangements of the data that is nl D Exactly nl of the leaves of T are actually reachable by the algorithm on some input arrangement If T has more than nl leaves then some are not reachable We ll assume that T is pruned of all its unreachable nodes Lemma 9 Any binary tree with k leaves has depth at least lg k Proof Suppose T is a binary tree of depth d that has the maximum number of leaves possible of any tree of depth at most d Then all the leaves of T are on level at if there were a leaf on some level i lt at then we could replace that leaf with a full binary subtree of depth d 7i with a net gain of 2d 7 1 gt 0 leaves There are 2 1 many nodes possible on level at so T has 2 1 leaves Thus for any binary tree of depth d with k leaves we must have k 2d Taking the lg of both sides proves the lemma B Let T again be the decision tree for P acting on a list of n elements where T is pruned of unreachable nodes By the Claim above T has nl many leaves and hence by the Lemma T has depth at least lg nl so there is some initial arrangement of the input that forces P to make at least lg nl comparisons We ll be done if we can show that lgnl 9nlg The usual tricks will work here We have for large enough n 71 lgnl Zlgi i1 n 2 lgi in2i Z Z 1gn 2 l39lrL2l 2 712 lgn2 7121gn 1 n4 lgn 9nlg l Order Statistics and Selection Given an array A of n numbers the ith order statistic of A is the ith smallest element of A for 1 g i g n Theselection problem is given A and integer i return the ith order statistic of A 29 Instances of this problem include nding the minimum maximum median 75th percentile etc in Any of these selection instances require linear time at least because the ith order statistic for any i cannot be determined without examining all the elements of the array Conversely nding the minimum and maximum both easily take linear time How about the median This looks harder We can nd the median in time 0nlg n say by rst HeapSorting or MergeSorting the list then picking out the middle element Can we do better Yes First we ll give a randomized selection algorithm that runs in linear expected time and quadratic worst case time This algorithm works well in practice Finally we ll give a deterministic algorithm for selection that runs in worst case linear time and is thus asymptotically optimal The deterministic algorithm however usually does worse than the randomized one and so it is more of theoretical than practical interest Both algorithms use the same Partition subroutine as Quicksort To nd the 2th order statistic in Alp r with p lt r the idea is to partition the array by some pivot value in the array After partitioning if the left list has length exactly i 7 1 then the ith smallest element is equal to the pivot so we just return it Otherwise if the left list has length at least i then the ith order statistic is in the left list so we recurse on the left list Otherwise we recurse on the right list The two algorithms only differ by how the partitioning is done Randomized Selection The rst algorithm uses RandomPartition RandomizedSelectA p r Returns the ith smallest element of Alp r Preconditions p g r and 1 g i g r 71971 1 if p r then q eRandomPartitionA p r the left list is Ap q 71 and the right list is Aq 1 r ifq7pi71then Return the pivot return Aq ifq7pgti71then Recurse on the left list return RandomizedSelectA p q 7 1 else Recurse on the right list return RandomizedSelectA q 1 732 7 q 7 p 1 In the last line we subtract q 7 p 1 from i in the recursive call to account for the pivot and all the elements of the left list Let be the expected running time for RandomizedSelect Since RandomPartition which takes linear time selects a pivot uniformly at random from the list the probability that the left list will have length k is the same for all 0 g k g n 7 1 namely 171 It is a reasonable assumption that is monotone increasing in n which means that it will always take at least as long if we recurse on the larger of the two lists each time Thus n71 E01 W g Xmas Em e k 71gt k0 similar to the analysis of RandomizedQuicksort The right hand side is at most n71 2 om M22 Ek One can then prove using the substitution method that Lecture 12 Selection in Deterministic Linear Time De ning the Median For odd n the median for an array of n elements assume that they are all distinct is de ned to be the n 12 order statistic If n is even then the array actually has two medians the ii2 and the ii2 1 order statistic ln statistics we usually de ne the median77 in this case to be the average of the two medians Here we will simply take the lower of the two So for us the median will be the ln2l order statistic regardless of the parity of n Selection in Deterministic Linear Time For the deterministic linear time selection algorithm the idea is that we choose a pivot that is guaranteed to be close enough to the median each time This choice requires some work and there is a delicate balance between how hard we are willing to work to nd a good pivot versus the time saved by choosing a good pivot A Recurrence Before getting to the algorithm we will rst solve an important recurrence Lemma 10 Suppose oz and B are real numbers with 0 lt 043 and oz lt 1 Then if Tn is giuen by the recurrence T01 TWO TM 007 then Tn It is important here that the sum of oz and B be strictly less than one The lemma does not hold otherwise Proof Clearly Tn We show that Tn 0n via the substitution method For the induction we assume that n is large enough and that Tn cn for all n lt n where c gt 0 is some constant We prove that it follows that Tn cn We have for some constant a gt O Tn Tan an can c n an Ca B an en 7 31 provided Ca B a g c or equivalently gt a c 7 1 7 a 7 Since the denominator is positive the right hand side is a nite number so we can set c a1 7 Oz 7 B to satisfy the inequality D The Algorithm The linear time Select algorithm is the same as RandomizedSelect above but where we replace RandomPartitionA p 7 with the following procedure 1 Let 71 7 7197171 be the number of items in the array Divide ALP 7 into blocks B1 Bk of ve contiguous elements each Thus k 7151 and Bi Ap 517 5 p 517 1 for 1 1 lt k and Bk Ap 5k 7 5 7 which may have fewer than ve elements if 71 is not a multiple of ve 2 For all 1 g 1 g k nd the median 771 of block Bi Put 7711 771k into a separate array B1 Note that this takes constant time per block since each block has at most ve elements 3 Recursively call SelectB 1 k to nd the median z of 7711 mk F Partition ALP 7 as usual using x as the pivot Return the index q where z is placed after partitioning Let T71 be the running time of SelectAp 71 where 71 7719 1 The partitioning procedure above clearly takes linear time in 71 except for the recursive call to Select which runs on an array of size about 715 How close is z to the median of Ap 7 Let s count the minimum number of elements in ALP 7 that are less than z Since z is the median of 7711 771k about 112 of the 771 are less than z But since each of these 771139 is the median of a block of ve elements there are at least two more elements of the array A less than 771 so there are at least roughly 3112 or about 37110 elements of A less than m It follows that there are at most 77110 elements greater than z A symmetrical argument shows that there are at least 37110 elements of A greater than m so there are at most 77110 elements less than m So in the worst case when Select recurses on one of its sublists after partitioning that sublist will have size at most 77110 Thus in the worst case the time for Select satis es the following recurrence T71 T715 T77110 Letting Oz 15 and B 710 we see that 04 B 910 lt 1 so we apply the lemma to get that T71 Thus Select takes linear time in the worst case There was a bit of slop in the previous analysis We ignored round off errors for instance Taking these into account one can show that there are constants a I such that the worst case time satis es T71 S T715 a T77110 b 901 One can still apply the lemma in this case however By letting 0 be just slightly bigger than 04 and 3 just slightly bigger than B we still have 0 B lt 1 and T71 To71 TB71 71 32 for large enough 71 since the additive constants a and b are absorbed In our particular case we can set 0 04 130 730 and 3 130 1115 and we still have 0 B 2930 lt1 Lecture 13 Pointers and Records Using Arrays Explicit Memory Management Representing Trees Binomial Coef cients Explicit pointer and record types are not required to implement linked structures Any pro gramming environment that supports arrays and there are some that only do this will do One can mechanically convert any program to an equivalent program without pointers or records We ll show how this is done in two steps rst removing explicit pointer types then removing record types Doing Without Pointers Pointers are typically used to support linked structures in which case the pointers point to records To do without pointer types one must do one s own memory management rather than letting the system do it for you There are some limitations to this discussed below but for most algorithms these limitations are not a problem You declare an array of records big enough to hold the maximum number of records you expect to have active at any one time This will serve as a surrogate to the systems dynamic memory store often called the heap although it has no relation to priority queues Then instead of an explicit pointer to a record you use the integer index of the record in the array So pointer types become integer types in link elds or any other pointer variables and dereferencing becomes array indexing We must do our own memory management in this case simulating dynamic allocation malloc in C or new in C and deallocation free in C or delete in C Even if the system does support pointers and dynamic memory allocation doing our own memory management is sometimes more ef cient both timewise and memorywise Suppose we have the following declarations in C struct node double data struct node link struct node mylist 0 Here the pointer value 0 the null pointer is guaranteed not to point to any available memory and thus myllist is initialized as an empty linked list We replace the above with the following declarations any identi er not explicitly declared or de ned is assume to be previously struct node double data int link struct node heap MAXNUMRECS int heapsize 0 int freelist 1 int mylist 1 Note that the pointer type has been changed to int Analogous to the rst declaration above the value 71 the null index is guaranteed not to be a legal index into the array The heap array will hold records that we dynamically allocate The heaplsize variable keeps track of how much of the heap has been used so far initially none The freellist variable will be explained below To allocate a new record we could use heap heapsize then increment heapsize Unfortu nately this only allows a xed nite number of allocations and does not take advantage of reusing records that are previously deallocated To x this we could tag records that we deallocate then search the heap linearly for a tagged record when we want to allocate a new one This allows recycling of old records but the time cost of linearly searching the heap each time we want a new record is prohibitively high The best approach is to maintain a linked list of deallocated nodes in the heap lnserting and removing from this list at the front takes 01 time so this is very ef cient the best we can do asymptotically The freellist variable points to this list So to deallocate a record we insert it into the free list To allocate a record we rst check if one is available on the free list and use that Only when the free list is empty do we resort to incrementing heaplsize Thus deallocation and allocation are implement as follows void deallocateint p Deallocates a node pointed to by p heapplink freelist instead of pgtlink freelist freelist p int allocate Return a pointer to a newly allocated record or a null pointer if no memory is available int ret freelist 1 ret freelist freelist heapfreelistlink instead of freelist freelist gtlink return ret H i if heapsize lt MAXNUMRECS return heapsize return 1 out of memory This explicit memory management strategy can also be used with system dynamic allocation where you maintain your own free list In the current situation with arrays it works great provided you know in advance roughly how many records you ll need at any given time If you don t know this however or you have two or more different record types maybe of different size competing for memory then this scheme is less useful than system allocation The operating system uses a more sophisticated heap management system whereby different sized chunks of memory can be allocated These chunks are kept on a doubly linked circular list If two deallocated chunks of memory are seen to be contiguous then they are combined into one big chunk which is more useful than two smaller chunks Despite this heaps can still be subject to fragmentation if two or more different sizes of records are used System heap management is an interesting topic that every student should know about since it can signi cantly in uence the performance of algorithms that use dynamic memory Sometimes it should be avoided because of fragmentation problems where an explicit management scheme tailored to the problem at hand would work better Doing Without Records Instead of an array of records one can declare multiple arrays one for each eld of a record So the heap and struct declarations above become simply double dataMAXNUMRECS int linkMAXNUMRECS The data originally kept in the record at index i is now kept separately at data i and at link i Deallocation and allocation thus become void deallocateint p Deallocates a node pointed to by p Similar to free in C or delete in C linkp freelist freelist p int allocate Return a pointer to a newly allocated record or a null pointer if no memory is available Similar to malloc in C or new in C int ret if freelist 1 ret freelist freelist linkfreelist return ret if heapsize lt MAXNUMRECS return heapsize return 1 out of memory Doing Without Multidimensional Arrays If we were only allowed linear arrays of simple types we could still simulate multidimensional arrays by storing the multidimensional array in a linear array in row major order lntead of double matrix HEIGHT WIDTH int i j matrixi j 314 we would thus have double matrix HEIGHTWIDTH int i j matrixWIDTHij 314 This is exactly how multidimensional arrays are stored and indexed in memory anyway ees Hopefully all these de nitions are more or less familiar A tree is an undirected connected acyclic graph If T is a tree then the size of T is the number of vertices nodes in T We will only consider trees of nite size A tree of size n gt 0 always has exactly 71 7 1 edges This is worth stating as a theorem and proving First we de ne the degree of a vertex to be the number of vertices adjacent to it ie the number of edges incident to it Theorem 11 Any tree with n gt 0 vertices has exactly 71 7 1 edges Proof We go by induction on 71 If n 1 then the only tree on one vertex consists of that vertex and no edges Thus the theorem is true for n 1 Now assume that n gt 1 and that the statement of the theorem holds for all trees of size n 7 1 Let T be any tree of size n Claim 12 T has a vertex of degree 1 ie a leaf Proofof Claim First since T is connected with at least two vertices it cannot have a vertex of degree 0 Suppose then that there is no vertex in T with degree 1 Then every vertex in T has degree at least 2 Start at any vertex v1 and follow some edge to some other vertex 122 Since 122 has degree 2 2 there is some other edge to follow from 122 to some new vertex 123 We can continue in this way building a path 121122123 by following new edges each time but since T is nite we must eventually come back to a vertex already on the path ie vi 127 for some i lt j Thus we have a cycle ohm1 wig vj 12 which is impossible since T is a tree Thus T must have a vertex of degree 1 Let U be a vertex of T with degree 1 If we remove 12 and its only edge from T then the resulting graph T is clearly still connected and acyclic so it is a tree Further T has size n 7 1 so by the inductive hypothesis T has exactly 71 7 2 edges We obtained T from T by removing one vertex and one edge so T must have exactly 71 7 1 edges D 36 A rooted tree is a tree T that is either empty no nodes or has a distinguished node called the root and denoted rootT if T is empty then rootT is a null reference There is then a unique path from the root to any node The depth of a node p in T is the length of the path from the root to p and the depth of T is the maximum depth of any node in the tree if the tree is empty we ll take the depth to be 71 For nodes p and q in T we say that p is an ancestor of q or that q is a descendant of p ifp lies along the unique path from rootT to q If in addition p 7 q then we say that p is a proper ancestor of q or that q is proper descendant of p The subtree of T rooted at p is the tree of all descendants of p If T is a rooted tree and p is a nonroot node in T then the parent ofp is the unique immediate predecessor ofp on the path from the root The children ofp are all nodes that share p as a parent A leaf is a node with no children The root has no parent The parent of the parent is the grandparent a child of a child is a grandchild etc The height of a node p is the length of the longest path from p to a leaf The height of T is the height of its root which is the same as the depth of T The height of an empty tree is 71 by convention as with the depth A rooted tree T is ordered if there is a linear order left to right imposed on the children of each node A binary tree is a rooted ordered tree where each node has at most two children the left child and the right childiroots of the left and right subtrees respectively if a child is missing then that subtree is empty Representing Trees Except for binary heaps trees are usually represented as linked structures with information and links at each node A node p of a binary tree as well as containing a reference to satellite data typically contains three links to the parent parentp to the left subtree leftLpl and to the right subtree rightlpl parentrootT is always a null pointer In many applications the parent eld is not needed at any node and can be omitted to save space For an arbitrary rooted ordered tree not necessarily binary we cannot use a xed number of child elds since we may not have any a priori bound on the number of children a node may have lnstead each node has a pointer to a simple linked list of its children Thus together with a reference to satellite data the three links of a node p are parentLp leftmostLp pointing to the leftmost child if there is one and rightsiblingp pointing to p s immediate right sibling if there is one Binomial Coef cients For any integer k 2 0 and any n which could be any real number or even complex number we de ne the binomial ooe ioient n nn71n72nik1 k kl We will only consider the case where n is an integer and 0 g k g n In this case ltZgtwiwlt kgt is the number of ways to pick a subset of k elements from a set of n elements It also gures prominently in the Binomial Theorem Theorem 13 Binomial Theorem For any real or complex z and y and any integer n 2 0 V L n 7 n k n7k my 72 y k0 The Binomial Theorem immediately gives us some identities in 11 2 k0 gl Glt iC7lt171gtno The rst identity is also evident because both sides are the number of ways to choose a subset of any size of a set of n elements A Recurrence for Binomial Coe icients For any integer n 2 07 we have and and for integer k with 0 lt k lt n we have n 7 n 7 l n 7 l k T k 7 1 k 39 These equations are immediate from the de nition Some lnequalities A sometimes useful inequality is Z 7 B 271 1 2 3quot An upper bound on comes from Stirling s Approximation which implies that kl 2 kek Whence7 71 71k en k 7 ltgt k kl k n lt n k 7 kkn7k k7 and this is a good approximation Letting k m for some 0 g g 17 we get Actually7 it can be shown that n Ann i We 2nHx 7 38 where H 7lg 7 17 lg17 is the binary entropy of Our convention is always that 0 lgO 0 The Beads Problem You have n boxes labeled 1 n and k identical beads How many distinct ways can you put the k beads into the n boxes where each box can hold at most one bead The answer is Now suppose that a box can hold any number of beads Now how many ways are there Imagine the boxes lined up in a row with n 7 1 dividers between them Then any arrangement of beads in boxes is represented uniquely by a string such as Here the beads are represented as asterisks and the dividers by vertigules This string represents nine boxes and 16 beads with two beads in the rst box three in the second none in the third one in the fourth etc So there is a oneto one matching between arrangements of k beads in n boxes and strings consisting of k asterisks and n 7 1 vertigules The number of such strings is evidently gill Lecture 14 Probability Theory Hash Tables All the laws of probability can be derived from a few basic axioms We start with a sample space which is just an arbitrary set S The elements of S are called elementary events We will assume here that S is discrete ie S is either nite or countably in nite One could be more general An event is any subset of S As is customary we write 73S for the set of all events The empty set 0 is called the null event Two events A B Q S are mutually exclusive if A B Q A probability distribution on S is a mapping Pr 73S 7 R mapping events to real numbers that satis es the following axioms 1 PrA 2 0 for any event A Q S 2 Pas 1 03 PrAU B PrA PrB for any two mutually exclusive events A B Q S More generally if A1 A2 is some nite or countably in nite sequence of pairwise mutually exclusive events then We say that PrA is the probability of the event A or the probability that A occurs For x E S we will abuse notation and write PrM for Prm the probability of the elementary event z Axiom three implies that the probability of any event is the sum of the probabilities of its members elementary events Here are some easy consequence ofthe axioms For any event A we let A denote the complement S 7 A of A in S Pr Pr O This is because 0 0 0 that is Q is mutually exclusive with itself Applying the third axiom we get PrM PrW U 0 Pr Pr Subtract PrM from both sides 0 PrA 1 7 PrA for any event A Exercise 0 PrA U B PrA PrB 7 PrA O B for any events A B Exercise o If A Q B then PrA PrB Exercise 0 PrA 1 for any event A Conditional Probability Let A and B be events with PrB gt 0 De ne PrAB This is the conditiondlprobdbility ofA given B Look at aVenn diagram Note that PrB B 1 This is the probability we would get if we restrict our sample space from S to B rede ne events accordingly and rescale the probability distribution to satisfy the second axiom Dependence Events A and B are independent if PrA O B PrA PrB lf PrB gt 0 then clearly A and B are independent iff PrA PrA B Thus conditioning on B does not affect the probability of an independent event A A1A2 are mutually independent if PrA1 A2 PrA1 PrA2 Examples Let S represent two independent ips of a fair coin ie S H T x HT H for heads T for tails and for any 011 6 HT we set Pra b 14 Let A be the event the rst ip is heads77 Thus A HH H Let B be the event the two ips are different77 Thus B HT T We have PrA PrB 12 and PrA m B PrHT 14 PrA PrB so A and B are independent The following easy theorem relates PrA B with PrB A It forms the basis of Bayesian analysis Theorem 14 Bayes7s Theorem IfA and B are events with positive probability then PrA PrB A PrA B PM A p bidsed coin flip is given by the sample space S H T with PrH p and PrT q 17p where p is some real number with 0 g p g 1 lfwe ip ap biased coin n times independently then the sample space is H T and Pra1a2 4 Hprw i391 40 n where each a E H T and each term of the product is either p or 17p For 0 g k g n there are many tuples with exactly k heads and the probability of each such tuple is pk1ipnik pkqn Thus Prexactly k heads lt2gtpkq ik7 which is just the kth term in the binomial expansion of 1 1 p q lfp 12 then we call the coin unbiased or fair and we have Prk heads 2 Random Variables As above we assume a sample space S with a probability distribution Pr S a R satisfying the usual axioms A random variable over S is any mapping X S HR Thus the probability distribution is itself a random variable The expectation value of a random variable X is de ned to be EX Z Xa Pra 165 Linearity of Expectation For any two random variables X and Y and any real constant c we have ECX Y cEm For example suppose 0 g p lt 1 and we ip a p biased coin until we see tails Then the sample space is S THTHHTHHHTHkT with PrHkT pkq where q 1 7 p Note that this really is a probability distribution since 00 00 q k 7 k 7 7 2qu k0 k0 Let random variable X be the number of heads before the rst tail That is XHkT k for all k 2 0 What is EX lndicator Random Variables If A is an event then there is a natural random variable associated with A namely A the indicator random variable of A The function A maps an elementary event z to 1 if z E A and to 0 otherwise Notice that EIA is just PrA 41 Hash Tables A hash table is an array T1m in this case we say that T has in slots together with a function h mapping key values to integers in the range 1m The function h called the hash function is assumed to be easy to compute We would also like h to look as random as possible We store n elements into the hash table T To insert an item with key k we rst computei hk then place the item at We may have collisions ie two or more different items mapping or hashing to the same index Collisions can be resolved by either chaining or open addressing We ll only discuss chaining which is maintaining at each location a linked list of all the items inserted into T whose keys hash to i We d like to analyze the performance of a hash table assuming that h maps keys to indices uniformly at random independently for different keys For a hash table with m slots containing n items we de ne the load factor a 1 m This is the expected length of a linked list in the table Note that with chaining it is possible that ngtmandsoagt1 We assume that h takes 91 time to compute Clearly then the expected time for an unsuc cessful search is 1 04 The 1 is the time to compute h of the key and the 04 is the time to traverse the corresponding linked list Analyzing a successful search is a bit harder assuming any existing element is equally likely to be searched This is because if we restrict our sample space to just the items that are already in the table then any given item is more likely to be in a longer list than a shorter one Nevertheless the expected successful search time can still be shown to be 1 04 Assume that distinct keys k1 kn are inserted in order into an initially empty hash table with m slots and let oz nm as before We ll assume that each key k is are inserted onto the front of the linked list of keys hashing to This means that the time to successfully search for k is one plus the number of items inserted after k that hash to the same list as k For 1 ij n let Xij be the event that hkj Then we have Esuccessful seach time H Di lH M M 2 5X n71 Oi oz 1 71 77 2m 2 2n The second equality follows by linearity of expectation 42 Lecture 15 Binary Search Trees RedBlack Trees We all know what a Binary Search Tree BST is Access insertion and deletion all take h time in the worst case where h is the height of the tree At best a binary tree of size n gt 0 will have height lg it eg the almost full tree used for the binary heap At worst the height is n 7 1 and tree operations are no faster than with a linked list ie linear time This latter case occurs for example when items are inserted into the tree in order increasing or decreasing Note that Quicksort displays worst case behavior with a sorted array when the pivot is always chosen to be the rst element of the list This is not a coincidence there is a close connection between the sequence of pivot choices and a preorder traversal of the corresponding BST built by inserting items from the array by increasing index By the way the book allows duplicate keys in a BST 1 don t allow them If you really want duplicate keys with different satellite data of course then store all duplicate keys at the same node ie have the node point to a linked list of all the items with that key Although for random insertions and deletions the expected height of a BST is Olg n this is not satisfactory because inputs often don t look random ie some input orders eg sorted or almost sorted occur with above average frequency Thus we would like a way to keep the worst case time for tree operations to Olgn that is keep the height of the tree Olg This is typically done by performing structural alterations to the tree to balance it when it gets too out of balance We need to keep some extra information at each node to help us detect when the tree is becoming too unbalanced One such scheme is the AVL tree which I cover in CSCE 350 Here we ll see a different scheme red black trees A red black RB tree is a BST where each node at any given time has a color red or black If T is a RB tree we assume that any null child pointer points to a phantom leaf node Thus every key bearing node is considered an internal node A leaf has no information other than its color which is always black Thus we can implement leaves by a single shared black node nilT that is pointed to by any child pointer that would otherwise be null in an ordinary BST The conditions for a nonempty RB tree are as follows H The root is always black Every leaf is black If a node is red then both its children are black 7 For any node p in the tree all paths from p to leaves go through the same number of black nodes First we prove that a BST satisfyng these conditions the RB conditions must have height Olg We rst de ne the black height bhm of a node x in a RB tree to be the number of black nodes encountered on some any path from x to a leaf including the leaf but not including z itself Lemma 15 Let T be a Ted black tree with n nodes with height h Then h S 2 lgn 1 43 Proof We prove by induction on the height of a node x that the subtree rooted at x has size at least 2131M 7 1 If x has height zero then it is a leaf with black height 0 and subtree of size 1 2 0 20 7 1 which satis es the base case Now assume that x has positive height and let y and 2 be the children of m Clearly y and 2 have black height at least bhm 7 1 and since y and 2 have height less than the height of m we can apply the inductive hypothesis to y and 2 Let 3m 3y and 31 be the sizes of the subtrees rooted at m y and 2 respectively Then 3m 3y 31 1 2bhy 7 77 2bhz 7 1 2bhm71 7 77 2bhm71 7 1 2bhm 7 1 W N which proves the induction Now let T be the root of T T has height h and since no two adjacent nodes on any path from r to a leave can be red at least half the nodes on such a path must be black Thus bhr 2 712 By the inequality we just proved we have n 2 213110 71 Z 2M2 71 since 71 is the size of the subtree rooted at r ie T itself Solving this inequality for h proves the lemma An empty tree contains just the single leaf node m39lT lnsertion into a RB tree T happens in two phases In the rst we insert a node just as in the case for a BST If T was empty before the insertion then this rst node inserted becomes the root so it must be colored black Otherwise each inserted node is initially colored red The second phase restores the RB conditions which may have been violated after the rst phase This latter phase may only adjust colors of nodes or it may structurally alter the tree We look at this phase in more detail now The tree will be altered by means of rotations There are left and right rotations In a left rotation a parent p and its right child q move so that q takes the place of the parent and p becomes the left child of q The three subtrees below p and q are reattached the only way they can to preserve the BST order of the tree We ll call this operation LeftRotatep q A right rotation is just the inverse of a left rotation We ll call this RightRotatep q Note that the arguments to LeftRotate and RightRotate always come in increasing order Now for the second phase clean up or x up Assume a node x is inserted into a nonempty RB tree T Then z is not the root so it has a parent y paren z and an initial color of red Note that this does not affect the fourth RB condition If y s color is black there is nothing to do both children of z are leaves and hence black The problem is when y is red then we have two red nodes in a row We now assume this case The node y is red so it cannot be the root We consider y s sibling s z s uncle or aunt and their common parent p z s grandparent which must be black If s is red then we switch the colors of both y and s to black and ii switch the color ofp to red unless p is the root in which case we re done Note that we did not structurally alter the tree in this case but merely changed colors of some nodes Although we xed the problem with z and y both being red we may have created the same problem with p and its parent which may also be red p was black originally now it s red If this is the case then we do the entire operation again calling FiXUp recursively say with p and its parent in place of z and y respectively We make progress this way because we get closer to the root Now suppose s is black Here we will have to structurally alter the tree We ll assume that y is the left child and s is the right child ofp If not then we simply swap the roles of left and right in everything that follows If x is a right child of y then we do a LeftRotateyz so that now y is a left child of z otherwise we don t rotate In either event we now have a node 2 and its left child w both red here 2 w z 3 black is the right sibling of 2 red with common parent p black We do a RightRotatezp so that p is now the right child of 2 Finally we make 2 black and p red A simple case analysis shows that the RB properties are restored by these operations so there is nothing more to do Fixing up after regular BST insertion takes time Oh h is the height of the tree in the worst case ie when we must propagate red parent child pairs all the way up to the root so it does not affect the total asymptotic running time for insertion Note also that at most two rotations occur for any insertion Deletion from red black trees is similar rst a regular BST deletion then a X up but there are more cases to consider and we won t do it here Lecture 16 The AVL Condition Augmented Structures A binary tree satis es the AVL condition at a node x if the heights of the right and left subtrees of z differ by at most one The tree itself is an AVL tree if it satis es the AVL condition at each of its nodes Like red black trees AVL trees of size n are guaranteed to have height lg So if we have a BST that is an AVL tree searching is asymptotically optimal ie lg in the worst case One can show exercise that one can maintain the AVL condition given insertions and deletions and that the cost of maintenance of the condition does not asymptotically increase the time of insertiondeletion Thus AVL trees like RB trees are a worst case asymptotically optimal way to implement BSTs Here we show that any AVL tree of size n has height Olg We do this by considering the smallest possible size 771 of an AVL tree with height h 2 71 Clearly we have mil 0 m01 Now suppose h gt O and consider an AVL tree T of height h and of minimum size mh T consists of a root r with left and right subtrees T1 and T2 respectively At least one of T1 and T2 has height h 7 1 say T2 Then T2 has size mh1 since otherwise we can reduce the size of T without changing its height by reducing the size of T2 without changing its height The possible heights of T1 are then h 7 1 or h 7 2 Since T is as small as possible T1 must have the smaller height ie h 7 2 and be of size mh2 if T1 had height h 7 1 then deleting all the nodes on its bottom level would make T1 a strictly smaller AVL tree of height h 7 2 thus reducing the size of T We thus get the recurrence mh mh72 mh71 17 for all h 2 1 This bears some resemblance to the Fibonacci sequence F0 0 F1 17 Fn Fn72 Fnilv 7 for n 2 2 In fact Claim 16 For all h 2 71 mh Fh3 71 Proof lt suf ces to show that the function fh Fh3 71 satis es the same relations as mh since those relations uniquely determine mh We have f71F2711710 f0F3712711 and for h 2 1 M Fh3 e 1 Fh1 Fh2 1 Fh1 1 Fh2 1 1 fh72fhi11 Thus fh satis es the same relations as mh so fh m for all h 2 71 D In a previous exercise you showed that F 4ph where 4p 1 i 16 is the Golden Ratio Thus m Lph3 LpSLph 4ph Thus for any AVL tree of size n and height h we have and hence Taking the logW of both sides gives h Olog n Olgn which is what we wanted to show Augmented Structures Sometimes it is useful to add more information to data structure to allow it to do more things For example consider the problem of dynamic order statistics You have a collection of 71 keys that is changing over time with keys being inserted and deleted You wish to allow the usual dictionary operations such as insert delete look up print in order etc so you use a BST say a red black tree Suppose you also wish to support the Select operation which nds the kth smallest key for input k You can always do this in time k lgn say by cycling through the rst k 46 elements in order This is ne if we expect that Select operations will only be done rarely But if they are done frequently we can do much better Maintain an additional eld in each node that contains the size of the subtree rooted at that node If we have this then Select can easily be done in Olgn time It is easy to show how this extra eld can be updated correctly with insertiondeletion without affecting the asymptotic run times of those operations even if rotations are allowed eg for an AVL or red black tree Lecture 17 Dynamic Programming Sometimes a recursive implementation is too ine icient because of redundant recursive calls If the range of possible values passed to recursive calls is not too large then it is usually better to build the solution bottom up rather than solve it recursively top down This bottom up technique which usually involves lling in entries of a table is called dynamic programming Example computing Fibonacci numbers binomial coef cients The sequence of Fibonacci numbers Fnn20 is given by the relations F0 0 F1 1 Fn Fn72Fn717 for n 2 2 One could translate this directly into C code unsigned int fibunsigned int n i if n0 return 0 if n1 return 1 return fibn2 fibn1 This code will correctly compute F but it is very ine icient For example fig5 calls fib3 recursively twice and so on The number of redundant recursive calls is exponential in n A much saner approach is to use the relations to ll up a table with the Fibonacci sequence unsigned int fibunsigned int n unsigned int tab new unsigned int n2 tab0 O tab1 1 for i2 iltn i tabi tabi2 tabi1 return tab 11 lgnoring over ow this routine runs linearly in n This is a classic example of dynamic programming The code above can be improved further with the observation that only two adjacent Fibonacci numbers need to be remembered at any given time thus we only need constant extra space 47 unsigned int fibunsigned int n unsigned int current0 next1 temp for ngt0 n temp current next current next next temp return current Exercise can you get by with only two local variables Example optimal order for matrix multiplication A m x 71 matrix is a two dimensional array of numbers with m rows indexed 1 m and 71 columns indexed 1 n for m n 2 1 Two matrices A and B can be multiplied together forming the product AB provided they are compatible which means that the number of columns of A is the same as the number of rows of B Multiplying an m x 71 matrix A by an n x p matrix B yields an m x p matrix C AB where M 01m Alivlelkvjl39 w H 1 Thus the straightforward way of multiplying A with B requires mnp many scalar multiplications which dominates the total running time Matrix multiplication is associative ie ABC ABC It is not commutative however it may be that AB 7 BA Although ABC ABC so the order of multiplication does not affect the result the time taken for one order may be vastly different from the time taken by the other For example suppose A is 5 x 20 B is 20 x 2 and C is 2 x 10 Then computing ABC requires 0 5 20 2 200 scalar multiplications for computing AB plus 0 5 2 10 100 scalar multiplcations for matrix multiplying the result by C for a total of 300 scalar multiplications On the other hand computing ABC requires 0 20 2 10 400 scalar multiplications for computing BC plus 0 5 20 10 1000 scalar multiplcations for matrix multiplying the result by C for a total of 1400 scalar multiplications Thus if we are multiplying lots of matrices together we can get signi cant savings by choosing the order of multiplication wisely Suppose we have a list of matrices A1 An where A and A141 are compatible for 1 g i lt n Thus we have integers 190191 pn 2 1 such that A is pirl Xpi Given these values pi we would like to nd a way to fully parenthesize A1 An to minimize the total number of scalar multiplcations This is a job for dynamic programming For 1 g i g j g n we will let Ainj denote the product AiAi1A7z Note that Ainj has dimensions pirl x pj Suppose i lt j and that A A7 has been optimally parenthesized Then 48 the last matrix multiplication to be performed will be multiplying some Aim by Altk1j where i g k lt j is chosen to minimize the overall number of scalar multiplications This last matrix multiplication alone requires piilpkpj scalar multiplications Further7 Aink and Ak1j must both be parenthesized optimally7 for otherwise an improved parenthesization of one or the other will lead to a better parenthesization of Ainj overall Let mi7 j be the optimal number of scalar multiplications needed to compute Aij From the considerations above7 we have 70 ifij m M minigkltjm k mk 17jpi1pkpj in lt31 The optimal number of scalar multiplications for computing A1 is then 77117 Note that each mii 07 because is just Ai and so there is nothing to compute A naive implementation of mi7 j as a recursive function would take exponential time lnstead7 we note that there are only nn 12 many different m values that need to be computed Thus we can compute the m values by putting them into a reasonably sized array m1 n 1 Each diagonal element will be 0 Whenever we compute mij with i lt j we already have computed mi7 k and mk 173 for all i g k lt j so computing mij is straightforward In this case7 we also wish to keep track of the value of k that achieves the minimum7 since this will tell us where Ainj can be optimally split We could put these k values in another two dimensional array7 or we could just use mji to hold these values7 since these entries are not being used for m values MatrixChainOrderp7 n p0 n is an array of positive integers Returns an m array as described above let m1 7171 n be an integer array for ien downto 1 do mi 0 for jez 1 to 71 do compute mij mi for kez to j 7 1 do 8977112 kl mlk 17jl Pli llPlklPljl if s lt mij then mi jles mjiltk return m What is the running time of this procedure How much space is used Assume that the matrix entries do not get very large Example longest common subsequence Two nite sequences of objects X 17zmgt and Y lt91ymgt can be considered similar if they have a long subsequence in common For example7 if two strands of DNA have a long sequence of base pairs in common7 then they are likely to have descended from a recent common ancestor We d like to nd the length of a longest common subsequence LCS of X and A subsequence of a sequence X is any sequence obtained from X by removing zero or more elements from X Thus lt21 72k is a subsequence of 1 7mm iff there exist indices 1 1 lt i2ltltik msuchthatzjmijforall1 j k 49 Here is a recursive solution to the problem of nding an LCS of X and Y If m 0 or n 0 that is one of the sequence is empty then clearly the only LCS is the empty sequence of length 0 This is the base case Now suppose m n gt O and consider the pre xes Xm1 and Yn1 of X and Y respectively If Z is any sequence we let Z denote the sequence containing the rst i elements of Z If mm y then clearly any LCS of X and Y must end in this common value and be preceded by an LCS of Xm1 and Yn71 lf mm 7 y then any LCS of X and Y includes at most one of mm and yn as its last element Thus such an LCS must be either an LCS of X and Yn1 or an LCS of Xm1 and Y whichever is longer Let clj be the length of an LCS of Xi and Yj for 0 g l g m and 0 g j g n Then 0 if lj 0 else 01M Cliil illirl ifiyj7 maxclj 7 1 cl 7 1 otherwise Lecture 18 LCS continued Greedy Algorithms Huffman Codes The recurrence relations for clj make them easy to compute with dynamic programming using nested for loops for l and j where each index is increasing This algorithm takes mn time and space but the space can be reduced to minm How can we recover an actual LCS if we want one We keep track of how each cl j is obtained If M yj then we label clj with a diagonal arrow otherwise we label clj with either a left arrow 9 or an up arrow T whichever points to the entry equal to clj if there is a tie either arrow can be used this re ects the fact that there may be more than one LCS or that the same LCS can be obtained in more than one way When the table calculation is complete we build an LCS by following the arrows back from cm n prepending z onto the LCS we are building whenever a diagonal arrow is encountered at some row 2 One proves that this is indeed an LCS by induction on m n much the same way as the proof that the relations obeyed by clj imply correctness of the cl j Greedy Algorithms For some optimization problems even dynamic programming can be overkill When reducing a problem for a recursive solution one typically has a choice of possible reductions one of which eventually leads to a globally optimal solution Sometimes we don t know which choice is the right one so we must try all of them by dynamic programming say Sometimes however if one chooses a locally optimal reduction by some measure each time then this provably leads to a global optimum A greedy algorithm is one that follows this strategy ie it always picks a locally optimal step or more informally a step that looks best at the time If correct this can lead to signi cant speed up over trying all possible reductions Huffman Codes We ll only look at one example of a greedy algorithm constructing an optimal binary pre x code for an alphabet given that each letter has a frequency Such a code is called a Huffman Code Huffman codes are used for data compression Given an alphabet C 01 on a binary 50 pre x code for C is a mapping 4p C H 01 such that 4pc is never a pre x of 4407 for any i 7 j Elements of the range of 4p are called codewords We can extend 4p to encode a string a cilciz cik E 0 as the concatenation W7 Cn ci2 WM 6 071 Since no codeword is a pre x of any other codeword the string a can be uniquely recovered from Ma and a description of 4p itself Such a property of a code is called unique deooddbz39lz39ty All pre x codes are thus uniquely decodable further the decoding can be done in real time by reading the code once left to right Example Suppose C 1 b c d A simple pre x code for C is to encode each character as two bits 00 01 10 11 a b C 1111 Suppose a E 0 is a string of length 1000 Then this code encodes a by a string of 2000 bits If the frequencies of the letters in a are not uniform however we may be able to nd a better code one whose encoding of a is shorter Suppose a occurs in a about half the time 0 occurs about one quarter of the time and b and 1 each occur about one eighth of the time Thus we have the following letter frequences for a letter frequency b c d 125 Suppose we use the following pre x code instead a gt gt 0 b H 110 H 10 H 111 Then a is now encoded by a bit string of length 500 1 250 2 125 3 125 3 1750 which is only seven eighths as long as with the original code The reason this code does better is that we encode more frequent letters by shorter strings There are some uniquely decodable codes that are not pre x codes but it can be shown that for any uniquely decodable code there is a pre x code that compresses just as much Hence we can restrict our attention to pre x codes So our task is given an alphabet C with a frequency corresponding to each letter nd a binary pre x code that yields the shortest encoding given the frequencies Such an optimal code is a Huffman Code An easy way to picture a binary pre x code for an alphabet C is by a binary tree where each letter of C is the label of a unique leaf Then the codeword for a given letter c is found by taking a path from the root to the leaf 0 if the path goes to the left child then the next bit of the codeword is 0 if right child then the next bit is 1 Since no labeled node is the ancestor of any other the tree describes a pre x code Draw the tree for the example above Here is the algorithm to construct a Huffman encoding tree bottom up given an alphabet C 01 on where each c E C has a integer frequency attribute c gt O Huffman I reeC Let Q be a min priority queue empty lnsert all letters 0 E C into Q keyed by frequency For 2 91 to n 7 1 do z e ExtractMinQ y lt ExtractMinQ Form a new internal node 2 lelelml flyl leftzltx Tigh zley Insert 2 into Q Return the root of the tree Return ExtractMinQ The algorithm works by repeatedly merging a pair of nodes into a new node whose frequency is the combined frequencies of the original nodes What is greedy about it By merging two trees we are essentially adding 1 to the lengths of all the codewords in the two trees by virtue of the two edges from the new parent Since we are making these codewords longer we want their total frequency to be as low as possible Hence at each step we only merge the two available nodes with lowest possible frequency The algorithm above can be recast as a recursive algorithm It may be easier to see how the correctness proof works for the recursive version Huffman I reeC if 0 1 then return the sole element of C let m y be two elements of C with lowest freqency let 2 C be a letter flzleflzl flyl CH0 7 mi u z r e HuffmanTreeC let T be the tree rooted at r make leaf 2 in T an internal node with children z and y return r Lecture 19 Huffman Codes Proof of Correctness To show that this algorithm produces an optimal tree we rst give an expression for the cost of a tree T which is the total length of the encoding of a string whose letters occur with the given frequencies The length of the codeword for a letter c E C is the depth of c in T Thus the cost of the tree is BT Z flcld c 060 where dTc is the depth of c in the tree T We x an alphabet C C1 cn where n 2 2 and each ci has a frequency ci Our proof follows from two lemmas The rst says that the initial greedy merging step we take inside the for loop is safe in the sense that we won t miss an optimal tree starting this way For our purposes an encoding tree for C is a binary tree whose leaves are identi ed with the elements of C and each of whose internal nodes has two children An encoding tree T for C is optimal if it BT is minimum among the costs of all encoding trees for C Lemma 17 Let T be any encoding tree for C and let xy E C haue the two lowest frequencies of any letter in C Then there is an encoding tree T for C such that m and y are siblings on the deepest leuel of T and further BT BT Proof Let a and b be the two leftmost nodes on the deepest level of T It is easy to see that a and b must have a common parent Now if z y a b then we let T T and we are done Otherwise suppose WLOG that z ab and a z Then z is somewhere else in T and a 2 x by the choice of z and y Let T be the tree that results from swapping a with z in T Then the only difference between T and T is with the nodes z and a where d m dT a and dTa dT Thus we have BTBT flv ld melald a because a is a node of maximum depth in T Now if b y we re done Otherwise alter T in the same manner as above by swapping b with y to get another tree with the same or smaller cost satisfying the lemma The next lemma nishes the proof of correctness It says that our sequence of reductions actually produces an optimal tree Lemma 18 Let m and y be two letters in C with minimum frequency Let C C 7 U be the alphabet obtained from C by remouing m and y and adding a new letter 2 not already in C De ne the frequencies for letters of C to be the same as for C except that 53 Suppose that T is any optimal encoding tree for C and let T be the encoding tree for C obtained from T by replacing leaf 2 with an intemal node with children m and y Then T is an optimal encoding tree for C Proof First we compare BT with BT The only difference is that z in T is replaced with the parent of added nodes z and y in T and so d m dTy dT 1 All the other nodes are the same in T as in T Thus Ba MT 1 BT z Now we ll prove the lemma by contradiction Assume that the hypotheses of the lemma but that T is not an optimal encoding tree for C Then there is some encoding tree T for C with BT lt BT We ll use T to construct an encoding tree T for Cquot with BT lt BT which contradicts our assumption that T was optimal By Lemma 17 we may assume WLOG that z and y are siblings in T Let T be the tree we get by removing z and y and replacing their parent with 2 Note that T bears the exactly analogous relation to T as T bears to T namely having 2 instead of a parent of z and y Thus we can do the exact same calculation as we did above with BT and BT but this time with BT and BT This gives BHWBHWfM M Subtracting the second equation from the rst we get BT 7 BT BT 7 BT The left hand side is positive by assumption so the right hand side is also positive But this means that BT lt BT so T is not optimal D It follows from this lemma that our algorithm is correct the rst iteration of the for loop effectively reduces the construction of T to that of T Assuming inductively that the rest of the algorithm produces an optimal T we know by the lemma that our T is optimal Lecture 20 Amortized Analysis When performing a sequence of n operations on a data structure we often are less concerned with the worst case time taken by any single operation in the sequence but rather the worst case cost per operation averaged over the n operations Example binary counter Maintain an integer in binary Operations Reset to zero lncrement Display Assume Reset is done once at the beginning to initialize followed by n increments followed by Display We will need k lg 71 1 bits for the counter lncrementing is done in the usual way adding 1 with possible carries In the worst case a single increment may take k steps eg when a carry propagates through all k bits So we immediately get a bound of 0nk Onlgn for the total time taken for incrementing for an average of 0k time per increment This is not tight however and we can do much better The key observation is that the worst case does not happen very often In fact we require exactly i carries if and only if the result of the increment is an odd multiple of 2 since the carries will clear the i least signi cant bits leaving the 1st least signi cant bit equal to 1 This gives us a way to better compute the total time Tn taken by n increments starting at zero We ll assume that each carry takes unit time and that the total cost of an increment other than carries is also unit time so that the total cost of an increment is one more than the number of carries We group the sum for Tn by the number i of carries required Note that there are 0n2i many odd multiples of 2 between 1 and n gn Tm Z 10 7121 10 ngnj 4 2 O 71 Z 2 1 Oltn 2 gt i0 n O 7 since the in nite sum converges Three methods for analyzing the amortized complexity aggregate accounting and potential The potential method subsumes the other two Example stack with multipop Amortized time for a sequence of 71 operations starting with an empty stack is 01 per operation since at most 71 items are ever added to the stack and each such item is handled for only 01 time Aggregate analysis Example dynamically resizing an table array Assume Insert and Delete take unit time each one dollar If only lnsert is performed then a standard practice when the array becomes full is to allocate another array twice the size and copy elements from the old array into the new Assume that the cost of the actual allocation is dominated by the copying costs so we ignore it Thus the array will always be at least half full We charge three units three dollars for each insertion One dollar pays for the current insertion one dollar pays for the next time the item is copied into a larger array which we assume has unit cost and the last dollar pays for another item s next copy into a larger array Assuming an array currently of size 3 2 2 s is a power of 2 containing exactly 71 32 items Then exactly 71 more items will be inserted before the array is resized Each such additional item pays three dollars one of which is spent immediately to insert the item with the other two put in the bank After the 71 additional insertions there are exactly 271 3 dollars in the bank which is just enough to pay for the 3 items being copied from the smaller to the larger array We withdraw all this money from the bank Accounting method It is desirable to save space by allocating no more than 01 space per item so if Delete operations are possible we want to reduce the space allocated for the array when the number of items reaches 14 of the capacity of the array Why not 12 We ll use this case to illustrate the potential method The Potential Method We analyze the amortized complexity of a sequence of operations a1 an on a data structure S Let S be the state of the S after the ith operation a SO is the initial state of S before am For 0 g i g n we assign a real value ltIgtSi the potential which depends on the state of S lnitially ltIgtSo O and ltIgtSi will always be nonnegative In analogy to the accounting method the potential represents how much money the data structure has stored up to pay for future operations lf 0 is the actual cost of operation at then we de ne the amortized cost of operation a to be 239 61quot 7 That is 07 is the actual cost adjusted by the net change in the potential Let T be the total actual time for operations a1 an Since the potential starts at zero and remains nonnegative we have T H Ci ISn M H c ltIgtSi 7 IgtSzgt1l H j H 7 H H Thus the total time is bounded from above by the total amortized time and so any bound on the amortized time gives at least as good a bound on the actual time We choose a potential function to make the worst case amortized time of any operation as small as possible Back to Array Resizing Let n be the current number of items in the array between operations and let 3 be the current size of the array Set 04 ns the load factor Then it is always the case that 04 2 14 De ne the potential in this case as 17 27173 ifOzZlQ 7 32771 ifalt12 There are several cases to work through here Exercise 0 04 lt 12 after Insert 0 04 lt 12 before Insert and Oz 2 12 afterwards o a 2 12 before Insert and 04 lt 1 afterwards 0 Insert makes 04 1 so array needs expanding o 04 2 12 after Delete o a 2 12 before Delete but 04 lt 12 afterwards 0 04 lt 12 before Delete and 04 gt 14 afterwards 0 Delete makes 04 14 so array needs contracting In all cases we see that the amortized time of any operation is always 01 so this is optimal Potential Method for Previous Examples Multipop stack Let ltIgtS be the number of items in S Push only increases the potential by 1 so its amortized cost is 2 Pop and multipop both have amortized cost 0 Binary counter Let ltIgtC be the number of ones in counter C Then each increment just changes the least signi cant 0 to 1 and each carry changes a 1 to O and thus is compensated for by a decrease in the potential Thus increment has amortized cost 01 When is amortized complexity not an appropriate measure of complexity ln real time systems especially critical systems or when data structures are shared between many users eg in a database so that fair access is desired Lecture 21 Binomial Heaps Disjoint Sets Mergeable Heaps A mergeable heap min heap supports all the usual heap operations MakeHeap lnsert Min imum ExtractMin as well as supporting Union which takes two mergeable heaps and returns a single mergeable heap with all the items of the two heaps combined the two original heaps are destroyed Without Union regular binary heaps work ne but combining two binary heaps into one needs linear time We ll see an implementation of mergeable heaps binomial heaps where all these operations including Union take time Olgn in the worst case These heaps also support DecreaseKey and Delete in Olg n time Binomial Heaps A binomial tree Bk of height h is an ordered tree whose shape is de ned recursively in k as follows 0 B0 is a single node 0 For k gt O Bk is the tree that results from linking two binomial trees Bk1 of height h 7 1 so that the root of one becomes the leftmost child of the other Draw a picture of B0 B1 B2 and 133 The following properties of Bk are veri ed by induction 0 Bk has exactly 2k nodes 0 Bk has height h c There are exactly many nodes at depth i in Bk for 0 g i g k lnduction on k and o The root of Bk has degree k which greater than that of any other node 57 o If the children of the root are numbered from left to right by k 7 1 k 7 2 0 then child i is the root of a subtree Bi It follows immediately that the maximum degree of any node in a binomial tree of size n is lg n A binomial heap H is a list of binomial trees whose nodes contain items satisfying the following binomial heap properties 0 Each binomial tree in H obeys the usual min heap property the key of any nonroot node is at least the key of its parent The tree is min heap ordered o The heights of successive trees in the list H are strictly monotone increasing In particular no two trees in H have the same height Suppose H has size n gt 0 and consists of Z gt 0 many trees Let k0 lt k1 lt lt 14 be the sequence of tree heights Then since 14 2 Z 7 1 we have 71 n 21 2 i0 This implies Z Olg Conversely any number n gt 0 is uniquely expressible as a nonempty sum 23 2ki of increasing powers of two thus the whole shape of H is determined exactly by its size alone We use the leftmost childright sibling representation to implement binomial heaps We use the right sibling link to link the roots of the trees together the root list pointed to by headH Each node x also contains the number of its children in degreem Making an Empty Binomial Heap An empty binomial heap H is represented by headH being null This is what MakeHeap accomplishes and it takes 01 time Finding the Minimum in a Binomial Heap Traverse the list of tree roots and return the minimum key found This takes time linear in the number of trees which is Olg Merging Two Binomial Heaps Given binomial heaps H1 and H2 we traverse forward the root lists headH1 and headH2 merging the two lists by increasing tree height If we encounter a tree Bk in H1 and another tree Bk in H2 then we perform a carry operation we link the two together into a single Bk by making the root with bigger key the child of the root with smaller key We then merge this new Bk a one item list in with the two other lists Since we never encounter more than three trees of the same size this way it will work This is the Union operation Since we do a constant amount of work on each tree the time we take is linear in the total number of trees which is logarithmic in the size of the newly created heap lnserting into a Binomial Heap To insert z into H with 71 items we rst make a one element heap H containing m then merge it with H This takes time Olgn Extracting a Minimum from a Binomial Heap To remove a minimum element from H we rst nd a minimum element which will be the root of one of H s trees Bk We remove Bk from the root list headH Then we remove the root of Bk leaving a list of exactly k children of heights k 7 1 k 7 2 0 We then reverse this list to make a binomial heap H Finally we merge H with H The total time for this is Olgn since k Olg n we can reverse the list of children within this time and nding a minimum and merging each can be done within this time Decreasing a Key in a Binomial Heap After decreasing the key of some node in some tree Bk of H we simply cascade the node up through Bk as necessary just like we did with binary heaps Since Bk has height k Olg n the time taken is Olg Deleting a Node from a Binomial Heap To delete an arbitrary node x in H rst perform DecreaseKey decreasing m s key to foo Then do an ExtractMin The two actions combined take Olg 71 total time Question How can we augment a binomial heap so that nding the minimum takes 01 time without affecting the asymptotic times of the other operations This is mostly an academic exercise there is not much practical reason to do this Lecture 22 Disjoint Sets Starting Graph Algorithms Another useful data structure is one for maintaining a collection of pairwise disjoint nonempty sets C 1 Sk Each set 5 contains a unique distinguished element called its representative Any element of S can serve as its representative but there are never two or more representatives of S at the same time The set S is identi ed by its representative The three supported operations are as follows MakeSetm creates a new set whose sole element is z The representative of the new set is z of course To maintain disjointness with other sets we require that m not belong to any other set Findz returns the unique set S containing z Actually it returns the representative of Si Unionxy merges the set containing z with the set containing y into a single set if the two sets were different The two original sets are destroyed Note that we can test whether two elements z and y are in the same set because this is equivalent to Findm and Findy being equal Applications This data structure has many applications Example connected components in a graph Example building a maze Example Uni cation pattern matching We ll see others We often represent each set in the collection as an unordered rooted tree of its elements with the representative at the root and the other elements linked using parent pointers only This is the so called disjoint set forest We can implement Findz by following the parent pointers along the path from x to the root We can implement Unionz y by rst nding the roots of the corresponding trees using Findm 59 and Findy then making one root a child of the other The one remaining root becomes the representative of the combined set This basic approach works If we are not careful however it may produce tall trees which could make Findm costly in the worst case We can remedy this by following two additional heuristics Pathcompression When performing Findz once the root is found alter the parent pointers of all nodes on the path just traversed to point to the root directly This requires keeping each node along the path in some data structure like a stack during traversal Unionbyrank When performing Unionz y choose more wisely which root to make a child of the other Augment the data structure by maintaining some kind of extra information at each root its rank to help with the decision Always make the root with smaller rank point to the root with larger rank then update the rank of the remaining root There are different possibilities for union by rank If we keep track of the height of each tree at its root so rank equals height then we would always make the root of the shorter tree the child of the root of the taller one This won t increase the height unless the two heights are equal to begin with Unfortunately maintaining the height of a tree eg updating it correctly after a Find is too di icult and timeconsuming for this approach to be useful Instead we de ne the rank as if it were the height except that we don t try to alter it after a Find operation Thus the rank is an upper bound on the height When combining via Union two trees T1 and T2 with ranks T1 and r2 respectively we increment the rank of the combined root if 71 72 and otherwise leave it alone Analysis The time to perform m disjoint set operations on n elements is known to be Oman where 04 is a monotone very slowly growing but still unbounded function of n For example an grows even more slowly than lg 71 So for all practical purposes we have nearly constant amortized time per operation We won t do the analysis here but it is very clever and you are welcome to read it from the book I won t test on it Graph Algorithms Let G V E be a directed graph digraph V 121 vn is the set of vertices of G and E Q V x V is the set of edges of G If 1412 6 E then we say that v is adjacent to u but not vice versa unless 1214 6 E adjacency is not necessarily a symmetric relation There are two standard ways of representing G with a data structure Adjacency Matrix We encode G by an n x 71 matrix A whose ijth entry is 7 1 Uh Uj 6E Alzlj T 0 otherwise forlgij n Adjacency List We maintain an array V1 n of n linked lists where is a reference to a list of records representing edges leaving 1 in no particular order Each record in the list records a different index j such that 12312 E E This is also known as the edge list representation These data structures may be augmented with other information such as edge weights vertex weights Boolean markers et cetera We sometimes depict the directed edge uv as u a v or as v e ii We usually disallow self loops in a graph ie edges of the form 1 a 1 We can use the same structures to represent undirected graphs by considering a undirected graph to be a special case of a digraph where each undirected edge u lt gt v is represented by the pair of directed edges u a v and u e 12 Thus the adjacency matrix for an undirected graph is symmetric Aij AM for all ij Note that VP If 9lVl2 then we say that the graph is dense Likewise if El 0lVl2 then the graph is sparse We are abusing terminology here These properties really only apply to in nite classes of graphs rather than individual graphs The adjacency matrix for G has size lVlZ and the adjacency list for G has size lVl If G is dense then both representations above are roughly equivalent in size If G is sparse however the adjacency list representation is more compact and so we generally prefer it We ll assume that all our input graphs are given in the adjacency list representation and hence the size of G will be the size of this representation of G ie lVl If G is dense the adjacency matrix representation may be more useful if we want to nd out quickly whether two given vertices are connected by an edge It s easy to convert between the two representations Exercise The edge list representation is convenient for following edges forward but inconvenient for following edges backward which we occasionally wish to do For any digraph G V E we de ne CT to be the graph V E where E vu l uv E Thus GT is the same as C but with all edges pointing in the opposite direction Traversing an edge backward in G is thus the same as traversing the corresponding edge forward in CT Describe an algorithm that takes an edge list representation of any digraph G and produces an edge list representation of CT Your algorithm should run in linear time linear in the size of the input representation We use the notation GT because the adjacency matrix of CT is the transpose of that of G Some people use CR or GT instead Lecture 23 Graph Search Probably the most fundamentally useful graph algorithm is search which systematically visits all vertices or edges in a graph or part of a graph There are different kinds of graph search but all common types of graph search are special cases of a generic search algorithm that we now describe This is not in the book During the search each vertex will be one of three colors white grey or black White vertices are those that have not been found yet grey vertices are those that have been discovered but not completely processed black vertices have been completely processed and will not be processed further We use some collection B called the box to hold the grey vertices The data structure used for B can vary depending on the type of search The only operations we require B to support are MakeB re initializes B to be empty EmptyB tests whether B is empty Insertm B inserts a vertex z into B and DeleteB removes and returns some element x from B assuming B is not empty Possible box types include stack queue or priority queue We assume that each vertex has a color attribute that is either white grey or black GenericSearch takes a graph G V E as input and searches all white vertices of G GenericSearchG for each vertex v of G do if colorM white then GenericSearchAtG v GenericSearchAt takes a graph G V E and a vertex v E V as input and searches that portion of the graph that is reachable from 1 through white vertices only We use three visitation subroutines Start Update and Finish These three routines will vary depending on the type of search They may also share a persistent state eg they build some structure incrementally over several calls We assume that none of these routines alters the color attribute of any vertex we do that explicitly in GenericSearchAt GenericSearchAtG7 v Assumes colorM white B is a local box MakeB Startv m39l colorvltgrey lnsertv7 B Updatev m39l7 B repeat u e DeleteB Finishu colorultbluck for each w adjacent to u do if colo w white then we ll say that u discovers w here Startwu colorwltgrey lnsertw7 B if colo w grey then Updatew u B until EmptyB GenericSearchAt nds new vertices by their being adjacent to old ones The subroutine Start is called on a vertex when it is rst found and it enters the box its color changing from white to grey Once in the box the vertex will be Update d one or more times once for each edge leading to it from a black vertex The time taken by GenericSearchAt is dominated by the calls to Insert Delete Start Update and Finish The following table gives the maximum number of times each subroutine is called Routine of calls Update 1 Breadth First Search BFS This is the type of search that results from implementing the box B as a simple queue BFS nds new vertices in order of increasing unweighted distance from o It is used for example to nd the unweighted distance from v to any node The unweighted length of a path is the number of edges along the path the unweighted distance from node n to node v is the minimum unweighted length of a path from u to v or 00 if there is no path Depth First Search DFS This type of search results from implementing B as a stack DFS goes out as far as possible along a path from 1 before backtracking to another path Search Trees A useful structure that can be produced from a search from a vertex v of G is a search tree A search tree is an unordered rooted tree with root 1 on some of the vertices of G whose parent to child edges form a subgraph of G A vertex is added to the tree as a new leaf when it is discovered with parent the vertex that discovers it Assuming that each vertex has additional attributes parent leftmost and rightslbllng we build a search tree by including the following code in Startuw parentM ltw leftmostultnll Tightslbllngml lt leftmostw leftmostwltu This code sets it to be a leaf with parent w and adds it onto w s list of children In a breadth rst search tree the path from the root to any vertex in the tree is a shortest path unweighted Depth rst search trees are useful for nding among other things strongly connected compo nents in a digraph and articulation points in an undirected graph A digraph is strongly connected if for every ordered pair 1412 of vertices there is a directed path from u to 1 In a general digraph G we ll say that two vertices u and v of G are equivalent u E v if there are directed paths from u to v and from v to u The relation E is clearly an equivalence relation and the equivalence classes are the strongly connected components of G For an undirected connected graph G an articulation point is a vertex whose removal disconnects the remaining graph Dijkstra s Algorithm for SingleSource Shortest Weighted Path 64 We are given a digraph G V E where each edge 1412 has a real valued attribute cu 12 called the cost or distance of the edge 1412 Numerical attributes such as these are called edge weights In the adjacency list representation edge weights are stored in the linked list nodes We are also given a source vertex 3 E V We would like to nd the distance and a shortest directed path if it exists from s to each other vertex where the length of a path is the sum of the costs of the edges along the path BFS solved this in the case where all the edge costs are equal to one but here they could be arbitrary except that we forbid cycles of negative length For example we want to nd the shortest routes from the warehouse to each of the retail stores A beautiful algorithm of Dijkstra solves this problem in the case where all edge costs are nonnegative It is a special case of GenericSearchAtG 5 above where 0 Each vertex v has two attributes 7 dv is a real number that will eventually hold the shortest distance from s to v If v is not reachable from s then we make the distance 00 by convention 7 My will eventually point to the predecessor of 1 along a shortest path from s to 1 Following these elds backwards gives a shortest path from s to 1 Initially ds 0 and dv 00 for all u 7 3 Initially Mu ml for all u E V The box B is a min heap with items vertices keyed by their 1 attributes Insert and DeleteMin are the relevant operations We ll also use DecreaseKey see Update below Start and Finish are both no ops The Updatev u B procedure checks if new evidence has been found to decrease dv based on 1 being adjacent to u It is de ned as follows Updatev u B if du cu U lt dv then This implicitly sets dvltdu cuv DecreaseKeyB v du cu v bvltu We don t bother calling this routine initially on 3 Note that d values can only decrease they never increase The correctness of the algorithm all hinges on the fact that when a vertex v is removed from B its 1 and b attributes are correct We prove this by induction on the number of times DeleteMinB has been called so far Here is the idea First it is clear that we never set the d attribute of any vertex z to a nite value unless we actually have evidence that there is a path from s to z with at most that length This is easily shown by induction So now we only need to show now that aim is not too large when 1 leaves B Suppose a vertex v is just about to be removed from B Then dv is a minimum key in B Suppose there is a path p from s to v of length strictly less than dv Following p backwards from u there must be a point where we rst go from a nonblack vertex z to a black vertex y since u is grey but 3 is black We now know the following are true at this point in time o z is grey and thus z is in B Since y is black and z is adjacent to y z is discovered so it cannot be white dy is at most the length of that part ofp that goes from s to y Since y is black it was already removed from B previously so by the inductive hypothesis dy is correct ie it is the length of a shortest path from s to y so dy certainly can be no more than the length along p from s to y 1M is at most the length of that part of p that goes from s to z Since y is black at some point the edge yz was previously traversed ie Updatezy B was called When this happened 1M was set to dy cy m if it was larger But dy cy m is exactly the length of that part ofp that runs from s to m 1M lt du By assumption du is strictly greater than the length of p which in turn is at least the length along p from s to z here we need the fact that there are no negative edge costs This last item is a contradiction because du has to be the minimum key in B Thus no such shorter path p can exist To show that the b attributes are correct we observe by induction again that at any time in the algorithm and any vertex v if bu 7 nilthen bu is the predecessor to 1 along a path of length du from s to u The worst case running time for Dijkstra s algorithm is 9lVl lg if we implement B as a binary heap The reason for this is that B may have size as much as but no more than V and heap operations are logarithmic time Lecture 24 Minimum Spanning Trees You have a bunch of nodes computers or other devices and you want to connect them all to a common LAN in the cheapest possible way by laying physical links between pairs of nodes The only restriction is that there be a path in the network connecting any pair of nodes the path may go through several other nodes lf ci j is the cost of stringing a link between nodes i and j then the total cost of setting up the network is the sum of the costs of all the links strung One obvious rule to follow assuming all the ci j are positive is that there should be no cycles in the network for if there were a cycle p removing one link from p would give a cheaper network with the same connectivity So the cheapest network will be a tree spanning all the nodes We ll go over two greedy algorithms that each nd a minimum spanning tree in a graph The proofs of correctness for both algorithms are similar relying on the same lemma De nition 19 Let G be an undirected connected graph A spanning tree for G is a collection of edges of G that forms a tree on all the uertices of G If G has edge weights then the weight of a spanning tree T is the sum of the weights of the edges in T A minimum spanning tree for G is a spanning tree whose weight is minimum among all possible spanning trees It s a good exercise to prove the following Fact 20 Let G be an undirected graph with n uertices 66 o If G is connected then G has at least n 7 1 edges 0 If G has at least n edges then G has a cycle 0 IfG is a tree le connected and acyclic then G has exactly n71 edges This follows from the two previous facts Edge weights costs for a graph G V E are assumed given by a function w E a R Kruskal s Algorithm This algorithm uses a system of disjoint sets of edges KruskalMSTG w THE for each u E V do MakeSetv sort edges of E into increasing order by w for each 1412 6 E in order do Invariant proved below T is a subset of some MST for G if FindSetu 7 FindSetv then TltT U u 11 Unionu v T is an MST for G proved below return T During the execution of this algorithm T will be a forest of trees unconnected to each other starting with W many empty trees single isolated vertices with no edges We repeatedly add to T the lightest possible edge that joins two unconnected trees together If G is not connected then no spanning tree exists The algorithm can detect this G is connected if and only if exactly W 7 1 Union operations are performed if less then T will be a forest of at least two trees Prim s Algorithm This is a special case of generic search It is similar to Dijkstra s algorithm but with one crucial difference in the Update routine Each vertex has a real valued attribute d and a vertex valued attribute 7139 The MST is built as a rooted tree whose root can be any vertex The nal 7r value of each vertex will be its parent pointer PrimMSTG w for each vertex U do dvltoo 7rvltnll let 3 be any vertex of G dslt0 GenericSearchAtG s MST is encoded in 7r values T90 for each vertex U do if 7r12 7 nil do Tlt7T U 127r12 return T The subroutine GenericSearchAtG s is implemented as follows 0 The box B is a min heap with items keyed by their d Values 0 Start and Finish are no ops o Update12uB if wu12 lt d12 then 7r12lt7u d12lt7wu12 During the generic search phase a single tree is grown starting with the root 3 by repeatedly adding new vertices that are not already part of the tree as leaves The new leaf is chosen each time so as to add the lightest possible edge to the tree How can this algorithm be used to test whether G is connected Correctness Each algorithm is greedy in that the lightest edge satisfying some criterion is added to the tree in each step The correctness of both approaches will follow from Lemma 23 below which says that when building an MST by accumulating edges certain edges are safe to add De nition 21 Let G V E be an undirected graph A cut in G is a partition of V into two sets S and V 7 S Such a cut is denoted by S V 7 S De nition 22 Let S V7 S be a cut in C An edge u12 crosses the cut S V7 S if one of the endpoints u and 12 is in S and the other is in V 7 S IfA is a set of edges then we say that the cut respects A if no member ofA crosses the cut Lemma 23 Let G E be a connected undirected graph with edge weights w Suppose that A is a subset of some minimum spanning tree for G and let S V 7 S be any cut that respects A If u 12 is an edge crossing S V 7 S of minimal weight then A U u 12 is also a subset of some minimum spanning tree for G We say that u12 is a safe edge to add to A Proof Let T be some MST containing A If u 12 E T we are done so assume otherwise Adding u 12 to T yields a set U T U u 12 of V many edges which thus must have a cycle Further U must have a cycle 1 containing u12 since T itself is acyclic Since u12 crosses S V 7 S there must be some other edge on c besides u 12 say z y that also crosses S V 7 S Then z y E T and by the assumption that u 12 has minimum weight we have wm y 2 wu12 Now let T U 7 T had exactly V 7 1 edges and is connected any path in T that goes through z y can be rerouted through u 12 to be a path in T Thus T is a spanning tree and wT wT wu12 7 wxy wT Since T is an MST we must have wT wT and so also wu12 wmy and T is also an MST Further A U u 12 Q T and so A U u 12 is contained on some MST D 68 We now see how Lemma 23 implies the correctness of Kruskal s and Prim s algorithms In each case we only add safe edges ln Kruskal s algorithm we accumulate edges into T maintaining the invariant that T is always a subset of some MST We only need to show that when an edge uv is added to T there is some cut respecting T such that uv is a minimum weight light edge crossing the cut At any time in the algorithm and any vertex w we let Sw be the set in the disjoint set system that currently contains vertex w When edge u v is added to T Unionu v is called which joins the two previously disjoint sets Su and SH Consider the cut Su V 7 Su which clearly respects T before u v is added Any edge that crosses this cut has one vertex in Su and the other in some Sw 7 Su and so has not previously been added to T Since we take the edges in increasing order by weight it must be that u v is a minimum weight edge crossing the cut Thus it is safe to add to T and the loop invariant is maintained ln Prim s algorithm at any time during execution let T v 7rv l v is black and not the root T is initially empty and any edge u 7rv enters T when U is removed from B and turns black T is not actually maintained by the algorithm during the search but we could easily alter the search to maintain T Note that 7rw is always black from the time a vertex w is rst updated Immediately before 1 leaves T let S be the set vertices that are currently black and consider the cut S V 7 S which clearly respects T Since u is black and v is grey v 7rv crosses the cut S V 7 S Claim 24 U7rv is a minimum weight edge crossing the cut S V 7 S and is thus safe to add to T Proof Let x y be any edge crossing S V 7 S We show that wm y 2 wv7rv Immediately before u is removed from B one of the vertices z or y is black say m and the other say y is grey since it is adjacent to x but not black So y is in the box at this time We have dy wy wm y because the algorithm guarantees that dy is the minimum weight of any edge connecting a black node with y We also have dv wv 7rv But since u is about to be removed from B a min heap we must have dv dy which proves the claim Prim s algorithm is thus correct because only safe edges are added to T during the search phase Lecture 25 NPCompleteness This is the most important subject that most students don t learn well enough 0 Given a set of S integers is there a way to partition S into two subsets whose sums are equal 0 Given a graph G is there a path in G that goes though each vertex exactly once 0 Given a graph G and an integer K is there a set C of no more than K vertices such that every edge in G is incident to at least one vertex in C 0 Given a Boolean formula 4p is there a truth setting of the variables that makes 4p true 69 0 Given a graph G and an integer K does C have a complete subgraph of size at least K No algorithms are known for any of these problems that run in less than exponential time essentially by exhaustive search BUT a fast algorithm for any one of them will immediately give fast algorithms for the rest of them All these problems and many others are NP complete The theory of NP completeness is the best tool available to show that various interesting prob lems are most likely inherently di cult So far no one has been able to prove mathematically that NP complete problems cannot be solved by fast algorithms but this hypothesis is supported by a huge amount of empirical evidence namely the failure of anybody to nd a fast algorithm for any NP complete problem despite intense and prolonged effort So if your boss asks you to nd a fast algorithm for a problem and you cannot nd one you may be able to show your boss that the problem is NP complete and hence equivalent to the problems above which the smartest minds in the eld have failed to crack At least your boss would know that she won t do any better by ring you and hiring someone else Decision Problems We restrict our attention to decision ie yesno problems for convenience De nition 25 A decision problem is speci ed by two ingredients 1 a description of an instance of the problem always a nitely representable object and 2 a yes no question regarding the instance So a decision problem is a set of instances partitioned into yes and no instances All the questions above are decision problems When stating a decision problem we name it then explicitly give its two ingredients For example VERTEX COVER lnstance an undirected graph G and an integer K Question is there are set of vertices C of size at most K such that every edge in G is incident to a vertex in C All instances of a decision problem are either yes instances or no instances depending on the answer to the corresponding question We can apply these techniques to other kinds of problems eg search problems if we wanted Often a fast algorithm for a decision problem can be used to get a fast algorithm for a related search problem For example suppose we had an algorithm for VERTEX COVER above and we wanted an algorithm to nd a vertex cover of maximum size in a graph We can rst call VERTEX COVER repeatedly with different K values to determine rst the size of a maximum cover Then we can nd an actual cover of this size by repeatedly calling VERTEX COVER on graphs obtained by removing successive vertices from the original graph P and NP We say that an algorithm A solves a decision problem L if given any instance of L as input A outputs the correct answer to the corresponding question 70 De nition 26 We de ne P to be the class of all decision problems that are solvable in polynomial time That is P is the class of all decision problems H for which there exists a constant k and an algorithm that solves H and runs in time 0nk where n is the size in bits of the input Thus P is the class of all decision problems that are easily decidable77 easy77 polynomial time we don t need any ner granularity Without loss of generality we will assume that all algorithms must read their input sequentially as if from a le on disk say Likewise all outputs must be written sequentially eg to a disk le Thus reading input and writing output take time proportional to the size of each This will simplify much of the discussion below A decision problem is in the class NP if all its yes instances can be easily veri ed given the right extra information For example if a graph C does have a vertex cover C of size K this fact can be veri ed easily if the actual set C is presented as extra information we simply check that each edge in G is incident to a vertex in C Such extra information is called a proof or witness De nition 27 NP is the class of all decision problems H for which there exists an algorithm A that behaves as follows for all instances m of H o m is a yes instance ofH if and only if there is a y such that A outputs yes on input o A runs in time polynomial in the length of m Such a y when it exists is a witness and A is the algorithm that veri es using the witness that z is a yes instance of H In the case of VERTEX COVER z encodes a graph G and integer K and y if it exists would encode a vertex cover for G of size at most K Since A must stop within time 0nk for some constant h it can only read the rst 0nk bits of y where n is the length of m Thus we can limit the size of y to be polynomial in n All the problems listed above are in NP Also it is clear that P Q NP for a problem H E P a verifying algorithm could ignore any extra proof and just decides whether the input is a yes or no instance in polynomial time hence H E NP Reductions We want to compare decision problems by their dif culty De nition 28 Given two decision problems H1 and H2 we say that H1 polynomially reduces to H2 H1 17 H2 if there is a function f such that o f maps each instance of H1 to an instance of H2 0 f can be computed in polynomial time and o for each instance m of H1 m is a yes instance ofH1 is a yes instance of H2 and thus m is a no instance of H1 i is a no instance of H2 f is called a polynomial reduction from H1 to H2 71 This captures the notion that H1 is no harder than77 H2 or H2 is at least as hard as77 H1 The 17 relation is re exive and transitive The intuition that 17 at least partially orders problems by dif culty is supported by the following theorem Theorem 29 Pretty easy Suppose H1 17 H2 Then 0 ifll2 E P then H1 6 P and o if in e NP then n1 6 NP Proof Fix a polynomial reduction 1 from H1 to H2 running in time 0nk for some k First suppose H2 6 P decided by a deterministic decision algorithm A running in time 0nl for some 6 Consider the following decision algorithm B for H1 On input m an instance of H1 2H1 95 run A on input 2 and output the result Since 1 is a reduction 2 is an instance of Hg with the same answer as x in H1 so B correctly decides H1 Further B runs in time polynomial in n it rst computes z fz requiring time 0nk which can have length no more than in 0nk 1 does not have time to produce a bigger output the call to A thus takes time 0ml 0nkl 0nkl thus the total time for B is polynomial in n So B decides H1 in polynomial time and so H1 6 P Second suppose H2 6 NP with a yes instance veri er A running in time 0nl Consider the following algorithm B to verify yes instances of H1 On input z y where z is an instance of H1 we run A on input 2 y and output the result B runs in time polynomial in n for reasons similar to those above Note that we can assume that 0lzll 0nkl since A does not have enough time to read more than this For correctness we observe that z is a yes instance of H1 iff z is a yes instance of H2 iff there is a y such that A accepts 2 y iff there is a y such that B accepts z Thus H1 6 NP D De nition 30 Two decision problems H1 and H2 are polynomially equivalent H1 2 H2 if both H1 17 H2 and H2 17 H1 NP Hardness and NP Completeness De nition 31 A decision problemH is NP hard if for every problem H E NP we have TV 17 H Thus a problem is NP hard iff it is at least as hard as any problem in NP De nition 32 A decision problem is NP complete if it is in NP and it is NP hdrd Theorem 33 Easy Any two NP complete problems are polynomially equivalent 72 Proof If H1 and H2 are NP complete then in particular H1 6 NP and everything in NP reduces to H2 Thus H1 17 H2 Likewise H2 17 H1 D All the problems listed above are NP complete and hence polynomially equivalent Lecture 26 NPCompleteness Continued The Standard Technique The standard technique that we will use for showing that a problem H is NP complete takes two steps 1 Show that H E NP This is usually obvious 2 Find a polynomial reduction from H to H for some known NP complete problem H Since all NP problems are reducible to H and since the 17 relation is transitive it follows that all NP problems are reducible to H and thus H is NP complete Obviously the rst natural NP complete problem could not be proved NP complete using this method The rst such problem was SATlSFlABlLlTY SAT lnstance A Boolean formula 4p Question ls 4p satis able ie is there a setting truth assignment of the Boolean variables of 4p that makes 4p true SAT is clearly in NP Given a satis able formula 4p an easily veri able proof that 4p is satis able is a satisfying truth assignment of the variables Given such an assignment we simply compute the corresponding truth value of 4p in the standard bottom up way and check that 4p is indeed true under the assignment In the 1970s Steve Cook Waterloo Ontario Canada and Leonid Levin then in the USSR now at Boston U independently came up with an ingenious proof that SAT is NP hard They used the Turing machine model to describe algorithms 1 prove this theorem when I teach CSCE 551 Note Garey amp Johnson call this theorem Cook s Theorem Levin s work was unknown to them at the time Theorem 34 Cook Levin SAT is NP complete The Cook Levin Theorem provides the starting point we need to use our technique By now there are hundreds if not thousands of known NP complete problems to start from and there is much variety computer science operations research scheduling game playing etc Proving a problem to be NP complete adds to this list making it easier for further proofs etc CNF SAT Cook and Levin actually showed that the following restriction of SAT is NP complete CNFSAT lnstance A Boolean formula 4p in conjunctive normal form CNF Question ls 4p satis able A formula is in CNF if it is a conjunction 01 A A On of clauses Ci where a clause is de ned as a disjunction 61 v v am of literals 67 and where a literal is de ned as either a Boolean variable eg z or the negation of a Boolean variable eg x also written Note here that A means AND and V means OR Thus a truth assignment satis es a CNF formula if and only if it satis es every clause where a clause is satis ed if and only if at least one literal in the clause is true CNF SAT may appear easier than SAT at rst since we only need to worry about formulas in CNF instead of arbitrary formulas But CNF SAT is NP complete so it is polynomially equivalent to SAT We will take as given that CNF SAT is NP complete 3SAT We can restrict CNF SAT even further 3SAT lnstance A Boolean formula 4p in CNF where each clause in 4p has exactly three literals Question ls 4p satis able 3 SAT is NP complete and we can prove this using our standard technique by nding a poly nomial reduction from CNF SAT to 3 SAT Interesting fact If we restrict 4p to have at most two literals per clause the resulting problem 2 SAT can be solved in polynomial time Here is how the reduction will work Given an instance 4p 01 A A On of CNF SAT where the Ci are clauses we will replace each clause C 61 V V 6m of 4p with a conjunction of one or more 3 literal clauses depending on the value of m We take the conjunction of all the resulting clauses as our output formula Lp an instance of 3 SAT We must be sure that 4p is satis able if and only if Lp is satis able If m 3 then C already has three literals so we leave it alone If m 2 so C 61 V 62 then let y be a fresh variable fresh means that y does not occur anywhere else and replace C by the two clauses 1VZZVyA 1V 2vy Notice that any truth assignment that satis es C makes at least one of 1 and 2 true and so can be extended to a truth assignment by giving any truth value for y that satis es both replacement clauses above Conversely any truth assignment that satis es both clauses above must also satisfy C if the assignment did not satisfy C then 61 and 2 would both be false under the assignment so no matter how y was set one of the clause above must have been false If m 1 so C 61 let yl and yg be fresh variables Replace C by the four clauses 1VylVy2A 1VylVEA 1VmVy2A 1VEVE Again any truth assignment satisfying C makes 61 true and thus satis es all four replacement clauses Conversely any truth assignment that satis es all four clauses above must make 61 true and thus satisfy C If m gt 3 then using fresh variables yl ym3 we replace C with vbvw WEvawM AWiiZVZiVyii A A laM74 V m72 V ym73 A lami V grail V For example ll V V 65 is replaced with hvbvaW vhvaW thQ Suppose some truth assignment satis es C Then it makes some literal l of C true We can extend this assignment to satisfy all the replacement clauses simultaneously by making all the y s to the left of 6 true and all the y s to the right of 6 false That is we set yj to true for all j g l7 2 and we make yj false for all j 2 if 1 The true y s satisfy all clauses to the left of the one containing 1 and the false y s satisfy all clauses to the right 6 alone satis es the clause containing it Conversely it is not too hard to see that the only way a truth assignment can satisfy all the replacement clauses simultaneously is by making at least one of the 6 true Consider three exhaustive cases yl is false ym3 is true y is true and 344 is false for some 3 g l g m 7 2 Thus this assignment also satis es C Now let Lp be the conjunction of all the replacement clauses described above for all the clauses of 4p Constructing Lp can clearly be done in polynomial time in the length of 4p By the accom panying arguments we see that 4p is satis able iff Lp is satis able Thus we have CNF SAT 17 3 SAT and so since 3 SAT is clearly in NP 3 SAT is NP complete 3SAT 17 VERTEX COVER The reduction from CNF SAT to 3 SAT uses a technique called local replacement where we take each piece of the input instance and replace it with some object constructed from the piece In the reduction above each piece was a clause and we replaced it with one or more conjoined clauses To polynomially reduce 3 SAT to VERTEX COVER we must show how given an arbitrary instance 4p of 3 SAT to construct in polynomial time a graph G and integer K depending on 4p such that 4p is satis able if and only if G has a vertex cover of size at most K We must construct G and K without knowing whether or not 4p is satis able We use a different technique here called component design Given an instance 4p of 3 SAT we construct C out of two types of components truth setting components which encode possible truth assignments of the variables of 4p and satisfaction testing componentsione for each clauseiwhich check whether a clause is satis ed by a truth assignment Truth Setting Components Let u1 un be the variables of 4p G will have n truth setting componentsione for each variable The component for M is a pair of vertices joined by an edge We label one vertex M and the other 77 The n truth setting components are pairwise disjoint and there are no other edges between them U1 U1 U2 U2 um um Observe that any vertex cover of G must include at least one vertex in each component to cover its edge If only n component vertices are in the cover then each component has exactly one of 75 its two vertices in the cover Such a minimum cover then corresponds to a truth assignment of the variables namely the one that makes each literal true iff it labels a vertex in the cover Clause Satisfaction Testing Components Let 01 Cm be the clauses of 4p For each clause C 61 V 2 V 63 of 4p the graph G will have a satisfaction testing component consisting of three vertices joined by edges in a triangle The vertices of the component are labeled by the literals 1 2 and 63 respectively 52 1 3 Observe that any vertex cover of G must include at least two vertices of each satisfaction testing component These components are pairwise disjoint and there are no other edges between them Finally we include an edge connecting each vertex in each satisfaction testing component to the vertex in the truth setting components with the same label For example for the claus 741 VzTZVun we have U1 U1 U2 U2 um um ul un This concludes the construction of G Setting K n 2m completes the description of the output instance of VERTEX COVER constructed from 4p This construction is clearly doable in polynomial time Correctness We need to show that 4p is satis able if and only if the corresponding graph G has a vertex cover of size at most 71 2m By the observations above any vertex cover of G must have size at least 71 2m First suppose 4p is satis able Let t be a truth assignment of the variables 741 un that satis es 4p Then there is a vertex cover A of G A consists of exactly one vertex from each truth setting componentithe one labeled by the literal made true by titogether with exactly two vertices of each satisfaction testing component making 71 2m vertices in all The two vertices in 76 each satisfaction testing component are chosen as follows in the corresponding clause 0 choose the leftmost literal made true by t such a literal exists for each clause because t satis es 4p and include in A the two vertices labeled by the other two literals in Ci A has the right size ls it a vertex cover for G Each component s internal edges are covered by A so we need only check that each edge connecting a truth setting component to a satisfaction testing component is covered Each such edge e has endpoints labeled by the same literal Z If t is made true by t then the endpoint of e in the truth setting component is in A If t is made false by t then the endpoint of e in the satisfaction testing component must be in A since the only literal of that component left out of A is made true by t In either case e is covered by A Thus A is a vertex cover Now we must argue the converse if G has a vertex cover of size n 2m then 4p is satis able Occasionally not in this case it is more convenient to argue the contrapositive namely if 4p is not satis able then no vertex cover of size n 2m exists in G A conditional statemen if P then Q is always logically equivalent to its contrapositive if not Q then not P Suppose G has a vertex cover A of size n 2m Then by the observations above A must contain exactly one vertex of each truth setting component and exactly two vertices of each satisfaction testing component Let t be the truth assignment of 741 un that makes each literal true iff that literal labels a truth setting vertex in A The claim is that t satis es 4p Let C be any clause of 4p and let 3 be the satisfaction testing component for Ci One vertex u in 31 labeled with some literal t is not in A But the edge connecting it with the vertex 1 labeled 6 in the truth setting components must be covered by A and so u E A and so by the de nition of the truth assignment t t is made true by t and thus Ci is satis ed This is true for each clause so t indeed satis es 4p This concludes the proof that 3 SAT 17 VERTEX COVER and hence VERTEX COVER is NP complete INDEPENDENT SET and CLIQUE Let G V E be an undirected graph A clique in G is a subset C Q V such that every two vertices in C are adjacent ie C is a complete subgraph of G An independent set in G is the opposite a subset I Q V such that no two vertices in I are adjacent We can form decision problems based on the existence of cliques and independent sets CLIQUE Instance an undirected graph G and an integer K gt 0 Question does C have a clique of size at least K INDEPENDENT SET Instance an undirected graph G and an integer K gt 0 Question does C have an independent set of size at least K Both these problems are clearly in NP and we ll show that both are NP complete by polynomi ally reducing VERTEX COVER to INDEPENDENT SET and INDEPENDENT SET to CLIQUE These problems are often useful for showing other problems to be NP complete If G V E is an undirected graph we de ne G0 the complement of G to be V E where E uv l uv E V n 7 U and uv Note the following two easy facts 1 A is a vertex cover in G iff V 7 A is an independent set in G 2 C is an independent set in G iff C is a clique in G0 Fact 1 implies that VERTEX COVER 17 INDEPENDENT SET Via the polynomial reduction that maps an instance G K of VERTEX COVER to the instance G K of INDEPENDENT SET where K lVl 7K Fact 2 implies that INDEPENDENT SET 17 CLIQUE Via the polynomial reduction that maps an instance G K of INDEPENDENT SET to the instance G0 K of CLIQUE Restriction The simplest technique for showing a decision problem H NP completeione that works in many casesiis to show that there is a restriction of H that is already known to be NP complete One must of course also show that H E NP De nition 35 A decision problem H1 is a restriction ofa decision problem H2 if every yes instance of H1 is a yes instance of H2 and every no z39nstance of H1 is a no z39nstance of H2 For example 3 SAT is a restriction of CNF SAT which is itself a restriction of SAT Fact 36 If H1 is a restriction of H2 H1 is NP complete and H2 6 NF then H2 is NP complete Proof H1 polynomially reduces to H2 just by mapping each instance of H1 to itself D We can loosen the de nition of restriction somewhat by allowing H1 to embed into H2 Via some triVial transformation Then Fact 36 still holds for this looser de nition the polynomial reduction performs this triVial transformation For example the problem HAMILTONIAN PATH Instance an undirected graph G Question is there a Hamiltonian path in G ie a simple path that includes each vertex of G exactly once embeds triVially into the problem LONG PATH Instance an undirected graph G and an integer L gt 0 Question does C have a simple path of length at least L by taking an instance G V E of HAMILTONIAN PATH and mapping it to the instance G 7 1 of LONG PATH Recall that we de ne the length of a path to be the number of edges in the path which is one less than the number of vertices A path is simple if no vertex appears more than once in the path Supplemental Lecture Faster Scalar and Matrix Multiplication Integer Addition and Multiplication We represent natural numbers in binary as usual The size of a number n is the number of binary digits needed to represent 71 namely lgn 1 lgn 1 01 Adding two k bit natural numbers takes time k and the usual add and carry method that we all know from grade school except that it is base 2 is aymptotically optimal Adda b n an 710 and bn 710 are two bit arrays of length n Returns a bit array sn O of size n 1 070 for 2 70 to n 7 1 do silt7ai eabm 690 singlebit xor clt7 Majorityai Mi 0 snlt7c return 3 Subtraction is also clearly linear time using the subtract and borrow method from grade school Now consider multiplication The grade school approach adapted to base 2 is to repreatedly multiply the rst number by each bit of the second then add up all the results suitably shifted Multiplya b n an 710 and bn 710 are two bit arrays of length n s is a bit array of size 271 pad a and b with leading Us to length 271 7 1 ll s with all US for 2 70 to n 7 1 do if 1 then 37 AddsA 21271 7 1 using arithmetic shift return S Clearly this algorithm takes time nz Can we do better A Divideand Conquer Approach to Multiplication Assume that n is a power of 2 Otherwise pad input numbers with leading zeros out to the next higher power of 2 We are given two 71 bit natural numbers a and b to multiply Base case n 1 This is trivial Recursive case n 2m where m gt 0 is an integer the next lower power of 2 1 Write a ah2m a1 and b bh2m bl where ah and al are unique integers in the range 0 2m71 Similarly for b and bl These are the high and low halves of a and b respectively Clearly ab ahbh2 ath agbh2m agbl 2 Recursively compute the four subproducts ahbh ahbg albh agbg 3 Add up the four subproducts suitably shifted The time Tn ofthis algorithm satis es Tn 4Tn2 n and so by the Master Theorem Tn n27no better than the grade school approach We can use a trick however to reduce the number of recursive multiplications from four to three We recursively compute ahbh and 0151 as before but then we recursively compute p ah 1 0101 1 b5 This is enough because we have ab ahthn p 7 ahbh 7 015027 agbl Which requires a constant number of shifts additions and subtractions There s a technical glitch here The number of bits in ah a1 and b bl may be m 1 instead of m so in multiplying these directly we lose our assumption that m is a power of two There s no problem with adapting the algorithm for any 71 just split each number into two numbers of and bits respectively This works best in practice and it does not change the asympototic run time Alternatively we can keep the size of the recursive multiply to m bit numbers as follows to multiply two numbers m y of m 1 bits each express m bz2mCm7 y by2m l 0y7 where bhby 6 01 and cm and q are expressible with m bits each ie 0 obey lt 2 then notice that my bmby22m bmcy bycm m l cmcy Only one product on the right hand side is nontrivial away which is a product of two m bit integers The running time Tn of the algorithm above now satis es Tn 3Tn2 n and so Tn nlgs 901158quot which is a signi cant speed up over the naive quadratic time algorithm Matrix Multiplication We can use a similar idea to multiply two nxn matrices faster than the obvious ng algorithm This faster algorithm is due to Volker Strassen Although the idea is similar the actual algorithm is much more complicated in the case of matrices We use the divideand conquer approach again assuming that n is a power of two We count scalar multiplications which we regard as primitive and which dominate all the other operations including addition If n 1 then there is only one scalar multiplication Assume that n gt 1 and let m 712 Suppose A and B are the two 71 x n matrices to be multiplied together to get an n x 71 matrix C AB We can chop each of A B and C into four m x m submatrices blocks as 1 we 1 i The m x m submatrices are a b c d e f g h r s tu A nice property of matrix multiplication is that we can just multiply the submatrices as if they were scalars r 15 by s afbh t cedh u cfdh 80 The only caveat is that matrix multiplication is not commutative so the order of the factors matters We can naively just compute each of the eight products on the right hand sides recursively then add up the results This gives a running time Tn satisfying Tn 8Tn2 nz that is Tn ng by the Master Theorem This is asymptotically no better than our original approach By multiplying certain sums and differences of submatrices Strassen found a way to reduce the number of recursive matrix multiplications from eight to seven The run time of his method thus satis es Tn 7Tn2 nz that is Tn nlg7 I ll give his algorithm here so that you can check that it is correct and implement it if need be but the presentation won t give much insight into how he came up with it Letting A B C andn 2m as above we de ne in x m matrices A and B and P AiBi for 1 lt i lt 7 1 LetA1aandB1fihandsoP1afiah 2 Let A2 a b and B2 h and so P2 ah bh whence s P1 1 P2 3 LetA3cdandB3eandsoP3cede 4 Let A4 d and B4 gie and so P4 dgide whence t P3 P4 5 LetA5adandB5eiandsoP5aeahdedh 6 Let A6b7dand B6gh and soP6bgbh7dgidi whencerP5P47P2P6 7 Let A7aicand B7ef and soP7aeaficeicf whenceuP5P17P37P7 Exercise verify that all the conclusions are correct Faster Algorithms n bit integer multiplication can actually be done in time On lg it using a fast implementation of the Discrete Fourier Transform DFT known as the Fast Fourier Transform The technique also works for multiplying two polynomials of degree n in time Onlg DFT over Zn Fix an integer n 2 1 Let 4 eZMn we call 4 the primitive nth root of unity because it is the least positive integer such that w 1 The Discrete Fourier Transform on Zn denoted DFT is the linear map from C to C de ned by the n x n matrix whose i jth entry is wig for all 0 ij lt ii That is 1 1 1 1 1 1 run of w wgil 1 1 of w of w 2 DFTn W 1 mg w w wgnis 11 w were WM It is easily checked that the inverse transformation DFTgl is given by the matrix with ijth entry equal to my The Fourier Transform is useful for a variety of purposes including signal and image processing because it decomposes a signal into its component pure frequencies The digital signal read off of 81 an audio CD is in the frequency domain A CD player applies an inverse Fourier Transform to produce an analog signal Your ear is a natural Fourier transformer allowing you to recognize the various pitches in music Applying DFTn to a vector of n complex numbers naively takes 712 complex scalar multiplica tions However due to the extreme regularity of the DFTn matrix the time to apply both DFTn and DFT1 can be reduced to On lg n in the case where n is a power of two counting operations on complex scalars as primitive which is reasonable for our purposes since the we only need Olg 71 bits of precision This is the Fast Fourier Transform FFT which we won t go into here To multiply two 71 bit numbers a and b where n is a power of 2 we rst pad a and b with leading zeros out to 271 bits Next we apply DFTgn separately to both a and b as vectors of 271 values in 0 1 obtaining two vectors 6 and 3 of 271 complex numbers respectively Maintaining lgn bits of precision compute a vector E of size 271 whose ith entry is the product of the ith entries of E1 and of Now apply DFTg 1 to Eto obtain a vector 0 of 271 complex numbers If we did this with in nite precision the entries of 0 would be all integers With our level of precision they are all close to integers Let co 1 02n1 be the vector such that c is the integer closest to the ith component of 0 Then 2n71 ab Z c i i0 This last sum can be computed in time On using a method called Horner s Rule The entire time taken to multiply a by b is thus Onlg 71 when we use the FFT to implement DFT FFT can be efficiently parallelized it can be computed by a circuit known as a butter y network of depth lgn with a linear number of gates Fast Matrix Multiplication The fastest known way to multiply two 71 x n matrices is due to Coppersmith and Winograd and takes time 0n23937639quot Although this is the best known to date the possibility of a faster algorithm has not been ruled out mathematically For all we know a linear time algorithm ie one that runs in time nZ because the inputs and outputs are both of size 9012 may exist

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.