Write about your observations on timing measurements

Assignment Help Computer Engineering

Reference no: EM132121139

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. 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. 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. Do any of the previous two algorithms use tail recursion? Why or why not? Explain your answer.

If your answer is "No" then design the pseudo code for a tail recursive version of Fibonacci calculator; 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. Submit all your answers to written questions in PDF or text formats only.

For the Java programs. you must submit the source files together with the compiled executables. The solutions to all the questions should be zipped together into one .zip file and submitted via EAS (Refer to the course outline for more details on submission guidelines).

Reference no: EM132121139

Questions Cloud

The difference between multivalued and composite attribute : What is the difference between multivalued and composite attribute? Explain with Example.

Explain briefly what is a pixel : Regarding terminology for the quality of a picture, explain briefly What is a pixel? What is color depth?

Summarize the methodologies you used for your system : Summarize your selected software system to provide context for your colleagues. Summarise the methodologies you used for your system.

Difference between virtual memory and a memory map : What is the relation between virtual memory, a memory map, physical memory and swapping to secondary memory?

Write about your observations on timing measurements : 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 fil

How you are going to control the loading of this register : Register design A CPU register is simply a row of flip-flops (i.e. SR, JK, T, etc) put side by side in an array to make the size of register required.

What are static variables and instance variables : What is constructor? the purpose of default constructor?What are static variables and instance variables?

Identifies the key features of the organization : M5A3 Research Project - Write a short paper that identifies the key features of the organization's performance management system

Identify the primary key for each table : A client is requesting a relational database system to manage their present store with the anticipation of adding more stores in the future.

User Account

All Pages