Dynamic Programming

Objectives:

$$ Demonstrate knowledge of recursion by describing common applications and by effectively

using it to solve problems.

$$ Calculate time and space complexity of data structures and algorithms and be able to use

these complexities to choose the most appropriate for a given problem environment.

$$ Demonstrate knowledge of algorithms associated with different data structures.

$$ Apply object$-$oriented principles to the development and use of algorithms and data$-$

structures.

$$ Use of appropriate algorithms to solve common computing problems.

Problem

In chapter $12,$ section $3,$ we covered the principles and analysis of Dynamic Programming. In this

assignment you will implement and analyze the Fibonacci sequence algorithms. You will implement

two classes: Fibonacci, and Driver.

Fibonacci class:

This is a wrapper class for Fibonacci calculations. It should ONLY contain two static methods:

$$ numberRecursive$()$:

o This method calculates the nth Fibonacci number using the "classic" recursive

algorithm.

o The method receives the nth term in the Fibonacci sequence to compute then returns its

integer value.

$$ numberDynamic$()$:

o This method calculates the nth Fibonacci number using dynamic programming.

o The method receives the nth term in the Fibonacci sequence to compute then returns its

integer value.

Driver class:

Your Driver class should do the following actions:

$$ Implement your main$()$ method such that the method prompt the user to enter the nth term

of the Fibonacci sequence to compute. This value should be held in a variable named term.

$$ You program should run both algorithms and display:

$1.$ The nth value in the Fibonacci sequence from both algorithms, and

$2.$ The time it takes to compute.

$$ Record the average performance of each Fibonacci algorithm with the following nth terms $(5,$

$10,15,20,25,30,35,40,$ and $45).$ Using JavaFX plot a superimposed line graph for the two

algorithms.

Hint: how do the algorithms perform when you try to compute the $46$th term in the Fibonacci

sequence?

NOTE:

There is a PDF document required in this assignment.

$$ Comment your code.

o At the top of the program include your header comment.

o Note: Follow the instructions given.

$$ All methods should have method$-$level header comments using Javadocs convention.

$$ All blocks must be indented consistently and correctly. Blocks are delimited by opening and

closing curly braces.

$$ Opening and closing curly braces must be aligned consistently

$$ Variable names should convey meaning

Requirements

$1.$ Effectively use methods. A method should only perform at most two tasks.

$2.$ You must include all the inputs and outputs listed above and perform the computation

correctly

$3.$ Make the output look attractive.

$4.$ The program should display your name

Hints:

$$ Solve the problem in pieces.

$$ Start early.

Deliverables:

Submit the following items:

$2.$ Convert your description file to a PDF and name it as LastnameFirstname$\_$PA$04.$ Upload

this file SEPARATE from your project's $.$zip file

Note: Strictly follow the export instructions to submit your assignment.

Analysis:

$1.$ Make a MS Word document or equivalent, then copy and paste your plotted graph.

$2.$ describe your findings. In your description, be sure to

include which of the two Fibonacci algorithms performed better and why. Provide proof

of your findings.