*Due by 5pm on Friday, 10/19*

**Submission.** See the online submission instructions.
We have provided a starter file for the questions below.

**Readings.** Sections 2.7
and 3.2
of the online lecture notes.

**Q1.** Write a data-directed apply function that computes the area or
perimeter of either a square or a rectangle. Use a dictionary to store the
implementations of each function for each type:

class Square(object): def __init__(self, side): self.side = side class Rect(object): def __init__(self, width, height): self.width = width self.height = height def type_tag(s): return type_tag.tags[type(s)] type_tag.tags = {Square: 's', Rect: 'r'} def apply(operator_name, shape): """Apply operator to shape. >>> apply('area', Square(10)) 100 >>> apply('perimeter', Square(5)) 20 >>> apply('area', Rect(5, 10)) 50 >>> apply('perimeter', Rect(2, 4)) 12 """ "*** YOUR CODE HERE ***"

**Q2.** A mathematical function `G` on positive integers 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 `g` that computes `G(n)`. Then, write an
iterative function `g_iter` that computes `G(n)`:

def g(n): """Return the value of G(n), computed recursively. >>> g(1) 1 >>> g(2) 2 >>> g(3) 3 >>> g(4) 10 >>> g(5) 22 """ "*** YOUR CODE HERE ***" def g_iter(n): """Return the value of G(n), computed iteratively. >>> g_iter(1) 1 >>> g_iter(2) 2 >>> g_iter(3) 3 >>> g_iter(4) 10 >>> g_iter(5) 22 """ "*** YOUR CODE HERE ***"

**Q3.** The number of partitions of a positive integer `n` is the number of
ways in which `n` 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`. Once you have
done so, you can use very similar logic to the `count_change` function from
the lecture notes:

def part(n): """Return the number of partitions of positive integer n. >>> part(5) 7 >>> part(10) 42 >>> part(15) 176 >>> part(20) 627 """ "*** YOUR CODE HERE ***"

**Q4.** (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

However, this implementation relies on the fact (no pun intended) that `fact`
has a name, to which we refer in the body of `fact`. To write a recursive
function, 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. Return the expression
from the function below:

from operator import sub, mul def make_anonymous_factorial(): """Return the value of an expression that computes factorial. >>> make_anonymous_factorial()(5) 120 """ return YOUR_EXPRESSION_HERE

**Q5.** (Extra for experts) The `Rlist` class can represent lists with
cycles. That is, a list may contain itself as a sublist.

>>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> s[20] 3

- This question has two parts:
- Write a function has_cycle that returns True if and only if its argument, an Rlist instance, contains a cycle.
- Write a function has_cycle_constant that has the same behavior as has_cycle but requires only a constant amount of space.

Hint: The solution to B is short (~10 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

def has_cycle(s): """Return whether Rlist s contains a cycle. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> has_cycle(s) True >>> t = Rlist(1, Rlist(2, Rlist(3))) >>> has_cycle(t) False """ "*** YOUR CODE HERE ***" def has_cycle_constant(s): """Return whether Rlist s contains a cycle. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> has_cycle_constant(s) True >>> t = Rlist(1, Rlist(2, Rlist(3))) >>> has_cycle_constant(t) False """ "*** YOUR CODE HERE ***" class Rlist(object): """A recursive list consisting of a first element and the rest.""" class EmptyList(object): def __len__(self): return 0 empty = EmptyList() def __init__(self, first, rest=empty): self.first = first self.rest = rest def __repr__(self): args = repr(self.first) if self.rest is not Rlist.empty: args += ', {0}'.format(repr(self.rest)) return 'Rlist({0})'.format(args) def __len__(self): return 1 + len(self.rest) def __getitem__(self, i): if i == 0: return self.first return self.rest[i-1]