1. Consider the following algorithm: Algorithm Sum( m , n ) //Input: A positive
ID: 3671006 • Letter: 1
Question
1. Consider the following algorithm:
Algorithm Sum(m, n)
//Input: A positive integer n and another positive integer m n
//Output: ?
sum = 0
for i=m to n do
for j=1 to i do
sum = sum + 5
end for j
end for i
return sum
What does the algorithm compute? Show and determine the formula for the total number of additions (sum = sum + 5) performed by the algorithm.
_____________________________________________________________________________________________________
2. Consider the following recursive algorithm:
Algorithm Recursive(A[0..n-1])
//Input: A list A[0..n-1] of real numbers
//Output: ?
if n == 1 return A[0]
else do
value = Recursive(A[0..n-2])
if value > A[n-1] return value else return A[n-1]
end if
What does the algorithm compute? Establish and solve the recurrence relation for the total number of element comparisons (value > A[n-1]) performed by the algorithm.
Explanation / Answer
1.The first algoorithm will give the table of 5 from 5 to 50
output will be as follows
5
10
15
20
25
30
35
40
45
50
So total number of additions performmed is 10
2.
If the value of n is ,then the algorithm will return the first element
If the value is greater than the last but one element,then return value,otherwise return last but one element.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.