CSE310 HW02, Thursday, 02/04/2010, Due: Thursday, 02/11/2010Please note that you have to typeset your assignment using either LATEX or MicrosoftWord. Hand-written assignment will not be graded. You need to submit a hardcopybefore the lecture on the due date. You also need to submit an electronic version atthe digital drop box. For the electronic version, you should name your file using theformat HW02-LastName-FirstName.1. (10 pts) T(n) = 6 · T (n/2) + f(n), where f(n) = Θ(n). Use the master method to solveT (n). You need to specify a, b, logba, and decide the case. You also need to write the derivedconclusion.Solution:For this recurrence, we have a = 6, b = 2, f(n) = Θ(n), and thus we have that nlogba= nlog26.Since f(n) = Θ(n), Θ(n) ⊆ O(nlog26−), where = 1, we can apply case 1 of the mastertheorem and conclude that the solution is T (n) = Θ(nlog26).Grading Keys:1 pt for a;1 pt for b;1 pt for writing correct function f(n);5 pts for justifying the right case;2 pts for conclusion.2. (10 pts) T (n) = 3 · T (n/3) + 8n + 100√n. Use the master method to solve T (n). You needto specify a, b, logba, and decide the case. You also need to write the derived conclusion.Solution:For this recurrence, we have a = 3, b = 3, f(n) = 8n + 100√n, and thus we have thatnlogba= nlog33= Θ(n). Since f(n) = Θ(nlog33), we can apply case 2 of the master theoremand conclude that the solution is T (n) = Θ(n log n).Grading Keys:1 pt for a;1 pt for b;1 pt for writing correct function f(n);5 pts for justifying the right case;2 pts for conclusion.13. (10 pts) T (n) = 7 · T (n/2) + n3. Use the master method to solve T (n). You need to specifya, b, logba, and decide the case. You also need to write the derived conclusion.Solution:For this recurrence, we have a = 7, b = 2, f(n) = n3, and nlogba= nlog27. Since f(n) =n3= Ω(nlog27+), where ≈ 0.1, case 3 applies if we can show that the regularity conditionholds for f(n). For sufficiently large n, a · f(n/b) = 7 · (n3/23) ≤ c · f(n), where c = 7/8.Consequently, by case 3, the solution to the recurrence is T (n) = Θ(n3).Grading Keys:1 pt for a;1 pt for b;1 pt for writing correct function f(n);5 pts for justifying the right case;2 pts for conclusion.3 pts will be cut off if there is no justification of regularity condition;3 pts will be cut off if there is no claim that f(n) = Ω(nlog27+).4. (10 pts) Given the sequence8, 7, 3, 1, 4List all of the inversions in the sequence.Solution:We sequentially label the elements of the sequence with index i (i = 1, 2, 3, 4, 5). Accordingto the definition of inversion, all the inversions in this sequence are: <1, 2>, <1, 3>, <1, 4>,<1, 5>, <2, 3>, <2, 4>, <2, 5>, <3, 4>.Grading Keys:1 pt for each correct inversion.5 pts will be cut off if you do not use index representation.5. (10 pts) Let A be an array of n integers. We say element i is out of order with its left neighborif either i > 1 and A[i − 1] > A[i]. If we know that n is huge and that there are only 4elements that are out of order with its left neighbor. Between quick sort and insertion sort,which is the better algorithm for sorting array A? Justify your answer.Solution:Between quick sort and insertion sort, insertion sort is the better algorithm for sorting array2A. This is because that array A is an almost sorted array. That is to say, most elementsin array A are in their right place since array A has just 4 elements which are out of order.It is the best case for insertion sort while the worst case for quick sort. In this scenario,the number of inversions in this array is O(n), so the time complexity of insertion sort isΘ(n + O(n)) = Θ(n), however, the time complexity of quick sort is Ω(n log n).Grading Keys:6 pts for correct choice;1 pt for correct number of inversions;1 pt for correct time complexity of insertion sort;2 pts for correct time complexity of quick
View Full Document
Unlocking...