Question 1. In pseudo code, describe Algorithm ComputeAverage(A,n) that returns, for an input of an array A with n elements, the average value of these n elements.
Question 2 & 3. Consider the following algorithm described in pseudo code.
Algorithm Compute(n)
Input: positive integer n
Output: sum of all integers from 1 to n
value ← 0
for i ← 0 to n-1 do
value ← value + (i + 1)
end
return value
Determine the number of primitive operations of Algorithm Compute(n), counting assignments, comparisons, and returns only.
In pseudo code, describe Algorithm RecursiveCompute(n), an algorithm that outputs the sum of all integers from 1 to n as recursive algorithm.
Determine the number of primitive operations of Algorithm RecursiveCompute(n), counting assignments, comparisons, and returns only.
In pseudo code, describe Algorithm ComputeFast(n), an algorithm that outputs the sum of all integers from 1 to n in constant time.
Question 4. For the following, lg n = log2 n
Order the following functions by their growth rate (big-Oh).
f
(n) = lg n
f2(n) = n3 + 882
f
(n) = 17n +
n
0
1
f4
(n) = n lg n3
f5(n) = n3 lg n
f6(n) = 28n2 + 3
Which of the following functions are big-theta of one another?
g0
(n) = 17 · 2lg n
g1(n) = 1032
g2(n) = n lg n
1
g5(n) = 881n
g6(n) = n2 + 13
g4(n) = n
+ 81
2
f3(n) = 112 · 3n
f7(n) = 1n
g3(n) = n lg n + n
g7(n) = 1n
.
Question 5. Consider the following algorithm described in pseudo code.
. Algorithm arrayFind( , )
Input: An element and an -element array
Output: The index such that = [ ] or −1 if no element of is equal to .
←0
while < do
if = [ ] then return
else ← +1
end
return −1
Counting assignments, comparisons, and returns only, calculate the worst-case, ( ), and best-case, ( ), running times of Algorithm arrayFind.
