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!