Description

•  Implement all four methods to compute Fibonacci numbers that were discussedin the lecture: (1) naive recursive, (2) bottom up, (3) closed form, and (4) using the matrix representation.
•  Sample and measure the running times of all four methods for increasing n. For each method, stop the sampling when the running time exceeds some fixed amount of time (same for all methods). If needed, you may use classes or structs for large numbers (selfwritten or library components). Create a table with your results (max. 1 page). Hint: The ”gap” between samples should increase the larger n gets, e.g. n ∈{0,1,2,3,4,5,6,8,10,13,16,20,25,32,40,50,63,…}.
•  For the same n, do all methods always return the same Fibonacci number? Explain your answer.

• Bonus Plot your results in a line plot, so that the four approaches can be easily compared. Briefly interpret your results. Hint: Use logarithmic scales for your plot.

Problem 5.2 Divide & Conquer and Solving Recurrences

Consider the problem of multiplying two large integers a and b with n bits each (they are so large in terms of digits that you cannot store them in any basic data type like long long int or similar). You can assume that addition, substraction, and bit shifting can be done in linear time, i.e., in Θ(n).

• Derive the asymptotic time complexity depending on the number of bits n for a brute-force implementation of the multiplication.
•  Derive a Divide & Conquer algorithm for the given problem by splitting theproblem into two subproblems. For simplicity you can assume n to be a power of 2.
•  Derive a recurrence for the time complexity of the Divide & Conquer algorithmyou developed for subpoint (b).
• Bonus Solve the recurrence in subpoint (c) using the recursion tree method.
•  Validate the solution in subpoint (d) by using the master theorem to solve therecurrence again.