Types of AlgorithmsAlgorithm classificationA short list of categoriesSimple recursive algorithms IExample recursive algorithmsBacktracking algorithmsExample backtracking algorithmDivide and ConquerExamplesBinary tree lookupFibonacci numbersDynamic programming algorithmsFibonacci numbers againGreedy algorithmsExample: Counting moneyA failure of the greedy algorithmBranch and bound algorithmsExample branch and bound algorithmBrute force algorithmImproving brute force algorithmsRandomized algorithmsThe EndTypes of Algorithms2Algorithm classificationAlgorithms that use a similar problem-solving approach can be grouped togetherWe’ll talk about a classification scheme for algorithmsThis classification scheme is neither exhaustive nor disjointThe purpose is not to be able to classify an algorithm as one type or another, but to highlight the various ways in which a problem can be attacked3A short list of categoriesAlgorithm types we will consider include:Simple recursive algorithmsBacktracking algorithmsDivide and conquer algorithmsDynamic programming algorithmsGreedy algorithmsBranch and bound algorithmsBrute force algorithmsRandomized algorithms4Simple recursive algorithms IA simple recursive algorithm:Solves the base cases directlyRecurs with a simpler subproblemDoes some extra work to convert the solution to the simpler subproblem into a solution to the given problemI call these “simple” because several of the other algorithm types are inherently recursive5Example recursive algorithmsTo count the number of elements in a list:If the list is empty, return zero; otherwise,Step past the first element, and count the remaining elements in the listAdd one to the resultTo test if a value occurs in a list:If the list is empty, return false; otherwise,If the first thing in the list is the given value, return true; otherwiseStep past the first element, and test whether the value occurs in the remainder of the list6Backtracking algorithmsBacktracking algorithms are based on a depth-first recursive searchA backtracking algorithm:Tests to see if a solution has been found, and if so, returns it; otherwiseFor each choice that can be made at this point,Make that choiceRecurIf the recursion returns a solution, return itIf no choices remain, return failure7Example backtracking algorithmTo color a map with no more than four colors:color(Country n):If all countries have been colored (n > number of countries) return success; otherwise,For each color c of four colors,If country n is not adjacent to a country that has been colored cColor country n with color crecursively color country n+1If successful, return successIf loop exits, return failure8Divide and ConquerA divide and conquer algorithm consists of two parts:Divide the problem into smaller subproblems of the same type, and solve these subproblems recursivelyCombine the solutions to the subproblems into a solution to the original problemTraditionally, an algorithm is only called “divide and conquer” if it contains at least two recursive calls9ExamplesQuicksort:Partition the array into two parts (smaller numbers in one part, larger numbers in the other part)Quicksort each of the partsNo additional work is required to combine the two sorted partsMergesort:Cut the array in half, and mergesort each halfCombine the two sorted arrays into a single sorted array by merging them10Binary tree lookupHere’s how to look up something in a sorted binary tree:Compare the key to the value in the rootIf the two values are equal, report successIf the key is less, search the left subtreeIf the key is greater, search the right subtreeThis is not a divide and conquer algorithm because, although there are two recursive calls, only one is used at each level of the recursion11Fibonacci numbersTo find the nth Fibonacci number:If n is zero or one, return one; otherwise,Compute fibonacci(n-1) and fibonacci(n-2)Return the sum of these two numbersThis is an expensive algorithmIt requires O(fibonacci(n)) timeThis is equivalent to exponential time, that is, O(2n)12Dynamic programming algorithmsA dynamic programming algorithm remembers past results and uses them to find new resultsDynamic programming is generally used for optimization problemsMultiple solutions exist, need to find the “best” oneRequires “optimal substructure” and “overlapping subproblems”Optimal substructure: Optimal solution contains optimal solutions to subproblemsOverlapping subproblems: Solutions to subproblems can be stored and reused in a bottom-up fashionThis differs from Divide and Conquer, where subproblems generally need not overlap13Fibonacci numbers againTo find the nth Fibonacci number:If n is zero or one, return one; otherwise,Compute, or look up in a table, fibonacci(n-1) and fibonacci(n-2)Find the sum of these two numbersStore the result in a table and return itSince finding the nth Fibonacci number involves finding all smaller Fibonacci numbers, the second recursive call has little work to doThe table may be preserved and used again later14Greedy algorithmsAn optimization problem is one in which you want to find, not just a solution, but the best solutionA “greedy algorithm” sometimes works well for optimization problemsA greedy algorithm works in phases: At each phase:You take the best you can get right now, without regard for future consequencesYou hope that by choosing a local optimum at each step, you will end up at a global optimum15Example: Counting moneySuppose you want to count out a certain amount of money, using the fewest possible bills and coinsA greedy algorithm would do this would be:At each step, take the largest possible bill or coin that does not overshootExample: To make $6.39, you can choose:a $5 billa $1 bill, to make $6a 25¢ coin, to make $6.25A 10¢ coin, to make $6.35four 1¢ coins, to make $6.39For US money, the greedy algorithm always gives the optimum solution16A failure of the greedy algorithmIn some (fictional) monetary system, “krons” come in 1 kron, 7 kron, and 10 kron coinsUsing a greedy algorithm to count out 15 krons, you would getA 10 kron pieceFive 1 kron pieces, for a total of 15 kronsThis requires six coinsA better solution would be
View Full Document