*Due by 11:59pm on Wednesday, 2/20*

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

**Readings.** Section 1.7
of the online lecture notes.

**Q1.** In the lecture notes, we defined a `pig_latin` function to compute the
Pig Latin equivalent of an English word. The code that we used is as follows:

def pig_latin_original(w): """Return the Pig Latin equivalent of a lowercase English word w.""" if starts_with_a_vowel(w): return w + 'ay' return pig_latin_original(rest(w) + first(w)) def first(s): """Returns the first character of a string.""" return s[0] def rest(s): """Returns all but the first character of a string.""" return s[1:] def starts_with_a_vowel(w): """Return whether w begins with a vowel.""" c = first(w) return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'

This code repeatedly moves a letter from the beginning of a word to the end,
until the first letter is a vowel, at which point it adds on `'ay'` to the
end. However, this code fails when the original word has no vowels in the set
{a, e, i, o, u}, such as the word "sphynx." Write a new version of the
`pig_latin` function that just adds `'ay'` to the original word if it does
not contain a vowel in this set. Use only the `first`, `rest`, and
`starts_with_a_vowel` functions to access the contents of a word, and use the
built-in `len` function to determine its length. Do not use any loops.

def pig_latin(w): """Return the Pig Latin equivalent of a lowercase English word w. >>> pig_latin('pun') 'unpay' >>> pig_latin('sphynx') 'sphynxay' """ "*** YOUR CODE HERE ***"

**Q2.** 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 `towers_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 towers_of_hanoi(n, start, end): """Print the moves required to solve the towers 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). >>> towers_of_hanoi(1, 1, 3) Move 1 disk from rod 1 to rod 3 >>> towers_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 >>> towers_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 """ "*** YOUR CODE HERE ***" def move_disk(start, end): print("Move 1 disk from rod", start, "to rod", end)

**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 helper 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) Recall that the `summation` function computes the
sum of a sequence of terms from 1 to `n`:

def summation(n, term): """Return the sum of the first n terms of a sequence. >>> summation(5, lambda x: pow(x, 3)) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total

Write a function `interleaved_sum` that similarly computes the sum of a
sequence of terms from 1 to `n`, but uses different function to compute the
terms for odd and even numbers. Do so without using any loops or testing in any
way if a number is odd or even. (You may test if a number is equal to 0, 1, or
`n`.)

def interleaved_sum(n, odd_term, even_term): """Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up to n. >>> # 1 + 2^2 + 3 + 4^2 + 5 ... interleaved_sum(5, lambda x: x, lambda x: x*x) 29 """ "*** YOUR CODE HERE ***"