Dynamic Programming

1. (10 pts) Let B(n) be the number of different binary search trees containing the n keys 1, 2, . For this problem you will develop a dynamic programming algorithm that, given n, calculates B(n). Note that B(l) = 1 since there is only one one-node binary tree. For two nodes B(2) = 2 (either node can be root, and there is only one binary search tree consistent with each choice). (a) (I pt) Calculate by hand B(3). (b) (1 pt) How many n = 6 key binary trees are there with keys {1, 2, 3, 4, 5, 6} and key 3 at root (so the left subtree has two nodes, and the right one has 3 nodes) are there? (c) (3 pts) Construct a recurrence for B(n), I expect something with a sum. Include boundary con- ditions in your recurrence; what is a convenient boundary value for B(O)? Briefly justify (formal proof not required) that your recurrence computes the correct value. (d) (4 pts) Give an iterative (bottom up) algorithm based on the recurrence that computes B(n) by filling in a table. (e) (1 pt) What is the running time of your iterative algorithm as a function of n (use asymptotic notation)?