1) Consider the following sorting algorithm: First sort the first two thirds of
ID: 3662851 • Letter: 1
Question
1) Consider the following sorting algorithm: First sort the first two thirds of the elements in the array. Next sort the last two thirds of the elements of the array. Finally, sort the first two thirds again. (After each two-thirds sort, the relevant elements are stored in the same two thirds of the array were they resided before the sort; no extra storage is allocated.)
(a) Give an informal but convincing explanation (not a rigorous proof by induction) of why this algorithm returns a fully sorted array.
(b) Find a recurrence relation for the worst-case running time of this algorithm, then solve it by applying the Master Theorem.
2) Suppose you have a set of n coins. All of these coins have the same weight, except for one, which is fake. The fake coin weighs less than the real coins. In addition, you have a scale that you can use to weigh any two piles of coins. Given two piles, the scale will either report that the two piles have the same weight, or which of the two is lighter. Your goal is to identify the fake coin.
(a) Give an algorithm that uses the scale no more than log2 n + 1 times.
(b) Give an algorithm that uses the scale no more than log3 n + 1 times. Note here that we are not asking for O(log3 n), but for exactly log3 n + 1.
Explanation / Answer
1)
a)
7 9 8 6 5 3 1
7 9 8 6 5 // pick the first 2/3 of the set
5 6 7 8 9 3 1
7 8 9 3 1 // pick the last 2/3 of the set and sort
5 6 1 3 7 8 9
5 6 1 3 7 // finally pick the first 2/3 again
1 3 5 6 8 9 // the result is fully sorted
b)
Recurrence Relationship
T(n) = 3T*(2n/3) + O(n)
a = 3
b 3/2
c = 1
T(n)(nlog1.53)(n^2.710).
2)
1) Divide the coins in two halves.
2) weigh them
3) keep the lighter pile rejecting the other . repeat steps 1 to 3 until you are left with one coin.
b)
1) Divide the coins in three parts.
2) weigh them
3) keep the lighter pile rejecting the other . repeat steps 1 to 3 until you are left with one coin.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.