Fall 2013 CSE310 Midterm 1A (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. Cellphones and computers are not allowed. However, you can use a basic calculator.• You are NOT supposed to use a pencil. If you use a 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) = 100 × log n, g(n) = 0.001 ×nXi=1i.Answer: f(n) ∈ O(g(n)).2. f(n) = 1.0001n, g(n) = n300.Answer: f(n) ∈ Ω(g(n)).3. f(n) =nXi=1i2, g(n) = n3+nXi=1i.Answer: f(n) ∈ Θ(g(n)).4. f(n) = 2 × n!, g(n) = (2 × n)!.Answer: f(n) ∈ O(g(n)).5. f(n) = n0.1, g(n) =nXi=1100i.Answer: f(n) ∈ Ω(g(n)).1Problem 2A. (20 points: 5 + 5 + 5 + 5)There are two algorithms A1and A2, with time complexities T1(n) and T2(n), respectively.We know that T1(n) = 7T1(n/2) + 1000n2; T2(n) = 8T2(n/2) + n2;1. Use the master method to decide the asymptotic notation of T1(n). You may uselog27 = 2.81 in your calculations.Answer: a = 7, b = 2, f(n) = 1000n2. logba = 2.81. Take  = 0.1, then f(n) ∈O(n(logba)−). This is case 1 of the master method. So T1(n) ∈ Θ(n2.81).Grading: 5 pts for the correct answer. If the answer is wrong, earn 2 pts for knowingthe correct case.2. Use the master method to decide the asymptotic notation of T2(n). You may uselog28 = 3 in your calculations.Answer: a = 8, b = 2, f(n) = n2. logba = 3. Take  = 0.1, then f(n) ∈ O(n(logba)−).This is case 1 of the master method. So T1(n) ∈ Θ(n3).Grading: 5 pts for the correct answer. If the answer is wrong, earn 2 pts for knowingthe correct case.3. Which algorithm is asymptotically faster?Answer: A1is faster.Grading: 5 pts for the correct answer. No credit for saying T1is faster or T2is faster.4. The recurrence T (n) = 7T (n/2) + n2describes the running time of an algorithm A. Acompeting algorithm A0has a running time of T0(n) = aT0(n/4) + 10n2. What is thelargest integer value for a such that A0is asymptotically faster than A? You have towrite down the value of a, and a brief explanation.Answer: Using the master method, we know that T (n) ∈ Θ(nlog27). If a = 49, thenT0(n) ∈ Θ(nlog27).For any a > 49, we have case 1 and T0(n) ∈ Θ(nlog4a), and hence T0(n) ∈ Ω(nlog27).For a = 48, we have case 1 and T0(n) ∈ Θ(nlog448). Since log448 < log449 = log27,a = 48 is the largest integer value for a such that algorithm A0is asymptotically fasterthan A.Grading: 5 pts for the correct answer. If the answer is wrong, earn 3 pts for writinga = 49.2Problem 3A. (20 points: 10 + 5 + 5)You are given the array A of 6 elements such that A[1] = 10, A[2] = 60, A[3] = 20, A[4] =50, A[5] = 30, A[6] = 40. You are to sort A by calling quicksort(A, 1, 6). The codes forquicksort and partition are listed for your reference.quicksort(A, p, r) { partition(A, p, r) {if p < r { x := A[r]; i := p-1;k := partition(A, p, r); for j:=p to r-1 do {quicksort(A, p, k-1); if (A[j] <= x) {quicksort(A, k+1, r); i := i+1;} exchange A[i] and A[j];} }}exchange A[i+1] and A[r];return i+1;}(10 pts) Given the function call quicksort(A, 1, 6), there will be many comparisons in theform A[j] <= x when partition is called. List the first 10 such comparisons in thegiven order made by the algorithm. The first comparison is listed for you.(1) 10<=40 (2) 60<=40 (3) 20<=40 (4) 50<=40 (5) 30<=40(6) 10<=30 (7) 20<=30 (8) 10<=20 (9) 60<=50 (10)Grading: earn 1 pt each till the fist mistake.(5 pts) Write out the array content after one call to partition is completed.| A[1] | A[2] | A[3] | A[4] | A[5] | A[6] || 10 | 20 | 30 | 40 | 60 | 50 |Grading: binary(5 pts) Write out the array content after three calls to quicksort are completed.| A[1] | A[2] | A[3] | A[4] | A[5] | A[6] || 10 | 20 | 30 | 40 | 60 | 50 |Grading: binary3Problem 4A. (20 points: 5 + 15)(5 pts) Given an array of 5 integers such that A[1] = 50, A[2] = 10, A[3] = 20, A[4] = 40 andA[5] = 30. List all of the inversions of this array.<1, 2>, <1, 3>, <1, 4>, <1, 5>, <4, 5>Grading: earn 1 pt for each correct inversion. earn −1 pt for each wrong inversion.No credit for writing the pair of values, rather than the pair of indices.(15 pts) Array B is a sorted array of n integers, where n is a very large number. Array C isobtained from array B by swapping two elements. Now we have to sort array C.– Use asymptotic notation Θ to denote the number of basic operations needed byinsertion sort for sorting C.Answer: Θ(n)Grading: binary– Use asymptotic notation Ω to denote the number of basic operations needed byquicksort for sorting n elements.Answer: Ω(n log n)Grading: binary– Between quicksort and insertion sort, which algorithm is the faster algorithm forsorting array C? Why?Answer: Insertion sort is faster, since it requires Θ(n) basic operations. However,quicksort requires Ω(n log n) basic operations.Grading: 3 pts for correct answer, 3 pts for correct explanation.4Problem 5A. (20 points: 5 + 5 + 10)(5 pts) What is the number of leaf nodes in a decision tree for sorting n elements using quick-sort?Answer: n!Grading: binary(5 pts) Denote the lower bound on the height of a decision tree with N leaf nodes usingasymptotic notation Ω.Answer: Ω(log N).Grading: binary(10 pts) Draw part of the decision tree for insertion sort on 6 distinct elements (a1, a2, a3, a4, a5, a6)which includes the path from the root node to the leaf node < a6, a5, a1, a2, a4, a3>.You have to label each node with the comparison made at the node and label eachedge with YES or NO. For your reference, the insertion sort algorithm is listed here.Insertion-Sort(A)for j:= 2 to length(A) do {key := A[j]i := j-1while i>0 and A[i] > key do {A[i+1] := A[i]i := i-1}A[i+1] := key}Answer:(a1 > a2 ?) -N-> (a2 > a3 ?) -N-> (a3 > a4 ?) -Y->(a2 > a4 ?) -N-> (a3 > a5 ?) -Y->(a4 > a5 ?) -Y-> (a2 > a5 ?) -Y-> (a1 > a5 ?) -Y->(a3 > a6 ?) -Y-> (a4 > a6 ?)