COMP$482$ Project $4$: Crazy Trampolining

Due: $2355.2024$

Points: $30$ points possible

Overview: Imagine that you had a line of trampolines each with a different strength $($some trampolines are very bouncy, but others less so$).$ You will be given an integer array $\backslash ($ B $\backslash )$ which represents the bouncyness of the trampolines. You start on the last$/$rightmost trampoline and when at position $\backslash ($ i $\backslash )$ you can boounce up to $\backslash ($ B$[$i$]\backslash )$ trampolines to the left. Your goal ts to find the minimum number of bounces necessary to go from the rightmost trampoline to the leftmost trampoline.

Details: Your java program will be provided with a file called inpultxt. The first line will contain two integers: $\backslash ($ N $\backslash )$ the number of trampolines. The remainder of the file will contain $\backslash ($ N $\backslash )$ non$-$negative values which tell you the maximum number of cells you can move to the left in a single bounce. Your goal is to determine using dynamic programming the minimum number of bounces necessary.

Picky, but required specifications: Your project must:

$-$ be submitted via canvas.

$-$ consist of $1$ or more dot$-$java files $($no elass files, dip files, irmput files, or other files should be submitted$).$

$-$ have each file begin with a comment containing your name and the project number.

$-$ not be placed into any packagc.

$-$ have one file called Project$4.$java $($don$\text{'}$t be coneerned if canvas adds a 'flag' $-1,-2,...$ for repeated submissions$).$

$-$ compile with the command 'javac Project$4,$java".

$*$ run using the command java Project$4".$

$-$ accept input from a file called inputixt in the same directory as the Java file$($s$)$ formatted precisely as described above.

$-$ accomplishes the goal of the project. In ofher words. the output should be the correct answer formatted correctly.

$-$ be submitted on time $($early and multiple times is fine$).$

For each listed item you fail to follow, expect to lose at least $5$ points. However, submitting via email will guarantee you a zero.

Examples: Your program should work on any valid input. I will be testing on much, much larger inputs. So you must use dynamic programming. Using ordinary recursion will result in a very slow exponential time algorithm instead of the obvious $\backslash (\backslash$Theta$\backslash$left$($N$^\{2\}\backslash$right$)\backslash )$ algorithm. If you are looking for a challenge, see if you can speed the program up to time $\backslash (\backslash$Theta$($N$)\backslash ).$ I haven't written my version yet. So the following are not "real" results. Let me know if any of my hand$-$solutions are incorrect.

If inputixt contains:

then the output would be

If input.txt contains: