Programming & Problem Solving II
Programming & Problem Solving II CECS 274
Popular in Course
Popular in Computer Science and Engineering
This 21 page Class Notes was uploaded by Zackary Cronin on Monday October 5, 2015. The Class Notes belongs to CECS 274 at California State University - Long Beach taught by Donna Pompei in Fall. Since its upload, it has received 24 views. For similar materials see /class/218751/cecs-274-california-state-university-long-beach in Computer Science and Engineering at California State University - Long Beach.
Reviews for Programming & Problem Solving II
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/05/15
CHAPTER 2 ALGORITHMS RECURSION AND PERFORMANCE A Algorithms DLfn An algorithm is a list of instructions to accomplish a given task An algorithm has 0 or more inputs 1 or more results unambiguous instructions a nite number of steps in which it terminates Defn An algorithm is a nite sequence of instructions each of which has a clear meaning and can be performed with a nite amount of effort in a nite length of time using a nite amount of memory Example Design an algorithm that recognizes palindromes Defn A palindrome is a string that reads the same forward and backward Algorithm 1 1 Make a copy of the string with the order of the letters reversed 2 Compare the two strings 3 If they are equal the string is a palindrome Otherwise the string is not a palindrome Algorithm 2 Algorithm 3 B Recursion Defn A recursive algorithm or program is one that is de ned in terms of itself Note a base case must always be de ned when using recursion Example 1 Factorial Standard Iterative Defn n n nl n2 2 gt l Recursive Defn n n nl Base case 0 1 Note This base case is used in examples on following page C Code for the standard iterative definition int factorial int n int ans l for int i 2 i lt n i ans i return ans C Code for the recursive definition int factorial int n if n lt 0 or if n lt 1 return 1 return n factorial n 1 Both the iterative and recursive functions work correctly but how do they compare in terms of performance efficiency Review of Function Calls The context or execution environment of a function contains all of the following and probably more 0 local variables 0 parameters the address of the instruction the function is currently executing o and the return address of the instruction to execute upon termination of the currently executing function When a call is made to a new function we say that the context or execution environment of the current function has switched to that of the new function When a context or execution environment is switched the previous context or execution environment must be saved so that it can be reinstated upon return from the function call Context switching in Function Calls int main float funot1 int x1 int x2 mg int X Y floatZ int Q mt S float R into Z funct1X Y return 5 ll return 0 C funot2Q return R Context switching in Recursive Calls return R2 intmaino float funct1 float funct1 intX1 intX2 intX1 intX2 int X Y float Z intY1 Y2 intY1 Y2 float R1 R2 float R1 R2 N Z funct1X Y II II II if SomeCond if SomeCond return 0 R1 funct1Y1 Y2 R1 funct1Y1 Y2 I return R2 Example 2 Fibonacci Numbers 0r Rabbits from pp 7477 of the Textbook Defn The Fibonacci Numbers can be recursively de ned by the equations Fn Fn1 Fn2 Fl 1 FO 0 int Fibonacci int n Purpose Computes a term in the Fibonacci Sequence Precondition n is a non negative integer Postcondition Returns the nth Fibonacci Number if n lt 1 return 0 else if n return 1 else return Fibonaccin l Fibonaccin 2 Example 3 Permutations Note We include this example because it shows a problem that is much easier solved by recursion rather than iteration It is however quite advanced for this stage of CECS 274 Defn The permutations of the elements of a set are all the of unique ways of ordering the elements in the set Problem Design an algorithm to print all of the permutations of a set A B C D Standard Iterative Algorithm Very dif cult Recursive Algorithm 1 Start with the set in order A B C D 2 Print A followed by all permutations of BCD 3 Print B followed by all permutations of ACD 4 Print C followed by all permutations of ABD 5 Print D followed by all permutations of ABC Design for the C Implementation 0 Use an array which is divided into two parts A parameter called position will indicate the location of the first element of the back part 0 Start with everything in the back part 0 From the back part pick one letter at a time put it in the front part and generate permutations of the remaining back part 0 The base case occurs when the back part has only a single character C Code for Permutations include ltiostreamhgt const SIZE 4 void permutechar data int pos int main char arraySIZE 39A39 39B39 39C39 39D39 int pos O permutearray pos return 0 Note pos is set to 0 the first time this function is invoked void permutechar data int pos char newdataSIZE char hold copy data to newdata for int i O i lt SIZE i newdatai datai if pos gt SIZE l this is the base case so print for int i O i lt SIZE i cout ltlt datai cout ltlt endl else for int next pos next lt SIZE next pick a letter and put it in the front part hold newdatanext newdatanext newdatapos newdatapos hold recursive call permutenewdata pos l The output from the permute program is ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA Example 4 Binary Search Goal Search a sorted array of data for a particular item Idea A binary search takes advantage of the fact that the array is already sorted Algorithm Given a sorted array and an item you are searching for examine the middle element of the array If the middle element 1 to the one you want return 2 gt the one you want recursively search the front part of the array 3 lt the one you want recursively search the back part of the array Binary Search Notes Notice the array we are searching is effectively divided into two parts at each level of the recursion The base cases for the recursion occur when the item is found or it is determined that the item is not in the array If the item you want is not found notify the caller of the function of this fact 0 Remember a binary search will not work with an unsorted array 0 Our approach will return the indeX in the array to the position of the item we are searching for C Code for Binary Search The code for this recursive binary search is taken from p 86 in Carrano Helman and Veroff void BinarySearchconst int A int First int Last int Value intamp Index if First gt Last Index l Value not in original array else int Mid First Last 2 if Value AMid IndeX Mid Value found at AMid else if Value lt AMid Search the front half BinarySearchA First Mid 1 Value Index else Search the back half BinarySearchA Mid 1 Last Value Index C Performance Goal Develop a method for comparing the performance run time of different algorithms Problem Stating the running time of an algorithm is dif cult There are just m many variables For example 0 the input to the program 0 the machine it is running on o the programming language used Solution Performance approximation Defn Performance approximation is a generalization method of stating how an algorithm or program will perform as the size of the problem grows ONotation ONotation is used to describe the approximate performance of an algorithm or program Defn An algorithm is said to be OTn if the time it takes to run is lt c Tn where o Tn is a function 0 n is the size of the problem 0 c is a constant OTn is pronounced BigO of Tn Examples 48n On 035112 Onz 26 log 11 Olog2 11 Hints To simplify expressions in Onotation use the following 1 eliminate all constants 2 select the term that will grow fastest with 11 eliminate the other terms More Examples 17 8n3 On3 4n 8n2 3000 Onz log 11 14n On Note Calculating logz 11 lfx log 11 then 11 2X Let log 8 X then 8 2quot 23 thus X 3 log 8 To compute log 11 on a calculator log 11 log10 nlog10 2 Onotation Analysis of Algorithms Case 1 Linear Search of an Array n the size of the array Search time n2 in the average case n in the worst case Onotation On Case 2 Binary Search of an Array n the size of the array Array Size Comparisons 1 1 2 2 3 2 4 3 7 3 8 4 15 4 16 5 n L10g2 nJ 1 Search time Llogz nJ 1 in the worst case Onotation Ologz n Algorithm Running Times Faster Algorithms log n l n n logz 11 n2 113 15 Zn 3n n 11 11 Slower Algorithms 20 Limits on Task Size Given the Onotation for a task the following table shows the size of task that can be completed in different periods of time Running 1 Second 1 1 1 Time Minute Hour Day n 1 106 6 107 36 109 8641010 n2 1000 60000 36 106 864107 n3 100 6000 36 105 864106 2quot 19 1140 68400 1641600 In this table we assume that each operation takes 10396 seconds 21