Fall 2013 CSE310 Midterm 1A 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 Cell phones and computers are not allowed However you can use a basic calculator You are NOT supposed to use a pencil If you use a 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 100 log n g n 0 001 n X i i 1 Answer f n O g n 2 f n 1 0001n g n n300 Answer f n g n 3 f n n X 2 3 i g n n i 1 n X i i 1 Answer f n g n 4 f n 2 n g n 2 n Answer f n O g n n X 100 i 1 i Answer f n g n 5 f n n0 1 g n 1 Problem 2A 20 points 5 5 5 5 There are two algorithms A1 and A2 with time complexities T1 n and T2 n respectively We know that T1 n 7T1 n 2 1000n2 T2 n 8T2 n 2 n2 1 Use the master method to decide the asymptotic notation of T1 n You may use log2 7 2 81 in your calculations Answer a 7 b 2 f n 1000n2 logb a 2 81 Take 0 1 then f n O n logb a This is case 1 of the master method So T1 n n2 81 Grading 5 pts for the correct answer If the answer is wrong earn 2 pts for knowing the correct case 2 Use the master method to decide the asymptotic notation of T2 n You may use log2 8 3 in your calculations Answer a 8 b 2 f n n2 logb a 3 Take 0 1 then f n O n logb a This is case 1 of the master method So T1 n n3 Grading 5 pts for the correct answer If the answer is wrong earn 2 pts for knowing the correct case 3 Which algorithm is asymptotically faster Answer A1 is faster Grading 5 pts for the correct answer No credit for saying T1 is faster or T2 is faster 4 The recurrence T n 7T n 2 n2 describes the running time of an algorithm A A competing algorithm A0 has a running time of T 0 n aT 0 n 4 10n2 What is the largest integer value for a such that A0 is asymptotically faster than A You have to write down the value of a and a brief explanation Answer Using the master method we know that T n nlog2 7 If a 49 then T 0 n nlog2 7 For any a 49 we have case 1 and T 0 n nlog4 a and hence T 0 n nlog2 7 For a 48 we have case 1 and T 0 n nlog4 48 Since log4 48 log4 49 log2 7 a 48 is the largest integer value for a such that algorithm A0 is asymptotically faster than A Grading 5 pts for the correct answer If the answer is wrong earn 3 pts for writing a 49 2 Problem 3A 20 points 10 5 5 You are given the array A of 6 elements such that A 1 10 A 2 60 A 3 20 A 4 50 A 5 30 A 6 40 You are to sort A by calling quicksort A 1 6 The codes for quicksort and partition are listed for your reference quicksort A p r if p r k partition A p r quicksort A p k 1 quicksort A k 1 r partition A p r x A r i p 1 for j p to r 1 do if A j x i i 1 exchange A i and A j exchange A i 1 and A r return i 1 10 pts Given the function call quicksort A 1 6 there will be many comparisons in the form A j x when partition is called List the first 10 such comparisons in the given order made by the algorithm The first comparison is listed for you 1 10 40 2 60 40 3 20 40 4 50 40 5 6 10 30 7 20 30 8 10 20 9 60 50 10 30 40 Grading earn 1 pt each till the fist mistake 5 pts Write out the array content after one call to partition is completed A 1 10 A 2 20 A 3 30 A 4 40 A 5 60 A 6 50 Grading binary 5 pts Write out the array content after three calls to quicksort are completed A 1 10 A 2 20 A 3 30 A 4 40 Grading binary 3 A 5 60 A 6 50 Problem 4A 20 points 5 15 5 pts Given an array of 5 integers such that A 1 50 A 2 10 A 3 20 A 4 40 and A 5 30 List all of the inversions of this array 1 2 1 3 1 4 1 5 4 5 Grading earn 1 pt for each correct inversion earn 1 pt for each wrong inversion No credit for writing the pair of values rather than the pair of indices 15 pts Array B is a sorted array of n integers where n is a very large number Array C is obtained from array B by swapping two elements Now we have to sort array C Use asymptotic notation to denote the number of basic operations needed by insertion sort for sorting C Answer n Grading binary Use asymptotic notation to denote the number of basic operations needed by quicksort for sorting n elements Answer n log n Grading binary Between quicksort and insertion sort which algorithm is the faster algorithm for sorting array C Why Answer Insertion sort is faster since it requires n basic operations However quicksort requires n log n basic operations Grading 3 pts for correct answer 3 pts for correct explanation 4 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 quicksort Answer n Grading binary 5 pts Denote the lower bound on the height of a decision tree with N leaf nodes using asymptotic notation Answer log N Grading binary 10 pts Draw part of …
View Full Document
Unlocking...