CS 61A Structure and Interpretation of Computer Programs
Fall 2016
INSTRUCTIONS
• You have 2 hours to complete the exam.
Midterm 2 Solutions
• The exam is closed book, closed notes, closed computer, closed calculator, except one hand-written 8.5″ × 11″ crib sheet of your own creation and the official CS 61A study guides.
• Mark your answers on the exam itself. We will not grade answers written on scratch paper.
Last name
First name
Student ID number
CalCentral email
TA
Name of the person to your left
Name of the person to your right
All the work on this exam is my own.
(please sign)
2
1. (8 points) Halloween
For each of the expressions in the table below, write the output displayed by the interactive Python interpreter when the expression is evaluated. The output may have multiple lines. If an error occurs, write “Error”, but include all output displayed before the error. The Link class appears on page 2 of the midterm 2 study guide.
The first two rows have been provided as examples.
Recall: The interactive interpreter displays the value of a successfully evaluated expression, unless it is None.
Assume that you have started python3 and executed the following statements:
class Party:
guests = Link.empty
def __init__(self, time):
Party.guests = Link(time+1, Party.guests)
def attend(self):
self.guests.rest = Link(self.guests.rest)
return self.guests
class Costume(Party):
def __init__(self, bow, tie):
Party.guests.rest = Link(bow)
self.ie = Link(self)
def attend(self):
print(repr(self.ie))
Party.attend = lambda self: Party(9).guests
def __repr__(self):
print(‘Nice’)
return ‘Costume’
Expression
Link(1, Link.empty)
Link(1, Link(2))
Party(1).guests
Party(3).attend()
Party(7).attend()
Interactive Output
Link(1)
Link(1, Link(2)) Link(2)
Link(4, Link(Link(2)))
Link(10, Link(8, Link(4, Link(5))))
Costume(5, 6).attend()
Nice
Link(Costume)
Name: 3 2. (8 points) A List with a Twist
Fill in the environment diagram that results from executing the code below until the entire program is finished, an error occurs, or all frames are filled. You may not need to use all of the spaces or frames.
A complete answer will:
• Add all missing names and parent annotations to frames.
• Add all missing values created or referenced during execution.
• Show the return value for each local frame.
• Use box-and-pointer notation for list values. You do not need to write index numbers or the word “list”.
lamb = ‘da’
def da(da):
def lamb(lamb):
nonlocal da
def da(nk):
da = nk + [‘da’]
da.append(nk[0:2])
return nk.pop()
da(lamb)
return da([[1], 2]) + 3
da(lambda da: da(lamb))
Global frame
lamb ‘da’ da
da Global
f1: ___________ [parent=____________]
da lamb
Return Value
5
λ Global
f2: ___________ [parent=____________]
da
Return Value None
lamb f1
f3: ___________ [parent=____________]
lamb ‘da’
Return Value None
da f3
f4: ___________ [parent=____________]
nk da
2
Return Value
1 2 3 4 5 6 7 8 9
10 11 12
func da(da) [parent=G]
func da(nk) [parent=f3]
func lamb(lamb) [parent=f1]
list 012
list list 01012
list
01223 ‘da’
4
3. (6 points) Return Policy
Implement quota, which takes a one-argument function f and a non-negative integer limit. The function it returns has the same behavior as f, except that each value is only returned up to limit times. After that, the function returns an “Over quota” message instead, and the limit is decreased by 1 for future calls.
def quota(f, limit):
“””A decorator that limits the number of times a value can be returned.
>>> square = lambda x: x * x
>>> square = quota(square, 3)
>>> square(6) # 1st call with return value 36
36
>>> [square(5) for x in range(3)] # 3 calls when the limit is 3
[25, 25, 25]
>>> square(5)
‘Over quota! Limit is now 2’
>>> square(-6)
36
>>> square(-6)
‘Over quota! Limit is now 1’
>>> square(7)
49
>>> square(5)
‘Over quota! Limit is now 0’
“””
values = []
def limited(n):
nonlocal limit
y = f(n)
count = len([x for x in values if x == y])
values.append(y)
if count < limit:
return y
limit = limit - 1
return 'Over quota! Limit is now ' + str(limit)
return limited
# 4th call with return value 25
# 2nd call with return value 36
# 3rd call when the limit is 2
# 1st call when the limit is 1
# 5th call with return value 25
Name: 5 4. (6 points) A Classy Election
Implement the VotingMachine and Ballot classes based on the doctest below. The voting machine must determine which choice has the most votes (the winner) and detect if a ballot is used more than once. In case of a tie, the winner among choices with maximal votes is the one that most recently received a vote. Ballot.vote takes a string, and a VotingMachine must handle an arbitrary number of choices.
class VotingMachine:
"""A machine that creates and records ballots.
>>> machine = VotingMachine(4)
>>> a, b, c, d = machine.ballots
>>> d.vote(‘Bruin’)
‘Bruin is winning’
>>> b.vote(‘Bruin’)
‘Bruin is winning’
>>> c.vote(‘Bear’)
‘Bear is losing’
>>> a.vote(‘Bear’)
‘Bear is winning’
>>> c.vote(‘Tree’)
‘Fraud: multiple votes from the same ballot!’
>>> machine.winner
‘Bear’
“””
def __init__(self, k):
self.ballots = [Ballot(self) for i in range(k)]
self.votes = {}
def record(self, ballot, choice):
if ballot.used:
return ‘Fraud: multiple votes from the same ballot!’
ballot.used = True
self.votes[choice] = self.votes.get(choice, 0) + 1
if max(self.votes.values()) > self.votes[choice]:
return choice + ‘ is losing’
else:
self.winner = choice
return choice + ‘ is winning’
class Ballot:
used = False
def __init__(self, machine):
self.machine = machine
def vote(self, x):
return self.machine.record(self, x)
6
5. (6 points) Trick or Tree
Implement path, which takes a linked list s and a Tree instance t. It returns whether s is a path from the root of t to some leaf. The Tree and Link classes are on page 2 of the midterm 2 study guide.
Restrictions:
• You may not call the built-in len function on a linked list or invoke its __len__ method.
• You may not apply element selection (e.g., s[2]) on a linked list or invoke its __getitem__ method. from tree import *
from link import *
def path(s, t):
“””Return whether Link S is a path from the root to a leaf in Tree T.
>>> t = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)]), Tree(6)])
>>> a = Link(1, Link(3, Link(4))) # A full path
>>> path(a, t)
True
>>> b = Link(1, Link(3)) # A partial path
>>> path(b, t)
False
>>> c = Link(1, Link(2, Link(7))) # A path and an extra value
>>> path(c, t)
False
>>> d = Link(3, Link(4))
>>> path(d, t)
False
“””
# A path of a branch
if s is Link.empty or t.root != s.first:
return False
if t.is_leaf() and s.rest is Link.empty:
return True
return any([path(s.rest, b) for b in t.branches])
Name: 7 6. (6 points) Left it Right There
(a) (4 pt) Implement binary, which takes a list s of unique integers. It returns a binary search tree containing all of those integers, represented as a BTree instance or BTree.empty. The values in any path of this tree must appear in the same order as they did in s. The BTree class is on page 2 of the midterm 2 study guide.
from tree import *
def binary(s):
“””Construct a binary search tree from S for which all paths are in order.
>>> binary([3, 5, 1])
BTree(3, BTree(1), BTree(5))
>>> binary([4, 3, 7, 6, 2, 9, 8])
BTree(4, BTree(3, BTree(2)), BTree(7, BTree(6), BTree(9, BTree(8))))
“””
assert len(s) == len(set(s)), ‘All elements of s should be unique’
if not s:
return BTree.empty
root = s[0]
left = [x for x in s if x < root]
right = [x for x in s if x > root]
return BTree(root, binary(left), binary(right))
(b) (1 pt) Circle the Θ expression that describes the smallest possible height of the tree returned by binary(s) for a list s of length n. The height of a tree is the length of the longest path from its root to a leaf.
Θ(1) Θ(log n) Θ(n) Θ(n2) Θ(2n) None of these
(c) (1 pt) Circle the Θ expression that describes the largest possible height of the tree returned by binary(s) for a list s of length n. The height of a tree is the length of the longest path from its root to a leaf.
Θ(1) Θ(log n) Θ(n) Θ(n2) Θ(2n) None of these
8
7. (10 points) Summer Camp
(a) (6 pt) Implement sums, which takes two positive integers n and k. It returns a list of lists containing all
the ways that a list of k positive integers can sum to n. Results can appear in any order. def sums(n, k):
“””Return the ways in which K positive integers can sum to N.
>>> sums(2, 2)
[[1, 1]]
>>> sums(2, 3)
[]
>>> sums(4, 2)
[[3, 1], [2, 2], [1, 3]]
>>> sums(5, 3)
[[3, 1, 1], [2, 2, 1], [1, 3, 1], [2, 1, 2], [1, 2, 2], [1, 1, 3]]
“””
if k == 1:
return [[n]]
y = []
for x in range(1, n): # range(1, n-k+1) is OK
y.extend([s + [x] for s in sums(n-x, k-1)])
return y
OR
if n == 0 and k == 0:
return [[]]
y = []
for x in range(1, n+1):
y.extend([s + [x] for s in sums(n-x, k-1)])
return y
(b) (4 pt) Why so many lines? Implement f and g for this alternative version of the sums function. f = lambda x, y: (x and [[x] + z for z in y] + f(x-1, y)) or []
def sums(n, k):
“””Return the ways in which K positive integers can sum to N.
>>> sums(2, 2)
[[1, 1]]
>>> sums(4, 2)
[[3, 1], [2, 2], [1, 3]]
>>> sums(5, 3)
[[3, 1, 1], [2, 2, 1], [2, 1, 2], [1, 3, 1], [1, 2, 2], [1, 1, 3]]
“””
g = lambda w: (w and f(n, g(w-1))) or [[]]
return [v for v in g(k) if sum(v) == n]