if it is possible, please send the text solution instead of handwriting. if hand

Question

if it is possible, please send the text solution instead of handwriting. if handwriting, please make it clear as possible as you can.

Problem 3 (3 3 bonus points). Suppose Bob has n balls of different sizes, indexed by 1,2, n. Each time, you can specify a set S C 11,2, m of size at most Vn and ask Bob the smallest ball in S. Your goal is to sort the n balls according the their sizes, using as few questions as possible (3 points). Give an algorithm that sorts the n balls using O(m) questions. You can assume n is an integer Hint. Divide S into Vn groups with size Vn, show that each the group could be sorted with O(Vn) questions and design an algorithm to merge the sorted groups. (3 bonus points). Prove that any correct sorting algorithm needs at least 2(n) ques- tions

Explanation / Answer

1. Divide the entire set of balls, S, into smaller subsets of atmost O(n) size each.
2. Let the set of this smaller subsets be G. And clearly, |G| = n
3. Let G'
4. For each subset g G
5.   Let g'
6.   For i 1 to length(g)     #Length of g will be n for all sets, except for the last, which may contain less elements.  
7.       Let a min(g)          #Ask Bob and get minimum element of g
8.       g' g' U {a}
9.        g g - {a}
10   End Loop
11. End Loop
12. While |G'| > 1
13    Let g'1, g'2 G'                        # Pick two sets from G'
14.   G' {g'1, g'2}                          # Remove them from G'
15.   G' G' U MERGE (g'1, g'2)       # Add the merged set back into G'  
16. End Loop
17. return G'

NOTE : I have explicitly written the algorithm for MERGE procedure. It's simply the MERGE procedure from MergeSort algorithm.

EXPLANATION :
   First of all, we have to divide the set of balls into smaller subset of O(n) size each. There will be n such subsets. We can do this in O(n) time, by making a single traversal over the elements of S. Let the set of these smaller subsets be G. Then for each of the n subsets present in G, we sort it in O(n) time. Therefore, step 4 to 11 are going to take O(n * n) = O(n) time.
   Now, since we have all the sorted subsets in G', we need to merge them. Every time we pick two sets from G', merge them in O(n) time and add it back into G'. Since subset each has n elements, merging them takes O(2*n) = O(n) time. And therefore, steps 12 through 16 takes O(n * n) = O(n) time.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.