CS 6363 002 DESIGN AND ANALYSIS OF COMPUTER ALGORITHM HOMEWORK 1 Problem 1 Problem 2 2 p40 a We need to show that the elements of A form a permutation of the elements of A b Loop invariant At the start of the each iteration of the for loop of lines 2 4 A j min A k j k n and the subarray A 1 n is a permutation of the values that were in A j n at the time that the loop started Initialization Initially j n and the subarray A j n consists of single element A n The loop invariant trivially holds Maintenance Consider an iteration for a given value of j By the loop invariant A j is is the smallest value in A j n Lines 3 4 exchange A j and A j 1 if A j is less than A j 1 and so A j 1 will be the smallest value in A j 1 n afterward Since the only change to the subarray A j 1 n is this possible exchange and the subarray A j n is a permutation of the values that were in A j n at the time that he loop started we see that A j 1 n is a permutation of the values that were in A j 1 n at the time that the loop started Decrementing j for the next iteration maintains the invariant Termination The loop terminates when j reaches i By the statement of the loop invariant A i min A k i k n and A i n is a permutation of the values that were in A i n at the time that the loop started Loop invariant At the start of each iteration of the for loop of lined 1 4 the subarray A 1 i 1 consists of the i 1 smallest values originally in A 1 n in sorted order and A 1 n consists of the n i 1 remaining values originally A 1 n c Initialization Before the first iteration of the loop i 1 The subarray A 1 i 1 is empty and so the loop invariant vacuously holds 1 Maintenance Consider an iteration for a given value of i By the loop invariant A 1 i 1 consists of the i smallest values in A 1 n in sorted order Part b showed that after executing the for loop of lines 2 4 A i is the smallest value in A 1 n and so A 1 i is now the i smallest values originally in A 1 n in sorted order Moreover since the for loop of lines 2 4 permutes A i n the subarray A i 1 n consists of the n i remaining values originally in A 1 n Termination The for loop of lines 1 4 terminates when i n so that i 1 n 1 By the statement of the loop invariant A 1 i 1 is the subarray A 1 n 1 and it consists of the n 1 smallest values originally in A 1 n in sorted order The remaining element must be the largest value in A 1 n and it is in A n Therefore the entire array A 1 n is sorted d The running time depends on the number of iterations of the for loop of lines 2 4 For a given value of i this loop makes n i iterations and i takes on the values 1 2 n 1 The total number of iterations therefore is Thus the running time of bubblesort is n2 in all cases The word case running time is the same as that of insertion sort Problem 2 1 f n 100n1 01 log n n1 01 g n n log n 5 n f n g n 2 Let m log n then n 2m f n log n log n log m m g n n1 01 log n 21 01m m 2 m m 2 lim lim log 2 f n g n 3 2 lim 4 lim lim 2 2 0 f n g n Problem 3 1 Consider lim log lim log log 0 cn o log log n n 2 1 2 2 2 2 2 Because 2 and 3 Problem 4 3 4 p 62 1 False Let f n n and g n n2 Then n O n2 but not n2 O n 2 False Let f n n and g n n2 Then min f n g n n but not n2 n n 3 True 4 False Let f n 2n and g n n Then 2n O n but not 22n O 2n 5 Yes and No If f n 1 for large n then f n 2 f n and the upper bound will not hold Otherwise f n 1 and the statement is trivially true 6 Yes f n O g n implies g n f n We have f n c g n for positive c and thus f n g n 7 False Let f n 2n then f 2 2n 2 8 Show that f n o f n f n Problem 5 4 3 7 p62 4 3 Apply Master Method with a 4 b 3 f n n Master method Case 1 T n nlog34 Now we apply substitution method Guess T n c nlog34 hold true for some n0 4 With n larger than 3n0 4 3 4 3 Since 0 we fail to prove that T n c nlog34 Hold true for n larger than n0 New guess T n c nlog34 dn hold true for some n0 With n larger than 3n0 4 4 3 3 4 3 3 T n c nlog34 dn hold true when d 3 4 T n O nlog34 Similarly we can prove that T n c nlog34 d n for some c d T n nlog34 From and T n nlog34 5 Problem 6 4 3 9 p 88 Problem 7 1 T n T n 2 n where T 0 1 T n n n 2 T n 4 T n n n 2 n 4 T n 6 T n n n 2 n 4 n 6 T n 8 T n n n 2 n 4 n n 2 T 0 T n n n 2 n 4 2 1 T n 1 n2 2 T n 7 T n 4 n3 where n 4k and T 1 1 T n n3 7 T n 4 T n n3 7 n 4 3 7 T n 16 T n n3 7 n 4 3 72 n3 46 T n 16 T n n3 7 64 n3 7 64 2 n3 7 64 k 1n3 7k 6 T n n3 7k k log 7k When n is big enough T n n3 Constant nlog47 n3 Problem 8 6 4 3 160 HEAPSORT A Increasing Order Decreasing Order Build Max Heap A O n O 1 For i A length down to 2 O n O n O logn O logn Exchange A 1 …
View Full Document
Unlocking...