Given Algorithm 0: public int fib(int n){ if (n The tree below represents Algorithm 0 traced out when n = 6: fib/6) fib(5) b(4) fb(4)

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

1

3

5

0

2

Flag this Question

Question 21 pts

2. B

3

2

1

5

0

Flag this Question

Question 31 pts

3. C

1

3

5

0

2

Flag this Question

Question 41 pts

4. D

3

2

1

0

5

Flag this Question

Question 51 pts

5. E

0

5

1

2

3

Flag this Question

Question 61 pts

6.

Algorithm 0 has _____ recursive calls for n = 6.

24

14

10

26

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

0

1

2

3

5

Flag this Question

Question 81 pts

8. B

1

2

3

5

0

Flag this Question

Question 91 pts

9. C

2

3

5

0

1

Flag this Question

Question 101 pts

10. D

5

3

2

1

0

Flag this Question

Question 111 pts

11. E

3

2

1

0

5

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.

10

14

24

20

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

The tree below represents Algorithm 0 traced out when n = 6: fib/6) fib(5) b(4) fb(4) ib(3) fib(3) St(2) fib/3) fib(2) ib(2) fib(1) ib(2) fb(1) fib(1) fib(0) fib(2) fib(1) fb(1) fib(1) fb(1) fb(0) fib(1) For questions 1 through 5, What number is passed up the recursive call at each letter?