Description
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.
