1 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.2 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 / m3 lim→()()= lim →log 2.∗= ∞ f(n) = Ω g(n) 3. lim→()()= lim→2 4= 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< < () 2< < Because = θ () and = θ () ∑ = θ ()4 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 n05 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 3+ ()≤4 [ 3−3] + ()≤ + −43 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)6 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 …
View Full Document
Unlocking...