CS 61A

Time: Tue 9/12/17 2 pm

Higher Order Functions

Digit Fidget (fa15-mt1-3)

IMPORTANT DEFINITION Each digit in a non-negative integer n has a digit position. Digit positions begin at 0 and count from the right-most digit of n. For example, in 568789, the digit 9 is at position 0 and digit 7 is at position 2. The digit 8 appears at both positions 1 and 3.

  1. Implement the find_digit function, which takes a non-negative integer n and a digit d greater than 0 and less than 10. It returns the largest (left-most) position in n at which digit d appears. If d does not appear in n, then find_digit returns False. You may not use recursive calls.

    def find_digit(n, d):
      Return the largest digit position in n for which d is the digit.
      >>> find_digit(567, 7)
      >>> find_digit(567, 5)
      >>> find_digit(567, 9)
      >>> find_digit(568789, 8) # 8 appears at positions 1 and 3
      i, k = 0, 
      while n:
        n, last = n // 10, n % 10
        if last == :
        i = i + 1
  2. Find all values of y between 1 and 9 (inclusive) for which the final expression below evaluates to True. Assume that find_digit is implemented correctly.

    def compose1(f, g):
      def h(x):
        return f(g(x))
      return h
    f = lambda x: find_digit(234567, x)
    compose1(f, f)(y) == y

Lambda at Last (fa14-mt1-4)

  1. Fill in the blank below with an expression so that the second line evaluates to 2014. You may only use the names two_thousand, two, k, four, and teen and parentheses in your expression (no numbers, operators, etc.)

    two_thousand = lambda two: lambda k: 
    two_thousand(7)(lambda four: lambda teen: 2000 + four + teen)
  2. The if_fn returns a two-argument function that can be used to select among alternatives, similar to an if statement. Fill in the return expression of factorial so that it is defined correctly for non-negative arguments. You may only use the names if_fn, condition, a, b, n, factorial, base, and recursive and parentheses in your expression (no numbers, operators, etc.).

    def if_fn(condition):
      if condition:
        return lambda a, b: a
        return lambda a, b: b
    def factorial(n):
      Compute N! for non-negative N. N! = 1 * 2 * 3 * ... * N.
      >>> factorial(3)
      >>> factorial(5)
      >>> factorial(0)
      def base():
        return 1
      def recursive():
        return n * factorial(n-1)

Tree Recursion

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

Misc Midterm 1 Prep

You Complete Me (sp15-mt1-3)

Add parentheses and single-digit integers in the blanks below so that the expression on the second line evaluates to 2015. You may only add parentheses and single-digit integers. You may leave some blanks empty.

lamb = lambda lamb: lambda: lamb + lamb
lamb(1000)__________ + (lambda b, c: b__________ * b__________ - c__________)(lamb(__________), 1)__________