CS 61A Structure and Interpretation of Computer Programs
Fall 2016
INSTRUCTIONS
Final Solutions
• You have 3 hours to complete the exam.
• The exam is closed book, closed notes, closed computer, closed calculator, except two hand-written 8.5” × 11”
pages 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
Room
Row & Seat Number
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. (16 points) What Would Python Display?
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. Assume that expressions are evaluated in the order that they appear on the page, with the left column before the right column.
The Pair class appears on page 2 of the final study guide. The reduce function appears on page 1 of the final study guide. The first two rows have been provided as examples.
Assume that you have started python3 and executed the following statements:
swap = lambda paws = lambda emit = lambda time = lambda mite = lambda s, t = print,
a, b: [b, a]
s: reduce(swap, list(s), 3)
y: [x+y for x in y]
t, f: (t and f(t)) or print(t+2) mu: time(mu + 1, print)
[3 * x for x in range(8)]
time(me, lambda k: [k.pop()])
def
def
Expression
5*5
print(Pair(6, 1))
ti(me): while me: yield
newt(graves):
tina = graves.pop()
if graves.pop() % 3 == 0:
graves.pop() print(tina, graves.pop()) if graves:
return Pair(tina-1, newt(graves)) return Pair(tina+1, tina)
Interactive Output
25
(6 . 1)
Expression
Interactive Output
paws(range(4, 6))
[5, [4, 3]]
tuple(ti([5, 6]))
([6], [5])
s(newt([2, 5, 8]))
82
(9 . 8)
s(newt(t))
21 12
90
(20 10 . 9)
print(2, s(print(3)))
emit([[3], [2]])[1]
3
None
2 None
[2, [3], [2]]
s(Pair(Pair(4, 5), nil))
((4 . 5))
time(2, mite)
3 5 4
Name: 3 2. (8 points) A Function By Any Other Name
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 lists. You don’t need to write index numbers or the word “list”.
Green boxes indicate parts of the diagram that were scored during grading.
9 10 11 12
func your(name) [parent=Global]
name = [2, lambda your: name[0]]
def your(name): def what(s):
nonlocal name
name = [name, s]
return what is your(name)
def your(s): s[1][1](name[:1])
return what your(True)(name)
Global frame
your
name 0 2 1 func λ(your) [parent=Global]
your Global
f1: ___________ [parent=____________]
name 0 True 1
what func what(s) [parent=f1]
your
Return Value
f2: _
what f1
__________ [parent=____________]
s
func your(s) [parent=f1]
Return Value
False
f3:
your f1
___________ [parent=____________]
s
Return Value None
λ Global
f4: ___________ [parent=____________]
your
0
True
Return Value 2
1
2
3
4
5
6
7 list 8
list
list
4
3. (8 points) Boxes and Arrows
Fill in the environment diagram that results from executing each block of code below until the entire program is finished or an error occurs. Use box-and-pointer notation for lists. You don’t need to write index numbers or the word “list”. Please erase or cross out any boxes or pointers that are not part of a final diagram.
t = [1]
t.append([t, [1]])
Global frame
t
(a)
(b)
(c)
list
list
list
list
list list
01
list
02
list
01
1
0
1
01
12
2
03
13
2
3
(d)
t = [1, 2]
t.append(t[t[0]:t[t[0]]])
t = [3]
t.extend(t + [t] + [[t]])
t = [1, 2, 3, 4]
t[1] = t[2:4]
t[2:3] = t
t[4] = t.pop()
Global frame
t
Global frame
t
01
1
21
3
44
54
Global frame
t
0
list
03
14
Name: 5 4. (16 points) A Tree or a List
A flat list is a list containing integers and None that describes a binary tree of integers. The root is element 0. The left branch of element i is element 2∗i+1 and the right is 2∗i+2. The None value is used to indicate an empty tree, such as an empty left branch when the corresponding right branch is not empty. None values at the end of a flat list can be omitted. Four examples of trees and the flat lists that describe them appear below.
(a) (4 pt) Implement grow, which takes a flat list s of integer node values (which may also contain None, as described above) and an index i that is 0 by default. When i is 0, grow returns a BTree instance described by s. The BTree class appears in the left column of page 2 of the midterm 2 study guide.
def grow(s, i=0):
“””Return a binary tree described by the flat list S when I is 0.
>>> grow([3, 1, 4])
BTree(3, BTree(1), BTree(4))
>>> grow([3, None, 4])
BTree(3, BTree.empty, BTree(4))
>>> grow([3, 1, None])
BTree(3, BTree(1))
>>> grow([6, 3, 8, 1, None, 7])
BTree(6, BTree(3, BTree(1)), BTree(8, BTree(7))) “””
if i >= len(s) or s[i] is None: return BTree.empty
left, right = grow(s, 2*i+1), grow(s, 2*i+2) return BTree(s[i], left, right)
(b) (4 pt) Implement leaves, which takes a flat list s and returns a generator over the leaf values of the tree described by s. You may not call grow in your solution.
def leaves(s):
“””Return a generator over the leaf values in a binary tree described by S.
3 14
[3, 1, 4]
3
[3, None, 4]
4
3
1
[3, 1]
or
[3, 1, None]
6
[6, 3, 8, 1, None, 7]
3 8 or
17
[6, 3, 8, 1, None, 7, None]
>>> [1, >>> [1] >>> [1, “””
f = for
list(leaves([3, 1, 4]))
4]
list(leaves([3, 1, None]))
list(leaves([6, 3, 8, 1, None, 7])) 7]
lambda x: x >= len(s) or s[x] is None
i in range(len(s)):
if s[i] is not None and f(2*i+1) and f(2*i+2):
yield s[i]
6
(c) (2 pt) Circle the Θ expression that describes the height of the tree returned by grow(s) for an s of length
n that ends with an integer. 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
(d) (6 pt) A Set instance represents a set of integers as a binary search tree. The node values are stored in a flat list called items. Implement the find method, which returns whether an element is in the Set and if not, adds it as a new leaf if the argument add is True. Hint: int(True) is 1 and int(False) is 0.
class Set:
“””A set of ints stored in a binary search tree described by a flat list.
>>> s = Set()
>>> [s.add(k)
[False , False ,
>>> s.items
[6, 3, 8, 1, 4, None, 9]
>>> [s.has(k) for k in range(10)]
[False, True, False, True, True, False, True, False, True, True] >>> [s.add(3), s.add(2)] # 3 was already in the set; 2 was added [True, False]
>>> s.items # 2 appears as a leaf; the right branch of 1. [6, 3, 8, 1, 4, None, 9, None, 2]
“””
def __init__(self):
self.items = [] def add(self, v):
“””Ensure that V is
return self.find(v, def has(self, v):
“””Return whether V return self.find(v,
def find(self, v, add): i=0
in the set; return whether it was already there.””” True)
is in the set.””” False)
for k in [6, 3, 1, 8, 9, 4, 4, 4]]
False , False , False , False , True , True]
# The node values of a binary search tree
while i < len(self.items) and self.items[i] is not None:
if self.items[i] == v: return True
i = 2 * i + 1 + int(self.items[i] < v) if add:
self.items += [None] * (i-len(self.items)+1)
self.items[i] = v return False
Name: 7 5. (10 points) Reset
(a) (6 pt) Implement the fset function, which returns two functions that together represent a set. Both the add and has functions return whether a value is already in the set. The add function also adds its argument value to the set. You may assign to only one name in the assignment statement. You may not use any built-in container, such as a set or dictionary or list.
def fset ():
"""Return two functions that together represent a set.
>>> add , has = fset () >>> [add(1), add(3)] [False , False]
>>> [has(k) for k in [False, True, False, >>> [add(3), add(2)] [True, False]
>>> [has(k) for k in
[False, True, True, True, False] “””
items = lambda x: False def add(y):
# Neither 1 nor 3 were already in the set
# 3 was already in the set; 2 is added
range(5)] True, False]
range(5)]
nonlocal items
f = items
items = lambda x: x == y or f(x)
return f(y)
return add, lambda y: items(y)
(b) (4 pt) Implement the cycle procedure, which takes a non-empty Scheme list of values. It returns an infinite stream that repeats those values in order, indefinitely. For example, (cycle ’(6 1 a)) evaluates totheinfinitestreamcontainingthevalues6 1 a 6 1 a 6 1 a 6 1…
(define (cycle s) (define (with t)
(if (null? t)
(cycle s) ; or (with s)
(cons-stream (car t) (with (cdr t)))))
(with s))
8
6. (10 points) I Scheme for Ice Cream
The built-in append procedure is equivalent in behavior to the following definition.
(define (append s t) (if (null? s) t (cons (car s) (append (cdr s) t))))
(a) (1 pt) Circle True or False: The recursive call to append in the definition above is a tail call.
(b) (4 pt) Implement atoms, which takes a Scheme expression. It returns a list of the non-nil atoms contained in the expression in the order that they appear. A non-nil atom is a number, symbol, or boolean value.
scm> (atoms
(1)
scm> (atoms
(+ 2 3)
scm> (atoms
(+ * 2 3 4)
scm> (atoms
(* + 1 * 2 3 + 4 5)
1)
’(+ 2 3))
’(+ (* 2 3) 4))
’(* (+ 1 (* 2 3)) (+ 4 5)))
(define (atoms exp)
(cond ((null? exp) nil)
((atom? exp) (list exp))
(else (append (atoms (car exp)) (atoms (cdr exp))))))
(c) (5 pt) If Scheme had only numbers and two-argument procedures, parentheses would be unnecessary. To demonstrate, implement tally, which takes the list of atoms in a Scheme expression. It returns a list whose first element is the value of the original expression. Assume that the original expression consists only of numbers and call expressions with arithmetic operators (such as + and *) and exactly two operands. Hint: tally is similar to the built-in eval procedure: (eval ’(+ (* 2 3) 4)) evaluates to 10.
scm> (car (tally ’(1)))
1
scm> (car (tally ’(+ 2 3))) 5
; atoms in 1
; atoms in (+ 2 3)
; atoms in (+ (* 2 3) 4)
scm> (car (tally ’(+ * 2 3 4)))
10
scm> (car (tally ’(* + 1 * 2 3 + 4 5))) ; atoms in (* (+ 1 (* 2 3)) (+ 4 5)) 63
(define (tally s)
(if (number? (car s)) s
(let ((first (tally (cdr s))))
(let ((second (tally (cdr first))))
(cons (eval (list (car s) (car first) (car second)))
(cdr second))))))
Name: 9
7. (12 points) Hailstoned
The following two tables of integers from 0 to 99 (including 99) and 1 to 99 are used in the questions below.
create table ns as
with t(n) as ( select 0 union select n+1 from t where n < 99 ) select * from t;
create table ps as select n from ns where n > 0;
(a) (3 pt) Create a one-column table of all integers from 2000 to 9999 (including 9999). Do not use recursion. select a.n * 100 + b.n from ns as a, ns as b where a.n >= 20;
(b) (5 pt) Create a table with a row for each pair of different positive integers x and y below 100. The three columns contain x, y, and the greatest common divisor of x and y. For example, one row contains (20, 50, 10) because 10 is the largest n that evenly divides both 20 and 50. Another row contains (50, 20, 10).
select a.n as x, b.n as y, max(c.n) as gcd
from ps as a, ps as b, ps as c
where a.n <> b.n and a.n % c.n = 0 and b.n % c.n = 0
group by a.n * 100 + b.n;
(c) (4 pt) A hailstone sequence begins with a positive m. If m is even, divide it by 2. If m is odd, triple it and add 1. Repeat until 1 is reached. For example, the sequence starting at 3 is 3, 10, 5, 16, 8, 4, 2, 1. Create a two-column table with positive integer m in the first column and the length of the hailstone sequence starting at m in the second column. For example, one row contains (3, 8) because the hailstone sequence starting at 3 has 8 elements. This table should have one row for each m, but only include m for which the entire hailstone sequence starting at m consists of numbers below 100.
with hailstone(m, length) as (
select 1, 1 union
select n, length + 1 from hailstone, ps
where (n%2==0 and m == n/2) or
(n>1 and n%2==1 and m == 3*n+1)
) select * from hailstone;
10
8. (0 points) Draw! (Optional) Compare Python, Scheme, and SQL in a picture.