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)
Submit your solutions e
...
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)
Submit 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]