1. Consider the method that recursively calculates the Fibonacci sequence:

[1 pt] How many problems are at the deepest level in the recursion tree?

[1 pt] How many leaves are in the recursion tree as a function of n?

[1 pt] How many levels are in the recursion tree as a function of n?

int fib( int n )

{

if ( ( n == 0 ) || ( n == 1 ) ) {

return n;

}

else {

return ( f(n-1) + f(n-2) );

}

}

Assume that you are going to do this with all the recursive calls, rather than calculating and storing intermediate results (silly, I know, but for the purpose of this problem, its what Im looking for). For this problem, you may assume that n > 2.

[2 pts] Draw the top three levels of the recursion tree for fib(n)

1. Suppose that your friend decides to go to college at Metro State, and unlike most students, they plan to take all their courses here. They are going to go to school full time, taking three 4-credit courses every semester. They are going to major in Computer Science and minor in Math. Theyre very picky, so they plan to take 30 specific courses to graduate.

Assume that there is a 4-year schedule available (ha!) so that they know the day of every course, every semester, and the prerequisites for every course. Assume they only want to take courses that meet once per week in the evenings.

Using no more than the rest of this page, how would you approach this problem, using the techniques of solving constraint satisfaction problems that you have learned so far in this course? What algorithm(s) would you use, why, in what order?

Note that this is an intentionally open-ended question. There are a number of good strategies. One real challenge is to concisely explain what choices you made, and why you made the choices that you did.