Spring 2010 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.• You are NOT supposed to use a pencil. If you use pencil, you cannot challenge yourgrade after the midterm is graded.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) = n log n, g(n) =nXi=1i.Solution:f(n) = O(g(n))2. f(n) =nXi=12i, g(n) = n100.Solution:f(n) = Ω(g(n))3. f(n) =nXi=1n(n − i), g(n) = n3.Solution:f(n) = Θ(g(n))4. f(n) = nn, g(n) = 2n× 3n.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 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) = 64T1(n/4) + 100n2; T2(n) = 63T2(n/4) + 800n2;(5 pts) Use the master method to decide the asymptotic notation of T1(n).Solution:For this recurrence, we have a = 64, b = 4, f(n) = 100n2, and thus we have thatnlogba= nlog464= n3. Since 100n2= O(nlogba−), where  = 0.1, we can apply case 1of the master method and conclude that the solution is T1(n) = Θ(n3).Grading Keys:2pts for justifying the right case;3pts for conclusion.(5 pts) Use the master method to decide the asymptotic notation of T2(n). You may uselog463 = 2.9886 in your calculations.Solution:For this recurrence, we have a = 63, b = 4, f(n) = 800n2, and thus we have thatnlogba= nlog463. Since n2= O(nlog464−), where  = 0.1, we can apply case 1 of themaster method and conclude that the solution is T2(n) = Θ(nlog463).Grading Keys:2pts for justifying the right case;3pts for conclusion.(5 pts) Which algorithm is asymptotically faster?Solution:The algorithm A2is asymptotically faster.Grading Keys:5pts for right answer.(5 pts) The recurrence T (n) = 8T (n/2) + n describes the running time of an algorithm A.A competing algorithm A0has a running time of T0(n) = aT0(n/4) + n. What is thesmallest integer value for a such that A0is asymptotically slower than A?Solution:2The time complexity of T (n) is T (n) = Θ(n3). For any integer a greater than 4, thetime complexity of T0(n) is T0(n) = Θ(log4a). Since algorithm A0is asymptoticallyslower than A, we have that log4a > 3 ⇔ a > 43. From the inequality, we get a > 64.Therefore, the largest integer value for a is 65.Grading Keys:5pts for correct answer;3pts for knowing log4a > log28.3Problem 3B. (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). swap(i, j) swaps A[i] with A[j], for 1 ≤ i < j ≤ n.Let array B be obtained from array A by k swap operations. We need to sort B usingeither insertion sort or merge sort, and worst-case time complexity is the onlymetric.– If k = Θ(√n), which sorting algorithm is a better choice? Justify your answer.Solution:Merge sort is a better choice.A swap can introduce no more than n inversions. The total inversions will beΘ(n√n). Thus insertion sort would take Θ(n + n√n) time. However, merge sortalways takes Θ(n log n) time. So, merge sort is a better choice for this case.Grading Keys:4pts for correct choice;3pts for justifying the advantage of merge sort and disadvantage of insertion sort.– If k = Θ(√log n), which sorting algorithm is a better choice? Justify your answer.Solution:Insertion sort is a better choice.4Similar to the above analysis, insertion sort takes Θ(n +n√log n) time and mergesort takes Θ(n log n) time. So, insertion sort is a better choice.Grading Keys:4pts for correct choice;3pts for justifying the advantage of insertion sort and disadvantage of merge sort.5Problem 4B. (20 points: 5 + 5 + 5 + 5)(5 pts) Given the sequence of number as shown below in its array representation.7, 6, 5, 4, 3, 2, 1Show the binary min-heap obtained by sequential insertion into the initially emptyheap.Solution:The binary min-heap obtained is as follows:(5 pts) Given the sequence of number as shown below in its array representation.7, 6, 5, 4, 3, 2, 1Show the binary min-heap obtained by the linear time BuildHeap algorithm. Notethat you the linear time BuildHeap algorithm given in class is for a max-heap. Youhave to used the corresponding algorithm for min-heap.Solution:The binary min-heap obtained is as follows:(5 pts) Given the binary min-heap with its array representation in the following:1, 2, 3, 7, 6, 5, 46Show the binary min-heap obtained by the delete-min operation.Solution:The binary min-heap obtained is as follows:(5 pts) Given the binary min-heap with its array representation in the following:1, 2, 3, 7, 6, 5, 4Show the binary min-heap obtained by decreasing the value of the node with value 6to value 0.Solution:The binary min-heap obtained is as follows:Grading Keys:5pts for each subproblem.7Problem 5B. (20 points: 5 + 5 + 10)(5 pts) What is the number of leaf nodes in a decision tree for sorting n elements using mergesort?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