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

GPA 3.91

### View Full Document

## 20

## 0

## Popular in Course

## Popular in ComputerScienence

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

## Similar to CPSC 5115U 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

A Simpler Algorithm for Computing Averages Pick a Trial Value Say 95 Value Difference Sum 100 5 5 100 5 10 98 3 13 96 1 14 94 1 13 88 7 6 86 9 3 82 13 16 We have eight values 16 8 2 so the original estimate is too high by 2 The real average is 93 Linear Equations 2 X Y Z l 4 X Y Z 5 X Y Z O Coef cient Matrix Augmented Matrix 2 l l 2 l l l 4 l l 4 l l 5 l l l l l l 0 Elementary Row Operations 1 Exchanging two rows 2 Multiplying a row by a nonzero constant 3 Replace a row by the sum of that row and a constant multiple of another row We study the use of elementary row operators to solve these equations Will Row Exchanges Always Solve the Equations Before solving the rst set of equations consider this set 2X Y Z 1 2X 2Y 2Z 8 X Y Z 4 The augmented matrix 2 l l l 2 2 2 8 l l l 4 Row two minus twice row three R2 20R3 2 l l l 2 l l l 2 2 2 8 gt 0 O O O l l l 4 l l l 4 Notice the row of 0 s These equations cannot be solved Gaussian Elimination Use elementary row operators to place the matrix in upper triangular form Consider the original set of equations The augmented matrix is R3 lt R3 050Rl 2 l l l O 3 3 3 O 32 12 l2 Gaussian Elimination Continued R3 lt R3 05112 2 l l l O 3 3 3 O O 2 2 Row3says ZoZ 2 Z 1 Row2says 3oY 3oZ3 3oY 3o 13 3oY33 YO Rowlsays ZoX YZ1 20X 0 11 20X2 X1 END GAUSSIAN ELHVIINATION The solution is X 1 Y 0 Z 1 Continue with another solution method Gaussian elimination ended with 2 l l l O 3 3 3 O O 2 2 We illustrate another solution method by continuing the row operators Rllt Rl2 R2lt R23 R3 R32 1 l2 12 12 0 l l l O O l l Rllt RlR22 C Finish of the Second Solution Method R26 R2rR3 l O O 1 O l O O O O l 1 This augmented matrix represents the following set of three linear equations 10X OOY 002 1 00X loY 002 O 00X OOY 102 1 This says X 1 Y 0 Z l WARNING Watch out for roundoff error Consider the two equations 10000000X Y 1000001 10000000X Y 999999 This is obviously solved by X 1 and Y 1 Suppose a number system with only ve signi cant digits We solve for Y getting 20Y 1000001 999999 0 as the system cannot distinguish 1000001 from 999999 With the limited math we get 20X 2000000 or X 1 which is correct MATRIX INVERSE Consider matrix multiplication Let A and B be N by N matrices with each index in the range 1 to N inclusive This can be adapted to O based arrays easily Matrix produce C AoB C is also N by N and has values DoJ lN DoK lN CJK 0 DoL lN CJK CJK AJL BLK Recall that the time complexity of this algorithm is given by TN 6 N3 By my count TN 3oN3 N2 De ne the identity matrix IN by INJ K 1 if and only if I K INJK 0 if and only ifJ 7 K The inverse of N by N matrix A is that matrix A391 such that AoA391 A39loA IN Matrix Inverses by Elementary Operations Let A be given by 2 l l 4 l l l l 1 Form the augmented matrix A IN This is an N by ZON matrix twice as many columns as rows Here it is a 3 by 6 matrix 2 1 1 1 o o 4 1 1 o 1 o 1 1 1 o o 1 If we use elementary row operations to convert this to the 3 by 6 matrix IN B then B A4 Start of the Inversion Here is the original augmented matrix 2 1 1 1 o o 4 1 1 o 1 o 1 1 1 o o 1 Use elementary row operations R1 lt Rl 2 1 12 12 12 0 o 4 1 1 o 1 o 1 1 1 o o 1 R2lt R2 40R1 R3 lt R2 R1 1 12 12 12 0 o o 3 3 2 1 o 0 32 12 12 0 1 Inversion Continues We have changed the augmented matrix to this form 1 12 12 12 0 o o 3 3 2 1 o 0 32 12 12 0 1 R2e R23 1 12 12 12 0 o o 1 1 23 13 0 0 32 12 12 0 1 R1lt R1R22 R3 lt R3 150R2 1 o o 16 16 0 o 1 1 23 13 0 o o 2 12 12 1 Producing the Inverse We have now changed the augmented matrix to this form 1 o o 16 16 0 o 1 1 23 13 0 o o 2 12 12 1 R3 lt R3 2 1 o o 16 16 0 o 1 1 23 13 0 o o 1 14 14 12 Rze R2 1R3 1 o o 16 16 0 o 1 o 512 112 112 0 o 1 14 14 12 This has become the augmented matrix IN A 1 soA is 16 16 0 512 112 112 14 l4 12 Alternate Version of the Inverse 2 2 This can be written as A391 i 0 5 1 O 1 3 36 Start with AOX Y end with X A39loY 2202 111200 Onecanverifythat 5 1 1 0 4 1 1 0 12 0 3 3 6 1 1 1 O O 12 The Determinant of a Square Matrix Definition The determinant of an N by N matrix A denoted detA or A is a number that can be computed recursively as follows 1 17 then A all and all JN 2 IfN 2 2 then detA 2 SJ 0 am 0 detAJ Jl where SJ l ifJ is odd l ifJ is even an is the element in row 1 and column J A is the N l by N 1 matrix obtained from matrix A by removing row 1 and column J Example of Determinant Computation Here are the computations for 2 by 2 and 3 by 3 matrices a12 a12 det 2111 det 3122 a12 detlau a11392122 a12 a21 a21 322 311 312 313 det 321 322 323 331 332 333 a22 a23 a21 a23 a21 a22 all 0 det an o det an o det a32 a33 a31 a33 a31 a32 This recursive de nition leads to an enormous amount of computation and an equally large number of chances to make a mistake One can show that the time complexity for an N by N matrix is TN e N Properties of Determinants Here we examine a number of properties of determinants that considerably facilitate their computation Our new algorithm will have TN 6 N3 Here are the important properties The theorem numbers are from the text Theorem 46 a If B is a matrix obtained from matrix A by multiplying each entry of some row of A by a scalar c then detB codetA b If B is a matrix obtained from matrix A by interchanging two rows then detB detA c If B is a matrix obtained from matrix A by adding a multiple of row J to row K J 7 K then detB detA d If two rows of a matrix A are identical then detA 0 e If one row of a matrix A consists of entirely zero entries then detA 0 Theorem 411 The determinant of an upper triangular square matrix is the product of its diagonal entries Taken from Linear Algebra Second Edition by Stephen H Friedberg et al Prentice Hall 1989 ISBN 0 13 537102 3 pages 190 and 198 Use of Gaussian Elimination to Calculate Determinants The procedure called Gaussian Elimination converts a square matrix into upper triangular form This can be used to compute the determinant of the matrix Consider the 3 by 3 example matrix 2 l l A 4 l l l l 1 R2 lt R2 20R1 Obtain matrix B from matrix A by adding 20Rl to R2 B O 3 3 3 detB detA Chapter 4 Divide and Conquer The name Divide and Conquer is an interesting title applied to a specific design strategy that often leads to very efficient algorithms Many of the better search and sort algorithms are based on the divide and conquer strategy Algorithms designed according to this strategy have the following characteristics 1 A problem s instance is divided into several smaller instances of the same problem The strategy usually works best when the smaller instances are all of approximately the same size thus a divideandconquer sort strategy applied to a list of N items might break the problem instance into two instances each of size about N2 2 The smaller instances are solved in the same manner except that there is always a size at which another algorithm can be considered to be applied For example many sort algorithms designed with this strategy break down the problem instances into instances of size one which automatically are considered sorted L V The algorithm usually has a mechanism for combining the solutions of the smaller problem instances into the solution of a given instance 4 The algorithms designed according to the divideandconquer strategy are often often implemented with recursion but this is not necessary There is a convention often used in the illustration of these algorithms When the algorithm functions by producing two smaller instances of size N2 it is common practice to use problem instances of size N 2K K gt 1 as examples This is done for convenience only As the book notes the mere fact that one can produce a divideandconquer solution to a problem does not imply that the strategy produces superior results Consider the problem of adding a list of N integers which I denote by A1 A2 AN It should be obvious that the following algorithm solves the problem Function Add Al N Note the l based array It N gt 1 Then 81 Add Al NZ 82 Add A NZ l N Return 81 82 Else R e t u r n A l We shall first analyze this algorithm both by example and by the Master Theorem then consider a minor variant of the algorithm which will introduce an interesting design question But first a sample data set 7 as promised the size being a power of 2 Page 1 of 13 CPSC 5115 Last Revised July 20 2010 CPSC 51 15 Algorithm Analysis and Design Course Notes Consider adding the numbers 91 54 75 67 79 84 83 58 Apply the algorithm Note that we underline the sums produced 91 54 75 67 1 79 84 83 58 91 54 1 75 67 1 79 84 83 58 2 1 75 67 1 79 84 83 58 g 1 75 67 1 79 84 83 58 1E 179 84 83 58 g 1 142 1 79 84 83 58 1 79 84 83 58 179 84183 58 E l Dr l 83 58 E l E l 83 58 E l E l Er E l E l E E l E 591 Let s apply the master theorem to the algorithm TN 2oTN2 l Tl 1 In terms of the Master Theorem we have A 2 B 2 and FN l N0 so that FN e NO and D 0 BD 2 1 and A gt BD so we compute logBA logz2 1 and get TN e Nl This is no big improvement over the standard algorithm which requires exactly N e l additions to add a list of N numbers As a diversion consider the following variant of the recursive addition algorithm We observe that the smallest problem instance will either have size 1 or size 2 N l or N 2 and that we are wasting time invoking the addition of a single item to get itself We shall return to this variant of the design strategy when we consider other algorithms but note now that there is no particular reason to favor or disfavor it Function Add Al N Note the l based array It N gt 2 Then 81 Add Al NZ 82 Add A NZ l N Return 81 82 Else If N 2 Then Return Al A2 Else Return Al Page 2 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes SortMerge The next algorithm to be discussed is Mergesort which is a classic example of the divide and conquer strategy Before discussing that I propose to discuss an older but similar algorithm and remark on the situation under which it was developed The situation that gave rise to the sortmerge procedure used to be a common occurrence but is rarely encountered these days in which large computer memories are quire common Suppose that you have an array to sort but cannot fit the entire array in the main memory of the computer The question is how to get the job done One of the most common approaches to solving this difficulty was the sort merge algorithm We present the algorithm in its original form using magnetic tapes to store intermediate results Suppose that the computer memory is large enough for an array of size N but that your problem involves an array of size 40N The data to be sorted are assumed to be on a single magnetic tape call it Tape 1 The solution here would be a 5 way sort merge The first step would be to read 1A of the data into the computer sort it and store the sorted array on another tape We present one scenario Read in the first 1A of the data sort them and store the sorted results on tape 2 Read in the next 1A of the data sort them and store the sorted results on tape 3 Read in the next 1A of the data sort them and store the sorted results on tape 4 Read in the last 1A of the data sort them and store the sorted results on tape 5 At this point in the algorithm one had four sets of sorted data The next step was to do a fourway merge copying the data back onto tape 1 which ended with a sorted data set One should mention that the goal of this algorithm was just to get the job done There were very few timeefficiency considerations at that time Sortmerge remains a viable strategy which has great applicability to specific circumstances The author of these notes was involved in a project for which sortmerge was the ideal approach This involved creating a list of about 8000 7 10000 sorted names each of which was limited to eight characters The names were those assigned to electrical signals in a control system so the eight character limit was not a problem The main issue of interest here is that the list was built incrementally and sorted every night after the new data had been entered Thus at the end of a project one might have a list of 9000 items to sort The structure of the list might be 8600 sorted items followed by 400 unsorted items The items were not entered in any particular order so one could not determine the place of any of the new items in the final sorted list of 9000 items without doing the sort The solution at the time was very inefficient although it used an algorithm that appeared to be quite advanced More on this later The solution devised by this author was to sort the list of new items and then merge the new sorted list with the old sorted list to produce an updated sorted list One can merge 400 sorted items with 8600 sorted items in approximately 9000 comparisons Page 3 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes Mergesort We now arrive at the mergesort algorithm As the book notes this is a classic example of application of the divide and conquer design strategy An array of N elements is divided into two arrays of N2 elements each subarray is sorted and the two sorted subarrays are merged The best presentation of this algorithm is as a recursive procedure In the following algorithm we use the oor and ceiling functions which we de ne by example Let N be 7 Then N2 35 a real number and L35J 3 and F351 4 For any N we have LN2J I NZ I N Note that we also revert to the book s use of 0based arrays Algorithm Mergesort AO N 7 l Input An array AO N 7 l of sortable elements Output The array sorted in non decreasing order Work arrays Two arrays of size l NZ l If N gt l Then Copy A0 LN2J e 1 to BO LN2J e 1 Copy ALN2J N e 1 to CO TN2T e 1 Mergesort BO LN2i 1 Mergesort CO l39Nzl e 1 Merge B C A Merge B and C to give A Else do nothing 7 array of l element must be sorted End If Inspection of this algorithm shows that it is the merge algorithm that does the heavy lifting We present a straightforward implementation of a twoway merge algorithm which can be extended to an Nway algorithm with very little thought Note that the merge algorithm uses at most N comparisons to merge two arrays with combined element count of N Thus merge is a lineartime algorithm The algorithm below is slightly different from that on page 124 of the textbook in its handling of what happens when one of the input arrays has been completely processed At that time the merge algorithm just copies the contents of the other array into the output The doublewhile loops at the end of this next algorithm are a classic approach to this issue Page 4 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes Algorithm MergeBOP l COQ l AOP Q i l I O J O K O Initialize some indices While I lt P And J lt Q Do If Bl lt CJ Then AK Bl l l l Else AK CJ J J l End If Always increment K 7 the index into A K K l End Do At most one of the following loops will execute Again let s apply the Master theorem to this The recurrence equation is TN 20TN 2 N the Merge part taking N steps Using the Master theorem with TN AOTNB FN we see that A 2 B 2 and that FN N 6 N1 and D 1 BD 21 2 so A BD and we have TN e NDologN TN e NologN In a moment we shall investigate quicksort another NologN sorting algorithm and argue that it is on average a bit faster than mergesort However it is provable that any algorithm that sorts by comparison only must be QNologN so this is as good as it gets Page 5 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes Minor Modi cations to Mergesort One of the facts about most of the major algorithms is that people are always trying to improve them by making minor variations Here is one of the most common variations of the mergesort algorithm Algorithm Mergesort AO N 7 l Input An array AO N 7 l of sortable elements Output The array sorted in non decreasing order Work arrays Two arrays of size l NZ l If N gt 2 Then Copy AO LN2J 7 1 to BO LN2J a 1 Copy ALN2J N a 1 to C0 TN2T a 1 Mergesort BO LN2J a 1 Mergesort CO TN2T a 1 Merge B C A Merge B and C to give A Else If N 2 Then Why invoke another If AO gt Al Then recursive call for the Temp Al very simple case of a Al AO two element array AO Temp End If Else do nothing 7 array of l element must be sorted End If Again the student is invited to make an independent assessment of this algorithm Does the expected speedup of the algorithm justify the extra complexity of the extra case The student will note that the condition N gt 2 is first tested so that the extra case is rarely tested This variant appears to be a bit superior to the standard version of the algorithm but there may be an unexpected difficulty that we have not discovered Example of Mergesort On page 125 the textbook shows an example of the mergesort operation As predicted this example has 8 items to be sorted We shall show an example with 10 items in the list Before starting the example let s consider the split when N is an odd number The code is Copy AO LN2J a 1 to BO LN2J a 1 Copy ALN2J N a 1 to C0 TN2T a 1 Let N 5 Then LNZJ 2 and l NZ l 3 Under these conditions we have Copy A0 l to B0 l and Copy A24 to C02 Page 6 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes We now examine the operation ofthe algorithm on the list 3 l 4 l 5 9 2 6 5 3 The rst split divides the list into two sublists each of size 5 The sublists of size 5 are each divided into lists of size 2 and 3 etc 3 l 4 l 5 9 2 6 5 3 Split 31415H92653 More splits 31l415ll92l653 Anothersplit 31415H92653 Merge 13415H92635 Merge 13145H92356 Merge 11345H23569 Final Merge 11 2 3 3 4 5 5 6 9 Two Approaches to Splitting Arrays We have been considering the application of the divide and conquer strategy as a basis for algorithms to sort arrays To nobody s surprise we have been splitting arrays into two parts There are two obvious strategies The rst used by mergesort is to divide the array arbitrarily in half The array Al to N is divided into Al to LN2J and A N2 to N Another approach would be to pick a pivot value Ap with a value ideally close to the average value of the values in the array We then divide the array into two parts Items with value greater than Ap and items with value not greater than Ap Consider the division of the array Al to N split by pivot value Ap into two subarrays L an array of all items of value S Ap R an array of all items of value gt Ap If the pivot value is well chosen the arrays L and R will be of about the same size The next sort algorithm we shall study called quicksort applies this pivot value strategy to split the arrays We shall see that there are a number of strategies designed to pick a good pivot value The problem is that the simple and ef cient strategies can occasionally pick a very poor pivot value for an array while those strategies that can be guaranteed to pick a good pivot value are so complex that they slow the sort algorithm excessively Page 7 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes Quicksort This is a standard sort algorithm developed by CA R Hoare If you have any trouble recalling the name of the developer just think of quickie At the top level the quicksort algorithm has a standard description Algorithm Quicksort A LR Sorts an array using the quicksort algorithm Input A subarray ALR of AONl defined by its left and right indices L and R with L S R Output The subarray ALR sorted in nondecreasing order If L lt R Then S PartitionALR S is a split position so QuicksortALSl element AS is in its correct QuicksortASlR position End If The variations in the modi cations of quicksort are always found in the partition algorithm We shall study one of the more common varieties of the partition algorithm The student should be aware that there are quite a few variants of partition The reasons are quite simple 1 A more sophisticated partition algorithm makes the quicksort less likely to display the poor performance found in the worst cases 2 A more sophisticated partition algorithm takes more time and thus slows the execution of the quicksort Basically the question is how much we want to penalize the average performance of the algorithm to guard against bad performance in the worst case Most people have decided to select a rather simple but ef cient partition algorithm The basic strategy of all partition algorithms is simply stated Given a subarray ALR with R gt L and a pivot element F rearrange the subarray into three parts 1 First only elements that are less than or equal to P then 2 The pivot element F then 3 Only elements that are greater than or equal to P There are a number of strategies for selecting the pivot element from the subarray ALR The simplest method is to pick the first element F AL There are other methods with supposed advantages Here is one Compute index M L R 2 Examine three values AL AM and AR Use the middle value as the pivot If AL lt AR lt AM then P AR There are also several ways to partition the subarray given the value of the pivot element The book discusses one of the more popular ways based on two scans The student is invited to read the book for the justification of this approach We give the algorithm and then show a sample partition in order to illustrate it Page 8 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes The variant of the partition algorithm we use is as follows Notice that the three loops have been labeled as A B and C This will facilitate discussion Function Partition ALR I prefer to call it a function Partitions a subarray ALR defined by its left and right indices L and R with L lt R On output the subarray is partitioned The return value of the function is the split index P AL Pick the pivot value I L J R l Before we do anything we decrement J so this does not cause any problems Repeat Loop A Repeat Loop B I I 1 CAREFUL This can run off the Until Al 2 P end of the array Repeat Loop C J J 7 l This is OK because AL P Until AJ S P swap AIl AJl Until I 2 Swap Al AJ Undo last swap swap AL AJl Return J Before examining a typical instance of quicksort let s look at one of the worst cases the array is already sorted in nondecreasing order Suppose that the array is A09 with AK K so that AO 0 Al l and A9 9 Before loop A begins we have the following initializations PA00 L0 R0 10 J10 Loop B will eXit after one iteration with I l as Al l gt P Loop C will start with J 10 first compare A9 to P and continue to decrement J until J 0 as only AO is less than or equal to P Thus we have partitioned the array into three parts ALSl which is an empty array AO and Al9 In general one can show that if AL is smaller than any other element in the subarray ALR one partitions into an empty array an array of size 1 and an array of size R e L This leads to the worst case behavior Page 9 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes Now we examine a more typical problem instance with 10 elements to be partitioned Note that the fact that J R 1 does not imply the existence of an array element with that index IILI IRIJIPAL3 4 1L JR1 Loop A begins Loop B begins and continues until the index I is set as follows L III RJ 3141592654 Loop C begins and continues until the index J is set as follows LIJR 3141592654 Swap AI and AJ L III J R 3121594654 EndofLoopA JI4sowe go again Loop A begins again Loop B begins and continues until the index I is set as follows Ll I III J R 3121594654 Loop C begins and continues until index J is set as follows Note that J lt I Ll I JI IRII 3121594654 Swap AI and AJ L J I R 3125194654 End of Loop A Note that I gt J so loop A terminates Now swap AI and AJ again to undo the last swap to get L J I R 3121594654 Finally swap AL and AJ to get the partitioned array L J I R 1123594654 Page 10 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes Bina Search Binary search is an efficient algorithm designed to search a sorted a1ray Consider a subarray ALR with L S R that is in strictly nondecreasing order so that I lt J implies AI S AJ Let M L R2 The basic observation is that a search for a key K will have one of three possible outcomes 1 K AM the element has been found 2 K lt AM the element if present will be found in ALM e 1 3 K gt AM the element if present will be found in AM 1R Note that binary search is not strictly an application of the divide and conquer strategy which calls for breaking a problem into a number of smaller problems and solving each smaller problem In binary search we break the problem into two smaller subproblems but solve only one of the subproblems This observation leads to the recurrence for the time complexity of the algorithm TN TN2 1 It is easily shown by the Master Theorem that TN 6 log N There are two variants of the binary search algorithms 7 the iterative version and recursive version We shall present both versions beginning with the iterative version in the book Algorithm BinarySearch AO N 7 1 K Input An array AON 7 1 with N gt 0 sorted in non decreasing order and a search key K Output An index of an array element equal to K or 1 if there is no matching element L O R N 7 l While L S R Do M LltL Rgt2J If K AM Then Return M Else If K lt AM Then R M 7 l Else L M 1 End While Return 7 l Indicates failure We make a few comments on this version then move on to the recursive version 1 One could change the last line to read Return 7 M and indicate a place in the array where the key should be if it were to be inserted 2 This is one of the few places where an obsolete FORTRAN construct would work very well We would write I f K 7 A M 1 0 2 0 30 to indicate the actions to be taken for K lt AM K AM and K gt AM respectively Page 11 of 13 Chapter 4 Last Revised July 20 2010 CPSC 5115 Algorithm Analysis and Design Course Notes The recursive version of binary search is easily written Algorithm BinarySearch K ALR If L gt R Then Return 1 Else M LltL Rgt2J If K AM Then Return M Else If K lt AM Then Return BinarySearchK ALM l Else Return BinarySearchK AMlR End If End If It should be obvious that to search an array of N elements for element K one issues the call M BinarySearch K A0N 7 1 An Equation Solver Based on Binarv Search We now present a robust method for solving an equation FX 0 where FX is any function that can be evaluated easily for values of X Admittedly it does not converge to a solution as quickly as some methods such as Newton s method but it always converges Algorithm BinSolver EX X1 X2 EPS Input A function EX that can be computed and two values X1 and X2 such that EXl lt O and EX2 gt O We may have either X1 lt X2 or X1 gt X2 but X1 X2 EPS is the desired precision for the solution XL X1 YL EXL Evaluate EX repeatedly XH X2 YH EXH Set up the loop below Repeat XM XL XH 20 Produce a real number YM FXM In real number arithmetic it is better not to test for YM 00 but make lYMl sufficiently close to zero If lYMl S EPS Then return XM Else lf YM gt 0 Then XH XM Else XL XM End If Until lXL XHl lt EPS Return XM Page 12 of 13 Chapter 4 Last Revised July 20 2010 Computational Complexity An Overview Lecture View Graphs With Notes on Facing Pages Ed Bosworth Computer Science Department Columbus State University Columbus GA bosworthedwardcolstateedu August 2003 The study of computational complexity is based on some fairly complex and subtle mathematics Despite the formidable challenge of mastering the subject there are many topics that can easily be understood What we plan to discuss in this talk can be understood by any student who has programmed in any highlevel programming language preferably C or Visual Basic has been introduced to basic search and sorting algorithms and has a grasp of elementary algebra We use a number of problems as illustrations of the concept of computational complexity Searching a list Sorting a list where there is a defined comparison operator Matrix addition and multiplication We use C like syntax to illustrate some algorithms It is for this reason that we assume some familiarity with a higherlevel programming language We need some way to write our algorithms For the most part we assume only a basic knowledge of algebra39 the student being familiar with the following Logarithms either base 10 or natural logarithms Polynomials especially linear quadratic and cubic functions Exponential functions normally ex where e is the base of the natural logarithms The factorial function depicted as n for nonnegative integers n A bit of calculus really real analysis is used for those who like it but an understanding of calculus is not necessary for the understanding of this talk The calculus used relates to the limit of a function fn as n becomes very large informally as n gt 00 that s lazy eight for you nonmathematicians BACKGROUND ASSUMED Some programming experience maybe in Visual Basic 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 We have a number of concepts to examine The first is the diVision of the study of algorithms into four topics Problems a precise statement of something to solve It must state its parameters and declare what the structure of the desired solution should be Strategies These are general approaches to solVing a class of problems39 perhaps better Viewed as guidelines for creating algorithms Algorithms These are precise statements of the process to be used in solVing a specific problem One definition of an algorithm is that it is a sequence of nonambiguous instructions for solVing a problem in a finite amount of time l Within the field of Operations Research an algorithm is also expected to provably produce an optimal least cost or maximum profit solution Programs the implementation of an algorithm in a specific programming language using the constructs and data structures of that language We also mention here a number of complexity classes applied to characterize problems P NP NP Hard NP Complete Provably Intractable Unsolyable For the moment we just list the names We shall define these terms very shortly but note here that these terms classify a problem by the amount of time required to produce a solution 1 page 39 of the book Introduction to the Design amp Analysis of Algorithms Anany LeVitin published by AddisonWesley in 2003 ISBN 0201743957 Overview Problems Strategies Algorithms amp Programs Time Complexity Classes P NP NPComplete Provably Intraetable Unsolvable We now return to discussion of the four categories problems strategies algorithms and programs This slide shows some examples of each of these categories used to discuss our topic To make the distinction a bit clearer let us discuss a somewhat reasonable analogy taken from cooking Problem Strategies Algorithms Program prepare a potato to be eaten assuming that it is not to be eaten raw The basic applicable cooking strategies are Boiling Broiling Baking Frying Notice that none of these cooking strategies specifies how it is to be done but just a highlevel approach to solVing the problem of preparing the food to be eaten The algorithms in cooking are called recipes although a recipe in cooking assumes a considerable amount of common knowledge not allowable in the specification of an algorithm Consider a recipe that specifies to fold in ten whole eggs Most I hope all cooks know that a whole egg does not include the shell of the egg although the recipe nowhere says to discard the shell The program might correspond to the recipe along with the eXplicit choice of ingredients The analogy admittedly breaks down at this level of detail We should also define an instance of a problem This is the problem along with a specific input Thus addition of integers is a problem while 5 7 is an instance of the addition problem Similarly sorting a list of items is a problem while sorting the list of integers 3 l 4 l 5 9 2 6 5 3 5 7 9 8 9 is an instance of the sort problem 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 are the ones for which the only algorithmic solutions are generators of every possible solution with the provision of recording the best solution found up to the moment The problems that have classically been proven to be intractable include tiling a oor with irregularly shaped tiles This problem is somewhat related to that of working a jigsaw puzzle with all the pieces turned over so that there are no colors to give clues The best example of a problem with an intractable solution is the Traveling Salesman Problem T SP although that problem is not provably intractable The TSPOptimization problem is simply stated We are given a set of cities with the distance between each pair of cities defined in a table We are to produce a tour of all of the cities beginning in a given city it does not matter which visiting all of the other cities exactly once and returning to the original city Each tour has an associated cost The problem is to find the lowest The only known way to produce a provably optimal solution to TSP is to try all possible tours The basis of the algorithm is the brute force design strategy to produce a list of all possible tours and evaluate each Viewed this way TSP is an intractable problem The reason that TSP is not correctly classified as an Intractable Problem is that we cannot prove that this algorithm is the only way to solve it39 there might be an algorithm that is considerably better We shall see later that were one to prove that the bruteforce list all routes approach is the only way to solve the problem then the problem would be properly classified as intractable and the discoverer of the proof could line up for a number of prestigious awards and cash prizes Consider a tour of 11 cities The complete listing of tours will require consideration of 10 3628800 different tours That is quite a number A heuristic is defined as a commonsense rule drawn from experience rather than from a mathematically proven assertion 2 Algorithms are generally based on mathematically proven assertions 2 page 386 of the book Introduction to the Design amp Analysis of Algorithms Anany Levitin published by AddisonWesley in 2003 ISBN 0201743957 Intractable Problems Characteristic Try every solution and see if one works 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 It should come as no surprise that there are problems that cannot be solved by computer Unsolvable problems come in two varieties problems that are provably not solvable and problems for which we just do not yet know a solution There are a number of famous problems that are provably unsolvable Consider the geometric problem of trisecting an arbitrary angle While there are certain angles such as 270 degrees for which trisection is accidentally possible it can be shown impossible to trisect divide into three equal parts an arbitrary angle The proof is by an adversary argument If you have a method that will trisect any angle it must be able to trisect an angle of 60 degrees that is divide it into three angles of 20 degrees each It can be shown that such a trisection of this one angle gives rise to a solution to an algebraic equation for which it can be proven that no solution eXists Thus one cannot trisect an angle of 60 degrees and hence the procedure for trisecting an arbitrary angle does not eXist 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 We now focus on the issue of efficiency of algorithms This subject is somewhat different from the efficiency of programs the difference is significant Consider the factors that enter into the efficiency of a running program Certainly we have the efficiency of the algorithm but we also have the nature of the computer processor speed amount of memory and IO bandwidth are certainly factors and to some extent the particular instance of the problem In the study of algorithms we desire a measure of efficiency that is computer independent Of course it is always possible to speed up the execution of a program by running it on a faster computer with more memory For some problems this may actually be the only solution For most problems it is not the preferred solution Even in these days of cheap computers it is often cheaper to develop a more efficient algorithm than it is to buy new computers for the people who need the problem solved One of the more extreme examples of the advantage of a better algorithm comes from the area of cryptography Consider the simple monoalphabetic substitution cipher in which each letter is replaced by another letter In one view this is an unbreakable cipher there are 26 possibilities for the letter A 25 for B as the letter for A is taken 24 for C etc Thus there are 26 m 40329 0 1026 different keys for such a cipher The brute force approach to solving such a cipher is to generate all possible keys and find the key that generates a believable solution There is a slight gain in efficiency due to the fact that on average only half of the possible keys would be generated A computer that could generate one billion 109 trial keys per second would require on average 64 billion years to generate the proper key Based on this one could find a computer that was a million times faster and cut the solution time to 6 400 years or look for another algorithm Most of us would prefer the second option As a matter of fact there is a much better algorithm for cracking the monoalphabetic substitution cipher This algorithm is based on the observed frequency of letters in English text Given enough cipher text generally one needs less than 30 words enciphered this way a person can reliably crack a monoalphabetic cipher in less than a day using only pencil and paper This is quite a bit better than the 6400 years that even an impossibly fast computer would require using the brute force approach 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 As we noted above we are moving away from time in seconds as a measure of the efficiency of an algorithm If we do not use clock time to measure the efficiency what shall we use The answer is that we use basic steps An algorithm is conventionally defined to be a finite set of instructions which if followed lead to the solution of any specific instance of a general problem Within each algorithm we should find a number of basic steps which characterize the total work of the algorithm We select these basic steps with the understanding that measuring the number of executions of these basic steps will be a reasonable measure of the total number of instructions executed by the algorithm We often select as basic steps those instructions that take the larger amount of time to execute Consider the problem of sorting a list of items in which there is an established operator with which to compare the items The basic operation in such an algorithm is the comparison of two items We claim that a count of the number of key comparisons the key is what is used to compare the items yields a reasonable estimate of the total number of steps in the algorithm and thus the total clock time to run it on a given computer Where we are going with this argument is the development of a function TN to express the number of basic steps in the algorithm followed by an approach to characterize the function TN We now understand that if T TN then T is the run time expressed as count of basic steps but what is N Informally N is the size of the problem Formally N is the number of binary bits 0 or 1 required to encode describe an instance of the problem Informally we define N by example For the searching problem N is the number of items to be searched For the sorting problem N is the number of items to be sorted For the TSP Traveling Salesman Problem N is the number of cities to be visited For arithmetic algorithms such as factoring integers N is the number of digits in the integer The big question is simply stated If it takes so much time to solve the problem with this size input how much time will be required to solve an input that is twice as big 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 In order to do our work we need a way to see the big picture about functions We are used to this approach from our days in highschool algebra where we classified polynomials as linear quadratic cubic quartic etc Note that the two functions FX X2 l and GX 7X2 9X 15 are both quadratic Admittedly for every X 2 0 we have GX gt FX but we still say that the two functions are similar in that they grow quadratically To formalize this notion of growth rates of functions we borrow and adapt some notation from mathematics This notation is the Big 0 Big Q and Big 9 notation The functions that we in Computer Science describe with this notation always yield positive numbers nobody has found an algorithm with negative run time and nobody is interested in an algorithm with zero run time so we adapt the mathematics notation by dropping the absolute values found in some of the original notation Some times we want to say that a function FN grows no faster than a given function GN The Big O notation is useful here39 we want to show that FN is OGN At other times we want to say that the function FN grows at least as fast as a given function GN The Big Q notation is useful here39 we want to show that FN is QGN There are also times in which we want to say that the function FN grows exactly as fast as the function GN39 in this case we use the Big 9 notation and want to show that FN is GN Consideration of the above discussion gives us one of our first theorems in the analysis of algorithms FN is GN if and only if both FN is OGN and also FN is QGN Polynomial functions are easy to characterize All linear functions of N are N all quadratic functions of N are NZ all cubic functions of N are N3 etc Logarithmic functions and exponential functions are also easy to characterize Some mixed functions such as NoLogN require a bit more work We are interested in three broad classes of characterizations logarithmic polynomial and exponential Mixed functions such as NoLogN are considered polynomial for reasons shown below 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 Let us consider the class of functions called exponential This class is defined to be the set of all functions that are 92N they grow at least as fast as the exponential 2N It comes as some surprise to students that the factorial N is considered exponential but it is easy to prove that n e 92N we do it by the following lemma Lemma For N 2 4 N gt 2N Proof We first note that 4 24 gt 16 24 the inequality is false for N lt 4 We proceed to note that ifN gt 2N for N 2 4 then N1 N1oN gt 4oN gt 42N gt 2N One can also show that for N 2 7 we have N gt 3N gt eN gt 2N so N is definitely exponential Recall that the number e m 2718 is the base of the system of natural logarithms To show the growth rate of the factorial function we consider the claim that the number 100 can be called astronomical We demonstrate that this number is far beyond any quantity legitimately associated with the study of astronomy We give this demonstration for a number of reasons 1 To convince the student that the factorial function does grow very fast 2 As an illustration of some ways to computer numbers without use of a calculator 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 In these two slides we establish an extremely high lower bound for the number 100 One could further refine this estimate to obtain a higher number but this is sufficiently high One might use the approximation known as Stirling s Formula to get a better approximation of N N N mx 211N o 7 where e is again the base of the system of natural logarithms 6 My calculator gives the value of 100 as approximately 93326010157 so the derived lower bound of 3010152 is not too far off the mark Note that each of these values is enormously above the largest reasonable astronomical value of 1078 the estimated count of elementary particles in the known universe 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 We now give some examples of the use of the Big O and Big Q notation Remember that Big 0 determines the an upper limit of the growth rate of a function and that Big Q determines a lower limit The first statement that logN is ON merely states the obvious fact that the logarithmic function does not grow as fast as a linear function There are a number of ways to establish this fact The slide gives the straightforward application of the class ON Recall that we said that fn is Ogn if there exist positive integers K and N such that for all n 2 N fn S Kogn Here we want to prove that the function LogN is ON so we requote the above statement as LogN is ON if there exist positive integers K and N such that for all n 2 N LogN S KoN For this case we set N l K l and see that all n 2 l LogN S N The next statement leads us to the conclusion that when we label a function OLogN we do not need to specify the base of the logarithms Specifically for any N there exist positive finite real numbers such that log2N AolnN Bolog10N where log2N is the log ofN to the base 2 In terms of this new notation we have all three statements as true 10g2CN is 1HCN iiiCN is 10g10N 10g10N is 10g2N The clear implication of this statement is that any logarithm base will serve when we make statements on the time complexity of a function We now revisit the important mixed function NoLogN The following two are easily shown NoLogN is QN because for all N gt 1 we have NoLogN 2 N NoLogN is ONZ because for all N gt 3 we have NoLogN S N2 As a matter of fact NoLogN is best expressed as having complexity NoLogN Many very important sort algorithms have this time complexity Diversion into Some Mathematics Including Calculus We now make a few statements most of which will appeal only to those of us who like mathematics The first statement is fairly obvious and easily proven Lemma FN is OGN if and only if GN is QFN We now dabble in a bit of calculus involving the limits of functions of N as N approaches infinity FN is OGN if and only if bllim K for K 2 0 a finite number FN is QGN if and only if bllim K for K 2 0 a finite number FN is GN if and only if bllim K for K gt 0 a finite number Consider FN N and GN N2 We make the following statements FN is OGN because b13330 big brig 0 FN is not QGN because bllim lim N gm which is not a finite number FN is not GN because bllim 0 which is not a positive number Also it is obvious that FN is not GN because FN is not QGN Consider FN 7N2 13N 45 We say that FN is quadratic or FN is NZ 2 FCN is NZ because lim Faj im W Eisz 7 Ngtoo N N N N im7 Ngtoo Ngtoo 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 We now have the tools to speak of the big picture in examining the time complexity of an algorithm The basic steps for establishing the time complexity of an algorithm are simple 1 Determine the basic steps in the algorithm 2 Determine a way to count these basic steps let TN be that count 3 Determine the complexity of the time function TN We have three classes of algorithms according to the time complexity TN of the algorithm Logarithmic TN is Olog N Polynomial TN is ONK for K gt 0 Exponential TN is QeN note that this is the only class for which we consider the lower bound There are algorithms that are superexponential or worse that exponential in a number of ways We class these as exponential under the philosophy that worse than bad is still bad The careful reader will note that any algorithm that falls into the logarithmic complexity class also falls into the polynomial complexity class because log N grows more slowly than N We generally label an algorithm by the best class into which it can be placed If TN is ONolog N we call the time complexity polynomial because TN grows more slowly than N2 The polynomial class excludes K 0 If K 0 then NK l for all N gt 0 An algorithm is said to be Ol if it runs in constant time without regard to the size of the input in other words TN is not a function of N the size of the input Such algorithms are fairly rare and generally not useful 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 We now note that most problems can be solved by more than one algorithm For example there must be at least a dozen search algorithms and probably at least one hundred sort algorithms The time complexity of a problem is related to the time complexities of all algorithms known to solve the problem Basically the time complexity of a problem cannot be worse that the time complexity of the fastest known algorithm known to solve the problem Consider the problem of sorting a list of N items by comparison only We know a number of sort algorithms some haVing time complexity ON2 and some haVing time complexity ONolog N Based on this we say that at worst the time complexity of the sort problem is ONolog N because that it better than ON2 At this point we cannot truly classify the time complexity of the problem as that requires more work What we do know it that the complexity of the problem is either logarithmic or polynomial Remember that TN Nolog N is considered a polynomial time complexity function despite the fact that the function Nolog N is not a polynomial This is because for all N gt 3 we have N S Nolog N S N2 The student should also note that the existence of algorithms with poor time complexity does not affect the time complexity of a problem unless all algorithms known to solve the problem have poor time complexity This author has deVised an exponential time algorithm for sorting a list by comparison39 to be honest it is just plain silly Classification of problem complexities is done by upper bound analysis for both logarithmic and polynomial complexity classes The lower bound on time complexities of algorithms is used to establish a problem in the exponential complexity class One must be careful here as there are two possibilities If all algorithms known to solve the problem have exponential time complexity have TN e OeN then the problem might be in the class exponential time complexity However a problem can be classified as haVing exponential time complexity only if it can be proven that any algorithm that solves the problem must have exponential time complexity 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 The lower bound of the time complexity of a problem can only be established by theoretical analysis For most problems this is fairly difficult to do It is not enough to list the time complexity of every algorithm known to solve the problem and compare their time complexities Consider the Traveling Salesman Problem All algorithms known to solve this problem exactly have exponential time complexity However it cannot be proven that any problem solving TSP must have exponential time complexity so it is still theoretically possible though highly doubted that the problem has polynomial time complexity A number of highly talented people have attempted to prove that the TSP has exponential time complexity though nobody has yet come close to the proof There are two wellknown problems for which theoretical lower bounds can be placed on any algorithm that can solve them These are the search problem and sort by comparison problem The results are as follows Search an Ordered List The problem is Qlog N Sorting by Comparison The problem is QNolog N There are wellknown algorithms for searching an ordered list that have time complexity Olog N and wellknown algorithms for sorting by comparison that have time complexity ONolog N Based on this we say that each of the two problems is a well understood problem The student should note that sorting by comparison is not the only way to sort People usually do not sort cards by comparison thus we do not compare the Ace of Spades to the Queen of Hearts The problem of sorting a list in which the items such as cards can be placed into distinct categories has a solution that is ON 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 We now consider a simple example of a lower bound argument for a problem We consider the two problems of matrix addition and matriX multiplication in fact we consider any algorithm that assigns values to the elements of a matriX The argument is simple Consider an N by N array The array has N2 elements If distinct values are assigned to each of the elements we must have N2 assignment statements For this reason we claim that l the problem of adding any two N by N matrices is QN2 and 2 the problem of multiplying any two N by N matrices is QN2 These are robust lower bounds for these array problems and any array problem that possibly can allot different values to the elements of the array 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 the problem of matrix addition We have just shown that the problem of adding two N by N matrices must be QN2 We now show an algorithm for adding two matrices that is ON2 This is the wellknown algorithm HaVing a single algorithm that is ON2 and knowing that the matriX addition problem is QN2 we conclude that the addition problem is well understood 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 the problem of matrix multiplication We have shown that the problem is QN2 ie that any algorithm that solves the matrix multiplication problem must have TN e QN2 We have at least three algorithms known to solve this problem The wellknown algorithm has time complexity TN e ON3 Strassen s algorithm has time complexity TN e ON239807 where 2807 log27 The algorithm of Coopersmith and Winograd has time complexity TN e ON239376 Since the problem is QN2 there is no proof that we cannot find an ON2 algorithm that solves it The fact that it seems unlikely that we can find an algorithm that beats the result of Coopersmith and Winograd does not make it impossible that one should be found The only thing that can be said about the time complexity of the matrix multiplication problem is that it is polynomial 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 n j The following step is executed n2times cij 0 0 k lt n k for int k This step is executed n3 times Cli j Cli j ai1k bk1j 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 We now consider a classic problem probably invented in the 19th century by the French mathematician Edouard Lucas The problem is set in a Hindu temple in India but is called the Towers of Hanoi suggesting a setting in Vietnam All thatI can say personally is that I have yet to find a Vietnamese or Indian student willing to own up to the legend belonging to his or her country We discuss this problem because it allows a good proof of eXponential time complexity The Towers of Hanoi is not really an algorithm but a process We are asked to determine the minimum number of steps to complete the process The problem involves a number of disks and the goal is to move the disks under specific constraints In computing TN for the process we note the following N is the number of disks in the problem TN is the number of moves to complete the problem The problem is postulated as a set of three pegs Lucas specified diamond pegs with a number of disks on one of the pegs We traditionally number the pegs l 2 and 339 although a modulo3 numbering as 0 l and 2 would make the algorithm a bit easier to eXpress The goal is to move all of the disks from one peg say peg l to another peg say peg 2 while moving only one disk at a time and never placing a larger disk on top of a smaller disk In Lucas s story there were 64 gold disks on diamond pegs being moved one at a time day and night by a group of monks The claim in his story was that when the moves were complete the universe would end There are two algorithms that prescribe the moves to complete the process an iterative algorithm and a recursive one The recursive algorithm serves as a basis for computing TN We specify the iterative one here 1 Move the smallest disk one peg to the right under the following definitions Peg 2 is to the right of peg l peg 3 is to the right of peg2 and peg l is to the right of peg 3 2 Make the only other legal move not involving the smallest disk 3 If the process is not complete go to step 1 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 We now make the following observation which forms the basis of the recursive algorithm and allows a solution for the time complexity of the process To move N disks from peg 1 to peg 2 observing the constraints it suffices to do the following 1 Move N 1 disks from peg 1 to peg 3 observing the constraints 2 Move the largest and bottom disk from peg 1 to peg 2 3 Move N 1 disks from peg 3 to peg 2 observing the constraints Note that step 2 involves only the largest disk Note also that steps 1 and 3 involve repeatedly placing other disks on top of the largest disk but that this can never violate the constraint This gives rise to the recurrence for TN TN 20TN 1 1 It obviously takes 1 step to move 1 disk so Tl 1 Applying the recurrence we see that T2 201 1 3 T3 203 1 7 T4 207 1 15 etc We postulate the formula for TN as TN 2N 1 and use induction to prove it We already have a number of base cases for the inductive proof so we postulate TN 2N 1 and prove that TN1 2N1 1 IfTN2N 1thenTN12oTN1 2o2N 11 2o2N 2 1 2N1 1 and the claim for the time complexity is proven Later we shall show a formula for obtaining TN directly from its recurrence relation For those worrying about the end of the world moving 64 disks would take 264 1 steps which is approximately 184501019 Should the monks move 1 disk per second the process would take 586 01011 years 586 billion years or almost 40 times the best estimate of the age of the universe I find it hard to worry about things that distant 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 We next discuss a class of problems that facilitate the theoretical analysis of algorithms This class is called decision problems and comprises all the problems for which the answer is either Yes or No Associated with the idea of decision problems is the concept of verifying a solution and the time complexity of the algorithm to verify a solution It is often the case that the algorithm to verify a solution runs more quickly than the algorithm to create the solution it certainly does not run more slowly Consider the problem of sorting a list of N numbers by comparison only We already know that the time complexity of the best algorithms to do this job is TN e ONolog N Now consider an array filled with the numbers We can verify that the array is sorted merely by comparing adjacent pairs of numbers ie verifying that aO S al al S a2 and so forth to an 2 S an l Note that it has taken only N l comparisons to verify the claim that the array is sorted assuming that it is sorted If the array is not sorted then at takes at most N l comparisons to show that it is not sorted The fact that the determination can be done so quickly is due to the fact that the array has a comparison operator imposing a total order Thus if aO S al and al S a2 we know that aO S a2 etc Many other decision problems allow the solution to be verified in linear time or at least in polynomial time What we are saying is that the verification algorithm has polynomial time complexity often linear time complexity Note that most optimization problems cannot be so quickly verified Suppose thatl give you a TSP and claim that the length of the minimum tour is 980 miles Suppose also that I give you a tour with total length exactly 980 miles That does not verify the claim but only shows that the length of the optimal tour is not more than 980 miles The only way to verify that 980 miles is the shortest tour is to compute all other possible tours and show that no other tour has a total distance less than 980 miles This verification takes a lot of work So we now have an important class of problems and an important mechanism for quickly verifying the solution TSP can be cast as a decision problem The instance above cast as a decision problem does not make claims about the optimal solution but only asks if there is a tour with total distance not exceeding 980 miles If we produce such a tour its total distance can be computed in linear time and the claim quickly verified 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 We are now ready to state an important definition The class P is the set of decision problems for which there exists an algorithm with polynomial time complexity to solve it In our somewhat informal language the class P is that set of decision problems that have polynomial time complexity We also informally include other problems in the class P if the problem can be solved by a polynomial time algorithm Thus searching sorting matrix addition and matrix multiplication might be said to be in the class P although the claim would infuriate a number of mathematicians There is a formal extension of the class P to include nondecision problems solvable in polynomial time but this author has forgotten its name 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 As noted above optimization problems are often associated with decision problems This slide presents TSP both in its optimization and decision form It can be shown that the decision and optimization problems are logically equivalent We show one way of the equivalence and hand wave at the other It is easy to show that a solution to the optimization problem immediately yields a solution to the decision problem Suppose that we do the optimization problem and show that the shortest route has total length of 970 miles Then we can answer any decision version of the problem by comparing this to the known optimum Is there a tour with total length not exceeding 1000 miles You bet the shortest one is 970 miles If the distances are given as integer values it is easily shown that repeated solution to the decision problem will yield a solution to the optimization problem This repeated solution searches for values with a modified binary search algorithm Given an optimal distance of 970 miles we might proceed somewhat as follows Is there a tour less than 1000 miles Yes Is there a tour less than 900 miles No OK I am speeding up binary search Is there a tour less than 950 miles No Is there a tour less than 975 miles Yes Is there a tour less than 963 miles No Is there a tour less than 969 miles No Is there a tour less than 972 miles Yes Is there a tour less than 970 miles No Is there a tour less than 971 miles Yes the optimal tour is 970 miles Note that the above use of the decision problem to solve the optimization problem relied on the assumption that the total distance was an integer If the total distance is a real number one has to decide on the precision necessary to obtain a satisfactory answer 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 The next slide is just a joke It will have meaning only to those people who have to y a lot We used to say in Huntsville AL that you could not die and go directly to heaven but first had to be routed through Atlanta Side Remark The Real Version of the Problem Nashville Knoxville Atlanta Augusta Birmingham No such tour exists All ights must go through Atlanta Here we list a few notes on the solution to the Traveling Salesman Problem The first is the obvious remark that one can select the beginning city at random since the tour must go through all of the cities For N cities one has N 1 choices for the second city N 2 choices for the third city etc a total of N 1 possible routes Again note the statement that the only algorithms known to solve TSP have exponential time complexity This does not imply that there are no algorithms to solve TSP that have polynomial time complexity only that we do not know of any We suspect that there is no polynomial time algorithm that can solve the TSP but cannot prove that no such algorithm exists This for the theoreticians is quite a challenge Note however that there are a number of restricted versions of the TSP that do admit polynomial time solutions One is the rather practical application to situations in which plane geometry applies specifically the rule that the hypotenuse of a triangle is not longer than the sum of the lengths of the other two sides There are other efficient algorithms to get a solution that might be good enough Although it is quite difficult to obtain the distance of an optimal TSP tour it is quire easy to put a lower bound on this optimal distance Consider a graph representing an instance of the Traveling Salesman Problem This graph has the distance between each of N o the N nodes stated for a total of 2 J w d1stances Sort these distances it takes polynom1al tmie and choose the N smallest distances The total of these N distances is a lower bound on the minimum total distance of the TSP tour as the tour must traverse N links between the cities It is possible that this sum of the N smallest distances might actually be the answer to the TSP but it usually is not Given this lower bound on all possible answers to TSP we can then evaluate any answer obtained quickly by an approximation algorithm It has been found that many very useful algorithms will quickly determine a solution that does not exceed 150 of the theoretical minimum answer For some applications that is close enough 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 In giving a precise definition to the class NP we are asking a simple question what exactly does it take to prove that a given problem cannot be solved by an algorithm of polynomial time complexity At this point in the precise theory we introduce the Nondeterministic Turing Machine For this lecture we call that machine the perfect guesser and define that term within the context of a problem such as TSP in which a number of decisions must be made We have said that the TSP is a tour of N cities starting at any city desired At the first city we must choose which of the N 1 other cities we are to visit next At the second city we choose which of the N 2 unvisited cities we are to visit This continues until we get to the city that is next to last in the tour at which time we have only one choice to visit the last city followed by only one choice to return to the first city Suppose a computer that can instantly select the next city to visit This is not realistically possible as it is generally thought impossible to construct a magic crystal ball Admittedly it is possible to generate an algorithm that will always pick the next city correctly but all known algorithms to do this have exponential time complexity We are postulating a machine that will make each pick in polynomial time and thus solve the TSP in polynomial time If such a machine exists it might be possible to find a realistic algorithm that solves the problem efficiently Consider a problem so difficult that one cannot even imagine a magic ball that will solve it in polynomial time It is then a certainty that no realistic algorithm can solve the problem in polynomial time and that the time complexity of the algorithm must be exponential or worse The class NP thus identifies the set of problems that potentially do have polynomial time solutions including those that actually do have such solutions We now state a famous wellknown theorem P g NP To understand this note these informal definitions P the set of all decision problems that have polynomial time solutions NP the set of all decision problems that possibly have polynomial time solutions If a problem does have a polynomial time solution we note immediately that it possibly has one thus the set inclusion Put another way all decision problems that do have efficient solutions are part of the class NP 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 There is one other property that all problems in the class NP share Remember that every problem in the class NP is a decision problem This other property is polynomialtime veri ability which means that there eXists an algorithm with polynomial time compleXity to verify the solution Often times this verification algorithm operates in linear time but only polynomial time is required We noted above that optimization problems do not admit polynomialtime verification as one must check almost all other possible answers in order to verify a claim We should clarify what we mean by almost all other solutions This relates to the fact that some partial solutions can be pruned Suppose that we are at city N K 1 lt K lt N in a tour of N cities in the TSP optimization problem There are K more cities to be visited in this tour all beginning with the N K cities that we have already chosen This implies that there are K tours all beginning with this selection of N K cities that should be considered At this point we assume that we have generated a number of complete tours and recorded the shortest tour so far discovered along with its total distance Suppose that the shortest known tour has a total distance of 980 miles Suppose also that at city N K in the set of tours currently being generated the total distance of the tour so far is 990 miles Then each of the K tours based on this first choice of cities must have a tour distance exceeding 990 miles and none can be optimal so we discard all of these tours and look elsewhere pruning the search tree There is a leftover from the last slide that we should address here In the comments to that slide we said We now state a famous wellknown theorem P g NP To understand this note these informal definitions P the set of all decision problems that have polynomial time solutions NP the set of all decision problems that possibly have polynomial time solutions This statement does not follow common English usage in that the set NP includes all problems that actually do have polynomial time solutions Consider the set NP P which is the set of all problems in NP but not in P NP P is the set of all decision problems that might have polynomial time solutions but have not yet been shown to have polynomial time solutions This set may or may not be empty 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 next slide gives a very informal characterization of the time complexity classes We have two classes that are not very interesting for an algorithms class and two that form the basis of our study The two classes of problems that are not of interest to an algorithms course are the following P all problems in this class have wellknown polynomialtime solutions All of the important problems in this class should have been covered by a lowerlevel course Undecidable none of the problems in this class can be solved so no algorithms exist for any of them We now turn to the other two classes NP and Intractable All problems in these two complexity classes share the property that any algorithm known to solve the problem has exponential time complexity An advanced algorithms class can be viewed as a study of approaches to solving these problems with the hope that we might get some good solutions fairly quickly Many of the graph traversal methods studied in this course are embedded into algorithms to solve problems in these two classes 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 all problems in NP very unlikely It cannot be proven that such algorithms do not exist We now come to a very important class of problems the class NPComplete We begin with a statement that is wellknown and almost obvious NPComplete C NP Note that the set inclusion is proper stating the wellknown fact that there are problems in the class NP that are not in the class NPComplete NPC In fact the class NP NPC is known to contain many problems Recall that NP NPC the set of all problems in NP that are not also in NPC Since NPC C NP it follows that every problem in the set NPC and more than 1000 problems have been proven to be in this set has the property that while all known algorithms to solve the problem have exponential time complexity it is not possible to show that the problem cannot be solved by a polynomial time algorithm We now come to the important feature of problems in the set NPC These problems are all equivalent in the sense that each problem has the identical complexity Put another way if one can show a polynomialtime algorithm to solve any one of these problems then one can show a polynomialtime algorithm to solve each of the more than 1000 other problems in the class Note that this is not what the mathematicians call an existence proof that finding the polynomialtime solution to one of these problems means that it is theoretically possible to find a polynomialtime solution to another problem in the class and good luck in trying What it means is that a polynomialtime solution to one problem in the class forms an immediate basis for a polynomialtime solution to every other problem in the class and that these other solutions can be generated automatically by wellknown procedures Put another way solve one problem efficiently and you already have solved them all efficiently The ip side to the above statement is also important If one can prove that one only one of the problems in this set NPC cannot be solved by a polynomialtime algorithm then it follows that none of the problems in the set can be solved by a polynomialtime algorithm It is the common consensus that none of the problems in the class NPC can be solved by a polynomialtime algorithm but a consensus is not a proof The Problem Class NPComplete 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 NPComplete We now come to one of the most famous open questions in theoretical computer science Is P NP Each of the problem classes P and NP is a set and can be discussed with set notation It is a wellknown and easilyproven result that P g NP The question comes down to whether or not the set inclusion is proper Put another way is P C NP39 that is do there eXist problems in NP that are not in P Put another way is the set NP P an empty set or is there at least one problem in P that is not in NP What would a problem in the set NP P look like It would be a problem for which there is no known polynomialtime algorithm but for which there eXists a polynomialtime nondeterministic algorithm the old magic ball trick The eXistence of the nondeterministic algorithm continues to suggest that it might be possible to have a standard deterministic algorithm that has polynomial time complexity But this suggestion gives no help in establishing a proof and may be nothing more than wishful thinking The bottom line is that after a lot of work by some very smart people nobody knows We see another important property of the problem set NPC If any problem in the set NPC can be proven to have a polynomialtime solution then they all do and we have proven that P NP or alternately that the set NP P is empty Such a demonstration would be a major achievement in theoretical computer science 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 NPComplete problem would immediately imply that P NP So we get to the punch line of this talk We have identified the challenges for an advanced course on algorithms Ignore the problems that are easy to solve and the problems that are impossible to solve and focus on the other problems These problems share the property that research into more efficient solutions may bear fruit and will always be of value There are a number of open questions related to the class NPC and all are quite challenging We hope that the students in this class might be tempted to tackle one of the problems Chapter 10 Limitations of Algorithm Power At the beginning of the class we discussed a number of approaches to this subject We mentioned that we could consider problems strategies algorithms and programs At this point we restate these categories Algorithms can be de ned as formal wellde ned approaches to solving problems When algorithms are adapted to run on computers we call them programs We have noted that there are a number of strategies for designing algorithms in that many algorithms for different problems share common design approaches At this point we focus only on problems and algorithms Each problem of interest is usually solvable by a number of algorithms It is quite simple to assess the time complexity of a given algorithm We now address the more dif cult question of the time complexity of a speci c problem that is to specify the lower bound on time complexity on any algorithm that solves the problem Some lower bounds are simple even trivial Other lower bounds have de ed every attempt up to present to compute a meaningful value One of the best ways to introduce this chapter is to quote from the standard source on this subject the monograph by Michael Garey and David Johnson published in 1979 with the title Comnuters and Intractabilitv A Guide to the Theory of NP 39 This book opens with a hypothetical example You are the chief algorithm designer for a manufacturing company Your boss presents you with a problem for which you can nd no algorithm more ef cient than examining every possible solution to the problem and ranking the cost of each solution Since this approach is prohibitively expensive you decide to report to your boss What do you say 1 I can t nd an ef cient algorithm I guess that I mjust too dumb 2 I can t nd an ef cient algorithm because no such algorithm is possible 3 I can t nd and ef cient algorithm but neither can all these famous people The goal of this chapter is to allow the student to select one of the latter two answers and avoid being dismissed for incompetence In our discussions we shall use N as the size of the problem except when referring to square matrices the size of which we shall denote as N by N Thus we sort a list of N items search a list of N items factor an integer of N digits thus of magnitude between lON391 and lON or plan a tour of N cities We now state a trivial lower bound Trivial Lower Bound If any algorithm solving a problem must process a list of N items then any algorithm must be QN and thus the problem is QN We note here that the problem of searching an ordered list is Olog N because the search does not need to examine all of the N items in the ordered list We also note that the trivial lower bounds are sometimes quite meaningful as when we establish that the problem of adding NbyN matrices is QN2 because it involves examination of N2 elements A lower bound on computational complexity is considered to be tight if there exists an algorithm with that complexity Consider two problems associated with matrix arithmetic matrix addition and matrix multiplication Each of these involves processing an NbyN matrix and thus each of these problems must be QN2 Let s compare these two problems with another famous problem the Traveling Salesman Problem TSP which is also easily N W N N 1 j 2 shown to be QN2 as it must process K 2 intercity distances But one glance at the following table will show that we have vastly different scenarios Problem Lower Best Known Comment Bound Algorithm Matrix Addition QN2 0N2 Lower bound is tight Matrix Multiplication QN2 0N239376 Lower bound is not too bad TSP QN2 02N Lower bound is useless Decision Trees and Lower Bound Arguments We now discuss a method that can give nontrivial lower bounds for two problems of interest searching an ordered list of N items and sorting a list of N items The lower bound for each of these two problems is established by use of binary decision trees Although other decision trees are possible indeed ternary decision trees are discussed in the text we restrict ourselves to binary trees because we are dealing with operators having two results Search the operator is equality with two results or at Sorting the operator is either 2 with two results 2 or lt or S with two results S or gt The basic lower bound result depends on the fact that a binary tree of height H cannot have more than 2H leaf nodes Thus given a binary tree with L leaves we obtain the lower bound on the tree height as H 2 l logz Ll thus a binary tree with 8 leaves must have height at least 3 In a decision tree each leaf node represents a possible outcome ofthe sequence of decisions while each interior node represents a decision Thus if a problem modeled by a decision tree has L possible outcomes then the decision tree has L leaf nodes and a binary decision tree representing the problem must have height at least l logz Ll This observation places a lower limit on the time complexity of any algorithm that solves the problem We use binary decision trees to examine three different problems and skip the ternary trees 1 The maximum of a number of elements 2 Searching an ordered array 3 Sorting an array of N elements with a defined comparison operator Maxlmum ofThree Elements Here rs the brnary deersron tree for determrnrng the maxlmum ofthree elements For srmplrerty we assume that the elements are drstrnet A B A c andB c 1n thrs problem we have amrnrmum ofthree outeomes leadlng to amrnrmum tree herght of 2 V r perform atleast two eompansons Searchlng a Sorted Array Here we presenttwo arguments to establrsh the lowerbound on the number ofcompansons establrsh the eomplerrrty ofblnary seareh ofagame L Yes or No U L L The game that we play rs Guess anumber between 0 and lsquot wrth the allowed quesuon belng Is the number blgger than Nquot where the rst player ean glve any number The answerhonestly 1n the adversary argument approaeh the seeond player ehooses anumber Supposethatlamtheadyersary You ask Isthenumberlargerthan12quot lsay Noquot The 12 r14and 12 ln t a Ax uthe rtnl r presents me the adversary wrth no better way to answer Here rs aversron ofthe game for the rnterval 0 through 15rne1uswe After eaeh answer we present the closedxnterval thatrs eonsrstent wrtht e answers already gwen Thus xfthe number rs not greater than 7 rtrnust be m the e1osedrnterva1o7 Q Is the number larger than77 A No 07 Q Is the number larger than 37 A Yes 47 Q Is the number larger than 57 A No 4 5 Q Is the number larger than47 A No 44 t t n wt h ofrny answers Thrs is the number 4 whreh must be the answer xfIhave answeredtxuthfully xs eonsrstent wrth all answers and honest at the trrne ofthe answer e e An A A7 sortedrn rnereasrng order wrth no two elements equal In general the deexsxon tree for abxnary search ofN sorted elements has Nleaves thus the 2 hogah of algorrthrn algorrthrn that rs oaog N so we say that the 1owerhrnrt rs sharp Chapter 6 Matrices Gaussian Elimination and Matrix Inverses Chapter 6 of the textbook covers a number of topics but we shall only cover those topics related to matrices We shall present matrices within the context of linear equations The discussion will be limited to 3by3 matrices as smaller matrices are boring and larger matrices are a bit too messy for our discussions Consider the following system of linear equations in three variables 20X Y Z l 40X Y i Z 5 X Y Z 0 As we have learned in highschool algebra the variables X Y and Z are just place holders in that the real structure of the problem is contained in the numbers One use of matrices is to focus on this structure without attending to the variables There are two matrices associated with this problem the 3by3 matrix of coefficients and the 3by4 augmented matrix We show these two matrices just below Coefficient Matrix Augmented Matrix 2 l l 2 l l l 4 l l 4 l l 5 l l l l l l 0 There are a number of ways to solve this set of equations but first it is important to discuss what the mathematicians call elementary row operations The student should note that there are also elementary column operations but that these are of less use in our studies There are three elementary row operations 1 Exchanging two rows in a matrix and 2 Multiplying a row by a nonzero constant and 3 Replacing a row by the sum of that row and a nonzero multiple of another row Note that the third operation specifies the nonzero product of a row as adding a zero product of one row to another row does not change the matrix The insight of the method of elementary row operations is that in some sense they do not change the matrix For example the solution to a set of linear equations does not depend on what equation is written rst thus swapping rows should not change the solution Before working with this sample matrix and its associated set of equations let us consider two related sets of equations Each set of equations is related to the example above The first set of equations is shown below 20X 7 Y Z l 20X 2oY 2oZ 8 X Y Z 4 Examine the augmented matrix for the system 2 l 2 2 2 8 l l l 4 Perform the elementary row operation Row 2 7 20Row 3 to get the following 2 l l l O O O O l l l 4 This merely emphasizes the fact that the second equation is just a multiple of the third equation and does not convey any additional information Thus all we really have is the following set of two equations in three variables 7 the system is underdetermined 20X Y Z X Y Z ul 39 All that can be said of the solution to this set of equations is that it lies on the line specified by the equation 30X 20Z 5 For some problems this may be an adequate solution Consider now the next set of equations 20X Y Z l 20X 2oY 2oZ X Y Z 8 i 3 Examine the augmented matrix for the system 2 l l l 2 2 2 8 l l l 3 Perform the elementary row operation Row 2 7 20Row 3 to get the following 0 O O 2 l l l 3 This merely emphasizes the fact that this set of equations is not consistent 7 there is no possible solution Mathematicians use the rank of a matrix as a tool to investigate these problems in the solutions of systems of linear equations we shall just ignore the problems Gaussian Elimination We now consider the solution of the original set of equations by the use of Gaussian elimination This involves the use of elementary row operations to turn the matrix of coefficients into an upper triangular form in which all entries below the diagonal are 0 We actually work on the augmented matrix The set of equations is 20X Y Z l 4 0X Y i Z 5 X Y Z O The augmented matrix for this system is given by 2 l l l 4 l l 5 l l 0 Add 720Row l to Row 2 to get 1 l l 0 3 3 3 l l l 0 Add 7 120Row l to Row 3 to get 2 l l l 0 3 3 3 0 15 05 05 Add 7 120Row 2 to Row 3 to get At this point we can use the method to solve the equations as follows The third equation is 20Z 7 2 so Z 7 1 With the substitution of the value for Z the second equation becomes 30Y33orY0 With the substitution of Y 0 and Z 7 l the rst equation becomes 20X 0 711 or 20X 2 and X l The solution is l 0 71 I want to present another solution to this set of equations We left the augmented matrix as Divide Row 3 by 2 Row 2 by 3 and Row 1 by 2 to get the following 1 05 05 05 0 l l l 0 0 l 1 Now we see that the solution to the third equation is obviously Z 7 l and we can proceed with the solution to the other two equations as we did just above I want to proceed with elementary row operations just to make the students completely tired of them First add 120Row 2 to Row 1 to get 1 0 0 l l l l 0 l 1 Now add Row 3 to Row 2 to get 0 l 0 l 0 0 0 l 1 This corresponds to the following set of equations X 1 Y 0 Z 7 l and we obviously have another solution to the set of equations We next consider a method of solutions based on the inverse of the matrix of coefficients Matrix multiplication is a well defined operation and the definition of a matrix inverse follows from this operation Suppose that matrix A has an inverse denoted A39l Then we 1 0 0 have AOA391 A39loA I where I is the identity matrix For a 3by3 matrix I 0 l 0 0 0 l Matrix Inverse We have examined the set of equations given by 20X Y Z l 40X Y i Z 5 X Y Z O This can be written in matrix form as AoW B where 2 1 1 X 1 A 4 1 1W Y andB 5 1 1 1 Z 0 We can use the fact that A39loA I to convert the equation to 10W A39loB or W A39loB There are a number of methods by which the inverse of a matrix can be computed We focus on the method of elementary row operations In order to compute the inverse of a matrix we rst augment the matrix with the identity 2 1 1 1 0 0 creating A11 4 1 1 0 1 0 and use elementary row operations to produce I A39l 1 1 1 0 0 1 First divide Row 1 by 2 to get 1 1 2 1 2 1 2 0 0 4 1 1 0 1 0 1 1 1 0 0 1 Now add 7 40Row 1 to Row 2 and 7 10Row 1 to Row 3 to get 1 12 12 12 0 0 0 3 3 2 1 0 0 32 12 12 0 1 Divide Row 2 by 3 to get 1 12 12 12 0 0 0 1 1 23 13 0 0 32 12 12 0 1

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

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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