*Due by 11:59pm on Monday, 7/15*

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

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

**Q1.** Read Albert's debugging guidelines. Then fix the
problems with the following code. (Only fix the bugs; do not change the
structure of the computation.).

def divide_by_fact(dividend, n): """Recursively divide dividend by the factorial of n. >>> divide_by_fact(120, 4) 5.0 """ if n < 0: return dividend return divide_by_fact(dividend / n, n - 1)

**Q2.** Write a recursive function that divides an input sequence into a tuple
of smaller sequences that each contain 4 or 5 elements from the original
sequence. For example, an input sequence of 14 elements should be divided into
sequences of 4, 5, and 5 elements. Use as few 5-element sequences as necessary
in the result, and all 5-element sequences should be at the end. Finally,
preserve the relative ordering of elements from the original sequence.

*Hint*: You may assume that the input sequence has length at least 12. Think
carefully about how many base cases you need, and what they should be.

def group(seq): """Divide a sequence of at least 12 elements into groups of 4 or 5. Groups of 5 will be at the end. Returns a tuple of sequences, each corresponding to a group. >>> group(range(14)) (range(0, 4), range(4, 9), range(9, 14)) >>> group(tuple(range(17))) ((0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15, 16)) """ num = len(seq) assert num >= 12 "*** YOUR CODE HERE ***"

**Pizza Sort**

Leonardo da Vinci is well know for his inventions, his paintings, and his numerous contributions to many other fields. It is less known that he only turned to art after failing miserably as an apprentice in a pizzeria. (Granted, modern pizza was invented centuries after his era, but its precursors have been around since Roman times.)

One day, little Leonardo was at the pizzeria, mindlessly flipping over partially cooked crusts with a spatula. At that moment, inspiration struck, and he realized that he could sort the crusts in a stack, so that the largest ended up at the bottom and the smallest at the top, with each crust smaller than the one below it. He named his procedure "pizza sort" and wrote it down in a journal.

Unfortunately, that journal was lost to time, so pizza sort, perhaps Leonardo's greatest invention, remained unknown. Until now. Last year, a previously unknown journal was found in the hands of a private collector, and it appears to be that elusive journal in which Leonardo recorded his pizza sort. Unfortunately, time has not been kind to the journal, so many details are missing. But archaeologists have managed to recover one key piece of the puzzle: the only allowed move in pizza sort is to place the spatula under a crust in the stack and flip the set of crusts above the spatula:

""" ==== == ========== <--- spatula underneath this crust ======== || || \||/ \/ ========== } == } flipped ==== } ======== """

**Q3.** Implement this flip operation in code, with the stack of crusts
represented as a list starting from the bottom of the stack. Write a function
`partial_reverse` to reverse the subset of a list starting from `start`
until the end of the list. This reversal should be *in-place*, meaning that the
original list is modified. Do not create a new list inside your function, even
if you do not return it.

*Note:* As can be seen from the doctests, `partial_reverse` should return
`None`. (Don't put in an explicit `return None`, however; either leave out
any return statement or just use `return` with no expression.)

def partial_reverse(lst, start): """Reverse part of a list in-place, starting with start up to the end of the list. >>> a = [1, 2, 3, 4, 5, 6, 7] >>> partial_reverse(a, 2) >>> a [1, 2, 7, 6, 5, 4, 3] >>> partial_reverse(a, 5) >>> a [1, 2, 7, 6, 5, 3, 4] """ "*** YOUR CODE HERE ***"

The archaeologists also found some indecipherable symbols along with the description of the above procedure. As they could make neither heads nor tails of it, they called it "the da Vinci code." Hoping to crack it, they asked Eva Lu Ator, a leading computer scientist, for help. Upon closer examination, she realized that the da Vinci code was actual code, in a rudimentary programming language that Leonardo had invented. This code would find the position of the largest crust in a stack of pizzas.

**Q4.** Help Eva to translate the da Vinci code into Python. Write a function
that takes in a sequence and returns the index of the largest element in the
sequence:

def index_largest(seq): """Return the index of the largest element in the sequence. >>> index_largest([8, 5, 7, 3 ,1]) 0 >>> index_largest((4, 3, 7, 2, 1)) 2 """ assert len(seq) > 0 "*** YOUR CODE HERE ***"

**Q5.** Finally, help the world learn the secret of the da Vinci code by writing
the `pizza_sort` function. This function takes in a list and sorts its
elements in descending order, using only the previous two functions and the
built-in `len` function. It is well-known that Leonardo hated iteration, so
make sure to use recursion instead. (You may define a helper function if you
want.) Lastly, you may use slicing; we are talking about pizza, after all.

(Keep in mind, however, that slicing returns a new list, but you need to sort the existing list in place.)

def pizza_sort(lst): """Perform an in-place pizza sort on the given list, resulting in elements in descending order. >>> a = [8, 5, 7, 3, 1, 9, 2] >>> pizza_sort(a) >>> a [9, 8, 7, 5, 3, 2, 1] """ "*** YOUR CODE HERE ***"

Marvel in the genius that was Leonardo da Vinci!

**Q6.** Define a function `make_accumulator` that returns an `accumulator`
function, which takes one numerical argument and returns the sum of all
arguments ever passed to `accumulator`. Use a `list` and not a
`nonlocal` statement:

def make_accumulator(): """Return an accumulator function that takes a single numeric argument and accumulates that argument into total, then returns total. >>> acc = make_accumulator() >>> acc(15) 15 >>> acc(10) 25 >>> acc2 = make_accumulator() >>> acc2(7) 7 >>> acc3 = acc2 >>> acc3(6) 13 >>> acc2(5) 18 >>> acc(4) 29 """ "*** YOUR CODE HERE ***"

**Q7.** Define a function `make_accumulator_nonlocal` that returns an
`accumulator` function, which takes one numerical argument and returns the sum
of all arguments ever passed to `accumulator`. Use a `nonlocal` statement,
but no
`list` or `dict`:

def make_accumulator_nonlocal(): """Return an accumulator function that takes a single numeric argument and accumulates that argument into total, then returns total. >>> acc = make_accumulator_nonlocal() >>> acc(15) 15 >>> acc(10) 25 >>> acc2 = make_accumulator_nonlocal() >>> acc2(7) 7 >>> acc3 = acc2 >>> acc3(6) 13 >>> acc2(5) 18 >>> acc(4) 29 """ "*** YOUR CODE HERE ***"

**Q8.** (Extra for Experts) Recall the `count_change` function from earlier in
the semester. (Below, we have converted it to use a tuple rather than a function
to represent a coin sequence, but it is otherwise the same.) It was quite slow
on larger inputs, since it repeated the same computation many times. Instead,
write a function `make_count_change` that produces a more efficient version of
`count_change`. This more efficient version should only perform any computation
if it is called with a new pair of arguments. If it is called with a pair of
arguments previously seen, then it should just return the previously computed
value. Once you are done, compare the two versions on a large number such as 500
to make sure that your code is faster than the original version.

# Old version def count_change(a, coins=(50, 25, 10, 5, 1)): if a == 0: return 1 elif a < 0 or len(coins) == 0: return 0 return count_change(a, coins[1:]) + count_change(a - coins[0], coins) # Version 2.0 def make_count_change(): """Return a function to efficiently count the number of ways to make change. >>> cc = make_count_change() >>> cc(500, (50, 25, 10, 5, 1)) 59576 """ "*** YOUR CODE HERE ***"