Multipart question part 23 answer part b below Pascals trian

Multipart question part 2/3, answer part b) below.

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.

Solution

def print_pascal_tringle(rows):
left = [1]
right = [1, 1]
tringle = [left, right]
r = []
if rows == 1:
left[0] = str(left[0])
print(\' \'.join(left))
elif rows == 2:
for o in tringle:
for a in range(len(o)):
o[a] = str(o[a])
print((\' \')*(2-(a+1)), (\' \'.join(o)))
else:
for i in range(2, rows):
tringle.append([1]*i)
for n in range(1, i):
tringle[i][n] = (tringle[i-1][n-1]+tringle[i-1][n])
tringle[i].append(1)
for x in range(len(tringle)):
for y in tringle[x]:
s = str(y)
r.append(s)
print((\' \')*(rows-(x+1)), (\' \' .join(r)))
r = []
print_pascal_tringle(5)

Output: