CS173: Intro to Computer Science - Dynamic Programming (3 Points)

Developed by Professor Tralie and Professor Mongan.

Exercise Goals

The goals of this exercise are:
  1. To improve performance of a recursive algorithm by cacheing values via a Dynamic Program
Your job below is to change the fib method so that it checks to see if a particular Fibonacci number has been saved in memory before trying to compute it. If it's already been saved, simply return what's in memory.
Welcome to our online modules system! Be sure to log in with your Urinus ID before you proceed. For example, Professor Tralie's ID is ctralie. If you are not an Ursinus student, that's fine! Just make something up, and you can still run everything

                    

                

                

                    

                        

                    

                    

                        

                        

                        

                    

                

            


            

            
            

    



    
In this exercise [1], the main method computes fib(20) and fib(30), and by default, it outputs the following stats:



    
  
  • fib(20) = 10946, counts = 21891
    • 
  
  • fib(30) = 1346269, counts = 2692537
    • 




But once you start using the memory properly, you’ll get these stats instead, which are way more efficient



    
  
  • fib(20) = 10946, counts = 39
    • 
  
  • fib(30) = 1346269, counts = 21
    • 




In fact, now computing fib(30) takes even fewer than the 30 steps we would have done by hand, because we remembered some of the steps we did when computing fib(20) right before that.



Hints



    
  
  • Recall that to see if a key is in a HashMap map, you say map.containsKey(key), which returns true if the key is in the map and false otherwise. So you’d want to check the memory by saying something like fibMem.containsKey(N). You should use the result of this in an if statement
    • 
  
  • Recall that to retrieve values from the hash map, you use the get(key) method.
    • 





  
    
    
  1. 
      
    Developed by Prof. Chris Tralie ↩
    
    
    2.