QUESTION 1 Is the function below tail-recursive? int count(link x) { if (x == NU

Question

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).)

inside the node

outside the node

We do not write T(N) anywhere.

There is no such thing as "time complexity tree".

10 points   

QUESTION 3

In the time complexity 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 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) + 5N2   

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.

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".

Explanation / Answer

Answer)

1) True as it is a pattern where iteration occurs by avoiding the inefficiency.

2) T(N) is to be written outside the node.

Example: T(n) = O(n^2)

As per Chegg policy, a minimum of 1 question can be answered. We did 2.

Hit like if you find the answer useful. :)

Hope this answer helps. Thanks

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.