Exercise[32]

Pre-work

0. Read the lecture notes published at the following URL. Pay close attention to the Fibonacci example and the section on memoization.

   http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf

1. See also:
   • Algorithms
   • MR Algoreisms
2. Examine the code, read the comments, and follow the links posted at:
   • http://javascriptpi.blogspot.com/2017/01/funky-fibs.html
   • http://jdkpi.blogspot.com/2017/01/funky-fibs.html
   • http://jdkpi.blogspot.com/2017/01/big-fibs.html
3. Several reports, each listing a series of input values, output values, operation counts and run times for various "Fib functions" will be distributed in class. Study the data. Look for interesting patterns and surprising results.
4. Become more familiar with the algorithms and their implementations by performing your own experiments using both the Java code (Funky Fibs and Big Fibs) and the JavaScript code (Funky Fibs).

   You can run the Java code as follows:

   1. Paste the code into the online editor at https://www.compilejava.net/. (Be sure to overwrite the code that appears in the editor by default.)
   2. Enter one or more command line arguments in the input field that appears immediately below the text editor and above the buttons.
   3. Press the COMPILE & EXECUTE button.

Assignment

1. What is the common problem that all of the "Fib functions" (Java and JavaScript versions) are designed to solve?
2. How many distinct algorithms are used to solve the problem?
3. In English, describe how each algorithm works.
4. Compare Funky Fibs (Java) with Big Fibs (Java). What is the main difference between the two implementations?
5. Compare and contrast each distinct algorithm. In your analysis, answer the following questions.
   1. How easy or difficult do you think it is to understand the algorithm, implement it in code, and verify that it has been implemented correctly?
   2. How does the number of mathematical operations the algorithm performs vary as a function of the size of the inputs as well as the sequencing of successive inputs?
   3. How much space is required to store data used by the algorithm? Is the amount of space needed significant?
6. Compare and contrast the implementations of the algorithms. In your analysis, answer the following questions.
   1. When does the implementation produce correct and incorrect results?
   2. Discuss the performance (the time it takes to produce an answer) of each implementation. Are the performance differences significant?
7. What's the connection between each of following names and its corresponding "Fib function"?
   • Amnesic
   • Eidetic
   • Grinder
   • Unitary
   • Lacunar