CS101 Lab 4: Dynamic Programming

Purpose

The purpose of this lab assignment is to reinforce the concept of dynamic programming. Dynamic programming is an algorithmic technique that can be enormously beneficial in cases where a naive recursive approach is too slow because it repeatedly recalculates answers to the same subproblems. Consider the recursive definition of the N'th Fibonacci number and the naive recursive algorithm based directly on this definition. What is the running time of this algorithm as a function of N?

NAIVE APPROACH

[10 minutes max]

Let's see what this exponential running time means in reality. Write out the recursive definition of the N's Fibonacci number. Create a Java project, Fib, add a Java class, Fib, and in that class, write a Java function, public static int fib(n). Write the code required for this function to compute and returns the n'th Fibonacci number. Write a main routine that simply calls your fib function with an integer value (say 10), stores the result in a variable, x, and then prints the value of x on the console. Run your program a handful of times to test that it appears to be working. Be sure to test the base cases where n=0 and n=1, as well as several recursive cases, including n=2, n=3, etc.

[10 minutes max]

Once your program is running properly, start increasing the value of n to find the lowest value at which you notice a delay between the time you run the program and the time it produces an answer. Just manually edit and rerun your program repeatedly to do this. You might want to increase the value of n by 5 on each run. If your program is taking too long to run, use the red square button to terminate your program run then reduce the size of n. Once you find the value of n for which the program takes a noticeable time to compute an answer, do the following: run your program for successive values, n, n+1, n+2, etc. until your program takes "too long" to run. Use a watch or a wall clock or just count one-one-thousand, two-one-thousand, etc., to obtain rough running times for each such value of n. Plot the resulting data and show your plot to a TA. What do you see? What sort of function are you looking at? Explain what's happening. For small values of N, you're seeing that an exponential-time algorithm is fine, but at some point you "hit a wall" beyond which computing answers very quickly becomes infeasible.

DYNAMIC PROGRAMMING

The problem with the recursive solution is that it computes answers to given subproblems many times. In fact, the recursive version of fib(n) calls itself approximately 2^n times in order to compute fib(n). We can do much better with dynamic programming. The idea here is to use an array to store values for sub-problems, and to solve sub-problems in an order that requires that each be solved only once.

[20 minutes max]

Add a second function to your program, dfib(n), to compute and return the n'th Fibonacci number using dynamic programming. Element 0 will hold the value of Fib(0); element 1 will hold the value of Fib(1), ..., Element n will eventually hold the value of Fib(n), and that is the value that the function will return. The structure of your program is as follows. FIRST: Allocate an array of integers to hold the intermediate results. Be careful to get the array size right! Think carefully (an important part of thinking computationally). If asked to compute dfib(5), for example, how many array elements will be needed? What is the index of the element that will hold the final answer? SECOND: Initialize the elements of the array for which you already know the answers. THIRD: write a for loop that then fills in the rest of the array based on already known and filled-in answers. FOURTH: At the end of the loop, the last array element should contain the desired answer. Simply return that value. FINALLY: Test your program and modify it if necessary to correct any "bugs" that you discover. Do this at first by simulating its execution in your mind for the simple base cases, n=0 and n=1. Watch out for special cases here. In particular, if n=0, how many array elements will you need? If you try to fill in more than that, you will end up with an "array index out of bounds" error. You might need to use an if statement to make sure that some code executes only when appropriate. Then test your program by having the main routine call fib and dfib with the same arguments, and make sure that the results are identical for small values of n.

[10 minutes]

Now create a graph like the one produced for the first version of the function. Start with the value at which you noticed that the recursive program slowed down, and now get timings for values starting from that point and going up by one. If the program appears to compute an answer instantaneously, just record zero values for the timing. Keep going until "something" goes wrong. (Can you guess what's going to happen?) At that point, stop, and graph your data. Show the TA or a colleague and explain how the runtime of the dynamic programming version of the code compares to the runtime of the recursive version. Explain, as well, what went wrong.

[10 minutes]

The problem with your program is no longer in running time. Rather, it's occurring because of the limited range of the int data type. An int in Java is only 32-bits. A long is 64 bits. In this part of the exercise, you'll see what a difference it can make to use long rather than int (at the cost of consuming additional memory space). Change the return type of dfib from int to long, and change the other types in the function accordingly. (Which ints need to change to long, and which do not? Don't just change them all.) Once again, "search" for the smallest number at which you program obviously fails to produce a correct answer. You might want to increase the value of n by fifty or a hundred at a time at first.

[10 minutes]

What is the largest value of n for which your program computes a correct answer? Quickly estimate how long it would take the recursive version of the program to compute the same answer (assuming that it used long rather than int values). Express your answer in units that make the answer easy to understand (seconds, days, weeks, or whatever). Discuss the importance of dynamic programming. How do you think dynamic programming has helped biologists to make fundamental advances in genetics? How does the simple 1-D case that we've explored here relate to the 2-D case called for in your homework this week?

SUBMISSION

Submit Fib.java as usual.