CSE310 HW03, Monday, 10/21/2013, Due: Monday, 10/28/2013Please 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 CSE310-HW03-LastName-FirstName.1. (10 pts) Let array A contain 10 elements from index 1 to index 10 as follows.0, 1, 2, 3, 4, 5, 6, 7, 8, 9In other words, A[i] = i − 1 for i = 1, 2, . . . , 10. Suppose you are applying the linear timebuildheap algorithm to build a max-heap from the 10 elements of array A. For i = 5, 4, 3, 2, 1,show the array structure after the call to heapify(A, i) is completed. You should specifyAfter heapify(A, 5), the array contents are: followed by the array contents. Then dothe same for i = 4, 3, 2, 1.Answer:After heapify(A, 5), the array is0, 1, 2, 3, 9, 5, 6, 7, 8, 4After heapify(A, 4), the array is0, 1, 2, 8, 9, 5, 6, 7, 3, 4After heapify(A, 3), the array is0, 1, 6, 8, 9, 5, 2, 7, 3, 4After heapify(A, 2), the array is0, 9, 6, 8, 4, 5, 2, 7, 3, 1After heapify(A, 1), the array is9, 8, 6, 7, 4, 5, 2, 0, 3, 11Grading:2 pts for each correct array.2. (10 pts) Starting with an empty max-heap, you are to insert the numbers0, 1, 2, 3, 4, 5, 6, 7, 8, 9into the max-heap in the given order. Show the array contents after the first 6 insertions.Show the array contents after the first 7 insertions. Show the array contents after the first 8insertions. Show the array contents after the first 9 insertions. Show the array contents afterthe first 10 insertions.Answer:After 6 iterations, the array is5, 3, 4, 0, 2, 1After 7 iterations, the array is6, 3, 5, 0, 2, 1, 4After 8 iterations, the array is7, 6, 5, 3, 2, 1, 4, 0After 9 iterations, the array is8, 7, 5, 6, 2, 1, 4, 0, 3After 10 iterations, the array is9, 8, 5, 6, 7, 1, 4, 0, 3, 2Grading:2 pts for each correct array.3. (10 pts) In class, we have studied the linear time selection algorithm with group size 5. Supposewe will use group size 17, instead of 5. Again, we are using the median of medians as thepivot element. Assume that there are n elements, and all elements are distinct.2(4pts) What is the maximum number of elements that can appear on either side of the pivotelement? You should not use the asymptotic notations.Answer:The maximum number of elements on either side is:n − 9ldn/17e2− 2m≤2534n + 18.(4pts) Let T (n) denote the worst-case time complexity of your algorithm. Write down therecurrence formula for T (n).Answer:T (n) = T (n17) + T (25n34+ 18) + bn.(2pts) Use the asymptotic notations to denote T (n) as a function of n.Answer:T (n) = O(n)Grading:Binary.4. (10 pts) Suppose we use the first 8 natural numbers to denote 8 different objects. After someoperations, the array contents are as follows:---------------------------------| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |---------------------------------| 5 |-1 | 7 | 8 |-1 | 2 |-1 |-1 |---------------------------------where the first row show the array indices, and the second row shows the corresponding ar-ray elements. Suppose we are using union by rank and find without path compression.Show the array contents after each of the following operations (these operations are appliedin sequential order to the given disjoint-set).(3pts) union(1, 2)Answer:---------------------------------| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |---------------------------------| 5 |-2 | 7 | 8 | 2 | 2 |-1 |-1 |3---------------------------------(3pts) union(3, 4)Answer:---------------------------------| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |---------------------------------| 5 |-2 | 7 | 8 | 2 | 2 | 8 |-2 |---------------------------------(4pts) union(1, 3)Answer:---------------------------------| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |---------------------------------| 5 | 8 | 7 | 8 | 2 | 2 | 8 |-3 |---------------------------------Grading:Binary.5. (10 pts) Suppose we use the first 8 natural numbers to denote 8 different objects. After someoperations, the array contents are as follows:---------------------------------| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |---------------------------------| 5 |-1 | 7 | 8 |-1 | 2 |-1 |-1 |---------------------------------where the first row show the array indices, and the second row shows the corresponding arrayelements. Suppose we are using union by rank and find with path compression. Showthe array contents after each of the following operations (these operations are applied insequential order to the given disjoint-set).(3pts) union(1, 2)Answer:4---------------------------------| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |---------------------------------| 5 |-2 | 7 | 8 | 2 | 2 |-1 |-1 |---------------------------------(3pts) union(3, 4)Answer:---------------------------------| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |---------------------------------| 5 |-2 | 7 | 8 | 2 | 2 | 8 |-2 |---------------------------------(4pts) union(1, 3)Answer:---------------------------------| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |---------------------------------| 2 | 8 | 8 | 8 | 2 | 2 | 8 |-3
View Full Document
Unlocking...