Spring 2007 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 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 is the average case time complexity of mergesort for sorting n elements g n is the average case time complexity of quicksort for sorting n elements f n g n Grading is binary 2 f n is the worst case time complexity of mergesort for sorting n elements g n is the worst case time complexity of quicksort for sorting n elements f n O g n Grading is binary n X n X i i i 1 i 1 2 f n g n Grading is binary 3 f n i i 1 g n n3 4 f n nn g n 2n 3n f n g n Grading is binary n X n g n n1 0001 i i 1 f n O g n Grading is binary 5 f n 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 10T1 n 3 n3 T2 n 16T2 n 3 n2 5 pts Use the master method to decide the asymptotic notation of T1 n a 10 b 3 f n n3 For any constant in the interval 0 3 log3 10 we have f n nlog3 10 Also for c 10 1 we have 27 a f n b c f n Therefore we have case 3 of the master method As a result T1 n n3 Grading 3 pts for the case 2 pts for the final solution 5 pts Use the master method to decide the asymptotic notation of T2 n a 16 b 3 f n n2 For any constant in the interval 0 log3 16 2 we have f n O nlog3 16 Therefore we have case 1 of the master method As a result T2 n nlog3 16 Grading 3 pts for the case 2 pts for the final solution 5 pts Which algorithm is the faster A2 is faster 5 pts The recurrence T n 10T n 3 n2 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 The time complexity of Algorithm A is T n nlog3 10 For any integer a such that a 100 the time complexity of algorithm A0 is T 0 n nlog9 a T n For a 99 the time complexity of algorithm A0 is T 0 n nlog9 a nlog9 99 which grows slower than T n Therefore the answer is a 99 Grading 3 pts for the relationship log9 a log3 10 2 pts for the answer 2 Problem 3B 20 points 6 7 7 6 pts What are the major steps in Divide and Conquer Use quicksort to illustrate the steps Also give the time complexities of the major steps assuming sorting n elements 2pts Divide partition the array using a pivot n 2pts Conquer sort the portion to the left of the pivot recursively sort the portion to the right of the pivot recursively 2pts Combine nothing O 1 7 pts Suppose you are required to sort a very long sequence of numbers Assume that worst case time complexity is the only measurement Also we do not have any prior knowledge of the input sequence Between quicksort and heapsort which is the better algorithm for this problem Why Heapsort requires n log n time Quicksort requires n2 time Therefore heapsort is the better algorithm Grading 4 pts for the answer 3 pts for the reason 7 pts Suppose you are required to sort a very long sequence of numbers Assume that worst case time complexity is the only measurement Suppose that we know that the inversion number of the input sequence is n1 1 where n is the length of the input sequence Between insertion sort and heapsort which is the better algorithm for this problem Why Heapsort requires n log n time Insertion sort requires n1 1 time Therefore heapsort sort is the better algorithm Grading 4 pts for the answer 3 pts for the reason 3 Problem 4B 20 points 6 8 6 6 pts Given the following sequence of numbers 2 4 1 3 5 7 you are to insert the six elements in the given order to an initially empty max heap Show the resulting max heaps for the first n numbers in this sequence for n 1 2 6 2 4 4 4 5 7 2 2 3 4 4 1 1 2 1 2 3 5 2 3 1 Grading 1 pt each until the first mistake 8 pts You are given the sequence of numbers as shown in its array representation below 2 4 1 3 5 7 Compute the max heap obtained by the linear time BuildHeap algorithm You have to show the resulting array content after each of the outer Heapfy calls 2 4 7 3 5 1 2 5 7 3 4 1 7 5 2 3 4 1 Grading 2 pts each for the first two lines 4 pts for the last line 6 pts You are given a min heap with its array representation in the following 1 2 3 4 5 6 7 8 9 Show the min heap obtained after delete min from the given min heap 2 4 3 8 5 6 7 9 Grading binary 4 Problem 5B 20 points 5 5 10 5 pts What is the worst case time complexity of insertion sort for sorting n elements n2 O is OK but is not Grading is binary 5 pts Is the longest root leaf path in a decision tree related to the best case time complexity of the corresponding sorting algorithm or the worst case time complexity of the corresponding sorting algorithm Answer worst case Grading is binary 10 pts Draw part of the decision tree for insertion sort on 4 distinct elements a 1 a2 a3 a4 which includes the path from the root node to the leaf node a1 a4 a3 a2 You have to label each node with the comparison in the form ai aj made at the node and label each edge with YES …
View Full Document
Unlocking...