61A Homework 7

Due by 4pm on Monday, 5 March

You can grab a template for this homework either by downloading the file from the calendar or by running the following command in terminal on one of the school computers (the dot is significant: it denotes the current directory)

cp ~cs61a/lib/hw/hw7.py .

Readings. Chapter 3.2

Q1.

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

Write a tree-recursive function part(n) that returns the number of partitions of n.

Hint: Introduce a locally defined function that computes partitions of n using only a subset of the integers less than or equal to n.

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

    >>> part(5)
    7
    """
    # YOUR CODE HERE

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

Q3. Write another version of the recursive g from Q2, call it g_counted, that takes the same argument n and returns a pair (i.e., a two-element tuple) containing the value of g(n) and the number of calls to g that would occur in the recursive computation of g(n) (including the initial call, so that the second element of the returned tuple is always positive). For example:

>>> g_counted(2)
(2, 1)
>>> g_counted(4)
(10, 4)
>>> g_counted(5)
(22, 7)

Q4. Define a class vect that represents vectors in 2-dimensional space. You can think of vectors as being arrows in the plane having a direction and length, such as the distance and direction of one point in the plane from another. They are often represented as pairs of numbers, representing a distance in the x direction and y direction respectively. Given two vectors, v1 and v2, they can be added, subtracted, multiplied by a scalar (a number), and "dotted". We want them to behave as shown here:

>>> v1 = vect(3, 4)
>>> v1
vect(3, 4)
>>> print(v1)
(3, 4)
>>> v1.x
3
>>> v1.y
4
>>> v1.x = 7
Traceback (most recent call last):
    ...
AttributeError: can't set attribute
>>> v1 * 3
vect(9, 12)
>>> 3 * v1
vect(9, 12)
>>> v2 = vect(4, -2)
>>> v1 + v2
vect(7, 2)
>>> v1 - v2
vect(-1, 6)
>>> v1 * v2             # inner product = 12 - 8
4
>>> abs(v1)             # = sqrt(3**2 + 4**2)
5.0
"""

You may want to consult section 3.3 of the Python reference manual.

Q5. Using the memo-table idea from the FastEvaluator class in Lecture 16, write a function partm that memoizes the part function from Q1 (so that partm(n) computes part(n), but faster). You should be able to compute partm(500) almost instantly. (We used a class in lecture to hold the memo table, but a local variable in a function will work, too)

Q6.

Consider the rlist C in the following example, using a mutable rlist type adapted from HW #5:

>>> C = rlist(1, rlist(2, rlist(3)))
>>> C.rest().rest().set_rest(C)
>>> C.rest().rest().rest().first()
1
>>> C.rest().rest().rest().rest().first()
2

We say this list is circular. Circular lists can be useful, but they require tweaks to the usual implementations of some routines. For example, the rlist_to_list function from HW #5 would go into an infinite loop on C.

Write a function that determines whether an rlist is circular:

>>> C = rlist(1, rlist(2, rlist(3)))
>>> has_cycle(C)
False
>>> C.rest().rest().set_rest(C)
>>> has_cycle(C)
True
>>> C = rlist(0, C)
>>> has_cycle(C)
True

Q7. [Extra for experts.]

Do problem Q6 again, producing a function has_cycle2(C) that produces the same result as has_cycle(C), but does so with constant extra space (that is, without creating any data structures (such as lists, dictionaries, or sets) that grow over time.)

Q8. [Extra for experts.]

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!

Write an expression that computes n factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements). The sub and mul functons from the operator module are the only built-in function required to solve this problem.

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