**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!