Pascal's triangle looks as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
The first entry in a row is 1 and the last entry is 1 (except for the first
row which contains only 1), and every other entry in Pascal's triangle
is equal to the sum of the following two entries: the entry that is in
the previous row and the same column, and the entry that is in the
previous row and previous column.
(a) Give a recursive defnition for the entry C[i, j] at row i and col-
umn j of Pascal's triangle. Make sure that you distinguish the
base case(s).
(b) Give a recursive algorithm to compute C[i, j]; i >= j >= 1. Illus-
trate by drawing a diagram (tree) the steps that your algorithm
performs to compute C[6, 4]. Does your algorithm perform over-
lapping computations?
(c) Use dynamic programming to design an O(n2) time algorithm
that computes the first n rows in Pascal's triangle. Does the dy-
namic programming algorithm performs better than the recursive
algorithm? Explain.
