Referring to the slides from text book, Chapter 5, there are two versions of Fibonacci number 
calculators: BinaryFib(n) and LinearFibonacci(n). The first algorithm has exponential time 
complexity, while the second one is linear. 
a) In this programming assignment, you will implement in Java both the versions of Fibonacci 
calculators and experimentally compare their runtime performances. For that, with each 
implemented version you will calculate Fibonnaci (5), Fibonacci (10), etc. in increments of 5 up to 
Fibonacci (100) (or higher value if required for your timing measurement) and measure the 
corresponding run times. You need to use Java’s built-in time function for this purpose. You should 
redirect the output of each program to an out.txt file. You should write about your observations on 
timing measurements in a separate text or pdf file. You are required to submit the two fully 
commented Java source files, the compiled executables, and the text/pdf files. 
b) Briefly explain why the first algorithm is of exponential complexity and the second one is linear 
(more specifically, how the second algorithm resolves some specific bottleneck(s) of the first 
algorithm). You can write your answer in a separate file and submit it together with the other 
submissions. 
c) Do any of the previous two algorithms use tail recursion? Why or why not? Explain your answer. 
If your answer is ``No’’ then 
i. design the pseudo code for a tail recursive version of Fibonacci calculator; 
ii. implement the corresponding Java program and repeat the same experiments as in part (a) 
above. You will need to submit both the pseudo code and the Java program, together with 
your experimental results.

ComputerScienceExpert

(11)

Status NEW Posted 04 May 2017 06:05 AM My Price 9.00

-----------

Attachments

file 1493881265-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer