Fibonacci Implementations

Math 242 practice problems

Name: _________________

Learning Goals: Compare and contrast different algorithms for computing mathematical results.

Your task: Compare and contrast our Fibonacci algorithms from class by completing problems 1 and 2 below.

Due: Monday , February 28, at 5:00pm. Upload your solution as a Mathematica notebook to the Fibonacci Implementations assignment (Moodle link)

Grading: If you answer the question above and provide computational evidence to support your answer, you will earn a Satisfactory grade.

Need help? Review the notes from class, which are posed on the course web site. If you still need help, email Prof. Wright.

Problem 1

In class we discussed three methods for computing the Fibonacci number (Subscript[F, n]) without storing a list of Fibonacci numbers: the recursive method, the iterative method, and the exact formula method. For each of these methods, determine how the runtime depends on n. Don’t just say “the runtime increases with n,” but find a function that describes how the runtime depends on n. Write one or more sentences comparing the runtimes of these three methods.

Problem 2

In class we discussed three methods for computing a list of the Fibonacci numbers (Subscript[F, 1]),(Subscript[F, 2]),...,(Subscript[F, n]). One method simply calls a function from Problem 1 to compute each value. Another method used the AppendTo function, and the third method used Table to start with a list of size n. For each of these methods, determine how the runtime depends on n. Don’t just say “the runtime increases with n,” but find a function that describes how the runtime depends on n. Write one or more sentences comparing the runtimes of these three methods.