Problem 5.1 Fibonacci Numbers (12 points)
(a) (5 points) Implement all four methods to compute Fibonacci numbers that were discussed in the lecture: (1) naive recursive, (2) bottom up, (3) closed form, and (4) using the matrix representation.
(b) (3 points) 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 (self-written 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 2 f0; 1; 2; 3; 4; 5; 6; 8; 10; 13; 16; 20; 25; 32; 40; 50; 63; :::g.
(c) (2 points) For the same n, do all methods always return the same Fibonacci number? Ex-plain your answer.
(d) Bonus (2 points) 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 (10 points)
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).
(a) (2 points) Derive the asymptotic time complexity depending on the number of bits n for a brute-force implementation of the multiplication.
(b) (4 points) 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.
(c) (1 point) Derive a recurrence for the time complexity of the Divide & Conquer algorithm you developed for subpoint (b).
(d) Bonus (2 points) Solve the recurrence in subpoint (c) using the recursion tree method.
(e) (1 point) Validate the solution in subpoint (d) by using the master theorem to solve the recurrence again.
How to submit your solutions
You can submit your solutions via Grader at https://grader.eecs.jacobs-university.de as a generated PDF file and/or source code files.
If there are problems with Grader (but only then), you can submit the file by sending mail to k.lipskoch@jacobs-university.de with a subject line that starts with CH-231-A.
Please note, that after the deadline it will not be possible to submit solutions. It is useless to send solutions by mail, because they will not be graded.
