Please identify each problem as shown here, with a two-letter code prefixing the exercise number.
CA12.32: The ps procedure that follows calculates how many ways we can
parenthesize an
n-operand expression. For example, ps(4) evaluates to 5 because there
are five
ways to parenthesize a four-operand expression:
a−(b−(c−d)),
a−((b−c)−d),
(a−b)−(c−d),
(a−(b−c))−d, and
((a−b)−c)−d.
Write both a
memoized and a dynamic programming version of the procedure.
def ps(n):
if n == 1:
return 1
elif n == 2:
return 1
else:
total = 0
for k in range(1,n):
total += ps(k) * ps(n-k)
return total
CA12.29, that is, Exercise 12.29 on page 413 of Concrete Abstractions. Write your procedures in Python, not Scheme.
Extra Credit: Using dynamic programming, implement choose(m, p) so that it takes only O(p) space, instead of O(mp) space.