$30.00
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
// t_{k} = # of times while loop executes
n
while (k >= i + 1) do // C4  ^{P}(t_{k} + 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  ^{P}t_{k}
1
n
swap A[k] with A[k 1] // C6  Worst Case: ^{P}t_{k} Best Case: 0
1
end if
n
k ; // C7  ^{P}t_{k}
1
end while
i + +; // C8  n
end while

(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

(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:


Base case




i = 1 ) No elements in A[1 : : : i 1], so loop invariant trivially holds true


(Hint: you can assume that the inner loop moves the smallest ele
ment in A[i : : : n] to A[i])




i_{old} = value before iteration







A[1 : : : i_{old} 1] are sorted and smaller than A[i_{old} : : : n]







Inner loop moves the smallest element in A[i_{old} : : : n] to A[i_{old}] )



A[1 : : : i_{old}] are now in sorted order and smaller than A[i_{old} +
1 : : : n]




Since i_{new} = i_{old} + 1, A[1 : : : i_{new} 1] are sorted and smaller than



A[i_{new} : : : n], thus maintaining the loop invariant after iteration



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




(2 points) Give the bestcase and worstcase 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) ^{P}t_{k} + C4 ^{P}(t_{k} + 1)
1 1
n n

C4 ^{P}(t_{k} + 1) = C4n + C4 ^{P}t_{k}
1 1
n
! t_{k} = n k ) ^{P}(n k) = n 1 + n 2 + ::: + 2 + 1 ^{n}^{(}^{n}_{2} ^{1)}
1
Best Case:

Array is in sorted order ) C1 + (C3 + C8)n + C2(n + 1)
n n n
C7) ^{P}t_{k} + C4 ^{P}(t_{k} + 1) + C6 ^{P}0
1 1 1


O(n^{2})


(C5 +


Only C6 is not executed, so the runtime is the same as worst case ) f(n) 2 O(n^{2})


Asymptotic Notation (8 points)
Show the following using the de nitions of O, , and .

(2 points) 2n^{3} + n^{2} + 4 2 (n^{3}) f(n) 2 O(n^{3}):

2n^{3} + n^{2} + 4 2n^{3} + n^{3} + 4n^{3} = 7n^{3}

7n^{3} Cn^{3} for C = 7 and n n_{0} = 1 > 0 ) f(n) 2 O(n^{3}) f(n) 2 (n^{3}):



2n^{3} + n^{2} + 4 n^{3} + 0 + 0 = n^{3}

n^{3} Cn^{3} for C = 1 and n n_{0} = 1 > 0 ) f(n) 2 (n^{3}) Since f(n) 2 O(n^{3}) and f(n) 2 (n^{3}) ) f(n) 2 (n^{3})

(Hint: careful with the negative number) f(n) 2 O(n^{4}):


3n^{4} 9n^{2} + 4n 3n^{4} 0 + 4n(n^{3}) = 3n^{4} + 4n^{4} = 7n^{4}

7n^{4} for C = 7 and n_{0} = 1 ) f(n) 2 O(n^{4})

f(n) 2 (n^{4}):


3n^{4} 3 3n^{2} + 4n 3n^{4} n n n^{2} + 0 = 3n^{4} n^{4} = 2n^{4}


!
n^{4}
C
= 2_{4}
n
_{0} = 3 )
f(n)
2
(n^{4})
4
2
for
and
4
)
Since f(n) 2 O(n
) and f(n) 2 (n ) ) f(n) 2 (n

(4 points) Suppose f(n) 2 O(g_{1}(n)) and f(n) 2 O(g_{2}(n)). Which of the following are true? Justify your answers using the de nition of O. Give a counter example if it is false.

f(n) 2 O( 5 g_{1}(n) + 100 )

f(n) 2 O(g_{1}(n)) ) f(n) C g_{1}(n) for C = k_{1} and n_{0} = k_{2}

! 5 k_{1} g_{1}(n) 5 k_{1} g_{1}(n) + 100 ! By de nition f(n) 2 O(5g_{1}(n) + 100) for C = k_{1} and n_{0} = k_{2}
(b) f(n) 2 O( g_{1}(n) + g_{2}(n) )
! f(n) 2 O(g_{1}(n)) ) f(n) C_{1} g_{1}(n) for C_{1} = k_{1} and n_{0} = k_{2} ! f(n) 2 O(g_{2}(n)) ) f(n) C_{2} g_{2}(n) for C_{2} = m_{1} and n_{0} = m_{2} ! f(n) k_{1} g_{1}(n) + m_{1} g_{2}(n) k_{1} m_{1}(g_{1}(n) + g_{2}(n))
! By de nition f(n) 2 O(g_{1}(n) + g_{2}(n)) for C = k_{1} m_{1} and n_{0} = max(k_{2}; m_{2})
g_{2}(n)



False, Counterexample: f(n) = n, g_{1}(n) = n, g_{2}(n) = n^{2}





f(n) 2 O(n), f(n) 2 O(n^{2}), f(n) 2= O(_{n}^{n}_{2} ) ) f(n) 2= O(n ^{1})




f(n) 2 O( max(g_{1}(n); g_{2}(n)) )

Trivially true, since f(n) C_{1} g_{1}(n) and f(n) C_{2} g_{2}(n)





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





Thus, f(n) 2 O(max(g_{1}(n); g_{2}(n)))



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

n
n
n
_{i}P
(1)
(4i + 1):
=5

4 ^{P} i + ^{P} 1
i=5 i=5
n 4
) 4( ^{P} i ^{P }i) + (n 4) = 4(^{n(n}_{2}^{+1)} 10) + (n 4)
i=1 i=1
) 2n^{2} + 3n 44 ) sum is O(n^{2})
log_{2}(n)
(2) ^{P} 2^{i} (for simplicity you can assume n is a power of 2)
i=0
_{)} _{From formula sum =} 1 2^{log2(n)+1}
1 2
_{)} 1 2^{log2(n)} 2 _{=} 1 2n _{= 2n} _{1 ) sum is O(n)}
1 1