a02-solutions - University of Manitoba COMP 3170

Document Content and Description Below

University of Manitoba COMP 3170, Winter 2019 Assignment 2 Due Date: February 9, at 8:00pm There is no hurry. We shall get there some day. Rivers know this . . . A.A. Milne (Winnie-the-Pooh) Sub... mit your solutions electronically via Crowdmark. The assignment will be marked out of 65 (there is also 6 bonus marks). Please read http://www.cs.umanitoba.ca/~kamalis/ winter19/infoCOMP3170.pdf for guidelines on academic integrity. Problem 1 Quick-Select [6 marks] When doing Quick-Select and Quick-Select, it is desired to have a good pivot which is almost in the middle of the sorted array. When doing the average-case analysis of Quick-Select, we considered a good and a bad case; the good case happened when the pivot was among the half middle items of the sorted array, i.e., we had n/4 ≤ i < 3n/4 (i is the index of pivot in the partitioned array). In our analysis, we provided an upper bound for the time complexity of the algorithm in the good case and showed that T(n) ≤ T(3n/4) + cn in these cases for some constant c. Since the good case happened with probability 1/2, we could prove that the algorithm runs in linear time on average (see the recursion slide 10 of lectures on selections). Change the definition of the good case and assume the good case happens when we have n/10 ≤ i < 9n/10. Provide an upper bound for T(n) and use that to show that Quick-Select runs in O(n). Hint: start by calculating the probability of good case and bad case happening. Answer: We showed in the class that for the average cost of selection algorithm on an array of size n, we have T(n) ≤ cn + 1 n X i−1 j=0 T(n − j − 1) + Xn−1 j=i+1 T(j) ! Assuming n/10 ≤ j < 9n/10 (when pivot is good), we will have n − j − 1 < T(9n/10) and j − 1 < 9n/10. Consequently, T(n − j − 1) < T(9n/10) and T(j − 1) < T(9n/10). Note that 9n/10 − n/10 = 4n/5, i.e., with probability 4/ [Show More]

Last updated: 1 year ago

Preview 1 out of 6 pages