Homework 9
(Maximum 50 points)
Due 11:59 pm Friday April 9, 2021
Show the steps of deriving your answers. Points will be deducted for answers without adequate
steps discussed. Submit your homework via Blackboard as one PDF or Word document.
1. (25) [Fibonacci: memoization] The objective of this exercise is to run through a “full course”
of implementing a recursive function that, when evaluated, incurs significant overlapping
intermediate computations (typical of an optimal substructure in dynamic programming);
specifically, we will first remove redundant overlapping computations via memoization and then
remove the overhead of recursion via iteration. Let’s go!
Consider the Fibonacci sequence defined as a recursive mathematical function as follows:
𝐹(𝑛) = {
0 if 𝑛 = 0
1 if 𝑛 = 1
𝐹(𝑛 − 1) + 𝐹(𝑛 − 2) if 𝑛 ≥ 2
a) Write a recursive program function, “Fib(i)”, which, given an input integer i, computes a
Fibonacci number according to the mathematical definition above (by calling Fib(n)).
b) Write a recurrence relation that expresses the run-time T(n) of evaluating Fib(n), and solve it
to show that T(n) is exponential with n. A formal proof of run-time complexity is not
necessary. Hints: (1) the Fibonacci number can be approximated as 𝐹(𝑛) ≈
[𝜙𝑛]
√5
= Θ(𝜙
𝑛
)
where ϕ is the golden ratio (= 1+√5
2
= 1.61803…) and [·] denotes rounding to the nearest
integer; you can take advantage of this fact to derive that T(n) is exponential with n without
actually solving he recurrence relation; (2) the specific values of constants in the base cases
of a recurrence relation have no effect on the resulting big-O solution, so can be set to
arbitrary values as convenient for our purpose.
c) Rewrite the recursive program function Fib(i) from the exercise a by introducing
memoization array M[0..n]. Name the resulting function MFib (we call MFIb(n)).
d) Write your analysis of the run-time of MFib(n) from the exercise c and state the resulting
run-time complexity in the asymptotic big-O function of n. We do not need a recurrence
relation for this analysis. Hint: see the run-time analysis of the memorized recursive function
of Weighted Interval Scheduling in the lecture slide.
e) Rewrite the memoized recursive program function MFib(i) as a memoized iterative function.
Name the resulting function IFib; we call IFib(n)
2. (25) [Weighted Interval Scheduling: algorithm tracing] Consider the dynamic
programming algorithm we discussed for the weighted interval scheduling problem. Run the
bottom-up (i.e., iterative) implementation of the algorithm on the problem instance shown below.
Show the algorithm trace in the same manner as in Figure 6.5(a) and (b) (page 260) of the
textbook -- specifically, show in your answer:
a) The plot of sorted jobs.
b) The list of values of p(i) for each job i (i=1..8). (Note the job numbers here are the numbers
after the sorting.)
c) The memorization table (array) filled in after each iteration of the algorithm, with arrows
pointing to the array entries containing solutions to the two subproblems.
d) The set of jobs selected as a result. (There are two alternative sets of jobs that are optimal;
either one can be given as the answer.)
Last modified: April 1, 2021