Spring 2007 CSE310 Midterm Examination 01B (in class)Instructions:• There are five problems in this paper. Please use the space provided (below the ques-tions) to write the answers.• Budget your time to solve various problems (roughly 15 minutes for each problem) andavoid spending too much time on a particular question.• This is a closed book examination. You may not consult your books/notes.NAMEASUIDQuestion ScoreP1P2P3P4P5Total0Problem 1B. (20 points: 4 + 4 + 4 + 4 + 4)Use O, Ω, or Θ to relate each of the following pairs of functions. In particular, you needto write your answer as f(n) = O(g(n)), f (n) = Ω(g(n)), or f(n) = Θ(g(n)). In casef(n) = Θ(g(n)), you will not receive credit if you write f(n) = O(g(n)) or f (n) = Ω(g(n)),although both are implied by f(n) = Θ(g(n)).1. f(n) is the average case time complexity of mergesort for sorting n elements. g(n) isthe average case time complexity of quicksort for sorting n elements.f(n) = Θ(g(n)). Grading is binary.2. f(n) is the worst case time complexity of mergesort for sorting n elements. g(n) is theworst case time complexity of quicksort for sorting n elements.f(n) = O(g(n)). Grading is binary.3. f(n) =nXi=1i(i + 1), g(n) = n3+nXi=1i2i.f(n) = Θ(g(n)). Grading is binary.4. f(n) = nn, g(n) = 2n× 3n.f(n) = Ω(g(n)). Grading is binary.5. f(n) =nXi=1ni, g(n) = n1.0001.f(n) = O(g(n)). Grading is binary.1Problem 2B. (20 points: 5 + 5 + 5 + 5)There are two algorithms A1, A2, with time complexities T1(n), T2(n), respectively. We knowthat T1(n) = 10T1(n/3) + n3; T2(n) = 16T2(n/3) + n2.(5 pts) Use the master method to decide the asymptotic notation of T1(n).a = 10, b = 3, f (n) = n3. For any constant  in the interval (0, 3 − log310), we havef(n) = Ω(nlog310+). Also, for c =1027< 1, we havea · f (n/b) ≤ c · f (n).Therefore we have case-3 of the master method. As a result, T1(n) = Θ(n3).Grading: 3 pts for the case, 2 pts for the final solution.(5 pts) Use the master method to decide the asymptotic notation of T2(n).a = 16, b = 3, f (n) = n2. For any constant  in the interval (0, log316 − 2), we havef(n) = O(nlog316−). Therefore we have case-1 of the master method. As a result,T2(n) = Θ(nlog316).Grading: 3 pts for the case, 2 pts for the final solution.(5 pts) Which algorithm is the faster?A2is faster.(5 pts) The recurrence T (n) = 10T (n/3) + n2describes the running time of an algorithm A.A competing algorithm A0has a running time of T0(n) = aT0(n/9) + n2. What is thelargest integer value for a such that A0is asymptotically faster than A?The time complexity of Algorithm A is T (n) = Θ(nlog310). For any integer a such thata ≥ 100, the time complexity of algorithm A0is T0(n) = Θ(nlog9a) = Ω(T (n)). Fora = 99, the time complexity of algorithm A0is T0(n) = Θ(nlog9a) = Θ(nlog999), whichgrows slower than T (n). Therefore the answer is a = 99.Grading: 3 pts for the relationship log9a < log310; 2 pts for the answer.2Problem 3B. (20 points: 6 + 7 + 7)(6 pts) What are the major steps in Divide and Conquer? Use quicksort to illustrate thesteps. Also give the time complexities of the major steps, assuming sorting n elements.2pts: Divide: partition the array using a pivot. Θ(n).2pts: Conquer: sort the portion to the left of the pivot recursively, sort the portion tothe right of the pivot recursively.2pts: Combine: nothing. O(1).(7 pts) Suppose you are required to sort a very long sequence of numbers. Assume thatworst-case time complexity is the only measurement. Also, we do not have any priorknowledge of the input sequence. Between quicksort and heapsort, which is the betteralgorithm for this problem? Why?Heapsort requires Θ(n log n) time. Quicksort requires Θ(n2) time. Therefore heapsortis the better algorithm.Grading: 4 pts for the answer; 3 pts for the reason.(7 pts) Suppose you are required to sort a very long sequence of numbers. Assume thatworst-case time complexity is the only measurement. Suppose that we know that theinversion number of the input sequence is Θ(n1.1), where n is the length of the inputsequence. Between insertion sort and heapsort, which is the better algorithm for thisproblem? Why?Heapsort requires Θ(n log n) time. Insertion sort requires Θ(n1.1) time. Thereforeheapsort sort is the better algorithm.Grading: 4 pts for the answer; 3 pts for the reason.3Problem 4B. (20 points: 6 + 8 + 6)(6 pts) Given the following sequence of numbers,2, 4, 1, 3, 5, 7,you are to insert the six elements (in the given order) to an initially empty max-heap.Show the resulting max heaps for the first n numbers in this sequence for n = 1, 2, . . . , 6.24, 24, 2, 14, 3, 1, 25, 4, 1, 2, 37, 4, 5, 2, 3, 1Grading: 1 pt each until the first mistake.(8 pts) You are given the sequence of numbers as shown in its array representation below.2, 4, 1, 3, 5, 7,Compute the max-heap obtained by the linear time BuildHeap algorithm. You haveto show the resulting array content after each of the outer Heapfy calls.2, 4, 7, 3, 5, 12, 5, 7, 3, 4, 17, 5, 2, 3, 4, 1Grading: 2 pts each for the first two lines, 4 pts for the last line.(6 pts) You are given a min-heap with its array representation in the following:1, 2, 3, 4, 5, 6, 7, 8, 9Show the min-heap obtained after delete-min from the given min-heap.2, 4, 3, 8, 5, 6, 7, 9Grading: binary4Problem 5B. (20 points: 5 + 5 + 10)(5 pts) What is the worst case time complexity of insertion sort for sorting n elements?Θ(n2). O is OK, but Ω is not. Grading is binary.(5 pts) Is the longest root–leaf path in a decision tree related to the best-case time complexityof the corresponding sorting algorithm or the worst-case time complexity of the corre-sponding sorting algorithm?Answer: worst-case. Grading is binary.(10 pts) Draw part of the decision tree for insertion sort on 4 distinct elements (a1, a2, a3, a4)which includes the path from the root node to the leaf node < a1, a4, a3, a2>. Youhave to label each node with the comparison (in the form ai≤ aj?) made at the nodeand label each edge with YES or NO.[a1≤ a2], Y, [a2≤ a3], N, [a1≤ a3], Y, [a2≤ a4], N, [a3≤ a4], N, [a1≤ a4], Y, [a1, a4, a3, a2]Grading: 1 pt each until the first