CS61A Homework 1

Due by 11:59 PM on (that is, the end of) Friday, 6/22

This homework must be submitted both online AND on paper.

To turn in the paper copy, place your printed homework in the homework box labeled with the name of your TA, located in 283 Soda. The front page of your homework should include ALL of the following information:

To turn in the electronic copy, submit all of your answers (except for homework 0) in a file named hw1.py. Follow the instructions here to submit the electronic copy.

Readings. All problems in this homework can be solved with the subset of Python 3 introduced in sections 1.1–1.6 of the lecture notes.

If you would like, you can use the template file hw1.py for questions 1 through 7. To copy this file to your lab account you can run the command:

      cp ~cs61a/lib/hw/hw01/hw1.py .

to copy it into your current directory.

Q0. Tell us about yourself! Print and fill out homework 0. You do NOT need to turn this question in electronically!

Q1. In order to solve the following (extremely silly and nonsensical) question, you must go to Piazza: "You're rowing down a stream and a wheel falls off your boat. How many pancakes fit in a doghouse?"

Q2. Write a function that takes three positive numbers and returns the sum of the squares of the two larger numbers. Use only a single expression for the body of the function:

      def two_of_three(a, b, c):
          """Return x**2 + y**2, where x and y are the two largest of a, b, c."""
          return ____

Q3. Let us try to write a function that does the same thing as an if statement:

      def if_function(condition, true_result, false_result):
          """Return true_result if condition is a true value, and false_result otherwise."""
          if condition:
              return true_result
              return false_result

This function actually doesn't do the same thing as an if statement in all cases. To prove this fact, write functions c, t, and f such that either with_if_function or with_if_statement returns the number 1, but the other does not:

      def with_if_statement():
          if c():
              return t()
              return f()

      def with_if_function():
          return if_function(c(), t(), f())

Q4. Fill in the following function definition to add a to the absolute value of b, without calling abs:

      from operator import add, sub
      def a_plus_abs_b(a, b):
          """Return a+abs(b), but without calling abs."""
          if ____:
              op = ____
              op = ____
          return op(a, b)

Q5. Define a function piecewise that takes two functions, f and g, along with a number b and returns a new function that takes a number x and returns either f(x) if x is less than b, or g(x) if x is greater than or equal to b.

      def piecewise(f, b, g):
          """Returns the piecewise function h where:

          h(x) = f(x) if x < b,
                 g(x) otherwise

          >>> def negate(x):
          ...     return -x
          >>> def identity(x):
          ...     return x
          >>> abs = piecewise(negate, 0, identity)
          >>> abs(6)
          >>> abs(-1)

Q6. The summation function from lecture is only the simplest of a vast number of similar abstractions that can be captured as higher-order functions. Write a similar product function that returns the product of the values of a function for n natural number arguments. Show how to define the factorial function in terms of product:

      def product(n, term):
          """Return the product of the first n terms in the sequence formed
          by applying term to the integers 1, ..., n.

          term -- a function that takes one argument

          >>> def identity(x):
          ...     return x
          >>> def square(x):
          ...     return x * x
          >>> product(3, identity) # 1 * 2 * 3
          >>> product(5, identity) # 1 * 2 * 3 * 4 * 5
          >>> product(3, square)   # 1^2 * 2^2 * 3^2
          >>> product(5, square)   # 1^2 * 2^2 * 3^2 * 4^2 * 5^2

Q7. Show that both summation and product are instances of a more general function, called accumulate, with the following signature:

      def accumulate(combiner, start, n, term):
          """Return the result of combining the first n terms in a sequence.
          >>> from operator import add
          >>> def identity(x):
          ...     return x
          >>> def square(x):
          ...     return x * x
          >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
          >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
          >>> accumulate(add, 11, 0, identity) # 11
          >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2

accumulate takes the same arguments term and n as summation and product, together with a combiner function (of two arguments) that specifies how the accumulation of the preceding terms is to be combined with each value returned by term, and a start value that specifies what base value to use to start the accumulation. Implement accumulate and show how summation and product can both be defined as simple calls to accumulate.