CS 61A Structure and Interpretation of Computer Programs
Spring 2018
INSTRUCTIONS
• You have 2 hours to complete the exam.
Midterm 2 Solutions
• The exam is closed book, closed notes, closed computer, closed calculator, except two hand-written 8.5″ × 11″ crib sheet of your own creation and the official CS 61A midterm 1 and midterm 2 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)
POLICIES & CLARIFICATIONS
• If you need to use the restroom, bring your phone and exam to the front of the room.
• You may use built-in Python functions that do not require import, such as min, max, pow, len, and abs.
• You may not use example functions defined on your study guides unless clearly specified by the question.
• For fill-in-the blank coding problems, we will only grade work written in the provided blanks. You may only write one Python statement per blank line, and it must be indented to the level that the blank is indented.
• Unless otherwise specified, you are allowed to reference functions defined in previous parts of the same question.
• You may use the Tree, Link, and BTree classes defined on Page 2 (left column) of the Midterm 2 Study Guide.
2
1. (10 points) Buggy Quidditch
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. • To display a function value, write Function.
• If an expression would take forever to evaluate, write Forever.
The interactive interpreter displays the contents of the repr string of the value of a successfully evaluated expression, unless it is None.
Assume that you have started python3 and executed the code shown on the left first, then you evaluate each expression on the right in the order shown. Expressions evaluated by the interpreter have a cumulative effect.
1 class Ball:
2 points = 0
3 time = lambda: ‘Draco’
4
5 def score(self, who):
6 print(who, self.points)
7
8 def __str__(self):
9 return ‘Magic’
10
11 class Snitch(Ball):
12 points = 100
13 time = lambda: ‘Harry’
14 Snitch().points
15 def __init__(self):
16 self.points = self.points + 50
17
18 def score(self, p):
19 if not time():
20 print(Ball().score(p))
21 else:
22 Ball.score(self, p)
23
24 def chase(r):
25 r.time = Snitch.time
26 r.points += 1
27 quaffle.points += 10
28 print(r().points)
29
30 quaffle = Ball()
31 quaffle.points = 10
32 chasing = quaffle.score
33 time = lambda: Ball.points
34 malfoy = lambda: Ball.time()
Expression
chasing(quaffle)
Interactive Output
150 Magic 10
1
Harry 150
Snitch().score(‘Seeker’)
Seeker 0 None
chase(Ball)
Snitch().score(malfoy())
Name: 3 2. (6 points) NVRnment
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 all local frames. • Add all missing values created or referenced during execution.
• Show the return value for each local frame.
• Use box-and-pointer diagrams for lists and tuples.
s=1
def to(s):
ix = s[1:2]
ward[1] = 6
def re(st):
if st is not ward:
nonlocal s
s = s.extend(ix)
return re(ward)
else:
st.append(ix)
return re
ward = [3, 4] + list([5])
to(ward)(s)
Global
s1 to
ward
to Global
f1: ___________ [parent=____________]
s None ix
re
Return Value
re f1
f2: ___________ [parent=____________]
st
1
None
Return Value
re
f1
f3: ___________ [parent=____________]
st
Return Value
None
f4: ___________ [parent=____________]
Return Value
1 2
3 4 5 6 7 8 9
10 11 12 13 14
func to(s) [parent=Global]
list
func re(st) [parent=f1]
list
03
16
25
34
4
04
4
3. (12 points) Lists
Definition. A grid is a list of lists. Each list in a grid is called a row, and all rows must have the same length.
[[1, 2], [3, 4]] is a grid of integers, but [[1, 2], [3, 4, 5]] is not a grid.
(a) (2 pt) Implement column, which takes a grid g and a non-negative integer c that is smaller than the length
of a row in g. It returns a list containing the element at index c of each row in the grid. def column(g, c):
“””Return the column of g at index c.
>>> column([[3, 4, 5], [6, 7, 8], [9, 10, 11]], 1)
[4, 7, 10]
“””
return [row[c] for row in g]
(b) (4 pt) Implement print_grid, which takes a grid g. It prints one line for each row in g. Line k displays each element in row k, separated by the minimum number of spaces needed to align the left edges of the str strings for the elements of each column of the grid. At least one space should appear between any two elements. Extra spaces at the end of a line are ok. You may not use the column function above. Assume that g has at least one row.
def print_grid(g):
“””Print each row on a separate line with columns aligned.
>>> print_grid([[1, 234, 50, 4, 5], [67, 8, 90, 0, 500], [3, 4, 5, -500, 7]]) 1234504 5
678 900 500
3 4 5 -500 7
“””
cs = range(len(g[0]))
widths = [max([len(str(row[c])) for row in g]) for c in cs]
for row in g:
line = ”
for c in cs:
s = str(row[c])
line = line + s + ‘ ‘ * (widths[c] – len(s) + 1)
print(line)
Name: 5 (c) (4 pt) Implement expand, which takes a grid g, a number of rows h, a number of columns w, and a fill
value. It mutates the contents of g so that g has at least h rows and w columns. Any added values are fill. def expand(g, h, w, fill):
“””Expand grid g so that it has at least h rows and w columns.
>>> g = [[1, 2, 3], [40, 50, 60]]
>>> print_grid(expand(g, 2, 5, 10))
1 2 3 10 10
40 50 60 10 10
>>> print_grid(expand(g, 5, 6, 0)) 1 2 3 10 10 0
40 50 60 10 10 0
000000
000000 000000
>>> print_grid(expand(g, 0, 0, 5)) 1 2 3 10 10 0
40 50 60 10 10 0
000000
000000 000000 “””
for row in g:
row.extend([fill] * (w – len(row)))
# Alternate correct answer: row.extend([fill] * max(0, (w – len(row))))
for k in range(h – len(g)):
# Alternate correct answer: range(max(0, h – len(g)))
g.append([fill] * w)
# Note: This solution fails if w < len(g[0]) but h > len(g),
# # # # # #
return g
a case that was never demonstrated in the doctests.
So, it was given full credit.
A full-credit solution that works for all non-empty g is:
g.append([fill] * len(g[0]))
A correct solution that works for all g is more complicated:
g.append([fill] * ((g and len(g[0])) or w))
(d) (2 pt) Circle the Θ expression that describes how many new values must be added when a grid with n rows and n columns is expanded to 2 × n rows and 2 × n columns using the expand function. Assume that expand is implemented correctly.
Θ(1) Θ(log n) Θ(n) Θ(n2) Θ(2n) None of these
6
4. (12 points) Sequences
(a) (6 pt) Implement stretch, which takes a Link instance s with no cycles. It mutates s so that, for each
position k in the original s, the kth element is repeated k times. You do not need to use the name i. def stretch(s, repeat=0):
“””Replicate the kth element k times, for all k in s.
>>> a = Link(3, Link(4, Link(5, Link(6))))
>>> stretch(a)
>>> print(a)
<3, 4, 4, 5, 5, 5, 6, 6, 6, 6>
“””
if s is not Link.empty:
for i in range(repeat):
s.rest = Link(s.first, s.rest)
s = s.rest
stretch(s.rest, repeat + 1)
(b) (6 pt) Implement combo, which takes two non-negative integers a and b. It returns the smallest integer
that contains all of the digits of a in order, as well as all of the digits of b in order.
def combo(a, b):
“””Return the smallest integer with all of the digits of a and b (in order).
>>> combo(531, 432)
45312
>>> combo(531, 4321)
45321
>>> combo(1234, 9123)
91234
>>> combo(0, 321)
321
“””
if min(a, b) == 0:
return a + b
elif a % 10 == b % 10:
# 45312 contains both _531_ and 4_3_2.
# 45321 contains both _53_1 and 4_321.
# 91234 contains both _1234 and 9123_.
# The number 0 has no digits, so 0 is not in the result.
return combo(a // 10, b // 10) * 10 + a % 10
else:
return min(combo(a // 10, b) * 10 + a % 10,
combo(a, b // 10) * 10 + b % 10)
Name: 7 5. (10 points) Trees
Definition. A sibling of a node in a tree is another node with the same parent.
(a) (4 pt) Implement siblings, which takes a Tree instance t. It returns a list of the labels of all nodes in t
that have a sibling. These labels can appear in any order.
def siblings(t):
“””Return a list of the labels of all nodes that have siblings in t.
>>> a = Tree(4, [Tree(5), Tree(6), Tree(7, [Tree(8)])])
>>> siblings(Tree(1, [Tree(3, [a]), Tree(9, [Tree(10)])]))
[3, 9, 5, 6, 7]
“””
result = [b.label for b in t.branches if len(t.branches) > 1]
for b in t.branches:
result.extend(siblings(b))
return result
(b) (6 pt) Implement the Sib class that inherits from Tree. In addition to label and branches, a Sib instance t has an attribute siblings that stores the number of siblings t has in Sib trees containing t as a node. Assume that the branches of a Sib instance will never be mutated or re-assigned.
class Sib(Tree):
“””A tree that knows how many siblings it has.
>>> a = Sib(4, [Sib(5), Sib(6), Sib(7, [Sib(8)])])
>>> a.siblings
0
>>> a.branches[1].siblings
2
“””
def __init__(self, label, branches=[]):
self.siblings = 0
for b in branches:
b.siblings += len(branches) – 1
Tree.__init__(self, label, branches)