1 Part I: Fundamental

Problem 1. Consider the algorithm mystery() whose input is a binary tree, or more precisely, its root R. We denote by RLeft and RRight the left and the right children of R in the tree.

Algorithm mystery(R : root of a binary tree)

if R = ∅ then

return 0;

else

return 1+mystery(RLeft)+mystery(RRight);

end if

a) What does the algorithm compute? Justify your answer.

b) What is the algorithmic paradigm that the algorithm belongs to?

c) Assume that the tree is a perfect binary tree of height h (a binary tree is called perfect if every non-leaf node has precisely two children and all leaf-nodes are at the same level). Write the recurrence relation for C(h), the number of additions required by mystery(). Convention: a single-node tree has height 0.

d) Solve the above recurrence relation by the backward substitution method to obtain an explicit formula for C(h) in h for the perfect binary tree of height h.

e) Write the complexity class that C(h) belongs to using the Big-Θ notation.