Lab - Memoization

Part I - Laboratory Activities: Memoization

ACTIVITY: Counting nodes

In the Fibonacci tree for n = 5, how many times do you see:

• The value 3?
• The value 2?

In the Fibonacci tree for n = 7, how many times do you see:

• The value 4?
• The value 3?

Advanced: How many nodes in total for a Fibonacci tree for any size n?

ACTIVITY: Counting nodes, again

Consider the diagram on Slide 14:

How many times do you see:

• The value 3 circled? Squared?
• The value 2 circled? Squared?

Draw a Fibonacci tree for n = 7 showing memoization when it occurs. How many times do you see:

• The value 4 circled? Squared?
• The value 3 circled? Squared?

How many nodes in total are either circled or squared?

Compare these values to the previous diagram.

ACTIVITY: Fibonacci vs fibm

Find a value for n that causes the original function (Slide 4) to run for a few seconds.

Something in the range 30-50, depending on your computer.

Run the memoized version (Slide 12) on that value of n.

Run the memoized version on larger n.

Comment on the time you spend waiting for these functions.

ACTIVITY: Moosonacci numbers

Recall the Moosonacci problem, from Assignment 7.

Like Fibonacci, it's very inefficient.

Apply the memoization technique to the function moosonacci.

Compare the two versions using the timing method (Lab 06).

Attachment:- Assignment Files.rar