These problems are designed to be around exam difficulty. For more basic problems, see the topic-based guides and practice problems!

Nonlocal and Higher Order Functions
Draw the environment diagram for the following code:

def what ( a , b ):
x = a
def ha ( ha ):
nonlocal x
x = ha * 2
return x
return b ( ha ( x ), x )
what ( 4 , lambda x , y : x )

TOGGLE SOLUTION

What makes `what`

a higher order function?

a. it returns a function (what function?)
b. it takes in a function as an argument
c. both a and b
b , `what`

takes in a function as its second argument. It is not actually returning a function, but rather a function call to `b`

, so a is not correct.
TOGGLE SOLUTION

Write the simplest function possible (1-2 lines) that does the exact same thing as `what`

for any input `a`

, `b`

.

def foo ( a , b ):
a *= 2
return b ( a , a )

TOGGLE SOLUTION

List Mutability
Draw the environment diagram for the following code.

wow = [ 0 , 'c' , 's' ]
def f ( x ):
omg = []
y = lambda : x - 5
def g ():
nonlocal x
while x > len ( omg ):
x = y ()
omg . append ( x )
return omg [ 0 : 2 ]
return g ()
lol = f ( 11 )
wow . extend ( lol )
lol = wow + [ 'a' ]
wow = lol [ 1 :]

TOGGLE SOLUTION

Mutable Linked Lists
Implement `multiply`

, which takes in a Linked List and mutates it so that each link is duplicated by the amount of its entry. See the doctests for examples.

def multiply ( link ):
"""
>>> link = Link(2, Link(3))
>>> multiply(link)
>>> link
Link(2, Link(2, Link(3, Link(3, Link(3)))))
>>> link = Link(4, Link(1, Link(2)))
>>> multiply(link)
>>> link
Link(4, Link(4, Link(4, Link(4, Link(1, Link(2, Link(2)))))))
"""
"*** YOUR CODE HERE ***"

TOGGLE SOLUTION

def multiply ( link ):
def helper ( link , count ):
if count == 1 and link . rest != Link . empty :
multiply ( link . rest )
elif count != 1 and link != Link . empty :
link . rest = Link ( link . first , link . rest )
helper ( link . rest , count - 1 )
helper ( link , link . first )

Iterables and Iterators
Implement `mimic_list`

so that it behaves like Pythonâ€™s built-in `list`

constructor.
def mimic_list ( iterable ):
"""
>>> mimic_list((1, 2, 3, 4))
[1, 2, 3, 4]
>>> def perf_squares(n): # generates perfect squares
... i = 1
... while i <= n:
... yield i * i
... i += 1
>>> mimic_list(perf_squares(10))
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
>>> mimic_list("cs61a")
['c', 's', '6', '1', 'a']
"""
"*** YOUR CODE HERE ***"

TOGGLE SOLUTION

def mimic_list ( iterable ):
i = iter ( iterable ) # get iterable's iterator object
lst = [] # create an empty list
try :
while True : # add every elem in sequence to lst
lst . append ( next ( i ))
except StopIteration : # return lst when the sequence is done
return lst

2 . Recall that all `__iter__`

methods must return an iterator type. Well, a generator is an iterator, so you can write `__iter__`

to be a generator function! Write the `__iter__`

method for BinaryTree such that it returns a generator. Calling `next`

on this generator will return the elements of the BinaryTree in ascending order. Assume that all instances of BinaryTree fall under the constraints of a binary search tree:

the root entry is greater than or equal to all entries in the left side of the BinaryTree
the root entry is lses than or equal to all entries in the right side of the BinaryTree
class BinarySearchTree :
empty = ()
def __init__ ( self , entry , left = empty , right = empty ):
self . entry = entry
if left : assert isinstance ( left , BinaryTree )
if right : assert isinstance ( right , BinaryTree )
self . left = left
self . right = right
def __iter__ ( self ):
"""
>>> tree = BinaryTree(4, BinaryTree(2), BinaryTree(7, BinaryTree(5)))
>>> for entry in tree:
... print(entry)
2
4
5
7
"""
"*** YOUR CODE HERE ***"

TOGGLE SOLUTION

def __iter__ ( self ):
for value in self . left :
yield value
yield self . entry
for value in self . right :
yield value