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. 4. (a) By drawing out all full binary tree with 3, 5, or 7 vertices, determine the exact values of B3, Bs, and B. Why we have left out even numbers of vertices, like B4 and B6? (b) For general n, derive a recurrence relation for Bn (c) Show by induction that Bn is 2) 5. You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(n log n Given a sorted array of distinct integers A[1 .. n], you want to find out whether there is an index k for which A[k]-k. Give a divide-and-conquer algorithm that runs in time (log n). 6