Question

The purpose of this assignment is to reinforce dynamic programming algorithms. Specifically, the assignment is to do problem 15-8 on page 409 of the text. In addition, implement the algorithm that you construct. You may write your program in any modern language. I suggest Python because the output can be put in a visual representation

Part 1 reinforces the recurrence relation of the Fibonacci sequence with a comparison to the dynamic programming algorithm. (goals 1, 3, 4)

Using the same algorithm in different ways illustrates the efficiency achieved by different algorithmic methods.

Part 2 reinforce the use of algorithms using a modern language.

Answer 1

DP algo->

FIB(n)

dp=[0,1]

for i=2 to n do -> add(dp[i-1]+dp[i-2]) to dp list

return dp list

Code in Python

1) recursion

2) recursion with memoization

3) dynamic programming

Code

def fibrec(n):
if n<=1: return n
else: return fibrec(n-1)+fibrec(n-2)

for i in range(10):
print(fibrec(i),end=' ')

def fibrecDP(n, dp):
if n<=1:
dp[n]=n
return n
if dp[n]==-1: dp[n] = fibrecDP(n-1,dp)+fibrecDP(n-2,dp)
return dp[n]

dp=[]
n=10
for i in range(n+1):
dp.append(-1)
fibrecDP(n,dp)
print(dp)

def fibDP(n):
dp = [0,1]
for i in range(2,n+1):
dp.append(dp[i-1]+dp[i-2])
return dp

n=10
print(fibDP(n))