CSE310 HW03, Thursday, 02/18/2010, Due: Thursday, 02/25/2010Please 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 HW03-LastName-FirstName.1. (10 pts) Assume that you are using quicksort to sort 6 elements a1, a2, . . . , a6. Also assumethat the elements are distinct. Draw the part of the decision tree that contains the path fromthe root node to the leaf node corresponding to the ordering a1< a3< a5< a2< a4< a6.Solution:The decision tree is as follows.1Grading Keys:Starting from root node, 1pt for each correct node, until the 1st mistake;5pts will be cut off if there are 4 blocks.2. (10 pts) Prove that the average time complexity of insertion sort for sorting n elements isO(n2).Solution:Suppose the average time complexity of insertion sort for sorting n elements is T (n). Thusthe average time complexity of sorting the first n − 1 elements is T (n − 1). The average timefor inserting the nth element is1n(1 + 2 + · · · + (n − 1) + (n − 1)).So we haveT (n) = T (n − 1) +1n(1 + 2 + · · · + (n − 1) + (n − 1))= T (n − 1) +n + 12−1nBy solving this equation, we can getT (n) = T (n − 1) +n + 12−1nT (n − 1) = T (n − 2) +n2−1nT (n − 2) = T (n − 3) +n − 12−1n − 2...T (2) = T (1) +32−12We can get the equation concerning T (n) by adding up all the above n − 1 equations.T (n) =n + 12+n2+n − 12+ · · · +32− (1n+1n − 1+1n − 2+ · · · +12) + T (1)=(n − 1)(n + 4)4− (1n+1n − 1+1n − 2+ · · · +12) + T (1)= O(n2) − (1n+1n − 1+1n − 2+ · · · +12) + T (1)The average time complexity of sorting the first element is 0, or T (1) = 0.1n+1n − 1+1n − 2+ · · · +12=nXn=11n− 1 = Θ(log n)2Thus we can derive thatT (n) = O(n2) − (1n+1n − 1+1n − 2+ · · · +12) + T (1)= O(n2) − Θ(log n)= O(n2)The statement is proved.Grading Keys:5pts for deriving correct equation of T (n);5pts for proving.3. (10 pts) You are inserting the following 9 elements (in the given order) to an originally emptybinary min-heap.9, 8, 7, 6, 5, 4, 3, 2, 1Show the binary min-heap after each insertion.Solution:After 1st insertion:After 2nd insertion:After 3rd insertion:After 4th insertion:3After 5th insertion:After 6th insertion:After 7th insertion:After 8th insertion:4After 9th insertion:Grading Keys:1pt for each correct min-heap after each insertion.4. (10 pts) Assume that the following 9 elements are in array A, starting at index 1.9, 8, 7, 6, 5, 4, 3, 2, 1You are to build the binary min-heap using the linear time algorithm. Show the tree viewsafter each of the 4 heapify calls (from the outside loop, not the recursive calls).Solution:After 1st heapify call:5After 2nd heapify call:After 3rd heapify call:After 4th heapify call:Grading Keys:1pt for tree view after 1st heapify call;2pts for tree view after 2nd heapify call;3pts for tree view after 3rd heapify call;4pts for tree view after 4th heapify call.5. (10 pts) Given the binary max-heap in its array form:69, 8, 3, 7, 6, 2, 1, 5, 4Show the binary max-heap obtained after inserting the element 8.5 into the max-heap. Giventhe binary max-heap in its array form:9, 8, 3, 7, 6, 2, 1, 5, 4Show the binary max-heap obtained after the delete-max operation.Solution:The binary max-heap obtained after inserting the element 8.5 is as follows.The binary max-heap obtained after the delete-max operation is as follows.Grading Keys:5pts for binary max-heap after inserting the element 8.5;5pts for binary max-heap after delete-max
View Full Document
Unlocking...