Time: Thu 9/21/17 2 pm
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) 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
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.