1. Give the output of following algorithm when F(4) is called. F stands for Fibo
ID: 3821696 • Letter: 1
Question
1. Give the output of following algorithm when F(4) is called. F stands for Fibonacci numbers.
function F(n>=0:integer) :integer
if n<=1 then
F n
else
print n,
F F(n – 1) + F(n – 2),
print F
endif
return F
2. ) Consider the following problem. Given a list of n (n even) distinct positive integers, partition the list into two sub-lists of size n/2 such that the difference between the sums of the integers in the two sub-lists is maximized. Give an algorithm of lowest O complexity for solving the above problem. State your algorithm in no more than four simple English sentences. Do not write a pseudocode. What is the O complexity of your algorithm?
Explanation / Answer
function F(n>=0:integer) :integer
if n<=1 then //if n is less than or equal to 1.
F n //Assign n to result F.
else //If not.
print n, //Print n.
F F(n – 1) + F(n – 2), //The assign F(n-1) + F(n-2) to result F.
print F //Print F.
endif
return F
First let me calculate the values of F(0), F(1), F(2), F(3) before concluding on F(4)
F(0): 0 is <= 1, so will return 0.
F(1): 1 is <= 1, so will return 1.
F(2): 2 is > 1, so will print 2, then computes F F(1) + F(0) i.e., 1 + 0 = 1, and prints 1, and returns 1.
F(3): 3 is > 1, so will print 3, then computes F F(2) + F(1),
so for F(2), will print 2, then prints 1, and returns 1.
for F(1), will return 1.
Now, the sum F 1 + 1 = 2., now will print 2, and will return 2.
So,
when F(0) is called nothing will be printed, but will return 0.
when F(1) is called nothing will be printed, but will return 1.
when F(2) is called 2 1 will be printed, and will return 1.
when F(3) is called 3 2 1 2 will be printed, and will return 2.
Now, coming to F(4): will print 4, then calles F F(3) + F(2),
when called F(3) will print: 3 2 1 2, and will return 2.
when called F(2) will print: 2 1, and will return 1.
Finally, the summation 2 + 1 = 3 is assigned to F.
And will print 3.
And will return 3.
So, when F(4) is called, the output to screen is: 4 3 2 1 2 2 1 3.
And will return 3.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.