CS 61A Structure and Interpretation of Computer Programs Fall 2020 Quiz 7
INSTRUCTIONS
• Please review this worksheet before the exam prep session. Coming prepared will help greatly, as the TA will be live solving without allocating much time for individual work.
• Either Sean or Derek will be on video live solving these questions. The other TA will be answering questions in the chat. It is in your best interest to come prepared with specific questions.
• This is not graded, and you do not need to turn this in to anyone. Below is a tree, which will be referred to as t1 in future questions.
2
1. Node Function Generator
(a) Construct the generator function node_func_gen, which takes in a tree t, a one-argument filter function f and a one-argument mapping function g. node_func_gen yields one positional node function for each node position in the t. A positional node function takes in a tree as an argument and returns the value of the node at the specified position. For example, a positional node function constructed for the root of a tree will return the label of the root of any tree that it is given. You may assume that any trees passed to your positional functions have the same structure as t.
t
so
f Ebranches i yield ___la__m__b__d_a_________________l_a_b__e__l___________________________________
Pgp
Basecase Whendoyouyieldavalve
Say fonlykeeps evenvalues
You may not use list or any sort of comprehension.
def node_func_gen(t, f, g):
f t
>>> for func in node_func_gen(t1, f, g) # note: order doesn t matter
>>> f = lambda x: x % 2 == 1
>>> g = lambda x: x**2
4 lambdaf lambdat
…
…
1
25
9
49
print(func(t1))
f
f
if __________l_a__b__e__l__________________________________________________________:
xgX for i in range(len(t.branches)):
Oncewedecidetoyieldavalve howshouldwemodifyit
useg
if f Elabel
yield gCtlabel Howaboutintherecursivecase
ifitfE __________________b_r_a_n_c_h_es____________________________)
yield from __________(___l_a_m__b_d__a___l_a_m__b__d_a_____L_a_m__b__d_a_________b_r_a_n_c_h_e_s____, \
Whatdowegetwhenwerecuseon abranch
LeapofFaith
map
Ct fitf
lambda0 lambda f lambda6 f fbranchesfi i
function iterable
nodefore gen
g
do yieldI
doweyield2here
1 functionswhichtakeusfromthat filtered wegetageneratorof childnodeto our
mapped nodevalues
d todois thesefunctionsothey fromthe root
Alwl e have modify take
childthen
tothe recursion take
the way
you
will youtherest
Ef
Iso
functionfam k 2to4
d
recursion
map nodefmcgenE El fg
take return a function should i in a function f and positionalnode
fromrooot f t totarget tomapEtoith
needs brancfhrost
Cambda i lambda f lambdaE fCtbranches i3 o
g
sowe wantto mapthismodicationontoallrecursivelyieldedfunctions
branches
2. Fibonacci Tree
Implement fib_tree, which takes in a non-negative integer n and returns a depth-n Fibonacci tree of depth n. The root label of a depth-n Fibonacci tree is the nth Fibonnaci number (indexed from zero), and each node in the tree has exactly two children which contain the values needed to compute the Fibonacci number of their parent. If no lower Fibonacci numbers are required to compute the value of a node, then the node is a leaf.
def fib_tree(n):
>>> t = fib_tree(6)
>>> t.label
8>>> t.branches[0].label 5
>>> t.branches[1].label 3
fibutreecz
bs fistreeCD
f tco II
n21
return _______________________________________________________________
bs = _____________C__n_______________t_r_e__e__ln_________________________________ fib free D Ab 27
if _______________________________________________________________________
no
Tree
i
no
fibtreecy
o
Treeln
too
LOL label bs labeltbs B
return ________C___b__s_____________________________________________________
3
4
3. Subsequence Generator
foritemin yitem
add
CB to a
yieldfrom x yieldhomy
foritemin item yield
(a) Implement subsequences, which takes in a list lst and yields all subsequences of lst. You may not use the list function or any comprehensions.
def subsequences(lst):
>>> for seq in subsequences([1, 2, 3]) # note: order doesn t matter
…
…
[1,
[1,
[1,
[1]
[2,
[2]
[3]
[]
print(seq)
modifyresultstoincludetaxbeginning Cased includefirstitea
2, 3] 2]
3]
3]
D
Casey
don’t firstiten include
results recursive
1st
Cotontothefrontofall puts 1st results
if __________________________________________-:
a
yield from map(___________________________________, ___s_u_b_s_e_q__u_e_n_c_e_s___________)
Ust seq ClD yield from ___________________________________________________________________
oosel lambdaseq
Std 3
discards1st
cash
subsequences
else:
yield ________________________________________________________________________
C
subsequences 1,23
I up 2,3
i know 1st we
D
O fdoitadrgy.aadsubseueaceqffgEDqzz.gg
tf lo Glo Glo
f
subsequences
CT
don’tneedtomodify
yield
4. Minimax
You are playing a game with a friend. At the end of the game you are both given the same score. Your friend wants to make this score as low as possible, and you want to make this score as high as possible. This situation can be modeled with a tree: leaf nodes correspond to the game being over and contain the score at the end of the round. The values of intermediate nodes don’t matter.
Both you and your friend have perfect knowledge of this game tree t. With this setup, implement first_move, which takes in a game tree t as input and outputs the index of the branch in the tree corresponding to your optimal first move.
Hint: all even-depth layers correspond to your turns, and all odd-depth layers correspond to your friend’s turns.
def first_move(t):
>>> first_move(t1)
2
>>> # best choice is the rightmost child (value is 7)
>>> # index of rightmost child in t.branches is 2
Maxor min
probably
def optim_val(tr, fn=____________________):
if tr.is_leaf():
return __________________________
fn
triabel
Min
OptionVal b forbintrbranches return max(__________________b_r_a_n__c_h_e_s___, key=____________________________b__ra__n_c_h_e_s__)
return ____________([________________m__i_n_if_f_n_is_m__a_x_e_l_s_e_m_a__x_________________________])
rangellen E O130
bQ
lambda i optionvallt defmaxuscoreCES
return t.labelift.isleaf for elsemaxcaakscorelb
biathranches
5