Question - CS 5633: Analysis of Algorithms Spring 2014Homework 1
Please turn in a hard copy at the beginning of class on 1/23/14 .
1. Loop Invariants (10 points) :
Consider the code below with computes log nfor any n 0.
function log(n )
k = n
c = 0
while k >1do
k = k/2
c = c+ 1
end while
return c
end function
(a) State a loop invariant for the while loop that will allow you to prove t he
correctness of the algorithm.
(b) Use the loop invariant to prove the correctness of the algorith m. For this you
need to prove by induction that the invariant holds for each iteratio n of the
loop, and then use the loop invariant after the last iteration of the lo op to
prove the correctness of the algorithm.
(c) What is the runtime of the algorithm?
2. Evaluating Ru ntimes (10 points) :
Give the -running time for each example. Justify your answers
(a) fori= 0; i < n ;i = i+ 1 do
for j= 2 i; j < n ;j = j+ 3 do
· · ·
end for
end for
1
(b)fori= 3 n; i > 0;i= i 4do
for j= 20 n; j > 0;j= j /3do
· · ·
end for
end for
(c) fori= 3 n2
; i > 0;i= i 1do
for j= i; j > 0;j= j /2do
· · ·
end for
end for
3. Asymptotic Growth (10 points) :
Prove the following statements are true using the denitions of O, o,,and .
(a) 4 n5
50n2
+ 10 n ( n5
)
(b) 5 n2
/3
+ 8 log n o(n ).
(c) n5
+ 4 n2
+ 15 ( n3
)
4. Big-Oh Sorting (10 points) :
Sort the following functions in order of non-decreasing asymptotic growth. That is,
order them f
1, f
2, f
3. . . such that f
1
O(f
2)
, f
2
O(f
3), etc.
10 n
n1
/3
nn
log 2n n 5
2
log
2n
2