Problem 1: Fibonacci numbers
- Implement all four methods to compute Fibonacci numbers that were discussed in class: (1) naive recursive, (2) bottom up, (3) closed form, and (4) using a 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 5 seconds. Create a table with your results (max. 1 page).
Tip: the “space” between samples should increase the larger n gets, e.g. n ∈{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? Justify your answer.
- Plot your results in a line plot, so that the four approaches can be easily compared. Briefly interpret your results.
Tip: Use log scales for your plot.
Problem 2: Divide & Conquer and Solving Recurrences
Consider the problem of multiplying large integers a and b with n bits each. You can assume that addition, substraction, and bit shifting can be done in linear time, i.e., in Θ(n).
- Derive the asymptotic time complexity in the number of bits n for a brute-force implementation of the multiplication.
- Derive a divide & conquer algorithm for the given problem by splitting the problem 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 algorithm in (b).
- Solve the recurrence in (c) using the recursion tree method.
- Validate the solution in (d) by using the master theorem to solve the recurrence.
