$*************************$

public class Fibonacci $\{$

$/**$

public static long calculateFibonacciNumber$($int n$)\{$

$//$To Do

$\}$

public static void main$($String$[]$ args$)\{$

int n $=$ Integer.parseInt$($args$[0])$;

System.out.println$($calculatesFibonacciNumber$($n$))$;

$\}$

$\}$

$**************************$

$1-$ Use the Java code template above to implement the linear time Fibonacci algorithm shown below. Name the Java file LinearFibonacci.java.

function fib$2($n$)$

if n$=0$: return $0$

create an array f$[0...$n$]$

f$[0]=0,$ f$[1]=1$

for i $=2...$ n:

f$[$i$]=$ f$[$i$-1]+$ f$[$i$-2]$

return f$[$n$]$

$2-$ Test your Java Fibonacci program with n $=0,1,2,3,4,5,6,7,8,9.$ You may have to come with large integer numbers to see the effect on the algorithm runtime.

$3-$ Use the R code below to measure and visualize the runtime.

$*******************************$

k $<-10$

ns $<-34+(1$:k$)$

runtime $<-$ vector$($length $=$ k$)$

for $($i in $1$:k$)\{$

n $<-$ ns$[$i$]$

# Measure execution time of Java program

command $<-$ paste$("$java Fibonacci", n$)$

# Measure execution time and convert to microseconds

runtime$[$i$]<-$ system.time$($system$($command$,$ intern $=$ TRUE$))["$user$.$self"$]*1$e$6$

$\}$

# Plotting the results

plot$($ns$,$ runtime, type $="$b$",$ xlab $="$n$",$ ylab $=$ "runtime $($microsecond$)")$

grid$($col $=$ "blue"$)$

$***************************$