Solving recurrence equationsDeriving the count using the recursion tree methodBuilding the recursion treeSlide 4Example: recursive factorialAfter the first unrollingAfter the second unrollingAfter the third unrollingThe recursion treeDivide and ConquerSlide 11Slide 12Slide 13Binary searchSlide 15Slide 16Worst case analysisRecursion tree for BinarySearch (BS)After first unrollingAfter second unrollingAfter third unrollingTerminating the unrollingSlide 23Merge SortMerge Sort:Merge( S1 , S2, S ): PseudocodeRecurrence Equation for MergeSort.Recursion tree for MergeSort (MS)After first unrolling of mergeSortSlide 30Slide 31Slide 32Slide 33The sum for each depth01/13/19 cutler: divide & conquer 1Solving recurrence equations•5 techniques for solving recurrence equations:–Recursion tree–Iteration method–Induction (Guess and Test) –Master Theorem (master method)–Characteristic equations•We concentrate on the recursion tree method (others in the book)01/13/19 cutler: divide & conquer 2Deriving the count using the recursion tree method•Recursion trees provide a convenient way to represent the unrolling of recursive algorithm•It is not a formal proof but a good technique to compute the count.•Once the tree is generated, each node contains its “non recursive number of operations” t(n) or DirectSolutionCount•The count is derived by summing the “non recursive number of operations” of all the nodes in the tree•For convenience we usually compute the sum for all nodes at each given depth, and then sum these sums over all depths.01/13/19 cutler: divide & conquer 3Building the recursion tree•The initial recursion tree has a single node containing two fields: –The recursive call, (for example Factorial(n)) and –the corresponding count T(n) .•The tree is generated by:– unrolling the recursion of the node depth 0, –then unrolling the recursion for the nodes at depth 1, etc.•The recursion is unrolled as long as the size of the recursive call is greater than DirectSolutionSize01/13/19 cutler: divide & conquer 4Building the recursion tree•When the “recursion is unrolled”, each current leaf node is substituted by a subtree containing a root and a child for each recursive call done by the algorithm.–The root of the subtree contains the recursive call, and the corresponding “non recursive count”.–Each child node contains a recursive call, and its corresponding count.•The unrolling continues, until the “size” in the recursive call is DirectSolutionSize•Nodes with a call of DirectSolutionSize, are not “unrolled”, and their count is replaced by DirectSolutionCount01/13/19 cutler: divide & conquer 5Example: recursive factorial• Initially, the recursive tree is a node containing the call to Factorial(n), and count T(n). • When we unroll the computation this node is replaced with a subtree containing a root and one child: •The root of the subtree contains the call to Factorial(n) , and the “non recursive count” for this call t(n)=  (1). •The child node contains the recursive call to Factorial(n-1), and the count for this call, T(n-1). Factorial(n) T(n)01/13/19 cutler: divide & conquer 6depth nd T(n) 0 1 (1)Factorial(n) t(n)= (1)Factorial(n-1) T(n-1)After the first unrolling1 1 T(n-1)1for )1()1(1for )1()(nnTnnTnd denotes the number of nodes at that depth01/13/19 cutler: divide & conquer 70 1 (1)1 1 (1)After the second unrollingdepth nd T(n) 2 1 T(n-2)Factorial(n) t(n)= (1)Factorial(n-1) t(n-1)= (1)Factorial(n-2) T(n-2)1for )1()1(1for )1()(nnTnnT01/13/19 cutler: divide & conquer 80 1 (1)1 1 (1)After the third unrollingdepth nd T(n) 3 1 T(n-3)Factorial(n) t(n)= (1)Factorial(n-1) t(n-1)= (1)Factorial(n-2) t(n-2)= (1)1for )1()1(1for )1()(nnTnnTFactorial(n-3) T(n-3)2 1 (1)For Factorial DirectSolutionSize = 1 and DirectSolutionCount= (1)01/13/19 cutler: divide & conquer 90 1 (1)1 1 (1)The recursion treedepth nd T(n) n-1 1 T(1)= (1)Factorial(n) t(n)= (1)Factorial(n-1) t(n-1)= (1)Factorial(n-2) t(n-2)= (1)Factorial(n-3) t(n-3)= (1)2 1 (1)3 1 (1)Factorial(1) T(1)=(1)The sum T(n)=n* (1) = (n)01/13/19 cutler: divide & conquer 10Divide and Conquer•Basic idea: divide a problem into smaller portions, solve the smaller portions and combine the results.•Name some algorithms you already know that employ this technique.•D&C is a top down approach. Often, you use recursion to implement D&C algorithms.•The following is an “outline” of a divide and conquer algorithm01/13/19 cutler: divide & conquer 11Divide and Conquerprocedure Solution(I);beginif size(I) <=smallSize then {calculate solution} return(DirectSolution(I)) {use direct solution}else {decompose, solve each and combine}Decompose(I, I1,...,Ik); for i:=1 to k doS(i):=Solution(Ii); {solve a smaller problem}end {for}return(Combine(S1,...,Sk)); {combine solutions}end {Solution}01/13/19 cutler: divide & conquer 12Divide and Conquer•Let size(I) = n •DirectSolutionCount = DS(n) •t(n) = D(n) + C(n) where:–D(n) = count for dividing problem into subproblems–C(n) = count for combining solutionskiinCnDnTsmallSizennDSnT1otherwise)()()(for )()(01/13/19 cutler: divide & conquer 13Divide and Conquer•Main advantages–Simple code–Often efficient algorithms–Suitable for parallel computation01/13/19 cutler: divide & conquer 14Binary search•Assumption - the list S[low…high] is sorted, and x is the search key•If the search key x is in the list, x==S[i], and the index i is returned.• If x is not in the list a NoSuchKey is returned•Book’s version: returns an index i where x would be inserted into the sorted list01/13/19 cutler: divide & conquer 15Binary search•The problem is divided into 3 subproblems: x=S[mid], x S[low,..,mid-1], x S[mid+1,..,high]•The first case x=S[mid]) is easily solved•The other cases x S[low,..,mid-1], or x S[mid+1,..,high] require a recursive call •When the array is empty the search terminates with a “non-index value”01/13/19 cutler: divide & conquer 16BinarySearch(S, k, low, high)if low > high thenreturn