Referring to the slides from text book, Chapter 5, also added to moodle, there a
ID: 3877579 • Letter: R
Question
Referring to the slides from text book, Chapter 5, also added to moodle, there are two versions of Fibonacci number calculators: BinaryFib(n) and LinearFibonacci(n). The first algorithm has exponential time complexity, while the second one is linear. a) In this programming assignment, you will implement in Java both the versions of Fibonacci calculators and experimentally compare their runtime performances. For that, with each implemented version you will calculate Fibonnaci (5), Fibonacci (10), etc. in increments of 5 up to Fibonacci (100) (or higher value if required for your timing measurement) and measure the corresponding run times. You need to 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 timing measurements in a separate text or pdf file. You are required to submit the two fully commented Java source files, the compiled executables, and the text/pdf files. b) Briefly explain why the first algorithm is of exponential complexity and the second one is linear (more specifically, how the second algorithm resolves some specific bottleneck(s) of the first algorithm). You can write your answer in a separate file and submit it together with the other submissions. c) Do any of the previous two algorithms use tail recursion? Why or why not? Explain your answer. If your answer is ``No’’ then i. design the pseudo code for a tail recursive version of Fibonacci calculator; ii. implement the corresponding Java program and repeat the same experiments as in part (a) above. You will need to submit both the pseudo code and the Java program, together with your experimental results.
Referring to the slides from text book, Chapter 5, also added to moodle, there are two versions of Fibonacci number calculators: BinaryFib(n) and LinearFibonacci(n). The first algorithm has exponential time complexity, while the second one is linear a) In this programming assignment, you will implement in Java both the versions of Fibonacci calculators and experimentally compare their runtime performances. For that, with each implementeExplanation / Answer
A)
Binary
----------
package task2018;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class BinaryFibinicciCalculation {
public static void main(String args[]) {
List<String> outputList = new ArrayList<String>();
long startTime = System.currentTimeMillis();
long endTime = System.currentTimeMillis();
for (int i = 5; i < 50;) {
System.out.println();
i = i + 5;
endTime = System.currentTimeMillis();
outputList.add("i = " + i + ", Value = " + fib(i)
+ ", Time Taken = " + (endTime - startTime)+ " ");
startTime = endTime;
}
writeFile(outputList);
}
private static long fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
private static void writeFile(List<String> stringList) {
BufferedWriter bw = null;
FileWriter fw = null;
try {
fw = new FileWriter("E://binary_recursive_output.txt");
bw = new BufferedWriter(fw);
for (String line : stringList) {
bw.write(line);
bw.write(" ");
}
System.out.println(" File Writing Done");
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
if (bw != null)
bw.close();
if (fw != null)
fw.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
}
}
Output at ( E://binary_recursive_output.txt) You can change this path from program.
-----------
i = 10, Value = 55, Time Taken = 0
i = 15, Value = 610, Time Taken = 0
i = 20, Value = 6765, Time Taken = 0
i = 25, Value = 75025, Time Taken = 1
i = 30, Value = 832040, Time Taken = 5
i = 35, Value = 9227465, Time Taken = 5
i = 40, Value = 102334155, Time Taken = 56
i = 45, Value = 1134903170, Time Taken = 639
i = 50, Value = 12586269025, Time Taken = 7039
2. Linear Recursive Approch
----------------------------------------
package task2018;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class LinearFibonicciCalculation {
private static long fib(int num) {
long f[] = new long[num + 1];
int indx;
f[0] = 0;
f[1] = 1;
for (indx = 2; indx <= num; indx++) {
f[indx] = f[indx - 1] + f[indx - 2];
}
return f[num];
}
public static void main(String args[]) {
List<String> outputList = new ArrayList<String>();
long startTime = System.currentTimeMillis();
long endTime = System.currentTimeMillis();
for (int i = 5; i < 50;) {
i = i + 5;
endTime = System.currentTimeMillis();
outputList.add("i = " + i + ", Value = " + fib(i)
+ ", Time Taken = " + (endTime - startTime)+" ");
startTime = endTime;
}
writeFile(outputList);
}
private static void writeFile(List<String> stringList) {
BufferedWriter bw = null;
FileWriter fw = null;
try {
fw = new FileWriter("E://linear_recursive_output.txt");
bw = new BufferedWriter(fw);
for (String line : stringList) {
bw.write(line);
bw.write(" ");
}
System.out.println(" File Writing Done");
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
if (bw != null)
bw.close();
if (fw != null)
fw.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
}
}
Output at "E://linear_recursive_output.txt"
You can chnage this path from above code.
i = 10, Value = 55, Time Taken = 0
i = 15, Value = 610, Time Taken = 0
i = 20, Value = 6765, Time Taken = 0
i = 25, Value = 75025, Time Taken = 0
i = 30, Value = 832040, Time Taken = 0
i = 35, Value = 9227465, Time Taken = 0
i = 40, Value = 102334155, Time Taken = 0
i = 45, Value = 1134903170, Time Taken = 0
i = 50, Value = 12586269025, Time Taken = 0
B)
Description
-----------------
You can see the output given for the both the approch along wiht code.
there are three information printed in file against every execution of loop having interval of 5.
1. i iteration
2. Value or series sum
3. time in milisecond.
Now you can check that in Bineray recursive approach, time taken by second last and last interation is very high almost 639 and 7039 miliseconds or 1 and 7 seconds . and loop run for max 50 if we run the same loop for 100 then definately this time will reach to miunte which is very very high time consumtion.
Now instead of recursive approach if you check the linear approch output then you will find that within few miliseconds , all the execution got completed. so we can say Binary is very slow approach than linear.
Reason
------------
Fibonicci series works in following way
fib(2) = f(1) + fib(0)
fib(3) = fib(2) + fib(1)
fib(4) = fib(3) + fib(2)
......... = ........ + ........
fib(n) = fib(n-1) + fib(n-2) and so on.
so if you see in binary approach that the time taken grows exponentially with n. The reason is that fib(6), for example, calls fib(5) and fib(4). Fib(5) calls fib(4) again and fib(3).
a lot of work is being done repeatedly many times.
where in linear approach we reuse the already calculated values. we use array to store the already created values and reuse them whenever required.
You can check the code where we have taken array { long f[] = new long[num + 1]; }
we have Here no need to calcuate fib(4) twice and that is reason this approach is doing calculation in very few miliseconds or fast.
C)
package task2018;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class TailRecursiveFibCalculation {
private static long fib(long n, long a, long b) {
if (n == 0)
return a;
if (n == 1)
return b;
return fib(n - 1, b, a + b);
}
public static void main(String[] args) {
List<String> outputList = new ArrayList<String>();
long startTime = System.currentTimeMillis();
long endTime = System.currentTimeMillis();
for (long i = 5; i < 50;) {
i = i + 5;
endTime = System.currentTimeMillis();
outputList.add("i = " + i + ", Value = " + fib(i, 0, 1)
+ ", Time Taken = " + (endTime - startTime) + " ");
startTime = endTime;
}
writeFile(outputList);
}
private static void writeFile(List<String> stringList) {
BufferedWriter bw = null;
FileWriter fw = null;
try {
fw = new FileWriter("E://tail_recursive_output.txt");
bw = new BufferedWriter(fw);
for (String line : stringList) {
bw.write(line);
bw.write(" ");
}
System.out.println(" File Writing Done");
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
if (bw != null)
bw.close();
if (fw != null)
fw.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
}
}
Output
------------
i = 10, Value = 55, Time Taken = 0
i = 15, Value = 610, Time Taken = 0
i = 20, Value = 6765, Time Taken = 0
i = 25, Value = 75025, Time Taken = 0
i = 30, Value = 832040, Time Taken = 0
i = 35, Value = 9227465, Time Taken = 0
i = 40, Value = 102334155, Time Taken = 0
i = 45, Value = 1134903170, Time Taken = 0
i = 50, Value = 12586269025, Time Taken = 0
Description
----------------
Tail recursive approach is different then linear approach beacuse in linear approach we use array to store the calcuated value and reuse them when in tail recusive approach
we use last two calculated values and generate the third number of fibonicci series and we continue perform this task till the requirment n < 50 doesnot get meat.
you can check we have used following code in tail recursive approach
private static long fib(long n, long a, long b)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.