CS 61A Structure and Interpretation of Computer Programs
Spring 2018
INSTRUCTIONS
• You have 2 hours to complete the exam.
Midterm 1 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 midterm 1 study guide.
• 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, and abs. You may
not use functions defined on your study guide unless clearly specified in 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.
2
1. (12 points) Frame of Thrones
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”. The first two rows have been provided as examples.
The interactive interpreter displays the value of a successfully evaluated expression, unless it is None. Assume that you have first started python3 and executed the statements on the left.
from operator import add, sub
def winterfell(a, b):
a
b
return b(a+1, b(a))
da, ny = 20, 18
while da > ny:
da = ny
da, ny = ny + 1, da + 3
def tar(gar, yen):
if print(yen):
print(yen + 1)
return gar(yen)
def st(ar, k=None):
return lambda a, y: ar(y, a)
night = st(sub)
king = st(st(pow))
def jon(sn, ow):
print(ow)
jon = sn(ow)
print(ow)
return jon
def snow(ow):
def tarly(snow):
return ow + snow
ow += 2
return tarly
Expression
sub(pow(10, 2), 1)
ny
night(king(2, 3), 4)
Interactive Output
99
21
-4
print(4, 5) + 1
45 Error
(print(2) or 3) // (0 or 1)
2 3
winterfell(2, print)
2
3 None
tar(lambda x: x-7, 8)
8 1
jon(snow(5), 2)
2 2 9
Name: 3 2. (8 points) Stranger Frames
1 2 3 4 5 6 7 8 9
10 11 12 13
def lucas(mike):
return will
def dustin(lucas):
will = 1
def dustin(mike):
will = 2
return lucas
return lambda mad: dustin(3)(will)
will = 5 + 6
lucas = dustin(lucas)
lucas(max)
Fill in the environment diagram that results from executing the code on the right 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.
Globa
f1: _
f2: _
f3: _
f4: _
Global frame
lucas
dustin
will 11
func dustin(lucas) [parent=Global]
func lucas(mike) [parent=Global]
func dustin(mike) [parent=f1]
func λ(mad) [parent=f1]
func max(…) [parent=Global]
dustin Global
f1: ___________ [parent=____________]
lucas will
dustin
Return Value
1
λ
f1
f2: ___________ [parent=____________]
mad
Return Value 11
dustin
f1
f3: ___________ [parent=____________]
3 will 2
Return Value
mike
lucas Global
f4: ___________ [parent=____________]
mike
1
Return Value 11
stin(3)(will)
d
l
_
_
_
_
4
3. (10 points) Choose Wisely
(a) (4 pt) Implement sum_some, which takes a non-negative integer n and a function p. It returns the sum of all the digits d for which p returns a true value when given d as an argument. Assume that the function p takes a single digit d (from 0 to 9) and returns either True or False.
def sum_some(n, p):
“””Return the sum of the digits of N for which P returns a true value.
>>> even = lambda d: d % 2 == 0
>>> big = lambda d: d > 5
>>> sum_some(124567, even)
12
>>> sum_some(124567, big)
13
“””
total = 0
while n:
if p(n % 10):
total += n % 10
n = n // 10
return total
# Sum the even digits: 2 + 4 + 6
# Sum the big digits: 6 + 7
(b) (4 pt) Implement sum_largest, which takes non-negative integers n & k. It sums the largest k digits of n. def sum_largest(n, k):
“””Return the sum of the K largest digits of N.
>>> sum_largest(2018, 2) # 2 and 8 are the two largest digits (larger than 0 and 1).
10
>>> sum_largest(12345, 10) # There are only five digits, so all are included in the sum.
15
“””
if n == 0 or k == 0:
return 0
a = n % 10 + sum_largest(n // 10, k – 1)
b = sum_largest(n // 10, k)
return max(a, b)
(c) (2 pt) Complete the expression below by only adding parentheses so that the whole expression evaluates to 2018. Each blank should be filled with one or more parentheses.
(lambda a, x: x + (lambda y: lambda z: y+z+1000)(1000 _)(_ 10 _))(_ 5, _(_ lambda: 8 _)()_ )
Name: 5 4. (10 points) Editor
Definitions. An edit is a pure function that takes a non-negative integer and returns a non-negative integer. An editor for a non-negative integer n is a function that takes an edit, applies it to n, displays the result, and then returns an editor for the result.
(a) (3 pt) Implement make_editor, which takes a non-negative integer n and a one-argument function pr. It returns an editor for n that uses pr to display the result of each edit.
(b) (5 pt) Implement insert, which takes a single digit d (from 0 to 9) and a non-negative position k. It returns an edit that inserts d into its argument n at position k, where k counts the number of digits from the end of n. Assume that k is not larger than the number of digits in n. Your solution must be recursive.
(c) (2 pt) Implement delete, which takes a non-negative integer k and returns an edit that deletes the last k digits of its argument n. You may use pow or ** in your solution.
def make_editor(n, pr):
“””Return an editor for N.
>>> f = make_editor(2018, lambda n: print(‘n is now’, n))
>>> f = f(delete(3)) # delete the last 3 digits from the end of 2018
n is now 2
>>> f = f(insert(4, 0)) # insert digit 4 at the end of 2 (position 0)
n is now 24
>>> f = f(insert(3, 1)) # insert digit 3 in the middle of 24 (position 1)
n is now 234
>>> f = f(insert(1, 3)) # insert digit 1 at the start of 234 (position 3)
n is now 1234
>>> f = make_editor(123, print)(delete(10)) # delete 10 digits from the end of 123
0
“””
def editor(edit):
result = edit(n)
pr(result)
return make_editor(result, pr)
return editor
def insert(d, k):
def edit(n):
if k == 0:
return d + 10 * n
else:
return n % 10 + 10 * insert(d, k-1)(n//10)
return edit
delete = lambda k: lambda n: n // 10 ** k
6
No more questions.