CS 61A

Time: Thu 9/21/17 2 pm

Tree Recursions

Your Father's Parentheses (sp16-mt1-1)

Suppose we have a sequence of quantities that we want to multiply together, but can only multiply two at a time. We can express the various ways of doing so by counting the number of different ways to parenthesize the sequence. For example, here are the possibilities for products of 1, 2, 3 and 4 elements:

Assume, as in the table above, that we don’t want to reorder elements.
Define a function count_groupings that takes a positive integer n and returns the number of ways of parenthesizing the product of n numbers. (You might not need to use all lines.)

def count_groupings(n):
  For N >= 1, the number of distinct parenthesizations of a product of N items.

  >>> count_groupings(1)
  >>> count_groupings(2)
  >>> count_groupings(3)
  >>> count_groupings(4)
  >>> count_groupings(5)
  if n == 1:
  i = 
  while :
    i += 1

Mutual Recursions

Weekly Misc: Data Abstraction

One data abstraction introduced to the lecture so far: Rational numbers, represented by their numerators and denominators. Define constructors and selectors in very generalized terms.

Discuss the differences among Python list (& list comprehensions, unpacking), str (& some literals), dict. Furthermore, their use cases and how they can be useful to abstract data (like how list can be used to represent a rational number behind an abstraction barrier).

Oh, and what's an abstraction barrier after all?

If with extra time, try to implement data abstraction with higher order functions only.