### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Analysis of Algorithms CS 483

Mason

GPA 3.66

### View Full Document

## 71

## 0

## Popular in Course

## Popular in ComputerScienence

This 230 page Class Notes was uploaded by Leland Swift on Monday September 28, 2015. The Class Notes belongs to CS 483 at George Mason University taught by Staff in Fall. Since its upload, it has received 71 views. For similar materials see /class/215131/cs-483-george-mason-university in ComputerScienence at George Mason University.

## Popular in ComputerScienence

## Reviews for Analysis of 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: 09/28/15

C HMme CS a t W Wz m f R Paul Wiegand George Mason University Department of Computer Science March 29 2006 C iniine iHH CH iHCHCiH Introduction Space vs Time Tradeoff E Sorting by Counting String Matching Hashing B Trees Homework HlllHe input enhancement Preprocess the problem39s input and store additional information to accelerate problem solving a Counting methods for sorting n Improvements to string matching algorithm prestructuring Use extra space to facilitate faster andor flexible access to data a Hashing u lndexing with Btrees 1 Sometimes we gain time efficiency at the expense of space or viceversa 1 Sometimes we gain time efficiency while gaining space efficiency eg adjacency list representation 84 graph traversal algorithms C HMme A mm for ilt 0 to n 7 1 for ilt 0 to n 7 2 forjei1 to n71 do if Ai lt AU then CountU lt CountU 1 else CountU lt Count 39 1 for ilt 0 to n7 1 do SCounti lt Ai return 5 do Counti H 0 do 72 71 quotnin For each element to be sorted count Cn 20 2i11 T E 6n2 thetotal number ofelements smaller than this element Co COMPABISONCQUNTINGSORTAO i i i n 7 1 3 Somet39mes the 39npUt 395 77quot7 constrained in Fixed array of forjlt0 to uil do DDlt for iHo to n71 do DAi7lltDAi7l1 D39 values I for J41 to uil do 0mg Du71 for ilt n71 downto 0 do 1 H Ali l sD39 7 1 AU 1 Sometimes we want DU F DU 1 additional information information 1 Each in 7 u eparnnen C iHiine mm m We have a pattern string and a text string a We want to find the position of the first occurrence of the pattern in the text Example 1 Recall brute force text FOUR SCORE u Align the pattern at the start of the text pattern FATHER Compare each character of the pattern U 2 Each39of the text h hf h F U R S C u t ere s a nwismatc s it t e pattern F A T H R one to the right and repeat A T H E R F A H E If the pattern matches you are done If the end of the pattern is reached shift the pattern one to the right and repeat in nm in the worst case 1 But why shift only one each time DI Ho r I xi Wm Idea When we shift make as large a shift as possible I Match pattern from right to left El Consider character c of the text that was aligned against the last character of the pattern D dc 7 mif c is not in the first In 71 characters 7 dist from rightmost c in first In 7 1 characters7 otherwise I Still n in Avg case nm in worst case 1 But on average must faster than brute force for jeO to m72 do TPjem717j return T g glam D U D n D Idea When we shift make as large a shift as possible Match pattern from right to left Consider character c of the text that was aligned against the last character of the pattern tc Still n in Avg case nm in worst case mif c is not in the first In 71 characters dist from rightmost c in first In 7 1 characters7 otherwise May repeatedly over write shift value for a given character But on average must faster than brute force for jeO to m72 do TPjem717j return T Ho r o39l Q 151 1 No c in the pattern shift entire pattern length 2 c is in pattern but this is not the last one shift to align right most c in pattern 3 c is last character in pattern 84 no others in remaining m7 1 shift entire pattern length 4 c is last character in pattern 84 3 others in remaining m 71 shift to align rightmost c in pattern EDIT EEIIT SEVEN GIVE GI Theo u Hashes are often useful for implementing dictionaries basic operations INSERT SEARCH amp DELETE D Construct a data type to store records by key value Hash Tabe generally an array HOi i i m 71 1 Use the key to access the table by computing its address with a predefined Hash Function hk u If keys are nonnegative integers a simple hash function is hk k mod m n For strings of a fixed length we might use hk 25 ordcgt mod m in Or where C is a larger constant than any ordc I790 for ilt70 to 71 do hlt7h Cordci C inline Call in Hash functions should try to Distribute keys in the table as evenly as possible Be easy to compute a When the hash functions computes the same value for different keys a collision occurs a When m lt n n is the number of keys inserted into the table this Will occur 1 Even when m 2 n it is still possible depending on the data and the hash function u Hash implementations need to have a collision resolution method such as In Open hashing separate chaining u Closed hashing open addressing hi E D 391 E J El Each cell in the hash table is a linked list Values are stored in list collisions are handled by chaining values If n keys are distributed evenly each list is about the same size ai load factor 04 Average number of nodes visited during a successful search 5 z 1 l Average number of nodes visited during an unsuccessful search U z a Example rn 5 hk suitvalue cardvalue mod rn O Q 4 42 28 14 0 KQJA 1312111 in D Each cell in the hash table is a Exag Ple m llnked llSt hk suitvalue cardvalue mod m a Values are stored in list collisions Nomi 42gt28gt14gt0l KQJA 1312111 are handled by chaining values D If n keys are distributed evenly each list is about the same size ai 1 load factor 04 1 Average number of nodes visited during a successful search 5 z 1 l u Average number of nodes visited When l ad fad i5 quot5339 during an unsuccessful search U z a 84 keys are well distributed access is 91 on average El D D I All keys are stored in table On collisions we shift right until we find an open position At the end we wrap back to the start DELETE is problematic mark 84 skip Avg 7 comparisons when successful 5 m 17 Avg 7 comparisons when N1 7 1 unsuccessful 2 1 W C HMme Nmiwmcm 150 200 comparisons 100 sein comparisons 150 200 100 I The main problem is clustering u A cluster is a sequence of consecutive filled positions in the table a One possible solution double hash El Use a second hash function to compute the probe interval In h2k m72ik mod m72 We need h2k and m to be relatively prime only common divisor is 1 a Choosing a prime m ensures this D swem Mash u The main problem is clustering in A cluster is a sequence of consecutive filled positions in the table 150 200 a One possible solution double hash 100 I Use a second hash function to compute the probe interval h2k m727 k mod m72 We need h2k and m to be relatively prime only common 02 04 06 08 divisor i5 1 1 Choosing a prime m ensures this comparisons DU a We can still have problems as a approaches 1 a Only solution rehash scan table 84 relocate into a bigger table HlllHe lllll CH l anon El Cl U Often we need access to data stored on disk There can be a large number of data records And the records are typically indexed indexes provide key values and information about the record39s location In such cases we typically are less interested in counting key comparisons and more interested in counting disk accesses BTrees extend the idea of 23 Trees to make such considerations easier llK ll llK39ll ll39Wll I Data records stored in leaves in increasing order of the keys El Each parental node contains m 7 1 distinct ordered keys a All keys in T0 are smaller than K1 all keys in T1 are in K1K2 etc 1 Every BTree of order m gt 2 must satisfy 1 Root is leaf or has between 2 and In children 1 Internal nodes N root V leaf have bw lm2l and In children n The tree is perfectly balanced all leaves at same level C iniine inircuiuciicm H iii 5i H HESiWlii oii iii5 H H H 40 43 46 I Keys are ordered in the node so we can use binary search to find the pointer to follow D But we don39t care about key comparisons we care about disk access a We usually choose the order of a BTree 51 the node size corresponds with disk pages 1 How many nodes do we have to consider Height plus 1 m 1 What is the height of a BTree I Find smallest 7 of keys a BTree of order m and height h can ave 1 Root has at least one key a Level 1 has at least two nodes with at least lm2l 7 1 keys in Level 2 has at least 2 lm2l nodes with at least lm2l 71 keys I For a BTree of order m with n nodes and height h n 2 1 2 2 lmZl 1 Urn2i 7 1 2 lmle l 1 Which reduces to lt 4lm2lh71 1 n1 in So height is h S lgglmQ39lTl 1 seam a What is the height of a BTree 1 Find ave 1 El El III I smallest 7 of keys a BTree of order m and height h can Root has at least one key Level 1 has at least two nodes with at least lm2l 7 1 keys Level 2 has at least 2 lm2l nodes with at least lm2l 71 keys For a BTree of order m with n nodes and height h n 2 1 ZlQIZlW2l 1lm2l 1 2 lmZlH Which reduces to 7 So height is h g Ugh21 Since m is a constant even if very large this is Olog n lt 4 rmzw 171 HI HlllHe lnlrculw icm I There are a variety of INSERT functions for BTrees 3 Here39s a simple one 1 Find the appropriate leaf 84 insert key u If there are too many keys u Split node in half m Promote smallest key of new node to parent in This may percolate up the tree 3 Analysis is difficult but this is also Olog n V C HMme Nmiwmcm T Silp m emwm g I In section 72 a Boyer Moore Algorithm pp 255 259 3 1 M R Paul Wiegand George Mason University Department of Computer Science February 22 2006 Introduction to Recurrences 2 Solving Recurrences E3 Induction W B3 31 Rurr n e RI atiie 7 Definition Coren et al 2001 A recurrence relation is an equation or inequality that describes a function in terms of its values on smaller inputs Examples n Xnx 5forngt0x10 u Tn n Etc 9 ifn1 2Tn722n ifngt1 And Jetm It is also useful to think in terms of sequences El E El U D I D A sequence is an ordered list of numbers Eg 24681O12Hi positive even numbers We often refer to a sequence using a variable say X and we often indicate an element of the sequence with an index X We might also use something called the generic term Xn where Xn represents the nth number in the X sequence We can then use the generic term as a function to help define the sequence Xn 2n for n 2 Alternatively we could define the sequence by showing how to step from one element to another Xn Xn 71 n for n gt 07 XO 0 It is clear now why an initial condition is needed there can be many sequences defined by a recurrence the initial condition tells you which one by specifying the starting position of the sequence Wig am What This is complicated Why would I express a sequence or a function in this way What do I do with it now Sometimes it is the most natural way to so For example When analyzing recursive functions it is typically very natural to express the running time as a recurrence On the other hand it is a lot easier to deal with the closed form an algebraic form where the function appears only on the lefthandside of the inequaity and where more complicated notational elements such as summations are resolved Moreover we need the closed form to express the order ofgrowth of an algorithm39s efficiency properly El E1 1 Simply solving a recurrence is to find the closed form of the relation in An exact solution will be the fully specified algebraic closed form of the recurrence I For example Find the exact solution of Xn Xn 7 1 n for n gt 0 subject to initial condition X0 0 D Answer Xn ll for n 2 0 1 But typically we are interested in asymptotic bounds on the solution El For example Find the asymptotic solution of 39 i 1 Tn 2Tn2 Gn if 2 1 u Answer 9nlgn a We start with initial terms ofa sequence given by initial conditions i We use the recurrence equation itself to generate several terms a We look for a pattern that can be expressed in closed form Example Xn 2Xn 711 for n gt1 X1 1 X1 1 x2 2x112113 x3 2x212317 x4 2x3127115 Each number is one less than consecutive powers of two 2 4 8 16 so the solution is probably something like Xn 2 71 S S iIn X07 a We start at the penultimate step of the sequence eg Xn 71 n We express the final step in terms of the recurrence relation D We repeat this process for the antepenultimate step etc Example Xn Xn 71 n for n gt1 X1 1 Xn71n Xn72n71nxn72n71n Xn73n72n71nxn73n72n71n afterisubstitutions Xn7in7i1n7i2n to the initial condition x012nnn12 mama U U E Technically to solve a recurrence is just to elicit its closed form solution When someone else looks at your solution or you 15 minutes later you39d like to have a way to convince him or her that it is correct To do that you must prove it is true Substitution and recurrence trees are not proofs they merely help with intuition they help you guess the solution Typically we prove that a closed form solution is asymptotically correct by induction To obtain closed form asymptotic bounds on a recurrence we use induction and the definitions for BigO and BigQ Definition MathWorld The truth of an infinite sequence of propositions P for i 1Hi700 is established if 1 P1 is true and 2 Pk PM for all k This principle is sometimes also known as the method of induction Ogn tn 3c no gt 0 such that 0 g tn g c gn Vn 2 no Qgn tn 3c no gt 0 such that 0 g c gn g tn Vn 2 no uuu Hm 1 Consider the recurrence relation 1 Posit a guess for the asymptotic closed form solution 1 Write down the inequality from the Big OQ definitions El Use the definition and substitution to show that the definition holds after a step of the recurrence 1 Indicate the constant values for which the definition holds uuu Dom Consider the recurrence relation Posit a guess for the asymptotic closed form solution Write down the inequality from the Big OQ definitions Use the definition and substitution to show that the definition holds after a step of the recurrence 1 Indicate the constant values for which the definition holds Example 1 Recurrence Tn 2Tln2l n n Asymptotic solution Tn 6 Onlg n n BigeO Definition Tn S cnlgn u Given it holds for n assume it holds for WM Tln2l S 6 WM lainEl lls R Paul Wiegand George Mason University Department of Computer Science February 1 2006 Analysis Framework E Asymptotic Notation Nonrecursive Algorithms Recursive Algorithms amp Recurrence Relations Empirical Analysis Homework 1 Though there are other factors we concentrate our analysis on efficiency in Time efficiency how fast an algorithm runs a Space efficiency how much memory an algorithm El lnput size n Wallclock time depends on the machine but algorithms are machine independent 1 Typically algorithms run longer as the size of its input increases a We are interested in how efficiency scales wrt input size C mhrw What do we measure to judge the size of the problem C mhrw What do we measure to judge the size of the problem SORT21 22 2 211 quot39 2m b11 quot39 bml 21m 2mm bu bmk pX2nX 21X20 C mhrw M aSu ri What do we measure to judge the size of the problem SORT21 22 2n Number of list elements 211 quot39 2m b11 quot39 bml 21m 2mm by bmk pX2nX 21X20 What do we measure to judge the size of the problem SORT21 22 2n Number of list elements 311 quot39 3m bll b 1 I Order of matrices a Total number of elements 21m am by bmk pX2nX 21X20 What do we measure to judge the size of the problem SORT21 22 2n Number of list elements 311 quot39 a b quot39 b in Order of matrices a Total number of elements 21m am by bmk 39 7 pX anX 31X 30 a Degree of polynomial a Total number of coefficients C mhrw What do we measure to judge the running time on an algorithm an Measu rIn u What do we measure to judge the running time on an algorithm a Could count all operations executed I But we typically concern ourselves with the basic operation the one contributing the most to the total running time SORT2122 an Mesu r u What do we measure to judge the running time on an algorithm a Could count all operations executed I But we typically concern ourselves with the basic operation the one contributing the most to the total running time Key comparisons SORT21 22 an 211 2m b11 bml 21 3mm by bmk Mesu r What do we measure to judge the running time on an algorithm a Could count all operations executed I But we typically concern ourselves with the basic operation the one contributing the most to the total running time SORT21 22 an Key comparisons 311 2m bu bml mAdditions u Multiplications What do we measure to judge the running time on an algorithm Cl Could count all operations executed I But we typically concern ourselves with the basic operation the one contributing the most to the total running time SORT21 22 an a Key comparisons 311 2m bu bml mAdditions u Multiplications a In general we can approximate running time as Tn m cOpCn 1 Example Given Cn nn 71 what is the runtime effect of doubling the input size C HMme u IbeythenogbyX Iogb x n We can change bases logax logba 3 1 IbeythenogbyX n We can change bases logax si 39 Iogb x logba a v u92x u logbxy ylogbx n ogxyogxogy u Iog ogxilogy alogbx Xlogba firm F mm gym mag 4904 2w I We aren39t so interested in running times on small inputs but in how running time scales on very large inputs 1 We are interested in an algorithm39s order ofgrowth ignoring constant factors C mime m i W G y2x n We aren39t so interested in running times V V X V g on small inputs but in how running time g7 scales on very large inputs 1 We are interested in an algorithm39s order ofgrowth ignoring constant factors gt g 1 Constant 5 7 log n Logarithmic sublinear n Linear ii nlg n nlog n V j nquot for some constant k Polynomial a X k for some constant k Exponential a D Z D 41 E D E D gm n Factorial quotExponentialquot C mime ew Wit Emmi Time G y2x n We aren39t so interested in running times V V X V g on small inputs but in how running time g7 scales on very large inputs 1 We are interested in an algorithm39s order ofgrowth ignoring constant factors gt g 1 Constant 5 7 log n Logarithmic sublinear n Linear ii nlg n nlog n V j nquot for some constant k Polynomial a X k for some constant k Exponential a D Z D 41 E D E D gm n actorial quotExponentialquot x NOTE Given a nor negative integer d we can write a poiynomiai m the form 0 amquot where a are constants We caii d the degree of P we 2 the poiynomiai lt7 0 while ilt n and AU K do lt7 1 if ilt n return i else return 71 while ilt n and AU K do lt7 1 if ilt n return i else return 71 El Worst case is when K is not in A a Search every element requiring CW n n comparisons 1 Worst case analysis provides an upper bound lt70 while ilt n and AU y K do HI1 if ilt n return i else return 71 lt70 while ilt n and AH y K do lt7 1 if ilt n return i else return 71 CI Best case is when K is in AO a Search first element requiring Chest n 1 comparisons in Best case analysis provides a lower bound 1 Generally bestcase efficiency is not as useful 0 while ilt n and AU K do lt7 i if ilt n return i else return 71 l I E D D C D SEQUENTIALSEARCHAO i i i n 7 1 K lt7 0 while ilt n and AU K do lt7 i if ilt n return i else return 71 Average case asks a useful question What kind of running time to we expect to get when we don39t know the data Let p 6 01 be probability that K E A If successful let the PrK A1 PrK Ai Vi E 07 n 71 So the PrK Ai 5 Cam 152 wan17PM P391P39quot If p 1 ie K E running time is linear g39Qg if uroti lnformally we can think of 07 Q G as sets of functions a O gn set of all functions with the same or smaller order of growth as gn I 2n275n17 Oltn2 a 2nn100 72 onI I 2n6 Ologn i Q gn set of all functions with the same or larger order of growth as gn I 2n275n17 2n2 D 2nn100 7270nl D 2n6 llogn u G gn set of all func with the same order of growth as gn El 2n275n179n2 2nn100729nl I 2n6 logn g39Qg if uroti lnformally we can think of 07 Q G as sets of functions a O gn set of all functions with the same or smaller order of growth as gn I 2n275n1 6 Oltn2 u 2nn100 72 e onI I 2n6 Ologn i Q gn set of all functions with the same or larger order of growth as gn I 2n275n17 2n2 D 2nn100 7270nl D 2n6 llogn u G gn set of all func with the same order of growth as gn El 2n275n179n2 2nn100729nl I 2n6 logn 339ng 2 of wot lnformally we can think of 07 Q G as sets of functions a O gn set of all functions with the same or smaller order of growth as gn I 2n275n1 6 Oltn2 El 2nn100 72 6 Onl I 2n6 Ologn i Q gn set of all functions with the same or larger order of growth as gn I 2n275n1 60n2 D 2nn100 72 Qnl D 2n66 2logn u G gn set of all func with the same order of growth as gn El 2n275n179n2 2nn100729nl I 2n6 logn 339ng 2 of wot lnformally we can think of 07 Q G as sets of functions a O gn set of all functions with the same or smaller order of growth as gn I 2n275n1 6 Oltn2 El 2nn100 72 6 Onl I 2n6 Ologn i Q gn set of all functions with the same or larger order of growth as gn I 2n275n1 60n2 D 2nn100 72 Qnl D 2n66 2logn u G gn set of all func with the same order of growth as gn El 2n275n1 69n2 2nn10072 enl I 2n6 logn txin Definition Ogn tn 3c no gt 0 such that 0 g tn g c gn Vn 2 no ojrmza lil n le tn is in Ogn if tn is bounded above by some constant multiple of gn for all large n B We call 0 an asymptotic upper boun Nati n F 39 V Definition Qgn tn 3c no gt 0 such that 0 g c gn g tn Vn 2 no n le tn is in Ogn if tn is bounded below by some constant multiple of gn for all large n B We call 0 an asymptotic lower boun a f fir aliky For any two functions tn and gn we have tn E gn ifand only if tn E Ogn and tn E Q 2 8039 m 8039 u le tn is in Ogn if tn is bounded below by some constant multiple of gn c1 and bounded above by some constant multiple of gn C2 for all large n m We sometimes call such a bound tight Ift1n E 0g1n and t2n E 0g2n then f1quot Mquot E 0 maxg1quot7g2quot a Review the proof in the book p 56 u Advantage We can restrict our analysis to one part of an algorithm if we know the others to have a lower order of growth eg COUNTINGSORT p 24 n Advantage We can frontload an algorithm without increasing the time complexity as long as the preparation step has no greater an order of growth than main part eg shuffling data before QUICKSORT One common way to compare two algorithms is by taking the limit of the ratios of their running times Cg p rlngEWJEUQ 07 0 if tn is of smaller order than fn imH00 H7 c if tn is of the same order as fn 00 if tn is of greater order than fn Example Compare the orders of growth of lg n and mpri g r G One common way to compare two algorithms is by taking the limit of the ratios of their running times QQT PETLUEEWEUQ 07 if tn is of smaller order than fn O imH00 c if tn is of the same order as fn 00 if tn is of greater order than fn Example Compare the orders of growth of lg n and 1 I lg in W Wquot d lim Zlge algebra 7 lg Ham 7 lIm L39Hopltal39s Rule n oo n n 1 lim 2 lg e 0 lg e new n derivation One common way to compare two algorithms is by taking the limit of the ratios of their running times if tn is of smaller order than fn if tn is of the same order as fn if tn is of greater order than fn Example Compare the orders of growth of lg n and I lgn in W Wquot lim Zlge algebra d lg n oo i lIm c7 L39Hopltal39s Rule n ltgtltgt n W n 1 lim Zlgei0 Ige new n derivation lg n is of smaller order than Genra Q How will you measure input size What algorithmic parameter is it What is the agorithm39s basic operation Is it in the innermost loop Does the 7 of times the basic operation is executed depend on something other than the input size eg ordering of the input If so you have to consider worst best and average cases separately Specify a summation of the 7 times basic operation is executed Find a closedform solution if possible determine the order of growth from the formula for lt70 to n71 do forjlt70 to n71 do CI jlt70 for kHO to n71 do Cm H Cm All k1 BM C return M RIX1 IULTIPLYAO for 70 to Heel do forjlt70 to n71 do Cij lt70 for kHO to n71 do Ciiij H Ciiij Aii7ki Bikij C return Input size measure n the order of the matrices Basic operation Multiplication Dependency of op Depends only on input size Summation Mn 201 2101 51 Find the order Mn E 0 n3 while n gt 1 do count lt7 count 1 H lt7 5 return count mpl m i count lt7 1 while n gt 1 do count lt7 count 1 H lt7 5 return count 51 Input size measure n the integer given 121 Basic operation the n gt 1 comparison Dependency of op Depends only on input size Summation Here it is actually a recurrence relation but we know the answer Bn llg nl 1 31 Find the order Bn E Og n if n 0 return 1 else return Factoria1n 71 n if n 0 return 1 else return Factoria1n 71 n n n indicates input size we count multiplications u Fn Fn71n7 for ngtO a We call such equations recurrence relations a This defines a sequence but to make it unique we need an initial condition ie if n 0 return 1 El Recurrence relations can be useful analyzing some nonrecursive algorithms too eg BINARY Genra E v E Q How will you measure input size What algorithmic parameter is it What is the agorithm39s basic operation Is it in the innermost loop Does the 7 of times the basic operation is executed depend on something other than the input size eg ordering of the input If so you have to consider worst best and average cases separately Specify a recurrence relation for the 7 times basic operation is executed Solve the recurrence relation determine the order of growth of its solutions a Back substitution induction 1 Recurrence trees a Masters Theorem W 3 urbSaittu i U U Start with a large difficult input substitute it into the equation Continue for a few steps and note the pattern Use this intuition to posit a guess for the form of the solution Make use the of asymptotic definition to setup an inequality Use induction to show that solution works by showing that the inequality holds for all values of n if n1 return 1 else return BinaryLn2j 1 Relation Bn B if 7 1 return 1 Relation Bn B else return BinaryLn2j 1 39 B2k 1 1 3 2H 1 1 32H 2 B 2 k k Guess Bn 6 OIg n if n1 return 1 else return BinaryLn2j 1 39 B2k 1 1 3 2H 1 1 B2quot 2 2 B 2 k k Guess Bn 6 OIg n Relation Bn B From the de nition from O we want to prove that Bn S clgn 3039 3LnQJ1 GEM214d clgniclg21 S S clgniKgclgn We also have to show that the base case holds Genra Choose an appropriate experimental design F24 Decide on the efficiency metric and the measurement unit count vs time 1 How will input space be sampled range size etc all Implement the algorithm Generate a sample of inputs Run the algorithm on the sample inputs record results Analyze the results C HMme 1 Counter 1 Time Wit M ai 1 Counter u Identify 84 count basic operations as program runs a Requires additions to the code 1 Sometimes you can use a pro er to help identify the basic operation a Time 1 Counter 1 Identify 84 count basic operations as program runs a Requires additions to the code 1 Sometimes you can use a pro er to help identify the basic operation a Time a Measure the length of time it takes for the algorithm to complete the task 1 May be done in implementation or sometimes using OS commands 1 Times can be inaccurate 1 Small inputs may clock in below threshold of timer precision in On a multiprocessing 05 you will need to consider how much CPU time the user got etc a Times on different machines may differ u Sample the input space 1 Counts 84 times can vary on different inputs of the same size a Times can vary in the same input a For some kinds of algorithms counts can too eg RANDOMIZEDQUICKSORT I Choose an input range that makes sense for your purposes a Report the results a Aggregate average median etc results across runs for each input size and possibly for the same input 1 Tabulate or graph the data typically as size versus time p89 1 Fit a function to the data 1 Be careful what you conclude a Constants terms and factors can be misleading when input sizes are relatively small a When possible use a regression method to be as statistically certain as possi I Remember Empiricism is about beliefdon39t conclude too much Hllllie oar 39i g 2 1 Be careful what you conclude a Constants terms and factors can be misleading when input sizes are relatively small a When possible use a regression method to be as statistically certain as possi I Remember Empiricism is about beliefdon39t conclude too much rimcm Hllllie V o39i 39 g ratAiasiti 1 Be careful what you conclude a Constants terms and factors can be misleading when input sizes are relatively small a When possible use a regression method to be as statistically certain as possi I Remember Empiricism is about beliefdon39t conclude too much rimcm rimcm a This week39s assignments a Section 21 Problems 2 6 and 9 a Section 22 Problems 2 5 and 6 a Section 23 Problems 2 and 4 a Section 24 Problems 1 8 9 and 10 a Section 25 Problem 6 a Section 26 Problems 1 6 and 8 Challenge problem 3 a t R Paul Wiegand George Mason University Department of Computer Science January 25 2006 Introduction IE Algorithms amp Problems Fundamentals Problem Types Data Structures Homework ll a Course Syllabus D Personal lntl OdUCtloni In Office hours and contact info a Current position 84 n Grading projects 84 Research interests homewor s in Industry experience a Cheating D Personal expectations D Course Schedule a Course Introduction 0 HOW to succeed in Course title 84 topic U Be curious 84 motivated 1 Degree requirement 84 u Readll BEFORE class Pre req39s u Build good habits that work i Hand out info sheet for you I Ask for help Syllabus http www cs gmuedupwiegandcs483 Hiine in Why this course matters a Forrest for the trees a Making educated 84 informed decisions 1 Need as designer AND implementor 1 Engineer versus technician in Personal reflections a Don39t know BigO stuff a The JDK comes with a SORT routine I Etc a Key ideas from Henry Hamburger Firm What is a computational problem a Problem statement 1 The statement ofa probem specifies in general terms the relationship between input and output in Example Sort a set of numbers in nondecreasing order sorting probem Input ahazpuan Output a a zpiiaf El Problem instance in A problem instance consists of the input satisfying whatever constraints are imposed by the problem statement needed to compute a solution to the problem 1 Example problem instance Input lt46719381052gt 0utputsoution lt17273747576777879710gt a Are problems inherently hard or harder than others7 What is an algorithm u Algorithm 1 A recipe a list of instructions a transformation of data 7 u Cormen et al An algorithm is any welldefined computation procedure that takes some value or set of values as input and produces value or set of values as output a Levitin An algorithm is a sequence of unambiguous instructions for solving a problem ie for obtaining a required output for any legitimate input in a finite amount of time n In a sense algorithms are quotprocedural solutions to problems 1 Important point about algorithms 0 Unambiguous instructions 3 Input range specified carefully a Multiple representations for same algorithm a Multiple algorithms for solving the same problem a Different alg based on different ideas with different tradeoffs I vep l erat39t oquot quot DR Input mn NwheremZOngtOVmgtOAn20 Output Largest integer that divides both In and n evenly EUCLIDm n while n 7 0 do r e m mod n CONSECUTIVIEINTEGIEMm7 n step 1 teminmn i m step 2 1f t EN goto step 4 m H n step3 if E N return 139 7 H r step4 t lt7 t 71 goto step2 return In El Are these algorithms guaranteed to stop I Are there different input restrictions a Look over the middleschool method in the book Understand the problem Assess computational resources memory speed etc Decide between an exact or approximate algorithm Choose appropriate data structures Specify an algorithm in pseudo code Prove correctness Analyze the algorithm lmplement amp test the algorithm n An algorithm is correct if it produces the required result for every legitimate input I An exact algorithm produces solutions to problems that are exactly correct ri An approximate algorithm produces solutions to problems that are approximately correct 1 A data structure is a way to store and organize related information in order to facilitate access and modification El Algorithm analysis 1 Efficiency time space how algorithms scale wrt input size n Simplicity u Generality Type of problems solved a Range of inputs accepted U E El E D Arrange a set of values in a total or partial ordering Often make use of a key for sorting more complicated data With key comparison based sorts cannot do better than nlgn time Sorting algorithms are stable if given two elements with equal key values at positions 139 and j such that i ltj after the sort they will appear in positions Iquot and 1quot such that Iquot ltj Sorting algorithms are called in place sorts if they do not require more than a constant amount of memory beyond what is stored in the list 1 Searching 1 Find a given value called a search key in a set of values a A variety of algorithms exist sequential search binary search etc 1 Sometimes data are stored in data structures that make them more conducive for searching hash maps redblack trees etc a Engineers have to pay attention to applications where the underlying data may change frequently relative to the number of searches 1 String Processing 1 A string is a sequence of characters from some welldefined alphabet eg binary strings a Large class of problems dealing with the handling of strings n An example problem is string matching Find the positions of a substring in a master string 1 Graph Problems 0 A graph is a collection of vertices some of which are connected by edges 1 Traditional examples graph traversal finding shortestpath finding minimum spanning tree etc a Can be computationally very hard in Examples of hard graph problems 3 Traveling salesperson problem a Graph coloring problem Find the shortest tour that vis its all connected vertices exactly once Assign the smallest number of colors to vertices of a graph so that no two adjacent vertices are u Combinatorial Problems the same color 1 Problems in which one must find a combinatorial object that satisfies certain constraints and has some desired property in Tend to be the hardest types of computational problems in Many graph problems are combinatorial problems ri Geometric Problems 1 Geometric problems deal with geometric objects eg points llnesi pOlygonSi etc39 Given n points find the pair D For examp e of points with the minimum a Closestpair problem distance between them 393 convex hUll PrOblem Given n points in a set find 1 These are different than graph problems 5 smalls COWEX P0ly gon that contains all these points u Numerical Problems 1 Problems involving continuous mathematical objects in For examp e a Solving systems of equations I Computing derivatives 84 definite integrals n Optimizing numerical functions etc Hllllie Data I trr The following are two elementary data structures useful for produce more ab stract linear data structures called lists a finite sequence of data items array A sequence of n items of the same data type stored contiguously in memory and accessible using an index n Pre established fixed size n Constant time access insertion and deletion can be challenging 1 Example bit string 1001101 linked list A sequence of zero or more nodes each containing data and pointers to other nodes 1 Not necessarily fixed in size 1 Linear time access insertion and deletion are simpler a Linked lists can be singlelinked or doubly linked a Linked lists can have a header which stores useful information eg length HlllHe rum r atva Em 311m 3 Mom 392 Cebu mm The following are two special types of lists stack A list in which insertions and deletions can only be done at one end a LIFO last in first out a May be implemented by an array or a linked list a Basic operations PUSHPOP queue A list in which elements are accessed 84 deleted from one end front and inserted at the other end rear FIFO first in first out May be implemented by an array or a linked list Basic operations ENQUEUE DEQUEUE Position in a queue can be determined using a priority priority queues I D E El n Graphs are collections of points called vertices and line segments called edges connecting some of the vertices in Formally G V7 E where V is a finite set of labels corresponding to vertices eg V 3 bc and E is a finite set of pairs of these items eg E a7 ba7 c u Undirectecl graph Edges are unordered ie 37 b b7 3 u Directed graph Edges are ordered and thus imply a direction a e u Complete every pair of vertices is connected by an edge e e a e u Dense most vertices are connected 1 Sparse few vertices are connected adjacency matrix Enumerate vertices in 1 i i i n create an n x n matrix of boolean values indicating whether an edge exists between the specified vertices in Undirected graphs result in symmetric matrices u Easily determine if an edge exists requires space a Good for dense graphs b 1 O O adjacency list Create a linked list for each vertex containing the vertices to which that vertex is connected IEI A b A C 1 Somewhat more difficult to determine edge existence m A a more compact in space I A a a Good for sparse graphs HlllHe a We refer to a weighted graph when there are costs or values associated with the edges in a graph D D Adjacency matrix Use numeric values in cells of the matrix special character for noedge eg oo Adjacency list Attach values to nodes in the linked list 1 Properties of graphs D DUE DD pat a sequence of adjacent vertices connected by an edge A path is called simple if all edges are distinct Path length is the total number of vertices in the sequence A directed path is a sequence of vertices in which every consecutive pair of vertices is connected by an edge directed from the vertex listed first the next one A graph is connected if a path exists for every pair of vertices A cycle is a simple path of positive length that starts and ends with the same vertex A graph is said to be acyclic if it admits no cycles I HlllHe Tm A free tree is a connected acyclic graph A forest is multiple trees or an unconnected acyclic graph U l5 l lVl 1 D For every two vertices there39s always exactly one simple path between them I we can select an arbitrary vertex to be the root 1 For any v E T all vertices on the path between the root and v are called ancestors a The last edge on that path before v is called the parent v is the child of that node etc i A vertex with no children is called a leaf 1 A vertex with all its descendants is called a subtree D The depth v is the length of the simple path from the root to v a The height of a tree is the length of the longest simple path from l r HlllHe What is a set A set is an unordered collection possibly empty of distinct items a We can implement a set as a bit vector over the universal set a We can implement a set with a list structure with insertion constraints I A multiset or bag is a set without the uniqueness constraint an unordered collection of objects a Basic operations of a mutiset SEARCH INSERT DELETE u A basic data structure that accomplishes these operations is a dictionary D Sometimes we need to dynamically partition some n element set into a collection of disjoint sets 1 Sometimes we need to take the union or intersection of sets R Paul Wiegand George Mason University Department of Computer Science February 20 2006 Proving Correctness g The Correctness of SELECTIONSORT The Correctness of PARTITION Written UCIU D Recall the definition of a correct algorithm One returns the correct solution for every valid instance of a problem There are a variety of ways to prove correctness Correctness proofs are easy for some algorithms hard for others But there39s a standard way to prove correctness for many common algorithms using loops or recursion Identify and prove a loop invariance property There is a good discussion of this on pp 17 19 of Introduction to Algorithms 2quotd edition by Cormen et al These notes come from that text a We need to define a key property of the data manipulated by the main loop of an algorit m a The property must help us understand why the algorithm is correct a We must show that the property holds in the initial case is maintained each iteration and that when the loop terminates the property yields correctness 1 Determining this property in general can be difficult 1 But for simple common algorithms the property is often the key defining feature of the algorithm im vrreze ta 39 39 Initialization The loop invariance must be true prior to the first iteration of the loop Maintenance If the property holds prior to an iteration of the loop it must still hold after the iteration is complete Termination When the loop terminates the invariant provides a useful property that helps demonstrate that the algorithm is correct 1 To prove correctness we must prove the above about the loop invariance property D The first two pieces are similar to induction When they hold the loop invariant is true prior to every iteration of the loop a The termination is where is differs from induction and is the most important piece We are not showing that the loop invariant holds ad infinitum but rather that it results in a correct answer after a nite number of steps for M Oto n72 do min lt i for Jug i1 to n71 do if AU lt Amin minlt j SWAPAiAmin Loop Invariant At the start of each iteration of the outer most for loop the sublist A0H i71con7 sists of the i 7 1 smallest elements orig inally in A in sorted order The sublist Ain 7 1 contain the remaining ele ments in A Essentially L 39 L J L J J J Into two parts Loop Invariant At the st f Lerauon of me outerr The part to the e of 5 a sorted mower Oop me mm 0 71 coquot SW quotWquot 9 9quot quot A m of the 71 smaHesL e ements ongr e part from to the ght on maHy m A m sorted order ubhst whwch me a go thm 5 5th workmg n 7 1 am we remammg e er ments m A Sorted smaller Remaining sublist 39 m PARTKE TM Warfam 39 Initialization Maintenance Termination 7 At the first iteration i 0 the sublist to the left of i is empty It is reasonable to say that an empty sublist is ordered and obeys the loop invariant 7 At the start of any arbitrary iteration no element from 0 to i7 1 can ever be disturbed again During the step the inner for loop will find the smallest element in Ai 1 V V n 7 1 and will swap it for the Ai element This element is swapped into the i position The new Ai element cannot be smaller than any element 39n A0 V V i 7 1 because the loop invariant is true prior to the start of the iteration so it will simultaneously be the smallest element from i to the right and no smaller than any element to its left The loop invariant is preserved 7 When the last iteration of the algorithm terminates the loop counter will be on n 7 2 If the i 1 element is smaller it will be exchanged with the n 7 1St element Given that the sublist to the left of i is already sorted and neither An 7 2 nor An 7 1 can be smaller than any item in A0 V V n 7 2 because of the loop invariant the combined list will be in sorted order If the i element is not smaller the list is already sorted E El El Recall The sorting problem is to take a list of unordered items and order them by value We showed that the SELECTIONSORT algorithm will at each step preserve the property that items to the left of the main index are in sorted order and not greater than any item to the right If this property holds at initialization is maintained each step and terminates properly SELECTIONSORT must be a correct implementation of an algorithm for solving the sorting problem gt r s lt PARTITIONAI V V r QUICKSORTAI V V s 7 1 QUICKSORTAs 1 V V V r Loop Invariant for Partition At the start of the first repeat Io p in the PARTITION function the following holds for any array index k I k6ligtAk p n keur Ak 2p repeat i until p 2 AU repeat 7 7 until p S SWAPAiAj until i2 39 SWAPAiAj SWAPAIA39 Essentially L m r r h r n L A L Into three parts The part to the eft of except Ts L Lp 39quotW39am r Pammquot L m m L AL he start of the rst repeat Toop m the quotever yea er aquot e P V Va 9 ammoquot mam the foHowmg Ho dsfor The part to the ght of T5 never any army mdex k Ts than the pTVoLVa ue I k E U Aw lt p a The part m He made on whwch the k e U r AW p a gorwthm T5 5th workmg 39 m PARTKE TM Warfam 39 Initialization Maintenance Termination 7 Prior to the first iteration of the the loop i I and j r 1 There are no values at r 1 and we excuse the case where i I i The invariant holds prior to the step so everything to the left of i except I obeys the first condition of the variant and everything to the right of obeys the second condition The first repeat loop inside the main loop will skip past all consecutive values from that point forward that are less than p so we only need to consider the case when Ai S p Likewise with AU V r we only need to consider when 2 p Under that condition the two are swapped ithe previous Ai value now resides in the rightihand portion of the data list and the previous value now resides in the leftihand portion The invariant is preserved i The exception on the final iteration occurs when i Zj This can only occur once because of the until condition of the main loop and is corrected immediately after the loop terminates The pivot point is moved to the partition point by swapping it with the value Sincej is now less than or equal to i it resides in the leftihand set so S p obeying the first condition of the variant 3 a t er R Paul Wiegand George Mason University Department of Computer Science February 15 2006 Introduction to DivideAnd Conquer The MERGESORT Algorithm The QUICKSORT Algorithm The BINARYSEARCH Algorithm Binary Tree Traversal Fun With Multiplication Geometric Problems Homework Combine components into composite solution Example 20 3 Solve component problem instances Combine components into composite solution Example 20 3 30an71 Decompose a problem instance Solve component problem instances Combine components into composite solution n Example Zioa 90 ansl ao aim27H Sin2i quotquotl anil 3 rile A 39 d Decompose a problem instance Solve component problem instances Combine components into composite solution Example 20 3 30 alnQill Sin471 aim4i aing1i SLngj awnAim awnH an7 3 rile A 39 d Decompose a problem instance Solve component problem instances Combine components into composite solution Example 20 3 30 alnQill Sin471 aim4i aing1i SLngj awnAim awnH an7 3 rile A 39 d Decompose a problem instance Solve component problem instances Combine components into composite solution Example 20 3 90 3n71 1 spa471i alm39 an7 aLngilj 9 aim471 aim4i l quotquotl13ln271l aim2i 3 rile A 39 d Decompose a problem instance Solve component problem instances Combine components into composite solution Example 20 3 90 3n71 1 spa471i aith an7 ainzi quot39 t rile A 39 d Decompose a problem instance Solve component problem instances Combine components into composite solution Example 20 3 90 39an71 1 awn471i al3hq39 39 3n71 ainzi 39 39 1 Is this DampC example more efficient than brute force a Is this DampC example more efficient than brute force No it is n u Divideand conquer is not necessarily superior a Is this DampC example more efficient than brute force No it is n u Divideand conquer is not necessarily superior D But many times it is and many of the most efficient algorithms in CS are DampC u DampC typically involves recursion at least conceptually u DampC is well suited for parallelization a More generally a problem of size n can be partitioned into 2 instances of nonoverlapping components of size such that a 2 1 and b gt 1 we assume n is a power of b for simplicity n Given this the general divideand conquer recurrence can be defined as Tn aT fn a This generalization allows us an analysis shortcut weal If fn E nd where d 2 O in the gen eral divideandconquer recurrence then 6 nd if a lt bd Tn E ndlg n if a bd n390gba if a gt bd a More generally a problem of size n can be partitioned into 2 instances of nonoverlapping components of size such that a 2 1 and b gt 1 we assume n is a power of b for simplicity n Given this the general divideand conquer recurrence can be defined as Tn aT fn n This generalization allows us an analysis shortcut Master The rem For example H n E 9071 Where d 2 O in the gen 1 Recurrence for addition eral divideandconquer recurrence then Aquot 2Aquot2 1 6 nd if a lt bd Tn E ndlg n if a bd n390gba if a gt bd a More generally a problem of size n can be partitioned into 2 instances of nonoverlapping components of size such that a 2 1 and b gt 1 we assume n is a power of b for simplicity 1 Given this the general divideand conquer recurrence can be defined as Tn aT fn a This generalization allows us an analysis shortcut F examp39e H n E 9071 Where d 2 O in the gem El Recurrence for addition eral divideandconquer recurrence then Aquot 2Aquot2 1 u Since fn 1 it is in n0 6 nd if a lt bd Tn ndlgn ifabd uSoa2b2anddO n390gba if a gt bd a More generally a problem of size n can be partitioned into 2 instances of nonoverlapping components of size such that a 2 1 and b gt 1 we assume n is a power of b for simplicity 1 Given this the general divideand conquer recurrence can be defined as Tn aT fn a This generalization allows us an analysis shortcut F examp39e H n E 9071 Where d 2 O in the gem El Recurrence for addition eral divideandconquer recurrence then Aquot 2Aquot2 1 u Since fn 1 it is in n0 end ifaltbd Tn ndlgn ifabd uSoa2b2anddO loa d 607 lfagtb mSinceagtbdAnE V a More generally a problem of size n can be partitioned into 2 instances of nonoverlapping components of size such that a 2 1 and b gt 1 we assume n is a power of b for simplicity 1 Given this the general divideand conquer recurrence can be defined as Tn aT fn a This generalization allows us an analysis shortcut F mm H n E 9071 Where d 2 O in the gem El Recurrence for addition eral divideandconquer recurrence then Aquot 2Aquot2 1 9 nd ifaltbd u Since fn1 it isin n0 Tn ndlgn ifabd uSoa2b2anddO 907 if a gt bd m Since a gt bd ACn 6 90739s 0 7 BOm Ln2j 71 lt7C AOm Ln2j 71 COH n2 71 lt75 ALn2j H nil MERGESORTB MERGESORTC MERGEBCA C HMme if n gt 1 BOm Ln2j 71 lt7C AOm Ln2j 71 COH n2 71 lt75 ALn2j H nil MERGESORTB MERGESORTC MERGEBCA I39mlt90 whileiltpandjltq do if Bi Ak lt7 Bi i elseAkltiCjj k ifipAkH pq71gCCUH qil elseAk Hpq71 CBIXHp71 C HMme C HMme memm HMm W m MW HMm W m MW HMm W m MW HMm W m MW HMm W m MW HMm W m MW HMm W m MW How many comparisons n 7 1 muman Geomeh Homemm Decomposing 87516324 39 Decomposing 8716324 875 6324 39 Decomposing 8716324 8 1 6 4 Decomposing 8716324 6 4 4 39 8716324 lt8 ltgt lt1 Lgt Combining 39 8716324 Q12 3V Combining f 6f gt4 1 3X5 Combining 12 45678 n We count key comparisons 1 Assume wlog that n is a power of 2 n Cn 2Cn2 Mn7 n gt1C1 O 1 Applying the Mater Theorem a We count key comparisons E1 Assume wlog that n is a power of 2 n Cn 2Cn2 Mn7 n gt1C1 O 1 Applying the Mater Theorem I a 27 b 2 a We count key comparisons E1 Assume wlog that n is a power of 2 n Cn 2Cn2 Mn7 n gt1C1 O 1 Applying the Mater Theorem I a 27 b 2 n In worst case Mn E Gn17 so d 1 nraily 1 E r a We count key comparisons El Assume wlog that n is a power of 2 n Cn 2Cn2 Mn7 n gt1C1 O u Applying the Mater Theorem 3 a 27 b 2 n In worst case Mn E Gn17 so d 1 n a bd 50 nraily 1 E r a We count key comparisons El Assume wlog that n is a power of 2 n Cn 2Cn2 Mn7 n gt1C1 O u Applying the Mater Theorem 3 a 27 b 2 n In worst case Mn E Gn17 so d 1 n a bd 50 u Cn E nlg n if gt r s lt7 PARTITIONA H r QUICKSORTA s 71 QUICKSORTAS 1 r if gt r s lt7 PARTITIONA H r QUICKSORTA n s 71 QUICKSORTAS 1 n n n r PARTITIONA r p 9 AU lt7 j lt7 r 1 repeat repeat i until p 2 AU re eat jii until pg S P WAPAI397 AM until i Zj SWAPMULAUD SWAmAILAUD u nphcamgn Geomeh Hmmm How many comparisons m How many comparisons n muman Geomeh Homemm Decomposing 57816324 39 Decomposing 5716324 342 5 87 39 Decomposing 5716324 39 Decomposing 5716324 3 5716324 3 12 3 4 5 6 7 8 Combining 5716324 3 12 3 4 5 6 7 8 Combining It39s already combined nazly39 8 U In QUICKSORT the size of the split depends on the result of the PARTITION function a Best case 1 Worst case 1 Average case naly39 a U In QUICKSORT the size of the split depends on the result of the PARTITION function El Best case I Ideally the partition splits the sublist in half 0 Cbestn 2Cbestn2 n for n gt 1 Q7930 0 El Worst case 1 Average case naly39 a U In QUICKSORT the size of the split depends on the result of the PARTITION function El Best case I Ideally the partition splits the sublist in half 0 Cbestn 2Cbestn2 n for n gt 1 Q7930 0 D By the Master Theorem Cbegtn 6 9nlg n El Worst case 1 Average case nalyr39 m In QUICKSORT the size of the split depends on the result of the PARTITION function El Best case I Ideally the partition splits the sublist in half D Cbestn 2Cbestn2 n for n gt 1 Q7930 0 I By the Master Theorem Cbegtn 6 9nlg n El Worst case I But the partition might split only one item in the sublist El This happens when the sublist is already in increasing order I This degenerates the tree into a list pulling one item at a time and calling PARTITION on the remaining n 7 1 items 1 Average case nalyr39 133 In QUICKSORT the size of the split depends on the result of the PARTITION function El Best case I Ideally the partition splits the sublist in half D Cbestn 2Cbestn2 n for n gt 1 Q7930 0 I By the Master Theorem Cbegtn 6 9nlg n El Worst case I But the partition might split only one item in the sublist El This happens when the sublist is already in increasing order I This degenerates the tree into a list pulling one item at a time and calling PARTITION on the remaining n 7 1 items I Cwor5tnn1nn7139369n2 1 Average case An39zlyil r In QUICKSORT the size of the split depends on the result of the PARTITION function El Best case I Ideally the partition splits the sublist in half D Cbestn 2Cbestn2 n for n gt 1 Q7930 0 I By the Master Theorem Cbegtn 6 9nlg n El Worst case I But the partition might split only one item in the sublist D This happens when the sublist is already in increasing order I This degenerates the tree into a list pulling one item at a time and calling PARTITION on the remaining n 7 1 items I Cwor5tnn1nn7139369n2 u Average case Assume the partition is unbiased wrt position a s 6 0n 7 1 Prs 1V5 n 3 Cavgquot Zol n 1 Cavg Cavg 1 SH Cavg0 0 Cavg 0 An39zlyil r In QUICKSORT the size of the split depends on the result of the PARTITION function El Best case I Ideally the partition splits the sublist in half D Cbestn 2Cbestn2 n for n gt 1 Q7930 0 I By the Master Theorem Cbegtn 6 9nlg n El Worst case I But the partition might split only one item in the sublist D This happens when the sublist is already in increasing order I This degenerates the tree into a list pulling one item at a time and calling PARTITION on the remaining n 7 1 items I Cwor5tnn1nn7139369n2 u Average case Assume the partition is unbiased wrt position a s 6 0n 7 1 Prs 1V5 n U Camquot Z01 n 1 Cams 62w 1 SH Cavg0 0 Cavg1 0 n Cavg e Onn n an a In QUICKSORT the size of the split depends on the result of the PARTITION function El Best case I Ideally the partition splits the sublist in half D Cbestn 2Cbestn2 n for n gt 1 Q7930 0 I By the Master Theorem Cbegtn 6 9nlg n El Worst case I But the partition might split only one item in the sublist I This happens when the sublist is already in increasing order I This degenerates the tree into a list pulling one item at a time and calling PARTITION on the remaining n 7 1 items I Cwor5tnn1nn7139369n2 g Average case Some fixes include Assume the partition is unbiased wrt position Randolelng lnp39Jt order a 5 g 0 n 7 1 Pr5 V5 medianeofethree partitioning U Cang39 Z ol n 1 Cams Cavgn 1 SH Cavg0 0 Cavg1 0 n Cavg e On n n while lg r do In 9 LJ if KAm return In else if KltAm M7 mil else hi m1 return 71 while lg r do In 9 LJ if KAm return In else if KltAm M7 mil else hi m1 return 71 while lg r do In 9 LJ if KAm return In else if KltAm M7 mil else hi m1 return 71 while lg r do In 9 LJ if KAm return In else if KltAm M7 mil else hi m1 return 71 while lg r do In 9 LJ if KAm return In else if KltAm M7 mil else hi m1 return 71 a Best case a Key is at the midpoint in the list D C1795 6 91 constant time I VSO unlikely 0 Worst case 1 Average case a Best case a Key is at the midpoint in the list I C1755 6 91 constant time I VSO unlikely 0 Worst case I If the key is not in the list n 6mm Cwomqgj 1 for n gt 1 6mm 1 1 Average case a Best case a Key is at the midpoint in the list I C1795 6 91 constant time I VSO unlikely 0 Worst case I If the key is not in the list D Cworstn Cwom gj 1 for n gt 1 Cworst1 1 By the Master Theorem Cworstn 6 9Ig n 1 Average case in Best case a Key is at the midpoint in the list I Che 6 91 constant time I VSO unlikely 1 Worst case I If the key is not in the list U Cworstn Cwom gl 1 for n gt 1 Cworst1 1 By the Master Theorem Cworstn 6 9lg n 1 Average case I Not substantially worse than the worst case actually I Cavg 6 Ig n than a Binary tree T a finite set of nodes that is either empty or consists of a root and two disjoint binary trees TL and TR called the left and right subtree respectively a Note that the very definition recursively divides the tree into smaller similar structures 1 Many treerelated problems are solved by applying DampC methods n In particular many treerelated problems require an algorithm to traverse a tree if T0 return 1 else return maxIIEIGHT TLHEIGHT TR 1 1 Measure problem size by the number of nodes in a given tree n T u The counts for MAXIMUM and addition operations will be the same El So An T An D AnTR17 for nT gt 07 AO O if T0 return 1 else return maxIIEIGHT TLHEIGHT TR 1 1 Measure problem size by the number of nodes in a given tree n T u The counts for MAXIMUM and addition operations will be the same El So An T An D AnTR17 for nT gt 07 AO O if T0 return 1 else return maxIIEIGHT TLHEIGHT TR 1 El Measure problem size by the number of nodes in a given tree n T u The counts for MAXIMUM and addition operations will be the same 1 So An T An D AnTR17 for nT gt 07 AO O a Can draw tree39s extension by replacing empty subtrees with special nodes HEI Y T if T0 return 1 else return maxIIEIGHT TLHEIGHT TR 1 El Measure problem size by the number of nodes in a given tree n T u The counts for MAXIMUM and addition operations will be the same 1 So An T An D AnTR17 for nT gt 07 AO O a Can draw tree39s extension by replacing empty subtrees with special nodes 1 Special nodes are external nodes 2 Original nodes are internal nodes if T0 return 1 else return maxIIEIGHT TLHEIGHT TR 1 a Measure problem size by the number of nodes in a given tree n T u The counts for MAXIMUM and addition operations will be the same 1 So An T An D AnTR17 for nT gt 07 AO O a Can draw tree39s extension by replacing empty subtrees with special nodes Special nodes are external nodes Original nodes are internal nodes El HEIGHT makes one addition per internal Hg many lanai quotOdes does a tree node one comparison per internal and With n Internal nodes have external node if T0 return 1 else return maxIIEIGHT TLHEIGHT TR 1 a Measure problem size by the number of nodes in a given tree n T u The counts for MAXIMUM and addition operations will be the same 1 So An T An D AnTR17 for nT gt 07 AO O a Can draw tree39s extension by replacing empty subtrees with special nodes Special nodes are external nodes Original nodes are internal nodes El HEIGHT makes one addition per internal many external quotOdes does a tree node one comparison per internal and With n Internal nodes have X n external node T lnorder traversal Visit left subtree then root then right subtree Preorder traversal Visit root then left subtree then right subtree 8136ng Preorder traversal Visit left subtree then right subtree then root T lnorder traversal Visit left subtree then root then right subtree Preorder traversal Visit root then left subtree then right subtree 3136ng Preorder traversal Visit left subtree then right subtree then root T lnorder traversal Visit left subtree then root then right subtree Preorder traversal Visit root then left subtree then right subtree Defibgq Preorder traversal Visit left subtree then right subtree then root T lnorder traversal Visit left subtree then root then right subtree Preorder traversal Visit root then left subtree then right subtree 1306ng Preorder traversal Visit left subtree then right subtree then root T Preorder traversal Visit root then left subtree then right subtree lnorder traversal Visit left subtree then root then right subtree 61213 Preorder traversal Visit left subtree then right subtree then root T Preorder traversal Visit root then left subtree then right subtree lnorder traversal Visit left subtree then root then right subtree 61213 Preorder traversal Visit left subtree then right subtree then root T Preorder traversal Visit root then left subtree then right subtree lnorder traversal Visit left subtree then root then right subtree 213 Preorder traversal Visit left subtree then right subtree then root T Preorder traversal Visit root then left subtree then right subtree lnorder traversal Visit left subtree then root then right subtree 213 Preorder traversal Visit left subtree then right subtree then root T Preorder traversal Visit root then left subtree then right subtree lnorder traversal Visit left subtree then root then right subtree 213 Preorder traversal Visit left subtree then right subtree then root T lnorder traversal Visit left subtree then root then right subtree Preorder traversal Visit root then left subtree then right subtree Preorder traversal Visit left subtree then right subtree then root 126 T lnorder traversal Visit left subtree then root then right subtree Preorder traversal Visit root then left subtree then right subtree Preorder traversal Visit left subtree then right subtree then root 126 T lnorder traversal Visit left subtree then root then right subtree Preorder traversal Visit root then left subtree then right subtree Preorder traversal Visit left subtree then right subtree then root edge T lnorder traversal Visit left subtree then root then right subtree Preorder traversal Visit root then left subtree then right subtree Preorder traversal Visit left subtree then right subtree then root 60

### 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."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "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.