Analysis of Algorithms Homework #1 SOlution

Description

Justify all of your answers with comments/text in order to receive full credit.

Completing the assignment in Latex will earn you extra credit on Midterm 1.

1. Sorting (10 points)

Consider the sorting algorithm below which sorts the array A[1 : : : n] into increasing order by repeatedly bubbling the minimum element of the remaining array to the left.

Algorithm 1 mysterysort(int A[1 : : : n])

i = 1 // C1 | 1

while i <= n do // C2 | n + 1

//(I) The elements in A[1 : : : (i 1)] of the array are in sorted order and

are all smaller than the elements in A[i : : : n]

k = n; // C3 | n
// tk = # of times while loop executes
n
while (k >= i + 1) do // C4 | P(tk + 1)
1
//Inner while loop moves the smallest element in A[i : : : n] to A[i]
n
if A[k 1] > A[k] then // C5 | Ptk
1
n
swap A[k] with A[k 1] // C6 | Worst Case: Ptk Best Case: 0
1
end if
n
k ; // C7 | Ptk
1
end while

i + +; // C8 | n

end while

(1) (2 points) Consider running the above sort on the array [5; 3; 1; 4; 2]. Show the sequence of changes which the algorithm makes to the array.
5 3 1 4 2 ! 1 5 3 2 4 ! 1 2 5 3 4 !

1 2 3 5 4 ! 1 2 3 4 5

(2) (4 points) Use induction to prove the loop invariant (I) is true and then use this to prove the correctness of the algorithm. Speci cally complete the following:

(a) Base case

! i = 1 ) No elements in A[1 : : : i 1], so loop invariant trivially holds true
(b) Inductive step

(Hint: you can assume that the inner loop moves the smallest ele-

ment in A[i : : : n] to A[i])
! iold = value before iteration

! A[1 : : : iold 1] are sorted and smaller than A[iold : : : n]

! Inner loop moves the smallest element in A[iold : : : n] to A[iold] )
A[1 : : : iold] are now in sorted order and smaller than A[iold +
1 : : : n]
! Since inew = iold + 1, A[1 : : : inew 1] are sorted and smaller than

A[inew : : : n], thus maintaining the loop invariant after iteration
(c) Termination step

! Terminates when i > n, i.e. i = n + 1

! Loop invariant says A[1 : : : i 1] are sorted and smaller than

A[i : : : n]

! i = n + 1 ) A[1 : : : n] are sorted and smaller than A[n + 1 : : : n], i.e. the entire array is now sorted and the algorithm terminates correctly producing a sorted array

(3) (2 points) Give the best-case and worst-case runtimes of this sort in asymptotic (i.e., O) notation.

Worst Case:

! Array is in reverse order ) C1 + (C3 + C8)n + C2(n + 1) + (C5 + C6 +
n n
C7) Ptk + C4 P(tk + 1)
1 1
n n
! C4 P(tk + 1) = C4n + C4 Ptk
1 1
n
! tk = n k ) P(n k) = n 1 + n 2 + ::: + 2 + 1 n(n2 1)

1
Best Case:

! Array is in sorted order ) C1 + (C3 + C8)n + C2(n + 1)
n n n
C7) Ptk + C4 P(tk + 1) + C6 P0
1 1 1

2 O(n2)

+ (C5 +
! Only C6 is not executed, so the runtime is the same as worst case ) f(n) 2 O(n2)

2. Asymptotic Notation (8 points)

Show the following using the de nitions of O, , and .

(1) (2 points) 2n3 + n2 + 4 2 (n3) f(n) 2 O(n3):
! 2n3 + n2 + 4 2n3 + n3 + 4n3 = 7n3
! 7n3 Cn3 for C = 7 and n n0 = 1 > 0 ) f(n) 2 O(n3) f(n) 2 (n3):

! 2n3 + n2 + 4 n3 + 0 + 0 = n3
! n3 Cn3 for C = 1 and n n0 = 1 > 0 ) f(n) 2 (n3) Since f(n) 2 O(n3) and f(n) 2 (n3) ) f(n) 2 (n3)
(2) (2 points) 3n4 9n2 + 4n 2 (n4)
(Hint: careful with the negative number) f(n) 2 O(n4):
! 3n4 9n2 + 4n 3n4 0 + 4n(n3) = 3n4 + 4n4 = 7n4
! 7n4 for C = 7 and n0 = 1 ) f(n) 2 O(n4)
f(n) 2 (n4):
! 3n4 3 3n2 + 4n 3n4 n n n2 + 0 = 3n4 n4 = 2n4
! n4 C = 24 n 0 = 3 ) f(n) 2 (n4)
4 2 for and 4 )
Since f(n) 2 O(n ) and f(n) 2 (n ) ) f(n) 2 (n
(3) (4 points) Suppose f(n) 2 O(g1(n)) and f(n) 2 O(g2(n)). Which of the following are true? Justify your answers using the de nition of O. Give a counter example if it is false.
(a) f(n) 2 O( 5 g1(n) + 100 )
! f(n) 2 O(g1(n)) ) f(n) C g1(n) for C = k1 and n0 = k2

! 5 k1 g1(n) 5 k1 g1(n) + 100 ! By de nition f(n) 2 O(5g1(n) + 100) for C = k1 and n0 = k2
(b) f(n) 2 O( g1(n) + g2(n) )

! f(n) 2 O(g1(n)) ) f(n) C1 g1(n) for C1 = k1 and n0 = k2 ! f(n) 2 O(g2(n)) ) f(n) C2 g2(n) for C2 = m1 and n0 = m2 ! f(n) k1 g1(n) + m1 g2(n) k1 m1(g1(n) + g2(n))

! By de nition f(n) 2 O(g1(n) + g2(n)) for C = k1 m1 and n0 = max(k2; m2)

g2(n)

! False, Counterexample: f(n) = n, g1(n) = n, g2(n) = n2

! f(n) 2 O(n), f(n) 2 O(n2), f(n) 2= O(nn2 ) ) f(n) 2= O(n 1)

(d) f(n) 2 O( max(g1(n); g2(n)) )
! Trivially true, since f(n) C1 g1(n) and f(n) C2 g2(n)

! Clearly, f(n) will be less than or equal to the larger of the two functions.

! Thus, f(n) 2 O(max(g1(n); g2(n)))

3. Summations (4 points) Find the order of growth of the following sums.

n n n
iP
(1) (4i + 1):
=5
) 4 P i + P 1
i=5 i=5
n 4
) 4( P i P i) + (n 4) = 4(n(n2+1) 10) + (n 4)

i=1 i=1
) 2n2 + 3n 44 ) sum is O(n2)
log2(n)
(2) P 2i (for simplicity you can assume n is a power of 2)
i=0
) From formula sum = 1 2log2(n)+1
1 2
) 1 2log2(n) 2 = 1 2n = 2n 1 ) sum is O(n)
1 1