CSE310 HW03 Thursday 02 18 2010 Due Thursday 02 25 2010 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 HW03 LastName FirstName 1 10 pts Assume that you are using quicksort to sort 6 elements a1 a2 a6 Also assume that the elements are distinct Draw the part of the decision tree that contains the path from the root node to the leaf node corresponding to the ordering a1 a3 a5 a2 a4 a6 Solution The decision tree is as follows 1 Grading 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 is O n2 Solution Suppose the average time complexity of insertion sort for sorting n elements is T n Thus the average time complexity of sorting the first n 1 elements is T n 1 The average time for inserting the nth element is n1 1 2 n 1 n 1 So we have 1 1 2 n 1 n 1 n n 1 1 T n 1 2 n T n T n 1 By solving this equation we can get n 1 1 2 n n 1 T n 1 T n 2 2 n n 1 1 T n 2 T n 3 2 n 2 T n T n 1 T 2 T 1 3 1 2 2 We can get the equation concerning T n by adding up all the above n 1 equations 3 1 1 1 1 n 1 n n 1 T 1 2 2 2 2 n n 1 n 2 2 n 1 n 4 1 1 1 1 T 1 4 n n 1 n 2 2 1 1 1 1 O n2 T 1 n n 1 n 2 2 T n The average time complexity of sorting the first element is 0 or T 1 0 n 1 1 1 1 X1 1 log n n n 1 n 2 2 n 1 n 2 Thus we can derive that 1 1 1 1 T 1 n n 1 n 2 2 2 O n log n T n O n2 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 empty binary min heap 9 8 7 6 5 4 3 2 1 Show the binary min heap after each insertion Solution After 1st insertion After 2nd insertion After 3rd insertion After 4th insertion 3 After 5th insertion After 6th insertion After 7th insertion After 8th insertion 4 After 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 1 You are to build the binary min heap using the linear time algorithm Show the tree views after each of the 4 heapify calls from the outside loop not the recursive calls Solution After 1st heapify call 5 After 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 6 9 8 3 7 6 2 1 5 4 Show the binary max heap obtained after inserting the element 8 5 into the max heap Given the binary max heap in its array form 9 8 3 7 6 2 1 5 4 Show 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 operation 7
View Full Document
Unlocking...