hello , I need help with this question(java and pseudo code ) In class, we discu
ID: 3756149 • Letter: H
Question
hello , I need help with this question(java and pseudo code )
In class, we discussed about the two versions of Fibonacci number calculations: BinaryFib(n) and LinearFibonacci(n) (refer to your slides and the text book). The first algorithm has exponential time complexity, while the second one is linear.
a) In this programming assignment, you will design an algorithm (in pseudo code), and implement (in Java), two recursive versions of an Oddonacci calculator (similar to the ones of Fibonacci) and experimentally compare their runtime performances. Oddonacci numbers are inspired by Fibonacci numbers but start with three predetermined values, each value afterwards being the sum of the preceding three values. The first few Oddonacci numbers are:
1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, 2209, 4063, 7473, 13745, 25281, 46499, ...
For that, with each implemented version you will calculate Oddonacci(5), Oddonacci (10), etc. in increments of 5 up to Oddonacci(100) (or higher value if required for your timing measurement) and measure the corresponding run times. For instance, Oddonacci(10) returns 105 as value. You can use Java’s built-in time function for this purpose. You should redirect the output of each program to an out.txt file. You should write about your observations on the timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled files, and the text files.
Explanation / Answer
Executable Code -: (For exponential complexity)
import java.io.*;
class oddonacci
{
static long oddonacciseries(long n)
{
if (n <= 3)
return 1;
return oddonacciseries(n-1) + oddonacciseries(n-2)+oddonacciseries(n-3);
}
public static void main(String[] args) throws IOException
{
FileWriter fw1=new FileWriter("out.txt");
FileWriter fw2=new FileWriter("time.txt");
for(long i=5;i<=35;i+=5)
{
// starting time
long start = System.currentTimeMillis();
long os=oddonacciseries(i);
System.out.println(os);
// ending time
long end = System.currentTimeMillis();
fw1.write("Oddonacci(" + i+") ="+ os+" ");
fw2.write("Time in Oddonacci(" + i+") ="+
(end - start) + "ms ");
}
fw1.close();
fw2.close();
}
}
Ouput file for result
Oddonacci(5) =5 Oddonacci(10) =105 Oddonacci(15) =2209 Oddonacci(20) =46499 Oddonacci(25) =978793 Oddonacci(30) =20603361 Oddonacci(35) =433695873
Ouput file for Time measurements
Time in Oddonacci(5) =4ms Time in Oddonacci(10) =5ms Time in Oddonacci(15) =1ms Time in Oddonacci(20) =2ms Time in Oddonacci(25) =6ms Time in Oddonacci(30) =97ms Time in Oddonacci(35) =2042ms
Pseudo Code (For exponential complexity)(for oddonacci function only)
Start
if(n<=3)
return 1
else
return oddonacciseries(n-1) + oddonacciseries(n-2)+oddonacciseries(n-3)
End
Executable Code -: (For linear time complexity)
import java.io.*;
class oddonaccilinear
{
static long odl(int n)
{
long f[] = new long[n+3]; // 1 extra to handle case, n = 0
int i;
/* 0th and 1st and 2nd number of the series are1*/
f[0] = 1;
f[1] = 1;
f[2] = 1;
for (i = 3; i <= n; i++)
{
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i-1] + f[i-2]+f[i-3];
}
return f[n-1];
}
public static void main(String[] args) throws IOException
{
FileWriter fw1=new FileWriter("out1.txt");
FileWriter fw2=new FileWriter("tim2.txt");
for(int i=5;i<=70;i+=5)
{
// starting time
long start = System.currentTimeMillis();
long os=odl(i);
System.out.println(os);
// ending time
long end = System.currentTimeMillis();
fw1.write("Oddonacci(" + i+") ="+ os+" ");
fw2.write("Time in Oddonacci(" + i+") ="+
(end - start) + "ms ");
}
fw1.close();
fw2.close();
}
}
Pseudo Code (For linear complexity)(for oddonacci function only)
Start
initilize a array of size n+3
make value of f[0]=1
make value of f[1]=1
make value of f[2]=1
loop from i=0 to i<=n
make value of f[i]=f[i-1]+f[i-2]+f[i-3]
return f[n-1]
End
Ouput file for result
Oddonacci(5) =5 Oddonacci(10) =105 Oddonacci(15) =2209 Oddonacci(20) =46499 Oddonacci(25) =978793 Oddonacci(30) =20603361 Oddonacci(35) =433695873 Oddonacci(40) =9129195487 Oddonacci(45) =192167404461 Oddonacci(50) =4045078385041 Oddonacci(55) =85147942685809 Oddonacci(60) =1792344042191491 Oddonacci(65) =37728417907092161 Oddonacci(70) =794174268033812681
Ouput file for Time measurements
Time in Oddonacci(5) =4ms Time in Oddonacci(10) =1ms Time in Oddonacci(15) =0ms Time in Oddonacci(20) =0ms Time in Oddonacci(25) =0ms Time in Oddonacci(30) =1ms Time in Oddonacci(35) =1ms Time in Oddonacci(40) =0ms Time in Oddonacci(45) =0ms Time in Oddonacci(50) =0ms Time in Oddonacci(55) =1ms Time in Oddonacci(60) =0ms Time in Oddonacci(65) =0ms Time in Oddonacci(70) =1ms
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.