Please help me!! Thank you so much! Question 11 pts Given Algorithm 0: public in
ID: 3592273 • Letter: P
Question
Please help me!! Thank you so much!
Question 11 pts
Given Algorithm 0:
public int fib(int n){
if (n <=1) {
return n;
}
else {
return fib(n-1) + fib(n-2);
}
}
The tree below represents Algorithm 0 traced out when n = 6:
For questions 1 through 5,
What number is passed up the recursive call at each letter?
1. A
Flag this Question
Question 21 pts
2. B
Flag this Question
Question 31 pts
3. C
Flag this Question
Question 41 pts
4. D
Flag this Question
Question 51 pts
5. E
Flag this Question
Question 61 pts
6.
Algorithm 0 has _____ recursive calls for n = 6.
Flag this Question
Question 71 pts
Algorithm 1 is a top down solution and breaks the problem into subproblems by calculating and storing the solutions to the subproblems along the way. Its time complexity is O(n), but its space complexity is also O(n) because the values are stored in the array.
Algorithm 1:
int[] map;
int mapSize;
public int fib(int n) {
map = new int[n+1];
map[0] = 0;
map[1] = 1; //stores the 0th and 1st Fibonacci numbers
mapSize = 2;
return (fibHelper(n));
}
private int fibHelper(int n) {
if (n < mapSize) {
return map[n];
} else {
map[n] = fibHelper(n - 1) + fibHelper(n - 2);
mapSize++;
return map[n];
}
}
The tree below represents Algorithm 1 traced out when n = 6:
For questions 7 through 12
What number is passed up the recursive call at each letter?
7. A
Flag this Question
Question 81 pts
8. B
Flag this Question
Question 91 pts
9. C
Flag this Question
Question 101 pts
10. D
Flag this Question
Question 111 pts
11. E
Flag this Question
Question 121 pts
12. As you can see memorization is important given the difference of recursion calls between Algorithm 0 and Algorithm 1.
Algorithm 1 has _____ recursive calls for n = 6.
Flag this Question
Question 135 pts
Algorithm 2 is a bottom up solution that calculates the smaller values first and builds from them. Its time complexity is also O(n) but its space complexity is only O(1) because it only stores the values needed for the current computation rather than an entire array. Trace Algorithm 2 by hand when n is 6 and select the correct answer below.
public int fib(int n) {
if (n == 0)
return 0;
else {
int previousFib = 0;
int currentFib = 1;
for(int i = 0; i < n-1; i++) {
int newFib = previousFib + currentFib;
previousFib = currentFib;
currentFib = newFib;
}
return currentFib;
}
}
n
previousFib
currentFib
i
newFib
6
0
1
0
1
6
1
1
1
2
6
1
2
2
3
6
2
3
3
5
6
3
5
4
8
6
5
8
5
n
previousFib
currentFib
i
newFib
6
0
1
0
1
5
1
1
1
2
4
1
2
2
3
3
2
3
3
5
2
3
5
4
8
1
5
8
5
13
n
previousFib
currentFib
i
newFib
6
0
1
0
1
6
1
1
1
2
6
1
2
2
3
6
2
3
3
5
6
3
5
4
8
6
5
8
5
13
n
previousFib
currentFib
i
newFib
6
0
1
0
1
6
1
1
1
2
6
1
2
2
3
6
2
3
3
5
6
3
5
4
8
6
5
8
5
13
6
8
13
6
n
previousFib
currentFib
i
newFib
6
0
1
1
1
6
1
1
2
2
6
1
2
3
3
6
2
3
4
5
6
3
5
5
8
6
5
8
6
1 The tree below represents Algorithm 0 traced out when n 6: fibl6) fib 4) fibl5) b(3) fib(3) Sb(2) b(4) fibl3) fb 2) hb(2) D12) b1)b(0) For questions 1 through 5, What number is passed up the recursive call at each letter?Explanation / Answer
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
1.A 1
2.B 3
3. C 1
4. D 3
5. E 0
6 24 Recursive calls
7. A 0
8. B 1
9. C 2
10.D 5
11. E 3
12. 10 RECURSIVE CALLS
QUESTION 135
a
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.