Spring 2010 CSE310 Midterm Examination 01A (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.• You are NOT supposed to use a pencil. If you use pencil, you cannot challenge yourgrade after the midterm is graded.NAMEASUIDQuestion ScoreP1P2P3P4P5Total0Problem 1A. (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) = n log n, g(n) =nXi=1ni.Solution:f(n) = Θ(g(n))2. f(n) = 1.01n, g(n) = n1000.Solution:f(n) = Ω(g(n))3. f(n) =nXi=1i2, g(n) = n3+nXi=1i.Solution:f(n) = Θ(g(n))4. f(n) = n!, g(n) = 3n× 5n.Solution:f(n) = Ω(g(n))5. f(n) =nXi=11i, g(n) = n0.0001.Solution:f(n) = O(g(n))Grading Keys:4pts for each subproblem.1Problem 2A. (20 points: 5 + 5 + 5 + 5)There are two algorithms A1, A2, with time complexities T1(n), T2(n), respectively. We knowthat T1(n) = 27T1(n/3) + n2; T2(n) = 26T2(n/3) + 8n2;1. Use the master method to decide the asymptotic notation of T1(n).Solution:For this recurrence, we have a = 27, b = 3, f(n) = n2, and thus we have thatnlogba= nlog327= n3. Since n2= O(nlogba−), where  = 0.1, we can apply case 1 ofthe master method and conclude that the solution is T1(n) = Θ(n3).Grading Keys:2pts for justifying the right case;3pts for conclusion.2. Use the master method to decide the asymptotic notation of T2(n). You may uselog326 = 2.9656 in your calculations.Solution:For this recurrence, we have a = 26, b = 3, f(n) = 8n2, and thus we have thatnlogba= nlog326. Since n2= O(nlog326−), where  = 0.1, we can apply case 1 of themaster method and conclude that the solution is T2(n) = Θ(nlog326).Grading Keys:2pts for justifying the right case;3pts for conclusion.3. Which algorithm is asymptotically faster?Solution:The algorithm A2is asymptotically faster.Grading Keys:5pts for right answer.4. The recurrence T (n) = 27T (n/3) + 8n2describes 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?Solution:2The time complexity of T (n) is T (n) = Θ(n3). For any integer a such that a > 81, thetime complexity of T0(n) is T0(n) = Θ(log9a). Since algorithm A0is asymptoticallyfaster than A, we have that log9a < 3. From the inequality, we get a < 729. Therefore,the largest integer value for a is 728.Grading Keys:5pts for correct answer;3pts for knowing log9a < log327.3Problem 3A. (20 points: 6 + 14)(6 pts) What are the major steps in Divide and Conquer? Use merge-sort to illustrate thesteps. Also give the time complexities of the major steps, assuming sorting n elements.Solution:Divide: divide array into two sub-arrays with the size n/2. The time complexity ofdivide is O(1).Conquer: sort each sub-array by recursively calling merge sort.Merge: merge two sub-arrays into one sorted array. The time complexity is O(n).Grading Keys:2pts for the illustration of divide;2pts for the illustration of conquer;2pts for the illustration of combine;3pts will be cut off if there is no clarification of time complexity.(14 pts) Suppose you have an array A[1..n] which contains n numbers in sorted order, where nis a very big number (n >> 10000). The operation swap(i, j) swaps A[i] with A[j], for1 ≤ i < j ≤ n. We also call |j − i| the distance of swap(i, j). Let array B be obtainedfrom array A by k swap operations each with distance no more than 10. We need tosort B using either insertion sort or merge sort, and worst-case time complexity isthe only metric.– If k = Θ(n√log n), which sorting algorithm is a better choice? Justify youranswer.Solution:Insertion sort is a better choice.A swap can introduce no more than 10 inversions. The total inversions will beΘ(10n√log n) = Θ(n√log n). Thus insertion sort would take Θ(n + n√log n)time. However, merge sort always takes Θ(n log n) time. So, insertion sort is abetter choice for this case.Grading Keys:4pts for correct choice;3pts for justifying the advantage of insertion sort and disadvantage of merge sort.4– If k = Θ(√n), which sorting algorithm is a better choice? Justify your answer.Solution:Insertion sort is a better choice.Similar to the above analysis, insertion sort takes Θ(n +√n) time and merge sorttakes Θ(n log n) time. So, insertion sort is still a better choice.Grading Keys:4pts for correct choice;3pts for justifying the advantage of insertion sort and disadvantage of merge sort.5Problem 4A. (20 points: 5 + 5 + 5 + 5)(5 pts) Given the sequence of number as shown below in its array representation.1, 2, 3, 4, 5, 6, 7Show the binary max-heap obtained by sequential insertion into the initially emptyheap.Solution:The binary max-heap obtained is as follows:(5 pts) Given the sequence of number as shown below in its array representation.1, 2, 3, 4, 5, 6, 7Show the binary max-heap obtained by the linear time BuildHeap algorithm.Solution:The binary max-heap obtained is as follows:(5 pts) Given the binary max-heap with its array representation in the following:7, 6, 5, 1, 2, 3, 4Show the binary max-heap obtained by the delete-max operation.Solution:The binary max-heap obtained is as follows:6(5 pts) Given the binary max-heap with its array representation in the following:7, 6, 5, 1, 2, 3, 4Show the binary max-heap obtained by inserting a node with value 9.Solution:The binary max-heap obtained is as follows:Grading Keys:5pts for each subproblem.7Problem 5A. (20 points: 5 + 5 + 10)(5 pts) What is the number of leaf nodes in a decision tree for sorting n elements using heap-sort?Solution:The number of leaf nodes is n!.Grading keys:5pts for correct answer.(5 pts) Denote the lower bound on the height of a decision tree with N total nodes usingasymptotic notation.Solution:The lower bound on the height of a decision tree with N total nodes is Ω(log N).Grading keys:5pts for correct answer.(10 pts) Draw part of the decision tree for insertion sort on 5 distinct elements (a1, a2, a3, a4,