Spring 2010 CSE310 Midterm Examination 01A in class Instructions There are five problems in this paper Please use the space provided below the questions to write the answers Budget your time to solve various problems roughly 15 minutes for each problem and avoid spending too much time on a particular question This is a closed book examination You may not consult your books notes You are NOT supposed to use a pencil If you use pencil you cannot challenge your grade after the midterm is graded NAME ASUID Question Score P1 P2 P3 P4 P5 Total 0 Problem 1A 20 points 4 4 4 4 4 Use O or to relate each of the following pairs of functions In particular you need to write your answer as f n O g n f n g n or f n g n In case f n g n you will not receive credit if you write f n O g n or f n g n although both are implied by f n g n 1 f n n log n g n n X n i 1 i Solution f n g n 2 f n 1 01n g n n1000 Solution f n g n 3 f n n X 2 3 i g n n i 1 n X i i 1 Solution f n g n 4 f n n g n 3n 5n Solution f n g n 5 f n n X 1 g n n0 0001 i i 1 Solution f n O g n Grading Keys 4pts for each subproblem 1 Problem 2A 20 points 5 5 5 5 There are two algorithms A1 A2 with time complexities T1 n T2 n respectively We know that T1 n 27T1 n 3 n2 T2 n 26T2 n 3 8n2 1 Use the master method to decide the asymptotic notation of T1 n Solution For this recurrence we have a 27 b 3 f n n2 and thus we have that nlogb a nlog3 27 n3 Since n2 O nlogb a where 0 1 we can apply case 1 of the master method and conclude that the solution is T1 n n3 Grading Keys 2pts for justifying the right case 3pts for conclusion 2 Use the master method to decide the asymptotic notation of T2 n You may use log3 26 2 9656 in your calculations Solution For this recurrence we have a 26 b 3 f n 8n2 and thus we have that nlogb a nlog3 26 Since n2 O nlog3 26 where 0 1 we can apply case 1 of the master method and conclude that the solution is T2 n nlog3 26 Grading Keys 2pts for justifying the right case 3pts for conclusion 3 Which algorithm is asymptotically faster Solution The algorithm A2 is asymptotically faster Grading Keys 5pts for right answer 4 The recurrence T n 27T n 3 8n2 describes the running time of an algorithm A A competing algorithm A0 has a running time of T 0 n aT 0 n 9 n2 What is the largest integer value for a such that A0 is asymptotically faster than A Solution 2 The time complexity of T n is T n n3 For any integer a such that a 81 the time complexity of T 0 n is T 0 n log9 a Since algorithm A0 is asymptotically faster than A we have that log9 a 3 From the inequality we get a 729 Therefore the largest integer value for a is 728 Grading Keys 5pts for correct answer 3pts for knowing log9 a log3 27 3 Problem 3A 20 points 6 14 6 pts What are the major steps in Divide and Conquer Use merge sort to illustrate the steps Also give the time complexities of the major steps assuming sorting n elements Solution Divide divide array into two sub arrays with the size n 2 The time complexity of divide is O 1 Conquer sort each sub array by recursively calling merge sort Merge merge two sub arrays into one sorted array The time complexity is O n Grading Keys 2pts 2pts 2pts 3pts for the for the for the will be illustration of divide illustration of conquer illustration of combine cut off if there is no clarification of time complexity 14 pts Suppose you have an array A 1 n which contains n numbers in sorted order where n is a very big number n 10000 The operation swap i j swaps A i with A j for 1 i j n We also call j i the distance of swap i j Let array B be obtained from array A by k swap operations each with distance no more than 10 We need to sort B using either insertion sort or merge sort and worst case time complexity is the only metric If k n log n which sorting algorithm is a better choice Justify your answer Solution Insertion sort is a better choice A swap can introduce no more than 10 inversions The total inversions will be 10n log n n log n Thus insertion sort would take n n log n time However merge sort always takes n log n time So insertion sort is a better choice for this case Grading Keys 4pts for correct choice 3pts for justifying the advantage of insertion sort and disadvantage of merge sort 4 If k n which sorting algorithm is a better choice Justify your answer Solution Insertion sort is a better choice Similar to the above analysis insertion sort takes n n time and merge sort takes n log n time So insertion sort is still a better choice Grading Keys 4pts for correct choice 3pts for justifying the advantage of insertion sort and disadvantage of merge sort 5 Problem 4A 20 points 5 5 5 5 5 pts Given the sequence of number as shown below in its array representation 1 2 3 4 5 6 7 Show the binary max heap obtained by sequential insertion into the initially empty heap Solution The binary max heap obtained is as follows 5 pts Given the sequence of number as shown below in its array representation 1 2 3 4 5 6 7 Show the binary max heap obtained by the linear time BuildHeap algorithm Solution The binary max heap obtained is as follows 5 pts Given the binary max heap with its array representation in the following 7 6 5 1 2 3 4 Show the binary max heap obtained by the delete max operation Solution The binary max heap obtained is as follows 6 5 pts Given the binary max heap with its array representation in the following 7 6 5 1 2 3 4 Show the binary max heap obtained by inserting a node with value 9 Solution The binary max heap obtained is as follows Grading Keys 5pts for each subproblem 7 Problem 5A 20 points 5 5 10 5 pts What is the number of leaf nodes in a decision tree for sorting n elements using heapsort Solution The number of leaf nodes is n Grading keys 5pts for correct answer …
View Full Document
Unlocking...