Spring 2010 CSE310 Midterm Examination 01B 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 1B 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 i i 1 Solution f n O g n 2 f n n X 2i g n n100 i 1 Solution f n g n 3 f n n X n n i g n n3 i 1 Solution f n g n 4 f n nn g n 2n 3n 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 2B 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 64T1 n 4 100n2 T2 n 63T2 n 4 800n2 5 pts Use the master method to decide the asymptotic notation of T1 n Solution For this recurrence we have a 64 b 4 f n 100n2 and thus we have that nlogb a nlog4 64 n3 Since 100n2 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 5 pts Use the master method to decide the asymptotic notation of T2 n You may use log4 63 2 9886 in your calculations Solution For this recurrence we have a 63 b 4 f n 800n2 and thus we have that nlogb a nlog4 63 Since n2 O nlog4 64 where 0 1 we can apply case 1 of the master method and conclude that the solution is T2 n nlog4 63 Grading Keys 2pts for justifying the right case 3pts for conclusion 5 pts Which algorithm is asymptotically faster Solution The algorithm A2 is asymptotically faster Grading Keys 5pts for right answer 5 pts The recurrence T n 8T n 2 n describes the running time of an algorithm A A competing algorithm A0 has a running time of T 0 n aT 0 n 4 n What is the smallest integer value for a such that A0 is asymptotically slower than A Solution 2 The time complexity of T n is T n n3 For any integer a greater than 4 the time complexity of T 0 n is T 0 n log4 a Since algorithm A0 is asymptotically slower than A we have that log4 a 3 a 43 From the inequality we get a 64 Therefore the largest integer value for a is 65 Grading Keys 5pts for correct answer 3pts for knowing log4 a log2 8 3 Problem 3B 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 swap i j swaps A i with A j for 1 i j n Let array B be obtained from array A by k swap operations We need to sort B using either insertion sort or merge sort and worst case time complexity is the only metric If k n which sorting algorithm is a better choice Justify your answer Solution Merge sort is a better choice A swap can introduce no more than n inversions The total inversions will be n n Thus insertion sort would take n n n time However merge sort always takes n log n time So merge sort is a better choice for this case Grading Keys 4pts for correct choice 3pts for justifying the advantage of merge sort and disadvantage of insertion sort If k log n which sorting algorithm is a better choice Justify your answer Solution Insertion sort is a better choice 4 Similar to the above analysis insertion sort takes n n log n time and merge sort takes n log n time So insertion sort is a better choice Grading Keys 4pts for correct choice 3pts for justifying the advantage of insertion sort and disadvantage of merge sort 5 Problem 4B 20 points 5 5 5 5 5 pts Given the sequence of number as shown below in its array representation 7 6 5 4 3 2 1 Show the binary min heap obtained by sequential insertion into the initially empty heap Solution The binary min heap obtained is as follows 5 pts Given the sequence of number as shown below in its array representation 7 6 5 4 3 2 1 Show the binary min heap obtained by the linear time BuildHeap algorithm Note that you the linear time BuildHeap algorithm given in class is for a max heap You have to used the corresponding algorithm for min heap Solution The binary min heap obtained is as follows 5 pts Given the binary min heap with its array representation in the following 1 2 3 7 6 5 4 6 Show the binary min heap obtained by the delete min operation Solution The binary min heap obtained is as follows 5 pts Given the binary min heap with its array representation in the following 1 2 3 7 6 5 4 Show the binary min heap obtained by decreasing the value of the node with value 6 to value 0 Solution The binary min heap obtained is as follows Grading Keys 5pts for each subproblem 7 Problem 5B 20 points 5 5 10 5 pts What is the number of leaf nodes in a decision tree for sorting n elements using merge sort Solution The number …
View Full Document
Unlocking...