QUESTION 1

Is the function below tail-recursive?

int count(link x) {

if (x == NULL) return 0;

return 1 + count(x->next);

}

True

False

10 points

QUESTION 2

In the time complexity tree, where do we write T(N)?

Please see page 10 of the Recursion slides for this. The answer is: outside of the node. (I am clarifying it as in class, I wrote only N outside of node, instead of T(N). I should have written T(N).)

	a.	inside the node
	b.	outside the node
	c.	We do not write T(N) anywhere.
	d.	There is no such thing as "time complexity tree".

10 points

QUESTION 3

In the time complexity tree, inside the node we write:

	a.	the problem size (e.g. N)
	b.	the total cost
	c.	the local cost
	d.	none of the above

10 points

QUESTION 4

In the function call tree, inside the node we write

		the problem size (e.g. N)
		the total cost
		the local cost
		none of the above

10 points

QUESTION 5

Let T be a perfect tree with branching factor of 3 (each node has 3 children, except for the leaf nodes).

How many nodes will T have on level i? (The first level, where the root is, is level 0.)

(See Trees(theory only) slides for help (do for the tree with 3 branches the same that was done for trees with 2 branches).

Review the Blackboard notation conventions to make sure you write your answer according to our conventions.)

10 points

QUESTION 6

Let T be a full tree (see definition in slides) that has P external nodes (leaves). How many total nodes (internal and external) will it have? Give the answer as a function of P.

10 points

QUESTION 7

Consider the function call tree for the function below. What is the problem size for nodes at level i ?

Hint: At level 0 the problem size is N, at level 1 the problem size is N/2, at level 2 the problem size is N/4, at level 3 the problem size is N/8,...

Give the answer as a function of i and N.

int fact_2halves(int st, int ed){

int p;

//printf("(%d,%d),", st,ed);

printf(" (st,ed) = (%d,%d) ", st,ed);

if (st==ed) return st;

p = (st+ed)/2;

return fact_2halves(st, p)*fact_2halves(p+1,ed);

}

10 points

QUESTION 8

What will fact_2halves(4,7) return?

10 points

QUESTION 9

Print the (st,ed) pairs corresponding to the function calls generated from the call fact_2halves(1,7) , in the order in which they are created (due to the function calls). See the above code for the function definition. (You can check your answer by printing st and ed at the beginning of the function),

Do not put any empty space anywhere. Use a comma between st and ed and between pairs. Use () around pairs. For example if I thought that the pairs were (in this order): (3,6) , (8,9), (1,2) I would answer:

(3,6),(8,9),(1,2)

10 points

QUESTION 10

Consider the recurrence: T(N) = T(N-1) + 5N²

Which of the following gives the correct expression T(N-1)?

		T(N-1) = T(N-2)+5N2-1
		T(N-1) = T(N-2) + 5(N-1)2
		T(N-1) = T(N-2) + 5(N2-1)
		T(N-1) = T(N-1) + 5(N2-1)
		None. They are all wrong.