# CS 61A

Time: Thu 9/21/17 2 pm

## Tree Recursions

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:

• 1 element of 1 possibility
`a`
• 2 elements of 1 possibility
`ab`
• 3 elements of 2 possibilities
`(ab)c`
`a(bc)`
• 4 elements of 5 possibilities
`a(b(cd))`
`a((bc)d)`
`(ab)(cd)`
`(a(bc))d`
`((ab)c)d`

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)
1
>>> count_groupings(2)
1
>>> count_groupings(3)
2
>>> count_groupings(4)
5
>>> count_groupings(5)
14
"""
if n == 1:
return

i =
while :

i += 1
return ``````

## 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.