CSE310 HW03 Monday 10 21 2013 Due Monday 10 28 2013 Please note that you have to typeset your assignment using either LATEX or Microsoft Word Hand written assignment will not be graded You need to submit a hardcopy before the lecture on the due date You also need to submit an electronic version at the digital drop box For the electronic version you should name your file using the format 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 9 In other words A i i 1 for i 1 2 10 Suppose you are applying the linear time buildheap 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 specify After heapify A 5 the array contents are followed by the array contents Then do the same for i 4 3 2 1 Answer After heapif y A 5 the array is 0 1 2 3 9 5 6 7 8 4 After heapif y A 4 the array is 0 1 2 8 9 5 6 7 3 4 After heapif y A 3 the array is 0 1 6 8 9 5 2 7 3 4 After heapif y A 2 the array is 0 9 6 8 4 5 2 7 3 1 After heapif y A 1 the array is 9 8 6 7 4 5 2 0 3 1 1 Grading 2 pts for each correct array 2 10 pts Starting with an empty max heap you are to insert the numbers 0 1 2 3 4 5 6 7 8 9 into 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 8 insertions Show the array contents after the first 9 insertions Show the array contents after the first 10 insertions Answer After 6 iterations the array is 5 3 4 0 2 1 After 7 iterations the array is 6 3 5 0 2 1 4 After 8 iterations the array is 7 6 5 3 2 1 4 0 After 9 iterations the array is 8 7 5 6 2 1 4 0 3 After 10 iterations the array is 9 8 5 6 7 1 4 0 3 2 Grading 2 pts for each correct array 3 10 pts In class we have studied the linear time selection algorithm with group size 5 Suppose we will use group size 17 instead of 5 Again we are using the median of medians as the pivot 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 pivot element You should not use the asymptotic notations Answer The maximum number of elements on either side is l m dn 17e 25 n 9 2 34 n 18 2 4pts Let T n denote the worst case time complexity of your algorithm Write down the recurrence formula for T n Answer n T 25n 18 bn T n T 17 34 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 some operations 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 array 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 applied in 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 some operations 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 array elements Suppose we are using union by rank and find with path compression Show the array contents after each of the following operations these operations are applied in sequential 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 Grading Binary 5
View Full Document
Unlocking...