### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithm Analysis and Design CPSC 5115G

GPA 3.91

### View Full Document

## 54

## 0

## Popular in Course

## Popular in ComputerScienence

This 214 page Class Notes was uploaded by Earlene Cremin III on Sunday October 11, 2015. The Class Notes belongs to CPSC 5115G at Columbus State University taught by Edward Bosworth in Fall. Since its upload, it has received 54 views. For similar materials see /class/221205/cpsc-5115g-columbus-state-university in ComputerScienence at Columbus State University.

## Similar to CPSC 5115G at

## Reviews for Algorithm Analysis and Design

### 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/11/15

Evaluating Non Linear Functions Here we address the problem of evaluating a function for a given argument Consider the function FX to be evaluated at the value X X0 1 We assume that FX is a mapping from the real numbers into the real numbers The set of integers is here seen as a subset of the reals 2 We assume that FX is de ned at X X0 We do not attempt to evaluate expressions such as x l 3 We note that this can be expresses as nding the value Y0 such that Y0 FX07 or Y0 There are many similarities to solving non linear equations Thus solving for Y0 x25 is equivalent to solving the equation FX X2 25 0 We shall brie y discuss two main classes of functions 1 Polynomial functions 2 Functions that are not polynomials Evaluating Polynomials The rst topic to cover is that of polynomial functions By this we mean a standard polynomial with a nite number of terms A polynomial of degree N over the argument X is de ned to be of the form FX ANoXN AN10XN391 Azox2 AloX A0 N 2 0 and AN 7 0 The only real question in evaluating such a polynomial is the selection of an ef cient method The best method is called Homer s Rule ALGORITHM HORNER AO N X0 THE COEFFICIENTS ARE IN THE ARRAY AO N P AN THE COEFFICIENT OF XN FORK N 1 DOWN TOODO P P X AK END DO RETURN P THE VALUE OF FX AT X X0 NOTE This algorithm uses only the basic operations addition and multiplication that are available on any standard computer Sample of Homer s Rule Consider the polynomial FX A40X4 A30X3 AzoX2 AloX A0 Evaluate this at X X0 The basic part of the rule is P A4 Loop for K 3 Down To 0 Start P A4 K23 P PX0A3 PA4X0A3 K 2 P P39XO A2 A40X0 A3X0 A2 P A42 A30X0 A2 K 1 P P39XO A1 A42 A30X0 A2X0 A1 P A43 A32 A20X0 A1 K O P P39XO A0 A4 X03 A3 X02 A2 X0 A1 X0 A0 A4 X04 A3 X03 Az X02 A1 X0 A0 Functions That Are Not Polynomials Here we consider a subset of the non linear functions that are not polynomials The method to be discussed next applies to those real functions of real numbers that are both continuous and analytic in the mathematical sense In general none of these functions can be directly evaluated using only the primitive operations available on a stored program computer What are the basic mathematical operations available on a modern computer There are only four addition subtraction multiplication and division Some modern computers do not have direct implementations of division but rather support an inverse function YX Y UK The functions that we now discuss can be represented as in nite series Each term in the in nite series can be evaluated using only multiplication and division The terms can be combined with addition and subtraction The primary issue here is termination How does the algorithm terminate For polynomials we just evaluate all of the terms This is not an option here Four Sample Functions As examples let us discuss the following functions Trigonometric functions Sine and cosine Exponential functions EX and Ex Logarithmic functions The natural logarithm The methods used are based on series expansions obtained from calculus SinX x x331 XS5 X77 x991 x x36 XS120 x75040 x9362880 CosX 1 xzz x441 X66 XS8 1 x22 x424 x6720 XS40320 ExpX 1 x x221 x33 x441 XS5 Exp X 1 x x221 x33 1 x441 XS5 Lnl X X X22X33 X44X55 1ltXg1 But note that each series is in nite How do we know how many terms to evaluate to get the precision we need Precision Predictions from Calculus There are a number of results from calculus that will allow us to determine the number of terms to evaluate In order to apply the simplest result I shall restrict our consideration to the following functions SinX for the range 0 g X 3 752 0 3 X 3 90 CosX for the range 0 S X S 1t2 0 3 X S 90 EXp X for the range X 2 0 Lnl X for the range 1 lt X g 1 What these functions have in common is that each is represented by an in nite series with alternating terms The maximum error from evaluation of a nite number of the terms in such a series can be shown to be less than the absolute value of the rst omitted term Let us consider single precision arithmetic with precision given by s 1224 1 16777216 z 59610 8 Preliminary Assessment Each term in the series expansion of sine cosine and exponential is of the form XN N Let us rst consider the trigonometric functions Given the constraint that O S X 1t2 we see that the maximum error in stopping the series before the term XN N is Tc2N N We want to have 1132N N lt 8 02 How many terms do we need Here is a rough calculation Recall that 1 lt 4 so 1122 lt 2 We solve the inequality 1t2N N lt 2N N lt 02 which becomes 2N24 lt I have to do this by inspection trial and error N20 N12 Nl6 Nl4 N15 244 w 17561013 236 w 68721010 240 1100o1012 238 w 27491011 239 w 54981011 20 24331018 12 4790108 16 20931013 14 87181010 15 13081011 N is too big N is too small N is too big N is too small N is too small The choice is the 16th power it is the rst value of N for which 20 lt N The Trigonometric Functions As a result of the above calculations we have concluded that the following series expansions suf ce for the sine and cosine under the assumption of single precision SinX x x33 x55 x77 x99 x 11 x1313 x1515 CosX 1 x22 x44 X66 XS8 x1 10 x1212 x1414 Of course it is very likely that small values of X might lead to the inequality XN N lt 8 1224 w 596108 before all 8 terms are evaluated It that case the evaluation can be terminated early There is an entire mathematical theory devoted to placing an upper bound on the errors generated by approximation by a nite series This theory is the origin of the Big O notation that we used to express algorithmic complexity Decrease and Conquer Though the term is not commonly used decrease and conquer describes another powerful algorithm design strategy We shall use the decrease and conquer strategy to consider solutions to a few problems some of them common Here are the problems that we shall discuss l Integer exponentiation calculating the positive real power of a number 2 Insertion sort 3 The fake coin problem 4 Graph traversals BFS Breadth First Search and DFS Depth First Search 11 Topological sorting 6 Binary search trees Integer Exponentiation Algorithm 1 We consider four solutions to the integer exponentiation problem Given a real number A and an integer N 2 O compute AN the Nth power of A The first three algorithms are given to illustrate the differences between the three strategies studied so far We then show a more ef cient algorithm Brute Force Function FA N R l R Result what a brilliant name For K l to N Do R R A End Do Return R Integer Exponentiation Algorithm 2 This algorithm follows the standard divide and conquer strategy of trying to break the problem into two sub problems of equal size and solving each DivideandConquer Function FA N If N gt 1 Then M N 2 Integer division so 3 2 1 R FA M FA N MM Else If N 1 Then R A Else R 1 Return R Integer Exponentiation Algorithm 3 This algorithm is really just the brute force algorithm redone with recursive calls DecreaseandConquer Function FA N If N gt 1 Then RFA N 1A Else If N 1 Then RA Else Rl Return R Integer Exponentiation Algorithm 4 This algorithm is based on the binary representation of the integer power N For example let N 26 16 8 2 11010 in binary We observe that A26 A16 o A8 0 A2 Function FA N R 1 AP A AP is a to the power P While N gt 0 Do NR N mod 2 If NR 1 Then R R AP AP AP AP N N 2 Integer division 12 0 End While Return R One can show that the time complexity of this algorithm is log2N more accurately l 10g2N Here we need l 10g226 5 loops Insertion Sort Insertion sort is most useful when building an array one element at a time This is a good example of an algorithm sometimes called on line data items are received and processed one at a time Basic strategy Add an element X into a sorted array Al N 1 To do this 1 Find the largest index J l S J S N 1 such that AJ S X and 2 If J lt N 1 move every element With index gt J up one and 3 Then set AJl X Note that this can be applied to an entire array at once as the book does Algorithm for Insertion Sort Here is the basic step of the sort algorithm Procedure Insert A1N K X Assumes that AlK is sorted Places X in its place by moving up others Note the required order of moving elements J K While J 2 1 And AJ gt X DO AJ l AJ J J 1 End Do AJ l X Here is the entire algorithm Procedure InsertSort AlN For L 2 to N Do K L 1 Insert A K AL Sample of Insertion Sort Sort the array A1 8 3 1 41 5 9 2 6 L2 K 1 Insert A18 1 A2 X1 A1831415926 J 1 AJ 3 gt X So A2 A1 and A1 8 3 3 41 5 9 2 6 J 0 End loop AJ 1 A1 1 A1 8 1 3 41 5 9 2 6 K2 Insert A18 2 A3 X4 A18134 1 5926 J 2 AJ 3 S X so end loop AJ 1 A3 4 A1 8 1 3 4 1 5 9 2 6 Sample of Insertion Sort Part 2 L4 K23 Insert A18 3A4 X21 A1813415926 J3 AJ 4gtX A4 A3 A1 8 1 3 4 4 5 9 2 6 J 2 AJ 3 gt X A3 A2 A1 8 1 3 3 4 5 9 2 6 J 1 A11 X so end 100p AJ 1 A2 1 A1 8 1 1 3 4 5 9 2 6 It is easy to see that neither L 5 X 5 and L 6 X 9 result in any array swapping The Fake Coin Problem We are given N 2 3 coins exactly one of which is fake having a weight different om the real coins We are given a balance scale by which we can compare the weights of single coins or collections of coins The algorithm is based on the following observation for the 3 coin problem Consider three coins C1 C2 C3 with weights W1 W2 W3 Select two coins at random call them C1 and C2 place them on the balance scale and compare the weights If W1 W2 then coin C3 is the fake Ile 73 W2 then one of coins C1 or C2 is the fake Remove C2 and replace it with C3 If W1 72 W3 then C1 is the fake Ile W3 then C2 is the fake The Fake Coin Problem General Step Given a pile of N coins one of which is known to be fake we divide it into two piles P1 and P2 If N is odd then N 20K 1 Let each of P1 and P2 have K coins There is one coin left out Place the two piles on the scales and compare WPl to WP2 If WPl WP2 then the coin left out is the fake If WPl 73 WP2 then the coin left out is OK and the fake coins is in one of P1 or P2 At this point we have to decide which pile contains the fake coin Here is the rule Pl contains the fake coin if and only if P2 does not The Fake Coin Problem More General Step Given a pile of N coins one of Which may be fake divide into two piles IfN is odd then N 2K 1 Let each of P1 and P2 have K coins There is one coin left out If N is even then N 20K Each of P1 and P2 have K coins and no coin is left out Case 1 N 20K If WPl WP2 then the pile does not contain a fake coin If WPl 73 WP2 then the pile does contains a fake coin Which may be in either P1 or P2 Case 2 N 20K 1 If WPl 7t WP2 then the pile has a fake coin in either P1 or P2 If WPl WP2 then the pile may or may not have a fake coin Swap the odd coin out With one in P1 If WPl WP2 then the pile has no fake coin If WPl 73 WP2 then the odd coin is fake Graph Traversal Algorithms Many computer science problems are well modeled as graph traversal problems There are two basic graph traversal methods BFS Breadth First Search DFS Depth First Search A graph comprises a collection of nodes more later A graph traversal algorithm visits and marks every node in the graph Marking the vertices once visited prevents the algorithm going into endless loops More advanced graph traversal methods will use knowledge of the problem in order to limit the number of vertices in the graph that are visited Basic Terms in Graph Theory Let G V E be a graph With vertex set V and edge set E The vertex set V is a non empty set often denoted V1 V2 VN The edge set E is a set of pairs of vertices V J VK in which VJ e VG and VK e VG If VJ E then 1 Vertex V J and VK are said to be adjacent and 2 the edge V J VK is said to be incident to each of vertices V J and VK A path in a graph is de ned to be a sequence of edges beginning at the start vertex and ending at the destination vertex A graph is said to be connected if and only if each pair of vertices is connected by at least one path Representation of a Simple Graph We have two data structures commonly used to represent a graph 1 Adjacency matrix 2 Adjacency lism It is the structure of these objects that determine the progress of the graph search not the picture of the graph Here is a sample graph and its adjacency lism It is an undirected graph 0 e 1 gt 2 3 4 2 a 1 3 a 1 o o 4gt1 Intuitive Discussion of BFS and DFS The BFS and DFS algorithms are defined for general graphs but more easily illustrated on rooted trees We must specify the adjacencies implied above AgtBCD BgtAEF Egt B FgtB CgtAGH GgtC HgtC DgtAJK JgtD KgtD DFS on a Rooted Tree When started at the root of a rooted tree DFS goes deep hence its name Note that it proceeds immediately to a leaf node DFS imposes a tree structure on the graph that is searched For a tree such as we have above the imposed tree structure is the tree itself The red lines in the figure are drawn to suggest a search order They are not to be interpreted as edges in any graph Notes of the Analysis of Algorithm Ef ciency We now begin a topic that forms the foundation of the study of algorithms 7 the study of the time and space ef ciency of algorithms Time ef ciency relates indirectly to the clock time required by an algorithm and space ef ciency relates to the amount of memory used We think of two functions which might be called TN a measure of the time for the algorithm as a function of the size of the input MN a measure of the amount of memory required as a function of the input size As it develops we discover that time ef ciency seems to be more important that the amount of memory used by the algorithm As a result we usually pay little attention to the space ef ciency of an algorithm and focus on the time complexity The Measure of Algorithm Time If we ask how long an algorithm takes to execute we immediately might think of clock time There are a number of good reasons not to use time in seconds as a measure of TN 7 the time taken by the algorithm These all relate to the fact that the time in seconds to run an algorithm depends on too many factors external to the speci cation of the algorithm Some of the factors affecting the total running time of an algorithm include 1 the number of computer instructions executed to complete the algorithm and 2 the speed of the computer CPU Central Processing Unit and 3 the effectiveness of the computer s instruction set and 4 the amount of memory in the computer and 5 the fraction of time that the Operating System has scheduled for the program In the study of algorithms it is better to focus on the algorithm itself and not on factors such as CPU speed and scheduling by the Operating System that are external to the algorithm As a result we decide to count the basic steps of the algorithm Recall that an algorithm is de ned by the textbook as follows An algorithm is a sequence of nonambiguious instructions for solving a problem in a nite amount of time An input to an algorithm speci es an instance of the problem the algorithm solves Textbook page 39 The computation of TN the time complexity of an algorithm changes to an attempt to compute the total number of instructions executed for solving a problem instance of a given size In producing the execution count for an algorithm we do not just count the number of instructions in the nonexecuting algorithm but increase the count by one for every execution of any instruction Thus a loop with 10 instructions executed 20 times gets a count of 200 In order to simplify the analysis we often choose not to count every instruction or step in the execution of the algorithm but only the basic operations I often call these basic steps The idea is that a count of these basic operations is representative of the total number of instructions executed and can form the basis for an accurate time estimate Page 1 of 13 Chapter 2 Last Revised On August 25 2004 Consider the following code fragment written in FORTRAN just to be different K 200 c EXECUTE THE LOOP ENDING AT STATEMENT 500 D0 500 J 1 K CJ AU BU 500 CONTINUE If one were to do a time analysis of all of the instructions involved in the execution of this loop it would be necessary to rewrite the code in a less structured form Again note that the FORTRAN language uses numbers as statement labels K 200 J O 300 CONTINUE J J l CJ AJ BJ 500 IF J LT K GO TO 300 An accurate count of the instructions can now be made We note the following 1 The line labeled 300 is a noop that will be removed by the compiler 2 The next line has two operations an addition and an assignment 3 The line after that also has two operations an addition and an assignment 4 The line labeled 500 has two operations a comparison and a branch Based on the above arguments we would say that there are six instructions executed for each traversal of the loop leading to the conclusion that either of the code blocks corresponds to 1200 instruction executions This analysis is valid but contains more detail that we really need to understand the time complexity of the code fragment What we really want to know for the time complexity of the above code may be stated by example Suppose the value of K is doubled How much longer does the execution take There is a way to simplify the analysis and keep only the detail required for an accurate analysis of the time complexity This method focuses on the basic operations in the algorithm Look again at the above loop We quickly see that the basic operation of the loop can be found in the single statement We see then that this basic operation is executed K times so that the number of basic operations in this code fragment varies linearly with K and that doubling the value of K should double the run time of this code fragment Thus the estimate of time complexity of an algorithm is based on establishing the basic operations performed in the algorithm and finding a way to count these operations Page 2 of 13 Chapter 2 Last Revised On August 25 2004 The Measure of Problem Instance Size So now we have the function TN which measures of the time of the algorithm as a function of the N size of the input We have argued that the units of this function T TN should not be a measure of clock time but a measure of the basic operations executed by the algorithm in order to solve the problem We now must consider what we mean by the size of the input Fortunately the informal definition is quite intuitive For searching sorting finding the minimum or maximum value and similar operations on a list of N items having both and Z operators defined the size is N 7 the number of items For operations on square N by N matrices the size of the input is often stated as N although it is more properly N2 7 the total number of elements in the array In the big picture of importance to the analysis of algorithms there is no real difference between N and N2 and so we insist only that the measure of size for the array be identified For common arithmetic problems the size of the input is a bit more indirect We count the number of digits or the number of bits in the number Suppose we want to determine the time efficiency of a function to return the square root of a positive integer M The size of M is either the number of digits or number of bits in the number If we are counting the number of digits then the two numbers 1000 and 8000 have the same size Note again that because it is the big picture we are considering we can count either the number of bits in the number B or the number of digits in the number D B LlogzMJ 1 D Llog10MJ l but log10M log102ologzM so the two are related Growth of TN In the analysis of time complexity of an algorithm we are not so much interested in a precise statement of the function TN although that is important but in a statement of the growth rate of the lnction How fast does TN grow as a function of N We shall introduce a number of notations to express the growth rate of TN including OFN the Big O notation and QFN the Big Omega notation and FN the Big Theta notation There is a lot of interesting mathematics behind these notations and we shall study some of it but what we are really trying to say is quite simple From your high school days you should remember logarithmic functions polynomial functions and exponential functions Breaking the polynomial functions down a bit into linear quadratic cubic and other polynomial we are asking if the function is logarithmic exponential linear quadratic cubic or some other polynomial function We use the obvious definitions here so logN is logarithmic and N2 3N l is quadratic and N is exponential Page 3 of 13 Chapter 2 Last Revised On August 25 2004 Orders of Growth and Time Ef ciencies We pause to make an obvious point about the ef ciency of an algorithm We intend to use the three notations to describe the ef ciency of an algorithm saying something like This algorithm has time complexity OFN where we specify FN We should be precise here If we are speaking of the time complexity of an algorithm we say that the algorithm has time complexity OFN to mean that we have computed TN the time complexity function of the algorithm and that TN e OFN We should note that in the strict mathematical sense the objects OFN QFN and FN are sets of functions thus we make statements such as TN e OFN denoting set membership Note that this is equivalent to saying that TN has growth rate OFN As an example consider the function TN 40N3 l7oN2 320N 8 In what follows we shall show the following three statements TN e ON3 ithus TN is ON3 and TN e QN3 ithus TN is QN3 and TN 6 N3 thus TN is N3 But all we are saying is that TN is a cubic function of N Strictly speaking we can speak of the set of cubic functions TN AoN3 BoN2 CoN D characterized by the set of four numbers A B C D or just say that a given function is cubic Upper Limit on the Growth Rate The Big 0 We now investigate some formal notation to express the upper limit on the growth rate of a function such as TN We shall see that there are two ways to express this upper limit depending on whether one wants an upper limit or the best upper limit At this point to see what we are talking about consider the quadratic function TN 13oN2 52oN 17 We could say that this function is cubic in that it grows more slowly than a cubic function It is more common in algebra to call the function quadratic because the coef cient of N2 is nonzero and no higher power of N has a nonzero coef cient Thus we could say either that TN 130N2 520N 17 is ON3 or that it is ONz Although both statements will be shown to be true we consider the second statement 7 that TN e ONz to be better in that it gives a more precise statement of the growth rate De nition A function TN is said to be OGN denoted as TN e OGN if there exists some positive constant C and some nonnegative integer No such that TN S CoGN for all N Z No It should be emphasized at this point that any pair C No will do one does not have to pick the smallest values that do the job To show that this is true we show quickly that the above function TN 13oN2 52oN 17 is both ONz and ON3 Page 4 of 13 Chapter 2 Last Revised On August 25 2004 Let TN 130N2 520N 17 Then for N Z 1 we have TN s 52oN2 52oN 52 or TN s 1560N2 so TN e ONz We observe further that for N Z 1 we have TN S 1560N2 so TN S 1560N3 and TN e ON3 In both cases C 156 and N0 1 Although neither demonstration is considered elegant they both do the job with a minimal amount of effort and are valid We can similarly establish that TN 40N3 170N2 320N 8 is ON3 either by noting that for N Z 1 we have TN S 1280N3 or by the more elegant and tedious way of nding the number No such that for all N Z No we have TN S 50N3 Since we know that TN is a cubic function we know that the value No can be obtained either by guessing the larger of the three possible roots ofthe equation SON3 40N3 170N2 320N 8 or by solving it The equation becomes N3 7 170N2 7 320N 7 8 0 which does have at least one real root Not being handy with the solutions of cubic equations I elect to go with cruder estimates Lower Limit on the Growth Rate The Big Q De nition A function TN is said to be QGN denoted as TN e QGN if there exists some positive constant C and some nonnegative integer No such that TN Z CoGN for all N Z No The careful reader will note that this definition differs from the OGN definition only in replacing the S in the former definition by 2 It should be emphasized at this point that any pair C No will do one does not have to pick the smallest values that do the job To show that this is true we show quickly that the above function TN 13oN2 52oN 17 is both QN2 and QN Let TN 130N2 520N 17 Then for N Z 1 we have TN z 13oN2 13oN 13 or TN z 130N2 so TN e QN2 We observe further that for N Z 1 we have TN Z 130N2 so TN Z 130N and TN e QN In both cases C 156 and N0 1 Although neither demonstration is considered elegant they both do the job with a minimal amount of effort and are valid We can similarly establish that TN 40N3 170N2 320N 8 is QN3 by noting that for N Z 1 we have TN Z 40N3 Note that the simplicity of the demonstration is due to the fact that there are no negative coefficients in the polynomial Suppose that the polynomial were given as TN 40N3 7 170N2 7 320N 7 8 Then we would have to solve for an No such that for all N gt No we have TN Z 30N3 Again one can guess a value of do some algebra Note that TN is exponential if and only if TN e QKN for K gt 1 Page 5 of 13 Chapter 2 Last Revised On August 25 2004 A More Precise Limit on the Growth Rate The Big 9 De nition A function TN is said to be GN denoted as TN e GN if there eXists some positive constants C1 and C2 and some nonnegative integer No such that C10GN S TN S C20GN for all N Z No It should be emphasized at this point that any triple C1 C2 N0 will do probably subject to the condition that C1 lt C2 Again one does not have to pick the best values that do the job The careful reader will note that there is an alternate de nition for the class GN De nition TN e GN if and only if both TN e QGN and TN e OGN Either of these two de nitions will suffice for showing that TN e GN Before working some examples let us make some statements that might be definitions TN is linear if and only if TN e N and TN is quadratic if and only if TN e Nz and TN is cubic if and only if TN 6 N3 and TN is quartic if and only if TN 6 N4 etc We now reconsider our two examples First we consider TN 130N2 520N 17 For N Z l we have TN Z l3oN2 l3oN 13 or TN z 130N2 so TN e QNz For N Z l we also have TN S 520N2 520N 52 or TN s 1560N2 so TN e ONz Now we have two reasons for stating that TN e Nz 1 13oN2 s TNS1560N2 for all N z 1 2 Both TN e 9N2 and also TN e ONz We can similarly establish that TN 40N3 l7oN2 320N 8 is N3 For N z 1 we have TN z 4oN3 so TN e QN3 For N z 1 we have TN s 128oN3 so TN e ON3 Now we have two reasons for stating that TN 6 N3 1 4oN3 s TN s 128oN3 for all N z 1 2 Both TN e QN3 and also TN e ON3 Put another way we have shown the following 1 TN 130N2 520N 17 is a quadratic function of N and 2 TN 4oN3 17oN2 32N 8 is a cubic function ofN Page 6 of 13 Chapter 2 Last Revised On August 25 2004 Now for a Dose of Calculus We now mention some convenient ways for establishing the growth rates of functions The first method involves only a bit of algebra and the second involves some calculus If you do not like calculus remember that the use of these methods is not required for this class We first mention the selfevident polynomial method If TN is given as a polynomial then the name we give the polynomial linear quadratic etc gives the growth rate The second is based on the computing the limit as N gt 00 of the ratio of two functions Recall that we say that lim GN 00 if the function GN grows arbitrarily large as N Ngtoo grows arbitrarily large For example we say that hm N3 00 because as N grows large Ngtoo there is no upper bound to the value of the function N3 Consider a function TN We say the following 1 If hm gt 0 then TN is QGN Note that the limit could be 00 Ngtoo TN 2 If 11m 7 C for some pos1t1ve constant C then TN 1s GN Ngtoo GN TN 3 If lim GN lt 00 then TN is OGN Note that the limit could be 0 Ngtoo Consider TN 130N2 520N 17 We use the calculus methods to prove some properties Claim TN is QN 2 Proof w W 13 N 52 j 0Q Ngtoo Ngtoo N New N Claim TN is 9N2 2 TN1i 13oN 52N17 lim132 17 13 Ngtoo 7 N2 N330 N2 N N2 Proof hm Ngtoo Claim TN is NZ TN 2 11 Ngtoo N Proof lim 130N2520N17 m 2 lim 132 J 13 asjust above Ngtoo N N2 Page 7 of 13 Chapter 2 Last Revised On August 25 2004 Claim TN is ONz TN 130N2520N17 11m 2 Ngtoo N2 Proof lim 7 1iml3 l3 asjust above Ngtoo Claim TN is ON3 N 130N2520N17 13 52 17 llm 11m 3 Ngtoo N3 Ngtoo Proof lim T Again the careful reader will note the fact that if lim C for some positive nite Ngtoo constant C then TN is QGN GN and OGN This is consistent with the statement that TN e GN if and only if both TN e QGN and TN e OGN Those who really like calculus might want to use L Hopital s rule for the limit of a ratio I believe that the rule applied to time complexity TN is properly stated as follows dTN TN 4N 7 rov1ded that 1113mm lgdGNdN p both TX and GX as functions of real variables are differentiable and either 1 both hm TN 00 and 1imGN 00 or Ngt O Ngt O 2 both hm TN 0 and um GN 0 Ngtoo Ngtoo As an example we show that the time function TN logzN is O W The rst thing to do is note that the base of the logarithm does not matter so logzN is lnN and we prove the simpler assertion that TN lnN is O W Note that 1im1nN 00 and lim W 00 so we can apply the rule Ngtoo Ngtoo l i 3 lim LN imlnN lim 7N limLNA umi 0 NgtooGN Ngtoo NM NaoolN Ngtoo N Ngtoo N 4 The use of either calculus or L Hopital s rule is not expected in this class The student will be graded on such methods only if he or she elects to use them It is not anticipated that there will be any problems that require use of the calculus or any of its results Page 8 of 13 Chapter 2 Last Revised On August 25 2004 Mathematical Analysis of Iterative Algorithms For iterative algorithms the answer is just count the loops We begin with a few of the book s examples and then give a few new examples We rst show an algorithm to determine the minimum element of an array of size N As is the C convention we claim that the index values are in the range 0 N 7 1 Note that the algorithm rst sets the trial minimum value to a value known to be in the array It is not a good idea to set the trial minimum value to an arbitrarily large value as this may limit the applicability of the algorithm 7 say the minimum temperature of a set of stars Algorithm MinimumiValue Input A0 to N 7 1 MinVal A0 ForKltoN7lDo If AK lt MinVal Then MinVal Ak End Do Return MinVal The number of loops here is obviously N 7 1 so the complexity of this algorithm is N Look at another algorithm that requires slightly more subtle analysis Algorithm UniqueiElements Input A0 to N 7 1 An array of N elements ForIltoN72DO ForJI lToN7lDO If AI AJ then Return False Return True We want to count the number of comparison operators Note that the number of executions ofthe inner loop is given by N 7 l 7 I N 7 I 7 1 Thus the number ofloops done by the Z N algorithm is given by the sum ZltN I 1 There are two ways to solve this sum I0 1 Note that the term N appears within the sum so that the sum must be Nz or 2 Solve Jim 14 7 NEW 1 7 1 N1N717W N1WWDLN1 2 2 2 The number of loops in this problem is Nz so the algorithm is Nz Page 9 of 13 Chapter 2 Last Revised On August 25 2004 Another Example The following algorithm resembles matrix multiplication but is given only as an example of counting multiple loops What it does is not important for this example Algorithm SillyiExample Input Two arrays X 0 to N 7 1 and Y0 to N 7 1 ForI0toN71 ForJ0toN71 AI J XI YJ BI J XI 7 YJ CI J 0 End Loop End Loop ForI0toN71 ForJ0toN71 ForK0toN71 CI J CI J AI K BK J The number of executions of the basic steps in the first loop is 3oN2 and the number of executions of the basic steps in the second loop is 20N3 The time complexity of this algorithm which must do something is TN 2oN3 3oN2 so TN 6 N3 and the algorithm has cubic time complexity Mathematical Analysis of Recursive Algorithms We first investigate the time complexity of the recursive computation of Fibonacci numbers discuss a number of iterative procedures for computing the numbers and then discuss a general approach to the computation of the time complexity of recursive algorithms Fibonacci numbers introduced by Leonardo Fibonacci in 1202 are de ned by the following recurrence F0 0 F1 1 FN FN71 FN 7 2 for N gt1 The sequence begins as follows 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 etc Consider the time complexity of the recursive algorithm to compute the Nth Fibonacci number FibN If N lt 2 Return N Else Return Fib N 7 1 Fib N 7 2 The time complexity of this algorithm is seen to be given by TN TN 7 1 TN 7 2 so that the time complexity of this algorithm is also a Fibonacci number Page 10 of 13 Chapter 2 Last Revised On August 25 2004 We now present two iterative algorithms to compute the Nth Fibonacci number Note that each algorithm has time complexity TN e N but the first algorithm has space complexity MN e N due to the requirement of an array to hold intermediate values Fib0 0 Fibl 1 For K 2 to N Do FibK FibK 71 FibK 7 2 This algorithm compute and stores the values of each of the first N l Fibonacci numbers Should we desire only the value of the Nth Fibonacci number we can do this without the array thus with memory complexity MN e l Fl 0 Note the three work variables and the way that F2 l two are initialized before the first loop For K 2 to N Do This does not compute Fib0 F0 F1 F1 F2 F2 F0 F1 End Loop Return F2 The Master Theorem We now discuss a general method for determining the time complexity of recursive algorithms The theorem that can be used to determine the time complexity of most recursive algorithms is called the master theorem We begin with a simpler version of the master theorem one we can prove and then move to the general statement Theorem Let TN satisfy the following recurrence equation TN AoTN B T1 C then TN CoNP where P LogBA If C gt 0 then TN e NP Proof We use induction to prove this result Base case T1 C Co 1P for any F We now consider TN for N a power of B eg N BK for K gt 0 TB AOTB B AOTl AoC CoA TBz AoTB2 B AoTB AoCoA CoAz TB3 AoTB3 B AoTB2 AoCoA2 CoA3 We now see a general pattern TBK COAK If this is so then TBK AoTBK B AoTBK391 AoCoAK391 CoAK But A BP where P LogB A so we have TBK CoAK CoBPK CoBKP and infer that TN CoNP IfC 0 then TN 0 If C gt 0 then TN e NP Page 11 of 13 Chapter 2 Last Revised On August 25 2004 General Form of the Master Theorem The general form of the master theorem is found on page 123 of the textbook in chapter 4 and in an appendix at the end of the textbook These notes are taken from Appendix B of the textbook where we nd the Master Theorem on page 427 Theorem Let TN satisfy the following recurrence equation TN AoTN B FN Tl C where A 2 l B 2 l and C gt 0 If FN e Nd where d 2 0 then TN e Nd if A lt Bd TN e NdologN if A Bd TN e NP P LogBA if A gt Bd In order to understand this theorem let s try a few examples Here are three recurrences a TN 4oTN 2 N b TN 4oTN 2 N2 c TN 4oTN 2 N3 TN 4oTN 2 N Here A 4 B 2 and FN N FN e Nd for d 1 Bd 21 2 so A gt 13d and we calculate logBA logz4 2 We conclude that TN e Nz TN 4oTN 2 N2 Here A 4 B 2 and FN N2 FN e Nd for d 2 Bd 22 4 so A 13d and TN e NzologN TN 4oTN 2 N3 Here A 4 B 2 and FN N3 FN e Nd for d 3 Bd 23 8 so A lt 13d and TN 6 N3 The next example for inspection is sufficiently bizarre that one would not expect to see it in actual practice However complex it appears the answer is quite simple TN 4oTN 2 11oN3 23oN2 SoN 57 Here FN lloN3 230N2 SON 57 But FN is still a cubic polynomial so FN e Nd for d 3 and the above analysis still applies TN 6 N3 Page 12 of 13 Chapter 2 Last Revised On August 25 2004 The Knapsack Problem An Introduction to Backtracking Contents of this lecture I k11th A de nition of the Knapsack Problem and its two main variants A de nition of the backtracking design strategy The use of Greedy to solve the continuous knapsack problem The use of Backtracking to solve the 0 l knapsack problem The use of Greedy to get approximate solutions to the 0 l knapsack problem The Knapsack Problem Defined You are given a knapsack of limited capacity W gt 0 You are given a set of N items N gt 1 with weights and values described by arrays Weights W1 wz wN wK gt 00 Values v1 v2 vN vK gt 00 Find the most valuable subset of items that will t into the knapsack There are a few assumed constraints not usually stated 11 l 2 Wk gt W if all the items t into the knapsack the problem is trivial k1 2 WK 3 W for all K 1 S K S N individually every item will t into the knapsack 3 Often the items are ranked by value density that is value divided by weight For 1 SK SN let pK vK wK As vK gt O andwK gt O pK gt O andis de ned Order so that pl 2 pg 2 pN This occasionally facilitates a solution Two Common Variants of the Knapsack Problem Consider a knapsack of capacity W and a set of items de ned by the two arrays Weights W1 wz wN wK gt 00 Values v1 v2 vN vK gt 00 Use another array x1 x2 xN to describe the amount of each item to place into the knapsack There are two common variants of the problem Ol Knapsack Either xk O the item is not placed into the knapsack or xk 1 the entire item is placed into the knapsack Continuous Knapsack 00 xk 10 Put all of the item or any part of it into the Fractional Knapsack knapsack including no part of the item Another characterization Ol Knapsack xk e O l the set containing only 0 and 1 Continuous Knapsack xk e O 1 the closed interval same as 00 xk 10 Backtracking The backtracking strategy is a re nement of the exhaustive search strategy In backtracking solutions to a problem are developed and evaluated one step at a time Each partial solution is evaluated for feasibility A partial solution is said to be feasible if it can be developed by further choices without violating any of the problem s constraints A partial solution is said to be infeasible if there are no legitimate options for any remaining choices The solution of the problem is developed in backtracking as a search tree The abandonment of infeasible partial solutions is called pruning the solution tree In this the strategy differs from simplistic brute force which would generate all solutions even those arising from infeasible partial solutions Example Problem A Five Item Knapsack We are given a knapsack with a capacity of 12 pounds We are given the following ve items to place into the knapsack Item number 1 2 3 4 5 Value 180 160 55 40 20 Weight 60 80 50 40 20 Valuedensity 30 20 11 10 10 The only method guaranteed to produce an optimal solution involves generation of the approximately 2N here 25 32 subsets of the set 1 N One standard method for generating and evaluating these subsets involves a binary search tree Level 0 At the root no allocations have been made Level J At level J a decision has just been made about item J Is it to be placed into the knapsack or not Our Problem The Full Search Tree Here is a sketch of the full sixilevel search tree for this problem Questions Can backtracking prune this tree Do we really have to generate all 32 leaf nodes one for each subset A BFS Approach to Backtracking Lectures on backtracking often generate the tree one level at a time following a breadth first approach in order to illustrate what the algorithm does Actual implementations of the algorithm will follow different strategies Decide on 1 welgh Value 18 Decide on 2 welght 6 No No Yes Value 0 Value 16 Value 18 Value 34 Weight 0 Weight 8 Weight 6 Weight 14 T00 HEAVY The right subtree is pruned from the solution search tree as no solution generated as an extension of this one can possibly satisfy the weight constraint of the problem Our Search Tree Now Here is the full search tree as pruned by the above observation A subtree With 8 leaf nodes and 6 inteIior nodes has been removed from consideration Only the root node of the subtree was considered The 1 0 Subtree Yes on Item 1 and No on Item 2 We have decided on 1 and 2 Yes on 1 and No on 2 Decide on 3 Ws Value 18 Decide on 4 welght 6 V 40 No Yes W 4 Value 18 Value 2 Value 235 Value 275 Weight 6 Weight 10 Weight 11 Weight 15 Decide on 5 V 2 W 2 TOO HEAVY Yes V 20 Yes V 24 Yes V 275 W8 W12 W15 Tooheavy Nu V 18 No V 22 No V 235 W 6 W 10 W 11 The best answer so far Yes on 1 4 and 5 Value 24 and Weight 12 The Rest of the Problem in Subset Form We now consider solutions that do not take item 1 We examine a few subsets 2 W8 V16 23 W85 13 Too heavy This rules out subsets 2 3 2 3 4 2 3 5 and 2 3 4 5 24 W8412 V16420 245 W842 Too heavy 25 W8210 V16218 3 W5 V55 34 W527 V55275 345 W54211V554020115 4 W4 V4 475 W426 V426 5 W2 V2 The optimal solution Yes on 1 4 and 5 Value 24 and Weight 12 The Continuous Knapsack and Its Solution by Greedy In the 01 knapsack problem we must either take all of an item or none of it In the continuous knapsack problem we have the additional option of taking only a part of the item The amount we take is bounded by 00 and 10 0 and 100 It is easy to show that the Greedy solution is optimal Here is a description of the Greedy algorithm for Knapsack 1 Assume a set of N objects ordered by non increasing value density Weights W1 wz wN wK gt 00 Values v1 v2 vN vK gt 00 with pK vK wK We assume that pl 2 pg 2 pK 2 pKH 2 pN 2 Process the items in order taking each as long as it ts in the knapsack 3 When the rst item is found that will not t completely into the knapsack take that part that will t into the knapsack 4 The knapsack is now full and the optimal solution has been produced NOTE It may happen that step 2 terminates with no remaining knapsack capacity In this case the algorithm terminates and step 3 is not executed The Code to Solve the Continuous Knapsack Algorithm FractionalKnapsack Input a set of values and weights as described above Output a set of XK the fraction of item K to include Value the total value placed into the knapsack For K l to N Do XK 00 Initialize the output array Value 00 Capacity W Start with all of the knapsack capacity available and gradually decrease it K 1 While K S N And Capacity gt 00 Do If wk S Capacity Then The item all fits in Value Value Vk Capacity Capacity WK XK 10 Else Fill up the knapsack XK Capacity wk Value Value XKOVK Capacity 00 End If KKl End Do The Five Item Continuous Knapsack We are given a knapsack with a capacity of 12 pounds We are given the following ve items to place into the knapsack Item number 1 2 3 4 5 Value 180 160 55 40 20 Weight 60 80 50 40 20 Value density 30 20 11 10 10 The Greedy solution to the continuous knapsack 1 Take all of item 1 Value 180 Capacity remaining 6 2 Take 6 pounds of item 2 Value 18 602 30 The knapsack is full The answer to the continuous knapsack is X1 10 X2 075 X3 00 X4 00 X5 00 This is often written as avector 10 075 00 00 00 Greedy Produces the Optimal Solution to Fractional Knapsack We assume a set of N items ordered by value density pl 2 pz 2 pK 2 pKH 2 pN Assume that Greedy places item I with p1 in leaves item K with pK out Note pl 2 pK Adjust the Knapsack contents Remove a weight M of item I Add the same weight M of item K Removal changes the value by M 0 p1 Addition changes the value by M o pK Net change is M o pK p1 But pl 2 pK so this is not a positive number So no adjusting of the result of Greedy will increase the total value Greedy produces an optimal result Greedy for the 01 Knapsack Greedy can be modi ed to give a solution to the 01 knapsack problem It can be shown that the Greedy solution is not optimal though it is often good Here is the algorithm as modi ed for the discrete problem 1 Assume a set of N objects ordered by non increasing value density Weights W1 wz wN values v1 v2 vN with pK vK wK We assume that pl 2 pg 2 pK 2 pKH 2 pN 2 Process the items in order while a there are items remaining to be selected and b there is still capacity in the knapsack 3 If the item will t into the knapsack put it in and decrease the capacity remaining 4 When either the knapsack is lled or the list of items runs out the Greedy solution has been produced A Greedy Solution to the Discrete Knapsack We are given a knapsack with a capacity of 12 pounds We are given the following ve items to place into the knapsack Item number 1 2 3 4 5 Value 180 160 55 40 20 Weight 60 80 50 40 20 Valuedensity 30 20 11 10 10 7 1 Takeiteml Value01818 Weight O 6 6 Capacity remaining 6 2 Skip item 2 too big 3 Take item3 Value1855235 Weight 6 5 11 Capacity remaining 1 4 Skip item 4 too big 5 Skip item 5 too big The Greedy solution is x1 1 x2 0 x3 1 x4 0 and x5 0 The Greedy value is 235 which has been shown not to be optimal Use of Greedy t0 Bound the Discrete Knapsack Here we have an instance of the Knapsack problem and three different solutions The solution 1 O O l l with total weight 12 and total value 24 This can be shown to be optimal by exhaustive search A solution produced by Greedy This is l O l O O with weight 11 and value 235 This is a feasible solution that can serve as a lower bound on any optimal solution The solution to the fractional knapsack produced by Greedy This is 10 075 O O O with a total weight 12 and a total value 30 It is easy to prove that the optimal value for an instance of the discrete knapsack can never exceed the optimal value for the corresponding fractional knapsack problem Had we begun our solution of this instance of the discrete knapsack by attempting the two related Greedy solutions we would have discovered the following Whatever the optimal value may be it satis es 235 S VOPT S 30 Can Greedy Help Backtracking Under certain circumstances we can use the preliminary result from Greedy to rule out partial solutions that can never give rise to a solution with suf cient total value We generate a new value for each item the sum of the values of all items following it in the list Consider our example Item number 1 2 3 4 5 Value 180 160 55 40 20 Weight 60 80 50 40 20 Valuedensity 30 20 11 10 10 MaXRemaining 275115 60 20 00 MinimumViable 00 120 175 215 235 For example suppose that we have made a decision on item 3 and have arrived at a value of less than 175 The maXimum value for any solution based on this partial solution will be less that 23 5 the value of a known solution Thus it cannot be optimal and this partial solution can be dropped The New 1 0 Subtree Yes on Item 1 and No on Item 2 We have decided on 1 and 2 Yes on 1 and No on 2 Decide on 3 No Yes Value 18 Value 2 Value 235 Value 275 Weight 6 Weight 10 Weight 11 Weight 15 Decide on 5 TOO HEAVY Not enough Yes V 24 Yes V 275 value W 12 W 15 Too heavy Nu V22 No V235 W 10 W 11 Here We have been able to pnme one more subtree albeit a small one The New 0 Subtree No on Item 1 We have decided No on item 1 Decide on 2 W8 Not enough value Not enough TOO HEAVY va ue Computational Complexity An Overview Ed Bosworth Computer Science Department Columbus State University Columbus GA bosworthedwardcolstateedu August 2008 BACKGROUND ASSUMED Some programming experience maybe in Visual Basic Java C C or C Have seen some algorithms for searching and sorting Algebra including logarithms and exponents Factorial function N N 0 N 1 0 2 0 1 Overview Problems Strategies Algorithms amp Programs Time Complexity Classes P NP NPComplete Provably Intraetable Unsolvable Problems Strategies and Algorithms Problem Sort a list by comparison using a defined 2 operator Traveling salesman Strategy Divide and conquer Algorithm Bubble Sort Quick Sort Merge Sort etc Breadth first search depth first search etc Programs Implementation of an algorithm in a specific language Intractable Problems Characteristic Try every solution and see if one works Even modestly sized problems might take about one hundred years to solve on a supercomputer such as the Cray XT S Classic problem Tiling a floor with irregularly shaped tiles Like a jigsaw puzzle if you do it upsidedown except you know that the puzzle can be completed Heuristics For jigsaw puzzles you use a number of clues such as colors to aid in putting the puzzle together Heuristics do not guarantee an answer but often produce one Unsolvable Problems Some problems are provably unsolvable while other problems have no known solution This is different Classic unsolvable problem the Halting Problem It is provable that no solution exists Classic problem with no known solution Is P NP Be patient I shall define this one This is a decision problem Answer Yes or No Three possible answers can you prove one of them Yes No The problem is unsolvable Time Complexity of Algorithms Question How to make the program run faster Answers Buy a bigger computer Your boss has lots of money Implement in a more efficient computer language Devise a more efficient algorithm We focus on developing a more efficient algorithm Efficiency is measured in time complexity Which is different from total run time Run time is dependent on the computer This allows us to assess the algorithm independently of the computer and programming language implementation Time Complexity Number of Steps Identify the number of basic operations For searching and sorting this is the number of key comparisons How does this number depend on the size of the problem Size of the problem Sorting the number of items to be sorted Traveling salesman the number of cities to be Visited Factoring integers the number of digits We want to characterize the number of basic operations as a function of the size of the problem Bounds on Functions The BigO and Big2 notation for positive functions fn gt 0 fn is Ogn if there exist positive integers K and N such that for all n 2 N fn S K0gn fn is Qgn if there exist positive integers K and N such that for all n 2 N fn 2 K0gn Typical functions for gn logarithmic lnn log10n etc polynomial n2 n3 etc nologn is polynomial exponential 2 e n etc This course assumes that you are comfortable With the use of these functions CLAIM The Number 100 Is Astronomical Let39s put a lower bound on the value of 100 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 Note The square root of 10 is about 31623 Thus 9 gt 10 5105 105395 100 100999089a8079397069 I2019I11109 1 0 1 0 1 0 1 0 numbers numbers numbers numbers gt 9 gt 80 gt70 gt10 FACT 100 Is Bigger Than Astronomical 100 gt 100 o 9010 o 8010 o 7010 o 2010 o 1010 o 9 gt 100 o 9101010 o 8101010 7101010 o 2101010 o 1101010 o 9 We have 9 occurrences of 1010 so we group the numbers to get 100 gt 100 o 910 o 81quot o 710 o 210 o 110 1090 o 9 gt 100 o 910 1090 o 9 911 1092 gt 105511 1092 10605 1092 101525 gt 310152 There are only 1078 elementary particles in the known universe Scientific American March 2003 page 53 Examples of Function Bounds log10n is On because for n gt 1 log10n S n log10n and lnn are the same order because log10n log10e o lnn n2 nologn is Onz because For n gt 1 n2 nologn S 20n2 or Lim n a w n2 nologn n2 1 if you like calculus Big issue polynomial vs exponential Time Complexity of an Algorithm An algorithm A is said to be Ofn if the input size is a positive integer n the number of basic steps is Tn Tn is Ofn Bubble sort is Onz Quick sort is Onologn also Onz Both are polynomial Time Complexity Algorithms vs Problems Upper Bound Problem X is Ofn Let problem X be solved by algorithms A1 A2 An The time complexity of X is not greater than the minimum of the time complexities of A1 A2 An Thus we say that the problem of sorting by comparison is Onologn because there exists an Onologn algorithm to sort Big picture Sorting by comparison has polynomial time complexity Time Complexity Algorithms vs Problems Lower Bound Problem X is Qfn Let problem X be solved by algorithms A1 A2 An The time complexity of X is not greater than the minimum of the time complexities of A1 A2 An The lower bound for a problem must be established theoretically not just by comparing every algorithm known to solve it Sorting by comparisons only has been proven to be Qnologn Example Lower Bound for Matrix Addition and Multiplication Consider three square matrices N by N A B C Where C is either the sum or product of matrices A and B The basic structure for setting values for array C must be i lt n i for int i 0 for int j 0 j lt n j cij something It takes 112 steps to fill the n by n array so both the addition and multiplication problems are 9n2 Consider Matrix Addition The standard algorithm for C A B can be expressed as for int i 0 i lt n i for int j 0 j lt n j The following step is executed n2 times CH 2 ai j bi 2 This known algorithm takes 0n2 steps The problem is 9n2 so any algorithm must take 0n2 steps The matrix addition problem is well understood Consider Matrix Multiplication The standard algorithm for C A B can be expressed as for int i 0 i lt n i for int j 0 j lt 11 j The following step is executed n2times Ci j 0 for int k 0 k lt n k This step is executed n3 times Cij aik bkj C i j The number of steps is n3 n2 Which is 0n3 But the problem is 9n2 so matrix multiplication theoretically is an open problem Two known multiplication algorithms are 0n239807 and 0n239376 Neither algorithm is of much practical use Example Towers of Hanoi Published by the French mathematician Edouard Lucas in 1883 Question How many steps to move N disks Peg 1 Peg 2 Peg 3 RULES Move all disks from peg 1 t0 peg 2 Move one disk at a time Do not place a larger disk on top ofa smaller disk Recursive Solution to Towers of Hanoi To move N disks from peg 1 t0 peg 2 1 Move N 1 disks from peg 1 t0 peg 3 2 Move the big disk from peg 1 t0 peg 2 3 Move N 1 disks from peg 3 t0 peg 2 N 6 Let TN be the number ofsteps to move N disks The recurrence equation for TN is Tl 1 TN 2TN 11 It can be shown that the solution is TN 2N 1 Counting vs Enumeration At this point we make an important distinction between counting problems and enumeration problems By definition enumeration problems are almost always intractable counting problems may be Consider the problem of the permutations of the finite subset of integers denoted by 1 2 N say 1 2 3 4 There are exactly N distinct permutations of this set The value N may be determined by N 1 multiplications the problem is ON The enumeration problem calls for listing each permutation As each of the N answers must be listed the problem is ON By definition that is an intractable problem 4 241234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 Decision Problems A decision problem is one that has a Yes No answer ie is this list of numbers sorted An algorithm to verify that a list of numbers is sorted Will require at most 11 1 key comparisons Decision problems are associated With optimization problems For the travelling salesman problem to be defined later Optimization What is the length of the shorted tour Decision Does there exist a tour of length less than Y The Problem Class P A decision problem X is in the class P if and only if there exists a polynomial time complexity algorithm that solves it Put another way the problem X is 0nk k 2 1 Informally problems such as searching and sorting are said to be in P because there exist polynomial time algorithms to solve them Example Problem Travelling Salesman Nashville Knoxville Augusta Atlanta Birmingham Optimization What is the length 0fthe shortest tour starting at a city visiting each city once amp returning to the start Decision Does there exist such a tour with length lt 1000 miles Notes on the Solution One can pick the starting city arbitrarily There are N 1 possible routes to be considered The only algorithms known to solve TSP have exponential time complexity The decision problem can be verified in On time I give you a route and a claim it is less that 1000 miles You just add the length of the n legs of the route to produce the sum However algorithms exist that frequently solve in polynomial time polynomial time algorithms exist if we are dealing with plane geometry one will accept an answer S 150 of optimal The Problem Class NP A decision problem X is in the set NP if and only if it is solvable by a nondeterministic algorithm of polynomial time complexity Nondeterministic algorithms do not exist they are a theoretical abstraction Think of them as magic balls or oracles For TSP the magic ball always correctly indicates the next city in the route in polynomial time Without any need for calculations such as the standard search algorithms require The Problem Class NP Verifying the Answer A key feature of the class NP is polynomial time verifiability A claim that a TSP tour of M cities has length less than Y can be verified in M calculations Optimization problems are not in the class NP for the reason that a claimed answer the least total length is Y can be verified only be an almost complete enumeration of the M 1 possible tours The class NP Hard holds those hard problems that are as difficult to solve as any in the class NP Complexity Classes Approximately described Class Lower Limit Upper Limit P Polynomial Polynomial NP Polynomial Exponential Intractable Exponential Exponential or worse Undecidable NA NA Note Efficient polynomial time algorithms might exist for NP Hard problems but this is thought to be unlikely It cannot be proven that such algorithms do not exist It is provable that there can be no efficient algorithm Will ever solve an intractable problem The Problem Class NP Complete The problem class NP Complete is a subset of the class NP Hard if a problem is NP Complete it is also NP Hard There is a set of more than 1000 problems with an interesting property stated two ways An efficient polynomial time solution to any problem in the class implies an efficient solution to all problems in the class If any problem in the class can be proven to be intractable then all problems in the class are proven to be intractable TSP Decision Version is NP Complete The Big Question Is P NP From the fact that polynomial time solutions exist for problems in P it follows that P NP Question Is P C NP or P NP Nobody seriously believes that P NP In 40 years nobody has offered a convincing proof that PCNR An efficient solution for any NP Complete problem would immediately imply that P NP A proof that any NP Complete problem is intractable would immediately show that all such problems are intractable and that P c NP Graph Search Strategies Many 39 39 wmputei i ii an quot L the vertices ofwhich are searched systematically until adesired answer is found BreadthrFirst Search BFS and DepthrFirst Search DFS are two common and very important search strategies Each ofBFS and DFS can be applied to a general graph connected or unconnected Each ofBFS and DFS can be applied to a directed graph or an undirected graph 39 39 39 eaihofthese earch 39 A 39 ofthegraphbut the data structure that is used to represent the graph Here is a drawing ofthe graph that we shall consider in these lectures The Adjacency Matrix for the Sample Graph Here is the adjacency matrix for the sample graph Cells not containing a 1 are assumed to contain a 0 indicating that the edge is not in the graph A B C D E F G H I l l l l l A B C D E F G H I I Here is the adjacency list representation A gtCDE D gtA C G gtHJ I gtHJ B gtE3F E gtA3B3F H gtGI J gtGI C gtADF F gtBCE General Observations on Graph Search Graph searches can begin at any vertex in me graph Teaching examples generally begin atvertex A or vertex just to be simple i in any given time When viewing me depiction ofme graph we see me entire structure quot 39 u nln n39 nm sees 39 39 39 39 39 If quot 39 39 5 all l a forest 39 A ofo mime at Lhatpoint is quite small Here ms 39ning vertex A all malls semis chat vertex and d1 dune Venice Whe to which in adjacent Auxiliary Data Structures Each of the two search algorithms uses two auxiliary data structures in order to manage the search and to retrieve the search tree or trees induced on the graph Each of these data structures is an array indexed by the vertex labels Here is the way that we shall depict these two arrays for our sample problem Vertex A B C D E F G H I J Mark O O O O O O O O 0 Back 0 O O O O O O O O 0 Each of the arrays will be initialized to 0 before the search begins O The mark array exists in order to mark each vertex that has been visited As such it would suf ce to use the values 0 not visited and I visited We shall nd it very convenient to mark each vertex with a positive integer that indicates the order in which the vertex is visited The back array is not necessary or always used When used it indicates the parent node of any given vertex in the search tree or trees induced by the search algorithm More on the Auxiliary Data Structures Consider a search of our sample graph that begins at vertex A and recall that the adjacency list for that vertex is A gt C D E Each of the two search algorithms will begin at vertex A and move to vertex C as that vertex is the rst in the adjacency list 7 Vertex A B C D E F G H Mark 1 O 2 O O O O 0 Back 0 O A O O O O O O 0 Here we see that MarkA l as that is the rst vertex visited D l H O O BackA O as that vertex is the root of a search tree MarkC 2 as that vertex is the second vertex visited BackC A as the search tree moves from A to C NOTE The textbook does not use the Back array I nd it very useful REMEMBER By arbitrary convention each adjacency list is an ordered list stored in increasing order and processed in that order General Structure of the Search Procedures Each of the two search algorithms is presented as a pair of procedures For breadth rst search we shall have BFS and bfs For depth rst search we shall have DFS and dfs The rst procedure in each pair is a helper procedure It initializes the auxiliary data structures initializes a counter and then calls the traversal procedure This split of procedures allows for much cleaner code in the traversal procedure There is another major difference The helper procedure is applied to the entire graph DFSG The traversal procedure is applied to an individual vertex dfsv We begin with DFS Depth First Search in which the traversal procedure is recursive Depth First Search Here is the helper procedure DFS It is applied to the entire graph Algorithm DFS G DFS on a graph G V E The graph G may be connected or unconnected This operates by marking each vertex This uses two arrays Mark and Back count 0 Used to mark the order of search For each vertex v E V Do The primary purpose of helper Markv 0 procedure DFS is to initialize Backv 0 these arrays and call dfs End For For each vertex v E VG Do If 0 Markv then Vertex v is in a new component not connected to any vertex already visited by algorithm dfs dfsv End If End Do NOTE I never bother to declare my arrays This must be done for a real program DFS Traversal Algorithm Here is the graph traversal algorithm Note that it is recursive Algorithm dfsV V is a vertex in the graph G count count l This is a global variable MarkV count used to denote the search order We now search the adjacency list of V for vertices that have yet to be visited For each vertex w in V adjacent to V Do If 0 Markw Then Backw V Remember where we came from In dfsw the search tree V is a parent of w End If End Do End dfs NOTE The three global variables used here Many software engineers dislike this use of global variables Sample Problem for Depth First Search Here again is me sample graph nae will be traversed Here are me adjacency lists used to leplesene ans graph AgtCDE DgtAC GgtHI IgtHI Beamquot EamsBsF HGVI 1 370 CADF Fa icaE NOTE wlcln a vertex called G and one called H we cannot use eitherletter as a name on me graph So it is just an anonymous graph Call the Helper Procedure DFS The helper initializes the global data structures as follows count O Vertex A B C D E F G H I J Mark O O O O O O O 0 Back 0 O O O O O O O O O O O The vertex list for the graph is V A B C D E F G H I J Following the implicit order rule we shall begin with a call to dfsA After the call to the traversal procedure has been completed the helper procedure will search for the next unmarked vertex As we shall see it will be vertex G Put another way the graph is disconnected having two connected components The traversal procedure is called once for each of the two components The result of this call to DFS will be a forest of two trees each a spanning tree for one of the two connected components of the graph Call dfsA count count 1 Markv count This increments the variable count to l and marks the vertex A as the rst visited The total count of visited vertices is 1 just A Vertex A B C D E F G H I J Mark 1 O O O O O O O O 0 Back 0 O O O O O O O O O At this point the Back array is not assigned a value For each vertex w in V adjacent to V Do If Markw Then Backw V dfsw End If End Do One might be tempted to set Markw here and skip the marking step at the beginning of the dfs traversal procedure That would leave vertex A unmarked First Recursive Call from dfsA The adjacency list for vertex A is c D E uiw ucu A F 111 algoxichm marks it and makes d1 recursive call Vertex A B CID E F GIHII J Mark l 00000000 Back00A0000000 We are beginning to build the Search tree Call dfsC count count 1 Markv count These increment the variable count to 2 and mark the vertex C with its visit order Note that the strict requirement for DFS is that each vertex visited by marked with a value that is not zero This will prevent the algorithm from looping endlessly We choose to store the search order because that number is easily generated and carries additional information that might be useful in a number of applications Vertex A B C D E F G H I J Mark 1 O 2 O O O O O O 0 Back 0 O A O O O O O O 0 It is at this point that a manual procedure must start tracking the recursive call stack a task handled by the Run Time System of any language supporting recursion Here is the stack so far Stack gt A gt C DFS has called dfsA which called dfsC The adjacency list for C is A D F Vertex A has been marked so the next vertex to be visited in DFS is vertex D The algorithm sets BackD C and calls dfsD Call dfsD The state of the recursion at this point is given by the stack Stack gt A gt C gt D Vertex D is now marked with its traversal order The auxiliary arrays are now Vertex A B C D E F G H I J Mark 1 O 2 3 O O O O O 0 Back 0 O A C O O O O O O The adjacency list for vertex D is A C each of which has been visited and marked We are now in a position to de ne two terms seen in searches tree edge amp back edge A tree edge is discovered when moving from a new unvisited vertex from a vertex that has just been visited The edge is a directed edge from the recently visited vertex to the newly visited vertex In the example above A C is a tree edge as is C D A back edge is an edge from a vertex to an ancestor node in the search tree Usually this does not include the parent node So the edge D A is a back edge Note that we infer the existence of edges from the adjacency list of a vertex The adjacency list for D is A C so the graph has edges D A and D C Vertex D has no unmarked adjacent vertices so dfsD returns with no further calls Back to dfsC The return from the recursive call pops D from the stack so Stack gt A gt C Again the adjacency list for vertex C is A D F We are executing the loop For each vertex w in V adjacent to V Do If 0 Markw Then Backw V dfsw End If End Do The loop has examined vertices A and D It now examines vertex F which is found to be unmarked The Back vertex for vertex F is set and dfs is called The situation just before the call to dfsF is as follows D E F G H I J 3 O O C O C O O O O Vertex A B Mark 1 0 Back 0 O O O O O gtNO Call dfsF The state of the recursion at this point is given by the stack Stack gt A gt C gt F Vertex F is now marked with its traversal order The auxiliary arrays are now Vertex A B C D E F G H I J Mark 1 O 2 3 O 4 O O O 0 Back 0 O A C O C O O O O The adjacency list for vertex F is B C E Vertex B has not been marked so it is the next to be visited Recall that for teaching purposes each adjacency list is viewed as ordered by a standard sort in increasing order There are no duplicates in the list The back vertex for vertex B is now set Vertex A B C D E F G H I J Mark 1 O 2 3 O 4 O O O 0 Back 0 F A C O C O O O O The procedure is called recursively for vertex B Call dfsB The state of the recursion at this point Stack gt A gt C gt F gt B Vertex B is now marked with its traversal order The auxiliary arrays are now Vertex A B C D E F G H I J Mark 1 5 2 3 O 4 O O O 0 Back 0 F A C O C O O O O The adjacency list for vertex B is E F Vertex E has not been marked so it is visited next The Back vertex for vertex E is set Vertex A B C D E F G H I J Mark 1 5 2 3 O 4 O O O 0 Back 0 F A C B C O O O O Call dfsE The state of the recursion at this point Stack gt A gt C gt F gt B gt E Vertex E is now marked with its traversal order The auxiliary arrays are now Vertex A B C D E F G H I J Mark 1 5 2 3 6 4 O O O 0 Back 0 F A C B C O O O O The adjacency list for vertex E is A B F Each of these vertices has been visited and marked The procedure returns with no more recursive calls We now use the call stack to determine the next step in our solution Back to dfsB The state of the recursion at this point Stack gt A gt C gt F gt B The auxiliary arrays are as they were on exiting the call for vertex E Vertex A B C D E F G H I J Mark 1 5 2 3 6 4 O O 0 Back 0 F A C B C O O O 0 Again the adjacency list for vertex B is E F We are executing the loop O For each vertex w in V adjacent to V Do If 0 Markw Then Backw V dfsw End If End Do On entry to dfsB vertex E had been unmarked It was then visited by a call to dfsE and marked The loop now examines vertex F which has been marked With no more vertices in the adjacency list for B dfsB exits Back to dfsF The state of the recursion at this point Stack gt A gt C gt F The auxiliary arrays are as they were on exiting the call for vertex E Vertex A B C D E F G H I J Mark 1 5 2 3 6 4 O O O 0 Back 0 F A C B C O O O O The adjacency list for vertex F is B C E We have returned from a call to dfsB and now proceed with the loop over the adjacency list For each vertex w in V adjacent to V Do If 0 Markw Then Backw V dfsw End If End Do Having called dfsB we note that each of vertices C and E has been marked The call to dfsF returns with no further recursive calls Back to dfsC The state of the recursion at this point Stack gt A gt C The auxiliary arrays are as they were on exiting the call for vertex E Vertex A B C D E F G H I J Mark 1 5 2 3 6 4 O O O 0 Back 0 F A C B C O O O 0 Again the adjacency list for vertex C is A D F Each of vertices A D and F has been examined in the loop structure Vertex A had been visited prior to vertex C Each of vertices D and F have been visited from vertex C There are no more vertices in the adjacency list of vertex C The procedure returns with no more recursive calls Back to dfsA The state of the recursion at this point Stack gt A The auxiliary arrays are as they were on exiting the call for vertex E Vertex A B C D E F G H I J Mark 1 5 2 3 6 4 O O O 0 Back 0 F A C B C O O O O The adjacency list for vertex A is C D E We have returned from a call to dfsC and now proceed with the loop over the adjacency list For each vertex w in V adjacent to V Do If Markw Then Backw V dfsw End If End Do By now vertices D and E have been marked so the loop terminates after nding no additional vertices to visit The traversal procedure returns with no further recursive calls Back to DFS The auxiliary arrays are as they were on exiting the call for vertex E Vertex A B C D E F G H I J Mark 1 5 2 3 6 4 O O O 0 Back 0 F A C B C O O O O The procedure DFS continues its execution of the following loop For each vertex v E VG Do If 0 Markv then Vertex v is in a new component not connected to any vertex already Visited by algorithm dfs dfsv End If End Do So far there has been only one invocation of dfs from DFS This has been dfsA The procedure continues the loop through the array looking for the condition 0 Mark v The next unmarked vertex is G DFS continues with a call to dfsG Call dfsG The condition of the recursive stack is now Stack gt G The adjacency list for vertex G is H J The procedure will mark vertex G with a 7 and call dfsH The student is invited to show that the search here proceeds from G to H to I to J and yields the following auxiliary data structures Vertex A B C D E F G H I J Mark 1 5 2 3 6 4 7 8 9 l 0 Back 0 F A C B C O G H I We now use the Back array to retrieve the two search trees The precise algorithm is only slightly tricky but I here use an intuitive method Beginning at vertex I we read backwards I lt I lt H lt G Reading backwards from E we get E lt B lt F lt C lt A This leaves only vertex D to be connected D lt C Noting that the last two partial trees share a node in common we merge them Slide 1 of6 pages Algorithm De nition An algorithm is a nite set of instructions Which if followed Will accomplish a particular task In addition every algorithm must satisfy the following criteria i input there are zero or more quantities Which are externally supplied ii output at least one quantity is produced iii de niteness each instruction must be clear and unambiguous iv niteness if we trace out the instructions of the algorithm then for all valid cases the algorithm Will terminate after a nite number of steps v effectiveness every instruction must be suf ciently basic that it can in principle be carried out by a person using only a pencil and paper It is not enough that each operation be de nite as in iii but it must be feasible Hor7 6 Slide 2 of6 pages Algorithmic Effectiveness Note the above requirement that an algorithm in principle be carried out by a person using only a pencil and paper This limits the operations that are allowable in a pure algorithm The basic list is addition and subtraction multiplication and division and the operations immediately derived from these One might argue for expansion of this list to include a few other operations that can be done by pencil and paper I know an easy algorithm for taking the square root of integers and can do that with a pencil on paper However this algorithm will produce an exact answer for only those integers that are the square of other integers their square root must be an integer Operations such as the trigonometric functions are not basic operations These can appear in algorithms only to the extent that they are understood to represent a sequence of basic operations that can be well de ned Slide 3 of6 pages More on Effectiveness Valid Examples Sort an array in non increasing order Note The step does not need to correspond to a single instruction Find the square root of a given real number to a speci c precision Invalid Examples Find four integers A 2 0 B 2 0 C 2 0 and N 2 3 such that AN BN CN This is generally thought to be impossible Find the exact square root of an arbitrary real number The square root of 40 is exactly 20 The square root of 70 is some number between 2645 751311064 590 and 2645 751311064 591 Later we shall consider methods to terminate an algorithm based on a known bound on the precision of the answer Slide 4 of6 pages Heuristics vs Algorithms Computer Science De nition A heuristic is a procedure similar to an algorithm that often produces a correct answer but is not guaranteed to produce anything Operations Research De nition Problems are usually optimization problems either maximize pro ts and minimize costs An algorithm is de ned in the sense of computer science previous slide with the additional requirement that it always produces an optimal answer A heuristic is a procedure that often produces an optimal answer but cannot be proven to do so NOTE Both algorithms and heuristics can contain high level statements that cannot be implemented directly in common programming languages 6 g sort the array low to high Slide 5 of6 pages Euclid s Algorithm Compute the greatest common divisor of two non negative integers For two integers K 2 0 and N 2 O we say that K divides N equivalently N is a multiple of K if N is an integral multiple of K N KoL This property is denoted K N which is read as K divides N The greatest common divisor of two integers M 2 0 and N 2 O denoted gcdM N is de ned as follows 1 gcdM 0 gcdO M M 2 gcdM N K such that a K M b K N c K is the largest integer with this property Euclid s Algorithm gcdM N gcd N M mod N Floyd s Algorithm Floyd s Algorithm is applied to solving the all pairs shortest paths problem in graphs both directed and undirected It can be used to determine the shortest path from one speci c vertex to all other vertices However there are algorithms that are more ef cient for that limited problem Floyd s Algorithm is normally applied to weighted graphs but can be extended to unweighted graphs simply by assigning a weight of l to each edge Floyd s algorithm starts with the adjacency matrix for the weighted graph In the weighted graph AI J W I J the weight assigned to edge I J Question What weight to assign to edges that do not exist We return to this a bit later Floyd s Algorithm is quite similar to Warshall s Algorithm and uses the same basic strategy to generate the answers Because of the similarity the two algorithms are almost always discussed in sequence Warshall s Algorithm is rst then Floyd s Algorithm Sample Graph for Discussion Here is a sample graph It is based on the one in the textbook The adjacency matrix for this graph might be represented as follows This representation will not work for minimization problems Algorithms for these problems need to avoid use of edges that are not there In this representation it appears that each ofedge 2 4 and 4 2 exist and have weight 0 Avoiding Edges That Do Not Exist In the above representation many nonexistent edges will be selected because they seem to have zero weight There are three strategies to focus an algorithm on real edges 1 Use the adjacency list representation 3 I I III 4 I HI 2 Use aBoolean adjacency matrix in addition to the matrix of edge weights 3 Represent nonexistent edges as edges of extremely large weight Ourtext suggests using in nity no for such weights The adjacency matrix would be The Trouble With 00 The value 00 works well for hand solutions as we all know it is larger than any weight that can be assigned to an edge that really exists in the graph The dif culty comes in representing 00 as a value in the computer Most real number systems may have dif culty doing computations with the pseudo value The basic idea behind in nite weight edges is valid represent nonexistent edges as existing with such large weights that a minimization algorithm will never use them My solution is based on the sum of the weights of edges that do exist in the graph Consider again the rst adjacency matrix Vertex l 2 3 4 1 O O 3 O 2 2 O O O 3 O 7 O 1 4 6 O O O The sum of the weights for existent edges is 19 No real path through this graph can have a total weight more than 19 Double the sum of the edge weights and pick a value larger than that I use 40 My Adjacency Matrix Here is the version of the adjacency matrix that I favor Note that the diagonal values of 0 will not cause any dif culty The distance from a vertex to itself is O and will remain so throughout the computation Vertex l 2 3 4 1 O 40 3 4O 2 2 O 40 4O 3 4O 7 O 1 4 6 4O 4O Floyd s algorithm is a minimization algorithm We have selected the value 40 with some care so that no distance through existing edges will ever be 40 or greater Given that constraint Floyd s algorithm will never replace a nonexistent edge with a supposed path containing a nonexistent edge A Constraint on Floyd s Algorithm Floyd s Algorithm cannot correctly be applied to any graph that contains a cycle of negative total Weight Consider the result of a cycle With negative total Weight Paths from A to D Direct path Weight 3 1 4 Onecycle Weight3782311 TWocycles Weight37823782317 N CyclesWeight 4 7 3oN There is no bounded path ofleast Weight Personally I nd negative edge Weights not to be useful in describing graphs Absent negative edge Weights We have no problem With negative cycles Basic Structure of Floyd s Algorithm Floyd s Algorithm begins with the adjacency matrix adjusted to show weights We now call this matrix W For our problem we have the following 640400 As in Warshall s Algorithm we generate a sequence ofN 1 matrices to 1 1 K N Du v DIJ DIJquotquot Dmi quot L The initial de nition is as follows 0 D1 Wu K Du is the distance ofthe shortest path I gt J involving no vertices numbered above K Basic Strategy of Floyd s Algorithm The first observation is that K K71 DM 5 DLJ This arrives from the observation that Floyd s Algorithm is based on minimization so that consideration ofnew paths will not drive up the total distance 4 L isthatwe can r L quot L vertex I K 7 1 39 39 K to the calculation and examine the following two paths from vertex I to vertex J at set Given quot D K iid xer Ital Eachlmth InvnlvEs nnly vemces m the set 1 K r 1 vaertex K offers a short cut it becomes part ofthe path Code for Floyd s Algorithm Here is the code For I l to N Do For J 1 to N Do DI J WI J End Do J End Do I DK J X DI K J Then DI If X lt DI End Do J End Do I End Do K J X An Observation for Manual Calculation The key step in the calculation is DltKgtI J min DltK391gt1 J DltK391gt1 K DltK391gtK J If I J then DK391I J 0 We shall never decrease this value If I K then the equation becomes DKK J min DK391K J DK391K K DK391K J which becomes DltKgtK J min DltK391gtK J 0 DltK391gtK J DltK391gtK J If J K then the equation becomes DltKgtI K min DltK391gt1 K DltK391gt1 K DltK391gtK K which becomes DltKgtI K min DltK391gt1 K DltK391gt1 K o DltK391gt1 K For this reason we may ignore the following in our example 1 I 2 I 3 J Step 1 Start the Computation 040340 6 40 40 0 The key step D 1 J min Dawn J Dawn K DG quotgtK J K1113kipasl1lt K112 J1 SkipasJK J3 D2340 D21D13235 D235 J4 D2440 D21D1424042 D2440 K113 J1 SkipasJK J2 D327 D31D12404080D237 J4 D341 D31D14404080D241 K114 J1 SkipasJK J2 D4240 D41D1264046 D4240 J3 D4340 D41D13639 D439 Step 2 K 2 0403 K2D20540 407 0 6409 0 The key step D 1 J min Dawn J Dawn K DG quotgtK J K211J2 SkipasJK J3 D133 D12D234o545 D233 J4 D1440 D12D24404080D2440 K212 SkipasIK K213 J1 D3140 D32D21729 D219 J2 SkipasJK J4 D341 D32D2474047 D241 K214 J1 D416 D42D214o242 D416 J2 SkipasJK J3 D439 D42D234o545 D439 Step 3 K 3 3 K3 D 2 0 5 40 0 6 40 9 0 The key step D I J min DG quotI J Dawn K DG gtK J J 2 D1240 D13D323710 D1210 J3 SkipasJK J 4 D1440 D13D34314 D144 K312 J1 D212 D23D315914 D212 J3 SkipasJK J4 D2440 D23D34516 D246 K3133kipas11lt K314 J1 D416 D43D319918 D416 J2 D4240 D43D329716 D4216 J3 SkipasJK Step 4 K 4 01034 K4D2056 9701 61690 The key step 0 J min Dawn J Dawn K DG quotgtK J K411 J2 D1210 D14D4241620 D1210 J3 D133 D14D434913 D133 J4 SkipasJK K412 J1 D212 D24D416612 D212 J3 D235 D24D436915 D235 J4 SkipasJK K413J1D319 D34D41167 D317 J2 D3216 D34D4211617 D3216 J4 SkipasJK K4I4 SkipasIK CONTEXT FOR HASHING Hashing was developed in the 1950 s by researchers at IBM This research was in support of efforts to develop an efficient compiler for high level languages such as FORTRAN All modern compilers including these early ones use multiple passes of the source code The first pass generates the symbol table which includes a description of every variable used in the program The goal of the research was to produce a data structure for the symbol table that could be searched efficiently and implemented with little overhead Consider a collection of N symbols where commonly 100 S N S 1000 Storing the collection in an unordered linked list would yield a search time in N Storing the collection in an ordered linked list would yield a search time in logN Storing the collection in a properly indexed array would yield a search time in l that is the search time would be constant for any number of elements The question now becomes one of indeXing the array for ef cient search Variable Names in FORTRAN IV The constraint in early FORTRAN was that a variable name could contain 6 characters 1 All characters were either upper case letters or digits 2 The rst character must be an upper case letter 3 Embedded spaces were not legal but would usually be ignored by the compiler The size of the valid name space for FORTRAN variables is easily enumerated One character names 26 26 Two character names 26036 936 Three character names 260362 33936 Four character names 26363 1213056 Five character names 26364 43670016 Six character names 260365 1572120576 Total 1617038546 Of this space fewer than one entry in a million would be used by a typical program How does one insert names from such a large space into a reasonably sized array ALGORITHJVI FOR HASHING The procedure to create the array indices was called hashing Hashing distributes a large number of keys into an array Hash Table H O M 1 Assume K KOKI Ks1 A string with length S Keys are alphabetic ord KJ gt Integer Algorithm Hash K h O ForIOtoS lDo hhoCordK1modM End Do C and M are most commonly prime numbers Return h End Algorithm Because of the use of modulo M arithmetic hashing must have O based arrays A good hashing function will appear to distribute the keys to slots in the hash table almost randomly appearing to have a uniform distribution NOTE The precise encoding scheme is not important What matters is that each character in the string to be hashed has a unique integer representation that will identify it Example of Hashing M151 C301 REORDE The word has seven characters S 1 6 IO c R h0030182mod151 82mod151 82 I1 c E h82030169mod 151 24571 mod 151 138 I2 c O h138030179mod151 41617mod151 92 I3 c R h92030182mod151 27774mod151 141 I4 c D h141030168mod151 42509mod151 78 I5 c E h78030169mod151 23547mod151 142 I6 c R h142030182mod151 42824mod151 91 By this calculation we have h REORDER 91 Set H91 REORDE if H91 is not occupied Collision K1 7 quot K2 but Suppose K1 REORDER with hK1 91 K2 ALPHABET with hK2 91 Try to insert K2 into H91 but that slot is occupied We have a collision The Book s Hash Example A FOOL AND HIS MONEY ARE SOON PARTED Let hK be as defined in the textbook hA 1 hARE 11 0 1 hFOOL 9 hSOON 11 1 hAND 6 hPARTED 12 2 1 hHIS 10 3 o hMONEY 7 4 T 5 7 OPEN HASHING 6 i H 0 M 71 is an array ofheader 7 n nodes for linked lists 8 1 Here wehaveM13andH0 12 12 Remember that the array must be 11 t n n Oibased 12 gtPAPTED As always the value part of the node could contain other data Search Efficiency of Open Hashing N words in M slots Load factor OL N M We prefer 0L z 1 Number of probes for locating a key Successful S l 0L 2 Unsuccessful U 0L Duplicate Keys are not stored Start h hK Insertion ListhInsert Insert the item into the linked list rooted at the hash table entry Question Does one want to maintain the list in some sort of order Deletion ListhDelete Either delete the item from the list using standard linked list techniques or apply Lazy deletion mark as deleted Closed hashing one item per array entry N words in M slots Load factor or N M We require that or lt 10 and prefer that or lt 05 Handle collision by computing a new index for the colliding key Consider two keys K1 and K2 with K2 7 K1 Let h1 hK1 Assume Hhl is empty The algorithm places K1 into Hhl Try to place K2 by computing hK2 and nd hK2 hK2 h Closed hashing is rst come rst served so the key K2 cannot be placed in the slot already occupied by K1 K2 must be placed elsewhere There are two main strategies for placing the colliding key These can work only if or lt 10 and will be quite slow if or 2 075 approximately Linear Probing Let h h and repeatedly try h h 1 Mod M until Hh is empty Double Hashing Use a second hash function sK Initialize h h Compute h h sK mod M until Hh is empty Insertion and Deletion in Closed Hashing Insertion 1 If ct 10 raise an exception 2 Compute h hK 3 If Hh is blank then set Hh K and set HhDe1eted FALSE 4 If Hh K then set HhDe1eted FALSE 5 If Hh 2 K and Hh is not blank compute a new hash value h using either linear probing or double hashing and go to 3 Deletion 1 Compute h hK 2 If Hh is blank then exit the routine key K has not been found 3 If Hh K then set HhDe1eted TRUE The key is marked as deleted 4 If Hh 2 K and Hh is not blank compute a new hash value h using either linear probing or double hashing and go to 2 Why Use Lazy Deletion Suppose we have two keys K1 and K2 with hK1 hK2 h Suppose that each of Hh1 and Hh1 l is blank before insertion and that linear probing is used to resolve collisions 1 Insert K1 2 2K1 Hh1 l is blank 2 Insert K2 2 K1 Hh1 2 K2 3 Delete K1 real deletion not lazy deletion Hh1 is blank Hh1 2 K2 4 Search for K2 cannot nd as Hh1 is blank We need lazy deletion Summary and a Few Examples Hashing is the process of creating indices into a table of size M for each of a list of entries to be inserted into that table Because modulo S arithmetic is used in creating these indices the table is always implemented as a O based array HO M 1 The ideal hash function will place entries into the table in a fashion that appears to be random almost creating a uniform distribution One common approach to hashing creates the table with size M being a prime number Experience shows that this helps in distributing the keys and avoiding clusters A cluster is a sequence of contiguously occupied slots in the hash table This presents a problem for the use of linear probing to resolve collisions Hashing relies on two or three functions to create the index 1 A function here called MakeInt that converts the key to a positive integer MakeInt Key gt Integer 2 The primary hash function h1 MakeIntKey mod M 3 For double hashing a second hash function with another key is used Selection of the Hash Table Size As noted above experience indicates that setting the table size to a prime number will yield better distributions of the hashed entries If double hashing is used to resolve collisions then it is desirable to select the table size M such that each of M 2 and M is a prime number These sets are called twin primes Examples include 11 and 13 17 and 19 41 and 43 71 and 73 101 and 103 107 and 109 31 1 and 313 There are many more One last pair 99989 and 99991 Our example will use the pair 11 and 13 The table size is 13 H0 12 Hashing Integer Keys To focus on the issues of hashing including those of linear probing and double hashing we avoid the issue of converting the keys to integers by just hashing integers In our example we use a table of size 13 and examine each of linear probing and double hashing The hash functions are h1K K mod 13 h2K l K mod 11 Add 1 to avoid a zero offset When double hashing is used the algorithm generates a sequence of hash addresses terminating when a useable address is found For the key K the sequence is A1K h1K K mod 13 For index I gt 1 we have AJK AHK h2K mod 13 ConsiderK 119 9013 2 10011 9 h1ll9 2 and h2ll910 Double hashing produces the sequence 2 2 10 modl312 12 10 modl39 9 10 modl36 6 10 modl33 3 10 modl30 0 10 modl3lO etc 7 Hashing With Linear Probing We shall insert keys in the following sequence 119 85 43 141 72 91 109 147 38 137 148 and 101 At the beginning the hash table is empty lindex101112131415161718191101111121 1Key1 1 1 1 1 1 1 1 1 1 1 1 1 1 Insert 119 h119 2 11ndex101112131415161718191101111121 1Key 11191 1 1 1 1 1 1 1 1 1 1 Insert 85 h85 7 No collisions yet lindex101112131415161718191101111121 1Key1 1 11191 1 1 1851 1 1 1 1 1 Insert 43 h43 4 No collisions yet lindex101112131415161718191101111121 1Key1 1 11191 1431 1 1851 1 1 1 1 1 Hashing With Linear Probing Page 2 Insert 141 h141 11 No collisions yet 11ndex101112131415161718191101111121 1Key1 1 11191 1431 1 1851 1 1 11411 1 Insert 72 h72 7 1 collision Place after one probe 11ndex101112131415161718191101111121 1Key1 1 11191 1431 1 1851721 1 11411 1 Insert 91 h91 O No collision 11ndex101112131415161718191101111121 1Key1911 11191 1431 1 1851721 1 11411 1 Insert 109 h109 5 No collision 11ndex101112131415161718191101111121 1Key 1911 11191 14311091 1851721 1 11411 1 Hashing With Linear Probing Page 3 Insert 147 h147 4 Another collision 11ndex101112131415161718191101111121 1Key 1911 11191 143110911471851721 1 11411 1 Note that it took two extra probes to place the key It hashed to address 4 but that was full Probe 1 tried address 5 That was full Probe 2 tried address 6 and was successful Note that we have now grown a cluster of length 5 addresses 4 through 8 Insert 38 h38 12 No collision 11ndex101112131415161718191101111121 1Key 1911 11191 143110911471851721 1 11411381 Insert 137 h137 7 There is a collision Linear probing places this in address 9 11ndex101112131415161718191101111121 1Key 1911 11191 1431109114718517211371 11411381 Hashing With Linear Probing Page 4 Insert 148 hl485 There isacollision Linear probing places this in address 10 lindexlolil2l3l4l5l6l7l8l9l10l11l12l lKey l91l l119l l43l109l147l85l72l137l148l141l38l Note that it took six tries to place the key 148 We had to try addresses 5 6 7 8 9 and 10 before making a placement Insert 102 h20110 There isacollision Linear probing places this in address 1 lindexlolil2l3l4l5l6l7l8l9l10l11l12l lKey l91l102l119l l43 l109l147l 85 l 72 l137l148l141l 38 At this point with a load factor of l ll3 z 0846 before insertion we should have expected quite a few probes to make the placement Hashing With Double Hashing Again we shall insert keys in the following sequence 119 85 43 141 72 91 109 147 38 137 148 and 101 Nothing differs until we have a collision At the beginning the hash table is empty 11ndex101112131415161718191101111121 1Key1 1 1 1 1 1 1 1 1 1 1 1 1 1 Insert 119 h11192 11ndex101112131415161718191101111121 1Key 11191 1 1 1 1 1 1 1 1 1 1 Insert 85 h185 7 No collisions yet 11ndex101112131415161718191101111121 1Key1 1 11191 1 1 1 1851 1 1 1 1 1 Insert 43 h143 4 No collisions yet 11ndex101112131415161718191101111121 1Key 11191 1431 1 1851 1 Hashing With Linear Double Hashing Page 2 Insert 141 h1141 11 No collisions yet 11ndex101112131415161718191101111121 1Key1 1 11191 1431 1 1851 1 1 11411 1 Insert 72 h172 7 This is a collision h272 1 72 mod 11 7 Generate A2 7 7 mod 13 14 mod 13 1 11ndex101112131415161718191101111121 1Key1 17211191 1431 1 1851 1 1 11411 1 Insert 91 h191 0 Not a collision sojust place the key 11ndex101112131415161718191101111121 1Key 1911 11191 1431 1 1851 1 1 11411 1 Insert 109 h1109 5 Not a collision sojust place the key 11ndex101112131415161718191101111121 1Key 1911 11191 14311091 1851 1 1 11411 1 Hashing With Linear Double Hashing Page 3 Insert 147 h1147 4 This is a collision h2147 1 147 mod 11 5 Generate A2 4 5 mod 13 9 mod 13 9 11ndex101112131415161718191101111121 1Key1911 11191 14311091 1851 11471 11411 1 Insert 38 h138 12 This isanotacollision Just place the key 11ndex101112131415161718191101111121 1Key1911 11191 14311091 1851 11471 11411381 Insert 137 h1137 7 This is a collision h2137 1 137 mod 11 6 Generate A2 7 6 mod 13 13 mod 13 0 Still a collision A3 O 6 mod 13 6 mod 13 6 Place the key 11ndex1011121314 5 6 7 8191101111121 1Key 1911 11191 143110911371851 11471 11411381 Hashing With Linear Double Hashing Page 4 Insert 148 h11485 This isacollision h2148 1 148 mod 11 6 Generate A2 5 6 mod 13 11 mod 13 11 Still a collision A3 11 6 mod 13 17 mod 13 4 Still a collision A4 4 6 mod 13 10 mod 13 10 Place the key 11ndex101112131415161718191101111121 1Key1911 11191 143110911371851 1147114811411381 Insert 101 h1101 10 This is a collision h2101 1 101 mod 11 3 Generate A2 10 3 mod 13 13 mod 13 0 Still a collision A3 O 3 mod 13 3 mod 13 3 Place the key 11ndex101112131415161718191101111121 1Key 1911 11191101143110911371851 1147114811411381 Cryptographic Hashing A cryptographic hash function is a hash function with two properties 1 It is not invertible Given h one cannot determine a unique K such that hK h Collision K1 7 K2 but hKl hKZ 2 Crypto property Given h it is very hard to compute or derive a key K such that hK h Cryptographic hashing is often used for message authentication One procedure 1 Create message M 2 Compute the crypto hash h hM 3 Encrypt this hash producing Eh 4 Append Eh to M and send M amp Eh Another procedure is based on a secret authentication string called S This string is shared by the sender and receiver only nobody else knows it The procedure 1 Create message M 2 Append the secret string and compute h h M amp S 3 Append hM amp S to M and send the message as cleartext Sample cryptographic has functions include SHA l MDS and RIPEMD l60 Directed Graphs and Topological Sort Topological sorting is a process that is applied to directed acyclic graphs Definition A graph G is a nite nonempty set of vertices denoted VG together with a possibly empty nite set E g VG gtlt VG If we de ne VG N and EG M the graph G is called an N M graph In the formal theory we identify each vertex by an integer IfVG N we say that VG 1 2 3 N EGgJK 1 ngNand 1 gKgN There are a number of special classes of graph that we nd interesting When speaking of graphs we normally mean simple graphs formally de ned as VG 1 2 3 N andEGg J K 1 ngN 1 gKgN andJiK A directed graph is a simple graph in which the edge J K is not the same as the edge K J J K 7 K J An undirected graph is a simple graph in which the edge J K is de ned to be the same as the edge K J J K K J Graph Theory Informal De nitions A simple graph is a graph without edges connecting any vertex to itself no edge of the form J J The graph in the next gure is not simple as it has edges connecting vertex 1 to itself and vertex 4 to itself 0 0 This graph at right is also described as follows VG 1 2 3 4 7 7 7 EG 1 1 1 4 2 3 2 4 4a 4 Any simple graph over vertex set VG 1 2 3 4 would haVe EG Q 1 2 1 3 1 4 2 1 2 3 2 4 37 1 37 2 37 4 47 1 47 2 47 3 Directed and Undirected Graphs Here we characterize undirected graphs and show a common way to denote their edge set In the formal de nition an undirected graph over vertex set VG 1 2 N is de ned in terms of restrictions on its edge set EGg JK 1 ngN 1 gKgN and KwithJKK J It is common to write an edge with the smaller vertex number rst With this convention the edge set appears as follows EGg JK 1 ngN 1JltKgN In this notation an undirected graph over vertex set VG 1 2 3 4 would have EGg 12 l 3 14 2 3 24 34 Note the maximum size of the edge set NoN 1 If VG N then EG g 2 More on Directed and Undirected Graphs Directed graphs correspond to edge sets that contain ordered pairs Undirected graphs correspond to edge sets that contain unordered pairs Consider the gure below which shows an undirected graph and a directed graph Undirected Graph Directed Graph The two graphs appear similar but are quite different The graph at the left is said to be the undirected graph that underlies the directed graph The undirected graph has EG l 4 2 3 2 4 34 implicitly 3 2 e EG 4 l e EG 4 2 e EG and 4 3 e EG The directed graph has EG l 4 2 4 3 2 4 l 4 3 with no edges implicitly added Still More on Directed and Undirected Graphs Consider the following two graphs one directed and one undirected In what sense are they similar Each graph has VG 1 2 3 4 The undirected graph has EG 1 2 1 4 2 3 3 4 more conventionally written as EG 1 2 2 3 3 4 4 1 The directed graph has EG 1 2 2 3 3 4 4 1 17 4 4a 3 3a 2 27 1 The undirected graph can be seen as a simpler representation containing the same information as the directed graph Nevertheless they are not the same graph Directed Acyclic Graphs an zcancu r c c 0 9 0 9 0 9 9 9 Jo Jo Adjach lists AgtBCD AgtBC AgtBCD BgtAD BgtD BgtD CgtA Cgt Cgt DgtAB DgtA Dgt his A gt B gt D The directed graph at n39ghtis acyclic 44 Topological Sortin Tnnnln ical quot Theorem A g h can be sorted topologically if and only if it is a directed acyclic graph Topological sorting is an arrangement ofthe vertices in aDAG in such away that preserves the orderirrg implicit in the directiorr ofthe graph edges Consider the set ofcourse prerequisites represerrted by the graph below c1 and c2 are both prerequisites for c3 c3 is aprerequisite forboth c4 and c5 c4 is aprerequisite for CS Two Possible Topological Sorts Here again is the sample graph 6 We can easily see that there are two possible topological orderings These are c1 c2 c3 c4 c5 and c2 c1 c3 c4 c5 There are two algorithms commonly used for topological sorting 1 Depth First Search 2 Source Rem oval Source Removal The source removal algorithm is easier to implement and is intuitive De nition A source vertex is a Vertex with inedegree equal to 0 A source vertex is avenex with no incoming arrows Example There are two source vertices in this directed acyclic graph c1 and c2 Theorem Every nonrempty DAG has at least one source vertex Theorem Removal ofa source Vertex from anonrempty DAG will yield either an empty graph no vertices or another DAG The Source Removal Algorithm To sort a directed acyclic graph topologically one repeatedly applies the following steps Repeat Identify one source vertex Place that vertex in the sort order Remove from the DAG that vertex and all edges incident from it Until the Graph is Empty Give two or more candidate source vertices at any step choose arbitrarily The topological sort will depend on the choice taken but all such sorts are valid In our sample either vertex C1 or C2 can be chosen rst Remove the First ource We stem with the sample graph We see two source venices c1 and c2 Arbitrarily selecting c1 to remove we get Our list at the moment contains one Vertex c1 Remove the Next Source The graph how is We look now and see that there is exactly one source vertex C2 We remove it to get the next grep 9 The sort list is c1 c2 The N Queens Problem Another Introduction to Backtracking Contents of this lecture l k11th A de nition of the N Queens problem Illustration of the problem by its two main instances 4 queens and 8 queens A de nition of the backtracking design strategy The use of Backtracking to solve the N Queens problem The use of symmetry to generate multiple solutions from one backtracking solution The origin of this problem is the game of chess in which various chess pieces are moved on an 8 by 8 chess board The queen is the most powerful piece The chess board can be considered to have eight rows and eight columns In programs the board is usually represented as an 8 by 8 array with the array element BI J containing the name of the chess piece occupying that position The queen can move any number of spaces along any row column or diagonal in which it is currently located Attacking Queens A queen can attack any chess piece that is in a position to which it can move The N Queens problem requires placement of N queens on an N by N chessboard in such a manner as no queen can attack any other queen Here is the beginning of a solution on an 8 by 8 chessboard the standard size HHM nmm m The queen in row 5 of column 1 can attack any chess piece along a red line The queen in row 2 of column 2 can attack any chess piece along a blue line Neither queen can attack the other this is a valid placement Backtracking The backtracking strategy is a re nement of the exhaustive search strategy In backtracking solutions to a problem are developed and evaluated one step at a time Each partial solution is evaluated for feasibility A partial solution is said to be feasible if it can be developed by further choices without violating any of the problem s constraints A partial solution is said to be infeasible if there are no legitimate options for any remaining choices The solution of the problem is developed in backtracking as a search tree The abandonment of infeasible partial solutions is called pruning the solution tree In this the strategy differs from simplistic brute force which would generate all solutions even those arising from infeasible partial solutions Backtracking for N Queens The backtracking solution of the problem proceeds either by rows or by columns The book s solution proceeds by rows For no particularly good reason I have elected to proceed by columns For each column select a row into which to place the queen A partial solution is feasible if no two queens can attack each other given the placement in the columns up to this point It is important to note that no feasible solution can contain an infeasible partial solution The backtracking approach by columns is as follows 1 Move left to right processing one column at a time 2 For column J select a row position for the queen Check for feasibility a If there are one or more attacks possible from queens in columns 1 through J l discard the solution b For each feasible placement in column J make the placement and try placement in column J l c If there are no more feasible placements in column J return to column J l and try another placement 3 Continue until all N columns are assigned or until no feasible solution is found Smaller Instances of the NiQueens Problem A m H To understand why this is so examine the smaller instances g N1 N2 N 3 No solutions One No solution snlutinns The one queen problem has a mm solution one queen on a 17by71 board we e 1 r row 1 ofeolumn 1 The placement in rowZ ofeolumn 1 has similar dif culties e 1 1 y A placement inrow3 ofeolumnl forces aplacementinrowl ofeolumn 2 Together these prevent a placement in column 3 Placement in row 1 of column 1 is similar A e 1 1 Placements as Permutations The N Queens problem is a large problem especially for N 2 8 There are a few simple observations that can reduce the complexity of any solution method even a brute force approach Consider a number of solution strategies listed in order of decreasing silliness a There are N2 squares each of which can have a queen or not have a queen This leads to 2NN possible solutions 8 Queens N 8 264 z 1019392 w 1501019 possible solutions 4 Queens N 4 216 65536 possible solutions 0 But we have only N queens for N2 position thus the maximum count is N 8 4416165368 possible solutions N 4 1 l 820 possible solutions For N 4 even this silly solution has eliminated 973 of the solutions possible with the rst strategy Placeme perrow and one queen per column 3 ms as Permutations Part 2 1 Each of due integers 1 through N me number ofsolutions is reduced to N N 40 Here is a solution to me 47Queens problem By columns mas would be denoted as 3 1 4 2 Backtracking in the 3 Queens Problem We have argued that there is no solution to the 3 Queens problem Let s be a bit more formal about that Begin with a selection for column 1 of the 3 by 3 array Select row 1 The partial solution 1 1Q 123 Having made a tentative choice for column 1 we consider options for column 2 Backtracking in the 3 Queens Problem Part 2 Choices for column 2 are limited Row 1 is disallowed due to arow con ict Row 2 is disallowed due to a diagonal con ict Row 3 is allowed so make the placement 3 Q 2 The partial solution is 1 3 7 The only wmmn 3 is row 2 quot L 439 con ict quot column 2 quot L uptiun JUI Luiuuul 2 m L L 39 Luiuuul 1 is row 1 quot 39 L 4 L r 39 Lulu u we backtrack and try another assignment for column 1 Try row 2 Backtracking in the 3 Queens Problem Part 3 Begin with a selection for column 1 ofthe 3ebye3 army Select row 2 The partial solution 2 7 7 2 Q 1 2 3 Now there are no choices for column 2 Row 1 is disallowed due to a diagonal con ict Row 2 is disallowed due to arow con ict Row 3 is disallowed due to a diagonal con ict No placement in either row 1 or row 2 of column 1 will yield aviable solution How about placement in row3 ofcolumn 17 Backtracking in the 3 Queens Problem Part 4 What about a placement in row 3 of column 1 We can show that the following is a Valid placement for columns 1 and 2 ofthe puzzle The partial solution 3 l 7 3Q 2 1Q 123 But we have seen this case before Consider the following redrawing of the gure 1Q 2 3Q 123 This is just what we had earlier with the placement in row 1 of column 1 All we have done is to ip the board No solution with a placement in row 1 ofcolumn l is feasible It follows that no solution with a placement in row 3 of column 1 is feasible Arguments from Symmetry What we are saying is that a number of simple rotations and inversions will take one valid solution and transform it into a possibly distinct new valid solution Consider the 47Queens problem with its one known solution at top left 4 Q Flip Horizontal 3 2 1 Q 1 2 Flip Vertical Q 4 Flip Horizontal 3 2 gt Q 1 Q 1 2 Q 2 1 At the moment we have two distinct solutions from the one application of backtracking The Search Tree for 4 Queens C0nsider only 11k 4 3 and 4 in column 1 3 41 4 2 3 1 4 3 is bad 3 2 is bad 4 4 is bad 3 3 is bad 3 4 is bad 413 I DeadEnd 3 I 3 1 1 is bad 3 1 2 is bad 3 1 3 is bad 4 1 1 is bad 4 1 2 is bad 4 1 4 is bad 3 1 4 2 Dead end no valid choice for column 4 I A Solution 1 Having solved this one case we apply symmetry to get the solution 2 4 1 3 Arguments from Symmetry Considering Permutations Here is an algebraic statement of a few symmetry arguments for the N Queens problem Let the permutation R1 R2 RN1 RN be a solution to the N Queens problem The permutation RN RN1 R2 R1 is also a solution The permutation N l R1N 1 R2 N l RN1N 1 RN is also a solution The permutation N l RNN l RN1 N l R2N 1 R1 is also a solution Example for 4 Queens Solution R1 R2 R3 R4 3 142 Another R4 R3 R2 R1 2 4 l 3 Another 5 R1 5 R2 5 R3 5 R4 2 4 l 3 Another 5 R4 5 R3 5 R2 5 R1 3 l 4 2 Due to the small solution space two of these solutions are duplicates Application of the Attack Constraints The constraints of the N Queens problem are easily applied visually We now consider how to apply them in a computer program Remember that the solution progresses left to right selecting for one column and moving to the next column over The solution backtracks when necessary Constraint 1 No more than one queen per column This is satis ed automatically by representing any solution as a one dimensional array of N elements where RJ is the one row placement for column J 1 3 J g N Constraint 2 No more than one queen per row This might be satis ed by generating only permutations of the set 1 2 N A solution that is easier to program is to choose any row number for placement in column J and to compare this number to all previous choices R1 R2 RJ 1 The end result of the rst two constraints is that only valid permutations of the integer set 1 2 N will be valid The next two constraints trim the solution space Diagonal Constraints Constraint 3 No more than one queen per rising diagonal Constraint 4 No more than one queen per falling diagonal JIC HereJI J K I Here J 5 1 Two squares L L and 12 12 are on the same rising diagonal if ll 11 C and 12 12 C for the same value C thus 11711 lg 712 Two squares L L and 12 12 are on the same falling diagonal ifll K ill and lz K712 forthe same valueK thus 1111 lz 12 Application of the Diagonal Constraints Again this is based on storing the row selections for a given column as a l based array Rl to N with RJ as the row selection for column J Moving left to right building on the partial solution generated for rows 1 through J 1 Compute both J RJ and J RJ For each value ofK so that l s K S J l 1 If RK RJ discard RJ due to a row con ict 2 If RK K RJ J discard RJ due to a rising diagonal con ict 3 If RK K RJ J discard RJ due to a falling diagonal con ict Example The 5 Queens Problem Here is an example of the algorithmic approach to another small problem We attempt a solution of the problem beginning in column 1 We try row 1 rst Column 1 II 1 3 5 IRJ 1 Column 2 Try R2 1 This is disallowed as Rl R2 a row con ict Try R2 2 This is disallowed as Rl 1 R2 2 a rising diagonal con ict Try R2 3 Rl 1 and R2 3 no row con ict Rl 1 O and R2 2 1 no problem with a rising diagonal Rl 1 2 and R2 2 5 no problem with a falling diagonal The partial solution is thus as follows IJ 12345 IRU 13 Example The S Queens Problem Column 3 Building on the partial solution below we try for a placement in column 3 Column 3 R3 1 R3 2 Rp3 RB4 RB5 IJ 123 IRU 45 1 3 w This is disallowed as Rl R3 a row con ict RB 32 3 l Inn i0amnqm 2L RB3235 Rl 1 2 and R2 2 5 a diagonal con ict with row 2 This is disallowed as R2 R3 a row con ict RB 34 3l Inn i0amnqm 2L RB 35 32 Inn i0amnqm 2L RB3538 Rl l 2andR2 2 5 no problem with a rising diagonal a diagonal con ict with row 2 no problem with a rising diagonal no problem with a falling diagonal Example The S Queens Problem Column 4 Building on the partial solution below we try for a placement in column 4 IJ 12345 IRU 135 l Column4 R4 1 This is disallowed as Rl R4 a row con ict R42 R4 42 3 2 R1 1O R2 2 1 and R3 3 2 no problem with a rising diagonal R44246 Rl 1 2 R2 2 5 and R3 3 8 no problem with a falling diagonal The partial solution is thus as follows II 1 2 3 4 IRU 1352 We can clearly see now that RS 4 is the only possible candidate for a placement Nevertheless we shall follow an algorithmic solution Example The S Queens Problem Column 5 Building on the partial solution below we try for a placement in column 5 IJ 12345 IRU 1352 Column 5 RS 1 This is disallowed as Rl RS a row con ict RS 2 This is disallowed as R4 RS a row con ict RS 3 This is disallowed as R3 RS a row con ict RS 4 No row con icts R5 54 5 1 R1 1 0 R2 2 1 R3 3 2 and R4 4 2 no problem with a rising diagonal R55459 R112R225 R3 3 8 and R4 4 6 no problem with a falling diagonal We have a solution 1 3 5 2 4 More Solutions from Symmetry Here are the solutions represented as horizontal and vertical inversions The original solution is l 3 5 2 4 1 3 5 2 4 ip horizontally 4 2 5 3 1 ip vertically ip vertically 5 3 1 4 2 ip horizontally 2 4 1 3 5 There are probably more symmetries here but I want to stop after these obvious ones Pictures of the S Queens Solutions Here are the four in a different order than that in which they were genemted 5 Q 4 5 Q 3 B Trees and Related Data Structures REMEMBER Trees that are balanced have minimum height for a given node count are more quickly searched Balanced trees serve as ef cient indices into databases and other collections of indexed records The B Tree and its derivative data structures allow for very ef cient indexing The B Tree comprises a data structure and associated insertion and deletion algorithms One suspects that deletion would be done by Lazy Deletion marking as deleted The B Tree data structure contains two types of nodes index nodes and data nodes Index nodes are also called interior nodes Unlike a binary tree the interior nodes of a B Tree do not contain data values These interior nodes contain copies of the key values from some of the data nodes These key values are used by the index structure in ef cient location of the data nodes Index Nodes in a B Tree In a BiTree of Order M index nodes have M pointers and M 7 1 keys Example An Index Node Interior Node for BiTree of Order 4 Pu points to records with key Values K lt K Forl J M72here l J 2 P poinw to records With key Values K g K lt KM PNH here P3 points to records With key Values K 2 K3 Unless the index node is the root node of the BiTree there Will be additional constraints placed on the records pointed to by PD an NH All BiTree Varianw of Order 4 such as a B Tree Would have the same structure for interior nodes Additional Constraints Due to Parent Nodes Consider the root node of a BiTree of order 4 and is four child nodes The keys in the parent node restrict the key Values that can be accessed through each of the four child nodes Consider the following situation All nodes in the P2 subtree have Km g K lt szl All nodes in the P2 subtree have K2 g K lt Km Balance Requirements for a B Tree All Varianw of BiTrees including the B Tree follow the same balance constraints These constraints are enforced by the algorithm to insert new keys into the tree A BiTree of order M 2 2 satis es the following requiremenw 1 The root is either a leaf thus an isolated node or it has between 2 and M child nodes 2 The tree is perfectly balanced all ofits leafnodes are at the same level 3 Each node except for the root node and the leaf nodes has between fM 2 and M child nodes hence fM 2 7 l and M 7 1 key Values The last constraint can be rewritten as a requirement that at least fM 2 of the pointers in the node not be the null pointer Here Pu x NULL and P1 x NULLprZ NULL then P3 NULL lsz I NULL then P3 may or may not be NULL Leaf Nodes on a B Tree Leaf Nodes may contain data but usually contain pointers to data records as indicated here The data are most commonly stored on a disk R1 R2 R3 These pointers may actually be implemented as addresses on the disk used to store the data es Note the major structural difference between the index nodes and leaf nodes in a B7Tree of order M The maximum counts are as follows Index nodes M 7 1 keys and M pointers Leaf nodes M 7 1 keys and M 7 1 pointers one for each key Leaf Nodes on a B Tree Leaf Nodes in a B tree have and additional pointer R1 R2 R3 R10 R12 R15 A BiTree and a B Tree share the same index structure A B Tree has the leaf nodes organized in linkedilist fashion for faster sequential access The B Tree is the key index structure in the VSAM data access method and similar access methods developed by IBM B Trees Compared to Other Balanced Binary Trees Bina Tree Data stored in interior nodes BiTree also B Tree Interior nodes index nodes store only indices Any given index Value may also be a data Value but is not required to be Leaf nodes store either the data or pointers to the data an Leaf Nodes Example Insertion into a B Tree of Order Four E R1 R2 R3 Leaf Node Interior Node 3 keys 3 ke s 4 pointers 3 pointers Insert A B C D E and F in that order into the BiTree Insert A This creates the BiTree At this point the tree is just a single node Insertion Example Part 2 Insert B E IIIII R1 R2 Insert C El IIIIII R1 R2 R3 Insert D 7 Split the Tree and grow a new Root Introduction to Algorithm Analysis and Design The Idea of an Algorithm We begin our formal lectures with a de nition of the term algorithm The de nition of algorithm taken from the textbook is only partial An algorithm is a sequence of unambiguous instructions for solving a problem The full de nition must include the provision that the algorithm terminate for any valid input So we have the following de nition of algorithm taken from an another text De nition An algorithm is a nite set of instructions which if followed will accomplish a particular task In addition every algorithm must satisfy the following criteria i input there are zero or more quantities which are externally supplied ii output at least one quantity is produced iii de niteness each instruction must be clear and unambiguous iv niteness if we trace out the instructions of the algorithm then for all valid cases the algorithm will terminate after a nite number of steps v e cttveness every instruction must be suf ciently basic that it can in principle be carried out by a person using only a pencil and paper It is not enough that each operation be de nite as in iii but it must be feasible Hor76 The effectiveness criterion might be restated as it being possible to map each step in the algorithm to a simple instruction in the base computer language This violates the idea that algorithms exist independently of programming languages but corresponds to the basic practice that algorithms are quite often expressed using a programming language The rst algorithm for study is Euclid s algorithm for computing the greatest common divisor of two positive integers This algorithm has a very simple expression apart from any programming language For integers M and N assume M 2 N gcdM N gcd N M mod N The book computes gcd6024 12 Let s compute a more interesting example gcd225 63 gcd63 36 as 225 63 o 3 36 so 225 mod 63 36 gcd36 27 as 63 36 0 1 27 so 63 mod 36 27 gcd27 9 as 36 27 01 9 so 36 mod 27 9 gcd90 as 27903 so 27mod90 9 as gcdN 0 N for any N 2 0 Page 1 of 6 Chapter 1 Last Revised On August 25 2004 CPSC 5115 Algorithm Analysis and Design Course Notes We now discuss an iterative description of the algorithm Algorithm Euclid m n Computes the greatest common divisor of integers m and n using Euclid s algorithm Input Two nonnegative integers m and n not both zero It is not necessary that m 2 n Output The greatest common divisor of m and n while n i 0 do r m mod n m 6 n n e r end while return m We make a few random comments before commenting on the algorithm The first is the applicability of the criterion of placing the larger number first so that we compute the greatest common divisor gcdM N with M 2 N HEMMwmeMgMMmeNwwwmmMltMmmmeNM and we have gcdM N gcd N M and we then compute the greatest common divisor with the larger number placed first Thus the requirement M 2 N is not necessary but only an artifact of executing the algorithm by hand The second point is that as a software engineer I am uncomfortable writing code that might crash The following represents a better programming implementation Algorithm Euclid m n Computes the greatest common divisor of integers m and n using Euclid s algorithm Input Two nonnegative integers m and n Output The greatest common divisor of m and n First take care of the case for either argument 0 if O or O return 0 m lml Force both numbers to be positive n lnl as required by the algorithm while n i 0 do r m mod n m 6 n n e r end while return m Page 2 of 6 Chapter 1 Last Revised On August 25 2004 CPSC 5115 Algorithm Analysis and Design Course Notes The above pseudocode illustrates one of the major differences between the study of algorithm design and the study of software engineering Examples used in the study of algorithms generally do not include the error handling code required for robust implementations as required by proper software engineering In general we shall assume that all algorithms described in this course operate only on appropriate input At this point we offer another algorithm to compute the greatest common divisor This second algorithm is discussed in order to make an obvious point e that there are always a number of ways to solve a problem and not all of them are really worthwhile Algorithm ch m n First take care of the case for either argument 0 if n or m return 0 m lml Force both numbers to be positive n lnl as required by the algorithm t min m n l is a divisor of any two integers so we do not test it if we get that far in the loop while t gt 1 do if m mod t and n mod t then return t else t t 1 end while return t if it gets to here we return l In this version of the algorithm we have provided for zero input and forced the variables in the body of the algorithm to be positive integers We now compare this algorithm to that of Euclid The original algorithm presents problems for zero input We do note that each algorithm must specify the range of valid inputs My slight corrections to the algorithm do fix the problem with the input We now consider the problem of efficiency of this algorithm Note that the algorithm is guaranteed to terminate for any integer input Consider the computation of gcdM N with M 2 N It is easily shown that the algorithm will terminate after at most N e 1 loops as the variable t is decreased by 1 on each loop Consider now the efficiency of the algorithm It can be shown that the algorithm considers far two many possible advisors Consider the problem of computing the greatest common divisor of 142 and 146 using the second algorithm Each of these numbers is a multiple of2 and a prime number 142 7102 and 146 7302 Since each of 71 and 73 is a prime number it follows that gcd146 142 2 and the second algorithm will consider all numbers between 142 and 2 inclusive for 140 iterations Page 3 of 6 Chapter 1 Last Revised On August 25 2004 CPSC 51 15 Algorithm Analysis and Design Course Notes Let us apply the iterative version of Euclid s algorithm to compute the same number The main body of the loop is show below while n i 0 do enter with m 146 and n 142 r m mod n m e n n e r end while return m Lets follow the execution while n i 0 do n 142 r m mod n r 146 mod 142 4 m n m 142 n r n 4 end while while n i 0 do n 4 r m mod n r 142 mod 4 2 m n m 4 n r n 2 end while while n i 0 do n 2 r m mod n r 4 mod 2 O m n m 2 n r n 0 end while return m return 2 as n A third algorithm is presented based on the prime factors of the two numbers M and N Consider the first problem we did computation of the greatest common divisor of the two integers 225 and 63 The prime factorization of these two numbers is 225 9o25 32 52and 63 7o9 32o7 We then look for the factors common to both of the integers here the largest common factor is 32 9 which is the greatest common divisor of 225 and 63 While this is a great way to generate examples for the greatest common divisor problems it is not suitable for implementation as an algorithm The main difficulty is the difficulty in obtaining a list of prime numbers The algorithm also has some efficiency problems Page 4 of 6 Chapter 1 Last Revised On August 25 2004 CPSC 5115 Algorithm Analysis and Design Course Notes Other Considerations We consider algorithms to be procedural solutions to problems There are a number of other considerations when trying to design a speci c algorithm One consideration is whether or not one wants to obtain an exact solution to every instance of the problem Some problems such as the Traveling Salesman Problem admit easy solutions when those solutions need be only approximate Pseudocode is the most common device used to specify an algorithm Most often this pseudocode is a variant of a programming language with some of the grammatical constraints removed The rule for writing instructions in pseudocode is that every instruction be unambiguous and convertible to a nite number of instructions in the machine s assembly language For the study of algorithms we nd that there are a number of problem types that should be considered These problems are Sorting a list that supports a de ned comparison operator a Sorting by comparison b Sorting when another mechanism is allowed 2 Searching a list that supports a de ned equality operator 3 String processing 4 Graph traversal problems also called graph search problems 5 Combinatorial problems 7 how to generate certain combinatorial objects such as all permutations ofthe set 1 2 N 6 Geometric problems 7 Numerical problems V Is A Program An Algorithm One can argue that every program speci es an algorithm in that a program must be a nite set of steps each de ned in a speci c programming language which produces a speci c result Under this de nition the only way that a program can fail to be an algorithm is if the program enters an endless loop By de nition all algorithms must terminate and produce an answer so that a program or any other sequence of instructions that fails to terminate cannot be considered an algorithm For the purpose of this course we arbitrarily say that a program is not an algorithm The reason for this statement is that this course will focus on what the algorithm is to do assuming that all inputs are valid and that no errors occur in the processing Both of these assumptions are very dangerous in the implementation of programs However each of the assumptions is valid in the study of algorithms as it allows us to focus on the other issues of importance The speci c requirement for this course is that homework answers contain only a description of the algorithm assigned and not include such extra but important features such as user input of the data output of the data or error checking unless speci ed in the assignment One reason for this requirement is that it greatly facilitates the grading Page 5 of 6 Chapter 1 Last Revised On August 25 2004 CPSC 5115 Algorithm Analysis and Design Homework Set 3 DO NOT SUBMIT ANY WORK ON THIS SHEET 1 Given the undirected weighted graph represented by the following adjacency matrix use Kruskal s algorithm to nd a minimum spanning tree of the graph Notes The entries not shown represent edges not present This is problem 1 on page 318 7 see that if you prefer a drawing of the graph Since this is a solution by hand you may use either 00 or a large number such as 100 to represent an edge not present 2 For the above graph use Prim s algorithm to construct a minimum spanning tree beginning at vertex A E For the above graph apply Floyd s algorithm to nd the shortest paths between all pairs of vertices 4 For the input 30 20 56 75 32 19 and hash function hK K mod 11 a Construct the open hash table b Construct the closed hash table Note This is taken from problems 1a and 2a on page 266 Assigned 7212010 Due Thursday November 4 Binary Search Trees In order to better understand balanced search trees it helps to study simple binary search trees which can become quite unbalanced Binary search trees can be made to work ifpopulated correctly Each node in a binary search tree has two components 1 A value that is storedin the node and 2 Two possibly empty pointers one for the le subtree and one for the right subtree m an Smaller Larger Keys K s As the binary search tree is populated it grows from the root down Binary Search Trees Well Populated Here is a binary search tree that has been Well populated The insertion sequence for this binary tree is 4 2 31 3 5 7 It should be obvious that this tree is balanced Search time is O logN However it is not called a balanced search tree Binary Search Trees Poorly Populated Here is the tree generated for the insertion sequence 1 2 3 4 5 6 7 This tree is not balanced 13 search timeis ON What to Do About Unbalanced Trees The above unbalanced tree can be balanced by a straightforward algorithm There are two approaches to producing balanced search trees 1 Produce the tree in any desired way and then apply a balancing procedure to produce a balanced tree equivalent to it 2 Use a procedure that creates the search tree as a balanced tree and maintains the tree s balance during updates Search trees that are created and updated using special balancing procedures are called balanced search trees A binary search tree that just happens to be balanced is not called a balanced search tree That term is applied only to trees created and updated using procedures guaranteed to maintain the balance Side Remark Another Search Tree Structure Just to be complete We mention index trees In these trees the values are not stored in the tree but in an attached data structure often stored as a linked list This figure shows a binary tree adapted as an index tree It is just an example This structure is used to access data records that are stored on disk the key values are stored in the index structure The linked list allows for efficient sequential access to the data AVL Trees This data structure named a er its two inventors G M AdelsoniVelsky and E M Landis An AVL tree is a binary search tree coupled with a node insertion procedure designed to maintain the balance requirements The requirement is that the difference between the heights of the le and right subtrees of every node not exceed 1 The balance factor of a node is de ned as the difference between the height of that nodes right and le subtrees Acceptable Values are in the set fl 0 1 If the Values become either 72 or 2 the AVL tree must be rebalanced Notation for Binary Trees Here is our accidentally balanced tree and its standard representation The height of each ofthe le and light subtrees is 1 This happens to be an AVL tree More Notation for AVL Trees Here are some of the standard gures used in depicting AVL trees Balanced Balanced Becoming Unbalanced Balance Factor 0 Balance Factor 71 Balance Factor 72 In the figure to the right the pendant vertex is intended to denote the last vertex added to a AVL tree that previously had been balanced with balance factor 71 Rotations Fix the Balance Addition of a single node vertex to an AVL tree can change the balance factor of a node by at most 1 If the node to which the new node is attached has balance factor 0 then the balance factor will become either 1 or 1 and the tree remains AVL Addition to a node with balance factor not equal to O can cause its new balance factor to become one of 2 O 2 If the balance factor becomes either 2 or 2 it is necessary to rebalance the tree The newly inserted node will be a leaf node in the tree The rotation is applied to the tree rooted at the unbalanced node that is closest to the newly inserted leaf node There are two classes of rotation single rotations and double rotations Single Rotations Single Right Rotations R Rotations Single Left Rotations L Rotations Double Rotations Double Left Right Rotations LR Rotations Double Right Left Rotations RL Rotations R Rotations We sta with an AVL tree Our example has two nodes 1 Balance actor for Imde r39alue stored in node 0 Adding a leafnode to the le subtree causes the balance factor to become 2 This case is xed by a simple Reputation 2 0 1 0 R 0 0 L Rotations Add a node to an AVL tree Again our sample has two nodes before insertion 1 3 Adding a node to the right subtree causes the balance factor at the root to become 72 This is xed by a le rotation 2 0 The Double Rotations A LRrrotation is a le rotation followed by a right rotation 2 b k L A Rerotation is a right rotation followed by a le rotation 2 2 1 4 gt R L Use of the Rotations In building a AVL tree we apply the rotations as needed after inserting new nodes Right Rotations A new key is inserted into the left subtree of the left child of a tree whose root node had a balance factor of 1 before the insertion Its left subtree is deeper 2 0 1 0 as 0 0 R Left Rotations A new key is inserted into the right subtree of the right child of a tree whose root node had a balance factor of 71 before the insertion The right subtree is deeper 2 0 391 3 Min 0

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

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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