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. Note that at this point in the course, you'll only have seen how to solve this problem using memoization. (The exercise offers the alternative of using dynamic programming.) Write your procedures in Python, not Scheme.