CSM Mock Final Spring 2018
2
1. WWPD (10 pts)
For each of the expressions in the table below, write the output displayed by
the interactive Python interpreter when the expression is evaluated on the provided line. The interactive interpreter displays the repr string of the value of a successfully evaluated expression, unless it is None
Write FUNC to indicate a functional value.
Assume that you have started python3 and executed all the code in the left column first.
class A: a=5
def __init__(self, lst, n): a=1
c= [3, 5, 6] a= A(c, 2) b = A2(c, 3) c= b
self.lst = lst a.a
self.n = n
5
def update(self):
for i in range(len(self.lst)): c.a
self.lst[i] = self.lst[i] * self.n
self.a += 1 3
class A2(A): a.update() a = 3 c.update()
def update(self): A.a for i in range(len(self.lst)):
self.lst[i] = self.lst[i] – self.n 5
self.a -= 1
A2.a
class B:
def __init__(self, a): 3
self.a = a
a.lst
[3, 7, 9]
B(a).a.a
6
B(A).a.update()
Error
3
2. Environment Diagram (8 pts)
Create the environment diagram that results from executing the code below until the entire program is finished or an error occurs. Be sure to include the global frame as well as any other frames created.
def f(f):
def h(x, y):
z=4
return lambda z: (x + y) * z
def g(y):
nonlocal g, h
g = lambda y: y[:4]
h = lambda x, y: lambda f: lambda z: f(f(x) + ( y + z))
return y[5] + y[2:4] + y[6] return h(g(“cosmic!”), g(“why!”))
f = f(lambda f: f(f))(2)
Solution: https://goo.gl/DBp8GD
4
3. List Diagram (8 pts)
For each part, create the box and pointer diagram representing the lists after the code above is run. You do not need to include indices in your diagram.
6
7
#part a
t = [5, [6,7]] t.extend(t[1])
t
5
6
7
#part b
t = [5, [6,7], 8]
t.append(lambda: t.extend(t[-3:])) t[3]()
t
6
7
5
8
8
Func λ()
5
#part c
t = [5, [6,7], lambda: t.append([[0]])] b = t + [1]
b[2]()
t.extend(b.pop(1))
t
b
0
6
7
5
6
7
Func λ()
5
1
6
4. That’s Odd (6/6 pts)
Part A
Implement deep-apply, which takes in a (potentially nested) list of numbers s and a function f, and applies f to every element of s.
;(deep-apply ‘((1 (2)) 3) (lambda (x) (* x 2))) ;((2 (4)) 6)
(define (deep-apply s f ) (cond ((null? s) nil)
((not (pair? (car s))) (cons (f (car s)) (deep-apply (cdr s) f))) (else (cons (deep-apply (car s) f) (deep-apply (cdr s) f)))))
Part B
Implement parity, which takes in a (potentially nested) list of numbers s and replaces every element in s with either ‘odd’ or ‘even’ depending on whether the element is odd or even.
;(parity ‘(1 (2) 3)) ;(odd (even) odd)
(define ( parity s ) (cond? ((null? s) nil)
((pair? (car s)) (cons (parity (car s)) (parity (cdr s)))) ((odd? (car s)) (cons ‘odd (parity (cdr s))))
(else (cons ‘even (parity (cdr s))))))
;alt solution (define (parity s)
(deep-apply s (lambda (x) (if (odd? x) ‘odd ‘even))))
7
5. #5 (10 pts)
Suppose Samo the dog needs to make his way across an n x n grid to get back to Professor DeNero. Samo is a very loyal dog and wants to reach the Professor in the fewest moves possible, but at the same time, Samo is an opportunist, and notices treats scattered throughout the grid.
Suppose Samo starts at location (0, 0) on the grid G and Professor DeNero is at location (n, n) on the grid; that is, they are on opposite corners. Our input grid G tells us how many treats are at any location – for a location (x, y), the number of treats in that location can be found with G[x][y]. G[x][y] will never be negative. Given that Samo can move up, down, left, or right (no diagonals), and that Samo will eat all the treats in a location as he leaves it, fill in the function trail_of_treats to return the maximum amount of treats Samo can eat if he takes the minimum moves to get to Professor DeNero. (Samo will also eat all the treats at Professor DeNero’s location when he reaches it.)
def trail_of_treats(G):
return trail_helper(G, 0, 0)
def trail_helper(G, x, y): ifx==len(G)-1and y==len(G)-1:
return G[x][y]
elif x >= len(G) or y >= len(G): else: return -1
a = trail_helper(G, x+1, y) b = trail_helper(G, x, y+1) return max(a, b) + G[x][y]
#alternate solution
def trail_helper(G, x, y):
if x >= len(G) or y >= len(G): else: return 0
a = trail_helper(G, x+1, y) b = trail_helper(G, x, y+1) return max(a, b) + G[x][y]
8
6. Infinite Generator (10 pts)
Create a class Inf_Gen that generates an iterator that iterates through all the elements of some sequence, and upon reaching the end, loops back to the beginning. It should also be able to go in the reverse order and the first element should loop forward to the last element of the iterable.
class Inf_Iter:
“””Creates an iterator that can iterate in either direction over its elements for any number of calls to next().
>>> a = Inf_Gen([2,4,6,8,10]) >>> it = a.gen()
>>> next(it)
2>>> next(it) 4>>> next(it)
6>>> a.rev() >>> next(it)
4>>> next(it)
2>>> next(it) 10 >>>a.rev() >>> next(it)
8>>> next(it) 10 >>>next(it)
2“””
2
4
6
8
10
10
9
def __init__(self, lst): self.lst = lst
self.index = 0 self.reverse = False
def gen(self): while True:
yield self.lst[self.index] if self.reverse:
self.index -= 1
if self.index == -1:
else: self.index = len(self.lst) – 1
self.index += 1
if self.index == len(self.lst):
self.index = 0
def rev(self):
self.reverse = not self.reverse
10
7. Linked List (10 pts)
Create a function partition_sll that takes in a linked list as an argument and non-destructively returns a linked list composed of three smaller linked lists, one less than, one equal to, and one greater than, the first element of the original linked list.
def partition_sll(lnk): “““
>>> lnk = Link(5, Link(2, Link(3, Link(1, Link(4)))))
>>> partition_sll(lnk)
Link(Link(4, Link(1, Link(3, Link(2)))), Link(Link(5), Link(Link.empty)))
>>> lnk2 = Link(3, Link(4, Link(3, Link(1, Link(4)))))
>>> partition_sll(lnk2)
Link(Link(1), Link(Link(3, Link(3)), Link(Link(4, Link(4)))))
“““
less, equal, greater, pivot = Link.empty, Link.empty, Link.empty, lnk.first
while lnk is not Link.empty: curr = lnk.first
if curr < pivot:
less = Link(curr, less)
elif curr > pivot:
greater = Link(curr, greater)
else:
equal = Link(curr, equal)
lnk = lnk.rest
return Link(less, Link(equal, Link(greater)))
11
8. Branching Out (4/8pts)
Trees are implemented as objects for all parts of this problem.
Part A
Implement minimize_tree, which takes in a tree t and changes each node to have the smallest value found from that node downwards. That is, for every node n in t, n’s label should be the smallest number in the subtree rooted at n.
def minimize_tree(t):
[minimize_tree(b) for b in t.branches]
t.label = min([b.label for b in t.branches] + [t.label])
Part B
Define rotate, which rotates the labels at each level of tree t to the left by one destructively. This rotation should be modular (That is, the leftmost label at a level will become the rightmost label after running rotate.) You do NOT need to rotate across different branches.
def rotate(t): “””
>>> t1 = Tree(1, [Tree(2), Tree(3, [Tree 4]), Tree(5)]) >>> rotate(t1)
>>> t1
Tree(1, [Tree(3), Tree(5, [Tree(4)]), Tree(2)])
>>> t2 = Tree(1, [Tree(2, [Tree(3), Tree(4)]), Tree(5, [Tree(6)])]) >>> rotate(t2)
>>> t2
Tree(1, [Tree(5, [Tree(4), Tree(3)]), Tree(2, [Tree(6)])]
“””
labels = [b.label for b in t.branches]
n = len(t.branches) for i in range(n):
b = t.branches[i]
b.label = labels[(i + 1) % n] rotate(b)