CS333 Assignment 2Instructor: KD [email protected] Name:• This homework is due at the beginning of the class on March 11, 2008. Timely submission ofyour homework is recommended, because there will be 10% late penalty per day.• Always try to be precise and concise. Finally, always make sure your answers are readable!1: [20 points] Using the quicksort algorithm in the textbook (pages 60 − 66), showhow to sort the following list of integers.1, 2, 3, 4, 5, 6, 7(a) [10 points] Use the first element in a (sub)list as the pivot item. Show the sorting actionsstep by step.[n]: n is the pivot.Step:1: [1] | 2 3 4 5 6 72: [1] | [2] | 3 4 5 6 73: [1] | [2] | [3] | 4 5 6 74: [1] | [2] | [3] | [4] | 5 6 75: [1] | [2] | [3] | [4] | [5] | 6 76: [1] | [2] | [3] | [4] | [5] | [6] | 77: return {6, 7}8: return {5, 6, 7}9: return {4, 5, 6, 7}10: return {3, 4, 5, 6, 7}11: return {2, 3, 4, 5, 6, 7}12: return {1, 2, 3, 4, 5, 6, 7}.(b) [10 points] Randomly choose an element in a (sub)list as the pivot item. Show the sortingactions step by step.The following is a sample execution sequence where [n] is the pivot.Step1: 1 2 3 | [4] | 5 6 7 //Partition the list to 2 sublists: {1, 2, 3} and {5, 6, 7}.2: 1 [2] 3 | [4] | 5 6 | [7] //Use 2 as the pivot in {1, 2, 3} and use {7} as the pivot in {5, 6, 7}.3: 1 [2] 3 | [4] | [5] | 6 | [7] //Use {5} as pivot in {5, 6}.4: Return {5, 6}.5: Return {5, 6, 7}.6: Return {1, 2, 3}.7: Return {1, 2, 3, 4, 5, 6, 7}1HW2 CS333Instructor: KD [email protected]: [20 points] Do Exercise 2.6.ternarySearch(x, A, left, right) //x: item to search for, A: array{if (right < left)return ”x not found”else if (x = = A[(left+right)/3])return (left+right)/3;else if (x = = A[2(left+right)/3])return 2(left+right)/3;else if (x < A[(left+right)/3])ternarySearch(x, a, 1, (left+right)/3);else if (A[(left+right)/3] ≤ x ≤ A[2(left+right)/3])ternarySearch(x, a, (left+right)/3, 2(left+right)/3);else if (x > A[2(left+right)/3])ternarySearch(x, a, 2(left+right)/3, right);}Thus, the time complexity of this algorithm is expressed as follows:T (n) = 1 when n = 1T (n) = T (n/3) + 1 when n > 1Assume that n is a power of 3. (Dealing with a case in which n is not a power of 3 is trivial,similar to binary search.) A complete time complexity analysis foll ows:T (n) = T (n/3) + 1= T (n/9) + 2= T (n/27) + 3...= T (1) + log3n= Θ(log3n)3: [10 points] Do Exercise 2.11.Key Idea: Non-recursive variant of mergesort: mergesort in a bottom-up way./*The array is sorted by a sequence of passes. In each pass, the arrayconsists of blocks of size m. Initially, m=1; that is, we have n blockswhere each block has a single array element. In one pass, every twoadjacent blocks are merged. As a result, the next pass has to mergeblocks where each block is of size 2m. Repeat this until there isonly a signle block of size n.*/2HW2 CS333Instructor: KD [email protected]: array a[0..n-1];m = 1;while m ≤ n do{i = 0;while i < n-m do{merge subarrays a[i. . . i+m-1] and a[i+m . . . min(i+2 × m-1,n-1)];i = i + 2 × m;}m = m × 2;}4: [10 points] The behavior of a recursive algorithm is expressed by the followingrecurrence relations.T (n) = 7T (n/5) + 10n for n > 1T (1) = 1(a) [5 points] Find T(125).T (125) = 7 × T (25) + 10 × 125= 7 × T (25) + 1250T (25) = 7 × T (5) + 10 × 25= 7 × T (5) + 250T (5) = 7 × T (1) + 10 × 5= 57Therefore,T (125) = 7 × T (25) + 1250= 7 × 649 + 1250= 5793(b) [5 points] What is the time complexity of this algorithm? [Hint: Refer to Theorem B.5 inAppendix B.]By Theorem B.5, we get a=7, b=5, and k=1. Because 7 > 51, T (n) ∈ Θ(nlog57).5: [10 points] Do Exercise 2.7.max(left, right, A){3HW2 CS333Instructor: KD [email protected] the size of ar ray A is 1, simply return the only element in the array.Else, return the maximum of {max(left,(left+right)/2), max((left+right/2), right)}}This algorithm makes recusive calls until it gets n arrays where each array has a single element.Given n input data, it take the algorithm Θ(lg n) time to reach this stage. (Assume that n is powerof 2.) The algorithm then returns the maximum of the two nearby subsequences until it finds themaximum for all n numbers in the original arrary. Thus, the total number of comparisions for themerge is:n/2 + n/4 + n/8 + ... + 1 = n(1/2 + 1/4 + ... + 1/n)= n ·1/2(1 − (1/2)lgn)1 − 1/2= n · (1 − 1/n)= Θ(n).Note: r + r2+ ... + rn=r(1−rn)1−r.6: [10 points] You need to write a program to compute the nthFibonacci term forinput n, which is a positive integer greater than 1. Answer the following questions.(a) [2 points] Will you use Algorithms 1.6 or 1.7?Algorithm 1.7.(b) [8 points] Justify your choice in part (a).Algorithm 1.6 has e xponential time complexity in terms of n, while Algorithm 1.7 is Θ(n).7: [10 points] Do Exercise 1.28.T (n) = O(k2) = O(lg2n).8: [10 points] Do Exercise 2.37.fact(n){if (n == 0 or n = = 1) return 1;else return n · fact(n-1)}The time complexity is:T (n) = 1 if n = 1T (n) = T (n − 1) + 1 if n > 1.4HW2 CS333Instructor: KD [email protected] (n) = T (n − 1) + 1= T (n − 2) + 2= T (n − 3) + 3...= n − 1Thus, it does not have exponential time