program编程代写、c++，Python程序代做、代写algorithm编程

日期：2021-04-07 10:58

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