CS61A Homework 3

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

This homework must be submitted online. We do not require a paper copy.

To turn in the electronic copy, submit all of your answers in a file named hw3.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.7 of the lecture notes.

If you would like, you can use the template file hw3.py. To copy this file to your lab account you can run the command:

      cp ~cs61a/lib/hw/hw03/hw3.py .

to copy it into your current directory.

Q0. We would like to know if you are going to have any conflicts with the exam dates and times. Check your schedule (like the schedules for other classes you might have) to see if you have any conflicts and fill out this form (even if you have emailed us already).

Q1. A mathematical function g is defined by two cases:

      g(n) = n,                                   if n <= 3
      g(n) = g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3),  if n > 3

Write a recursive function that computes g. Then, write an iterative function, g_iter, that computes the same values.

Q2. Rewrite the continued fraction function from the last homework (question 4), continued_frac, to use recursion instead of iteration (so do not use a while loop). Hint: try writing a recursive helper function to do most of the work, rather than trying to do the recursion with continued_frac directly.

      def continued_frac(n_term, d_term, k):
          """Returns the k-term continued fraction with numerators defined by n_term
          and denominators defined by d_term.

          >>> # golden ratio
          ... round(continued_frac(lambda x: 1, lambda x: 1, 8), 3)
          0.618
          >>> # 1 / (1 + (2 / (2 + (3 / (3 + (4 / 4))))))
          ... round(continued_frac(lambda x: x, lambda x: x, 4), 6)
          0.578947
          """

Q3. A classic puzzle called the Towers of Hanoi is a game that consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

Only one disk may be moved at a time.
Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
No disk may be placed on top of a smaller disk.

Complete the definition of tower_of_hanoi which prints out the steps to solve this puzzle for any number of n disks starting from the start rod and moving them to the end rod.

      def tower_of_hanoi(n, start, end):
          """Print the moves required to solve the tower of hanoi game if we start
          with n disks on the start pole and want to move them all to the end pole.

          The game is to assumed to have 3 poles (which is traditional).

          >>> tower_of_hanoi(1, 1, 3)
          Move 1 disk from rod 1 to rod 3
          >>> tower_of_hanoi(2, 1, 3)
          Move 1 disk from rod 1 to rod 2
          Move 1 disk from rod 1 to rod 3
          Move 1 disk from rod 2 to rod 3
          >>> tower_of_hanoi(3, 1, 3)
          Move 1 disk from rod 1 to rod 3
          Move 1 disk from rod 1 to rod 2
          Move 1 disk from rod 3 to rod 2
          Move 1 disk from rod 1 to rod 3
          Move 1 disk from rod 2 to rod 1
          Move 1 disk from rod 2 to rod 3
          Move 1 disk from rod 1 to rod 3
          """

Q4. The number of partitions of a positive integer is the number of ways in which it can be expressed as the sum of positive integers in increasing order. For example, the number 5 has 7 partitions:

      5 = 5
      5 = 1 + 4
      5 = 2 + 3
      5 = 1 + 1 + 3
      5 = 1 + 2 + 2
      5 = 1 + 1 + 1 + 2
      5 = 1 + 1 + 1 + 1 + 1

To find the number of partitions for a given number, one can solve an easier problem of finding all of the partitions of a number n only using integers greater than or equal to another integer k. Solve this easier problem by writing a tree-recursive function part_help(n, k) that returns the number of partitions of n using integers greater than or equal to k.

      def part_help(m, k):
          """Return the number of partitions of m that use integers greater than
          or equal to k.

          >>> part_help(3, 2) # 3
          1
          >>> part_help(3, 1) # 3, 2 + 1, 1 + 1 + 1
          3
          """
          "*** YOUR CODE HERE ***"

      def part(n):
          """Return the number of partitions of positive integer n.

          >>> part(5)
          7
          >>> part(7)
          15
          """
          return part_help(n, 1)

Extra for Experts:

Note: "Extra for Experts" problems are completely optional. You are encouraged to try these questions. However, these are questions which we consider more difficult than what we would consider asking you on an exam, so please don't be discouraged if you don't solve them.

Q5. The recursive factorial function can be written as a single expression by using a conditional expression.:

      >>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
      >>> fact(5)
      120

To write a recursive function previously, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact without giving it a name (although we give a name to allow for doctests)!

Write an expression that computes n factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements).

Hint: Googling Y-combinator will tell you the solution, so don't do that until you've tried to solve the problem yourself!