CSE310 HW02 Solution and Grading Keys 1 15 pt Suppose we have two algorithms A1 and A2 for solving the same problem Let T 1 n be the worst case time complexity of Algorithm A1 and T2 n be the worst case time complexity of Algorithm A2 We know that T1 1 1 and T1 n 7 T1 n 2 f n where f n n2 We also know that T2 1 1 and T2 n 63 T2 n 4 30 n2 Use the master method to decide T1 n Follow all the steps as illustrated in class a b logb a etc a 7 b 2 logb a 2 80735 For 0 0 80735 we have f n O n2 80735 Therefore we have case 1 in the Master method As a result T1 n n2 80735 Grading 1 pt for a 1 pt for b 1 pt for logb a 1 pt for the correct case 1 pt for the correct answer Use the master method to decide T2 n Follow all the steps as illustrated in class a b logb a etc a 63 b 4 logb a 2 98864 For 0 0 98864 we have f n O n2 98864 Therefore we have case 1 in the Master method As a result T2 n n2 98864 Grading 1 pt for a 1 pt for b 1 pt for logb a 1 pt for the right case 1 pt for the right answer Which algorithm is faster Why Since T1 n O T2 n but T2 n 6 O T1 n we conclude that A1 is faster Grading 3 pts for the answer 2 pts for the justification 1 2 15 pt Let A 1 n be an array of n distinct numbers i j is called an inversion of A if i j and A i A j The inversion number of A denoted by inversion A is the total number of inversions of array A What is the relationship of the running time of insertion sort and the inversion number of the input array Justify your answer The running time of insertion sort on A is n inversion A since the number of element wise comparisions used by insertion sort is n 1 inversion A Grading 3 pts for the answer 2 pts for the justification List all the inversions of the following array i 1 2 3 4 5 6 A i 8 7 9 3 4 5 1 2 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 Grading 0 5 pt for each wrong entry either an inversion not listed or a non inversion listed Take 2 pts off if the inversions are represented using A i A j rather than i j Suppose you have an array A with n elements Array B is obtained from array A by deleting an element in array A and then inserting the deleted element into some place of the array Find an upper bound on inversion A inversion B We only need to consider the case where the inversion is increased The movement of the first element can increase the inversion by at most n 1 which is achievable when the array is sorted The movement of the second element can increase the inversion by at most n 2 which is again achievable Therefore the upper bound is 2n 3 Grading 5 pts for perfect answer 4 pts for saying 2n 3 pts for saying n 1 pts for saying O n 2 3 10 pt Given the sequence 8 1 2 7 6 5 3 4 List all the element comparisons made by insertion sort in the corresponding order Use a b to denote a comparison of a and b We will denote Ai to denote the insertion of element i The number of comparisons for the insertion of each element is given below Element A1 A2 A3 A4 A5 A6 A7 A8 Comparisons Sorted array no comparisons 8 1 2 1 8 2 3 1 3 1 2 8 3 4 2 4 1 2 7 8 4 5 3 5 2 5 1 2 6 7 8 5 6 4 6 3 6 2 6 1 2 5 6 7 8 6 7 5 7 4 7 3 7 2 7 1 2 3 5 6 7 8 7 8 6 8 5 8 4 8 3 8 1 2 3 4 5 6 7 8 Grading 0 5 pt for each wrong non existent comparison 4 10 pts Prove that in a binary tree with n elements the height of the tree is greater than or equal to blog2 n c Prove that in a complete binary tree with n elements the height of the tree is exactly blog2 n c Proof of the first claim We prove this by induction on the height of the tree T We will use size T to denote the number of nodes in T and use height T to denote the height of the tree T The claim to be proved is equivalent to size T 2height T 1 1 When height T 0 the tree contains a single node i e size T 1 Since 1 2 0 1 1 this verifies that height of the tree is 0 Now assume that the claim is true for binary trees of height no more than H i e height T H size T 2height T 1 1 0 1 Assume that T is a binary tree rooted at x with height H 1 There are two cases 1 x has only one child node c 2 x has a left child l and a right child r In any case none of the subtrees rooted at a child node of x has height greater than H Therefore none of them can have size bigger than 2H 1 1 Since the size of T is 1 plus the sum of the sizes of its two subtrees we have size T 1 2 2H 1 1 2H 2 1 3 This proves that the claim is true for trees of height H 1 as well By the principle of mathematical induction the claim is true for all binary trees 2 Grading 2 pts for the base case 3 pts for the induction step If other methods are used grade similarly Proof of the second claim Let T be a complete binary tree of size size T Let k be the integer such that 2k size T 2k 1 Since T is a complete binary tree nodes 2k 2k 1 size T are the nodes at the lowest level The other 2k 1 nodes form a full binary tree which has a height of k 1 Therefore the height of T is k It follows from the choice of k we have 2k size T 2k 1 Therefore k blog2 size T c 2 Grading 3 pts for finding the right k height 2 additional pts for the completeness 4
View Full Document
Unlocking...