1. [25 points] A binary tree is full if all of its vertices have either zero or two children. Let Bn
denote the number of full binary trees with n vertices.
(a) By drawing out all full binary trees with 3, 5, and 7 vertices, determine the exact values
of B3 , B5 , and B7 .
(b) Why have we left out full binary trees with even number of vertices, like B4, in part (a)
(c) For general n, derive a recurrence relation for Bn .
(d) Show by induction (substitution) that Bn is 2
(n) .
2. [25 points] Consider the problem of merging two sorted arrays A and B of n elements each
into one sorted array C of 2n elements. This problem asks you to prove that the minimum
number of comparisons to perform this task is 2n 1. The problem is split into two parts:
a) Show that if two elements x ∈ A and y ∈ B are consecutive in C, then they must be
compared.
b) Given the result from part (a), show that the lower bound on the number of comparisons
for merging A and B is 2n 1.