Problem regarding the fibonacci numbers

Assignment Help Basic Computer Science
Reference no: EM131106073

Fibonacci Numbers:

The Fibonacci sequence is given by : 0, 1, 1, 2, 3, 5, 8, 13, 21, ..... By definition the Fibonacci sequence starts at 0 and 1 and each subsequent number is the sum of the previous two. In mathematical terms, the sequence Fn of Fibonacci number is defined by the recurrence relation

Fn = Fn-1 + Fn-2 with F0=0 and F1=1

An algorithm for calculating the nth Fibonacci number can be implemented either recursively or iteratively.

Example Recursive:

fib (n) { if (n = 0) { return 0; } else if (n = 1) { return 1; } else { return fib(n-1) + fib(n-2); } }

Example Iterative:

fib (n) { fib = 0; a = 1; t = 0; for(k = 1 to n) { t = fib + a; a = fib; fib = t; } return fib; }

a) Implement both recursive and iterative algorithms to calculate Fibonacci Numbers in the programming language of your choice. Provide a copy of your code with your HW pdf. We will not be executing the code for this assignment. You are not required to use the flip server for this assignment.

b) Use the system clock to record the running times of each algorithm for n = 5, 10, 15, 20, 30, 50, 100, 1000, 2000, 5000, 10,000, .... You may need to modify the values of n if an algorithm runs too fast or too slow to collect the running time data. If you program in C your algorithm will run faster than if you use python. The goal of this exercise is to collect run time data. You will have to adjust the values of n so that you get times greater than 0.

c) Plot the running time data you collected on graphs with n on the x-axis and time on the y-axis. You may use Excel, Matlab, R or any other software.

d) What type of function (curve) best fits each data set? Again you can use Excel, Matlab, any software or a graphing calculator to calculate the regression curve. Give the equation of the function that best "fits" the data and draw that curve on the data plot. Why is there a difference in running times?

Reference no: EM131106073

Who should control the it policy within an organization

Who should control the IT policy within an organization and why? Does the responsibility for IT control depend on the organizational structure, the importance of the IT func

Monique food processing company

The "Monique Food Processing Company" Monique Food Processing Company produces light snacks that can be heated in a microwave. The following steps are included in the proces

Cases for a university library borrowing system

Create a set of use cases for a university library borrowing system. (Do not worry about catalogue searching, etc.) The system will record the books owned by the library and

Can you come up with a method to overcome this issue

To understand why angle-based outlier detection is a heuristic method, give an example where it does not work well. Can you come up with a method to overcome this issue?

Evaluate online tutorials and online communities

Ray and Jason have just finished developing the documentation for a system your team recently completed. Ray insists that the documentation should be printed in booklet form

Explains about the algorithm insertionsort

The insertion sort algorithm is stated below. Operation of insertion sort can be described as follows. The list at any moment is divided into two parts: sorted and unsorted.

State hypotheses test statistic and df p-value

Refer to Exercise 26 from Chapter 4 on the Alcohol Consumption data, in which a Poisson regression model was fit using first Saturday drink consumption as the response and p

Determine the diameters of each exit duct in m

Twentytwo percent of the entering mass flow exits at 10 bar, 220°C, with a velocity of 20 m/s. The rest exits at another location with a pressure of 0.06 bar, a quality of 8

Reviews

Write a Review

 
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd