WELCOMETO EXAMPREP5
not
sponsored
We’llstartat Berkeleytome 2 10pacifictime
Worksheetcanbefound intheDrivefolder linkscsbla.orgexamprep
MusicDjangoReinhardt
MinorSwing
Beyondthesea
Brazil
Feelfreeto ask questions inthemeantime
CS 61A Structure and Interpretation of Computer Programs
Fall 2020 Quiz 5
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. Tree Printer
(a) Your friend wants to print out all of the values in some trees. Based on your experience in CS 61A, you
decide to come up with an unnecessarily complicated solution. You will provide them with a function
which takes in a tree and returns a node-printing function. When you call a node-printing function, it
prints out the label of one node in the tree. Each time you call the function it will print the label of a
different node. You may assume that your friend is polite and will not call your function after printing
out all of the tree’s node labels. You may print the labels in any order, so long as you print the label of
each one exactly once.
def node_printer(t):
���
>>> t1 = tree(1, [tree(2,
… [tree(5),
… tree(6, [tree(8)])]),
… tree(3),
… tree(4, [tree(7)])])
>>> printer = node_printer(t1)
>>> printer()
1
>>> printer()
4
>>> printer()
7
>>> for _ in range(5):
… printer()
3
2
6
8
5
���
lamb = ____________________________________________________________________________
def step():
nonlocal lamb
next_node, lamb = lamb()
print(_________________________________________________________________________)
for ____________________________________________________________________________
____________________________________________________________________________
return step
lamb
lamb lambda
I nextnode
lamb
print l
lamb lanbd.x.fianbdaCx.fSl
reassignedto area afunction
tovisit E thatcontains
lambda ft
labelnextnode
b in branchesnextnode
lamb lambda x f lambda X f b lamb
affordbtolamb
lamb lambda b lamb
Notes
lamb isa function
Ittakesnoinputs
Itsfirstoutputis probably a
node
Itssecondoutputisanother
functionofthesamestructure
oneachstepC callweshouldprintexactly onething
whatdowehaveaccessto
land afunction hardto
understand
t a treebutonlypointstotheroof whatifwe’reprintingnodesfartherdown
nextn.de Seemspromising
sothefirstreturnfromlandshouldbeanewuniquenode
print
labelnextnode
weneedtoprogressthroughthe wholetree
Howdowedecidewheretogonext
I
can’tuse becausethiswouldgiveus
repeats t istherootnode
weneedtoconsiderall of nextnode’schildren wewon’tvisit
nextnodeagain
becauseitonlygetsprintedonc
d
for bin branchesnextnode
Nowwhatdowedoforeachofthesebranches
Wecan’trecorse immediately weneedto send tovisitlater
d
wheredowegetnodeseachtime Fromlambs
Howmightwedothisif lambwerea list
t
mayne tovisit E selectanewnodeand
removeit fromlist
nextIode Eovisitpop ofnodestovisitinanefuture
for bin branchesnextnode
y
toVisitappendb
Let’simplementthiswith lambdafunctions
Ournextnode tovisitpopa lineisreplacedwithnextnodelamb lambC
Howdowe append tothislambdafunction
Storeinnestedlambda
functionseachoneholdsonevalueandareferencetothenextlambdafunction
y In
etsserce
a linkedlist whichyou’lllearnaboutlater
FIFA
Sofyouwanttocreate anew
lambdafunctionwhichreturns
yournewvalueandtheprevious
lambdafunction
storethisinfoinlocalvariables
forbin branchesnextnode
lamb lambdax f lambdaCx f b lamb
Finallyhowdoweinitializelamb It shouldcontaintherootnodeofthetreeanditssecondreturnvaluedoesn’tmattersince itwillneverbecalledSooneexampleconebe
lamb Lambda Ct None
3
2. Layer Generator
(a) Construct the generator function layer_gen, which takes in a tree t and returns a layer iterator of t. A
layer iterator returns label values of nodes in the tree in level order; that is, it yields the root node, then
each node from the second level, then each node from the third level and so on. Hint: consider using the
pop method of lists.
def layer_gen(t):
���
>> lg = layer_gen(t1)
>>> for node_label in lg:
… print(nodel_label)
1
2
3
4
5
6
7
8
���
___________________________________________________________________
while _____________________________________________________________:
node = ________________________________________________________
_______________________________________________________________
_______________________________________________________________
tovisit Ef
to visit
to visitpop o
print labelnode
to visitextend branchesnode
4
3. Fibonacci Generator
(a) Construct the generator function fib_gen, which returns elements of the Fibonacci sequence in order.
Hint: The solution doesn’t require any lambda functions or crazy workarounds, but instead a clever leap
of faith. Consider using the zip function.
def fib_gen():
���
>>> fg = fib_gen()
>>> for _ in range(10):
… print(next(fg))
0
1
1
2
3
5
8
13
21
34
���
yield from _____________________________________________________________
a = ____________________________________________________________________
________________________________________________________________________
for ____________________________________________________________________:
____________________________________________________________________
a
0 I 1 2 35 8
About
0 I
fibgeno
nextta
x y in ZipcarfibgenCD
yield Xty
forbgen gives
rexts D
O c I 2 3 S 8
Whatshouldweyieldfromtostart
Rememberthetwo basecasesofFibonacci fcos 0 FCD I
yield
from O D
Wedon’thaveenoughlinestokeeptrackofpreandconandtoyield
values
solet’srecorse
1
Weonlyhave0andI sofarbutthat’senoughtocreatethenext
valueinthesequence
Butwecan’treachbacktogetpreviousvalvesso
instead letsgettwo
Fibonaccisequences sidebysideoffsetby I
www.fib.gencan O 1
outputsofar
new
instanceof C
So wejustneedtocreatetwoFbgenerators onethathassteppedforwardby 1
andyieldtheirsumateachstep
tomoveaniteratorforwardwecallnext
So a fibgenC
nexta
for X y in Zip afibgenG
i
yieldXty
5
4. Partition Generator
(a) Construct the generator function partition_gen, which takes in a number n and returns a n-partition
iterator. An n-partition iterator yields partitions of n, where a partition of n is a list of integers whose
sum is n. The iterator should only return unique partitions; the order of numbers within a partition and
the order in which the partitions are returned does not matter.
def partition_gen(n):
���
>>> for partition in partition_gen(4): # note: order doesn�t matter
… print(partition)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
���
def yield_helper(j, k):
if ______________________________________________________________________________:
yield _______________________________________________________________________
elif ____________________________________________________________________________:
for _________________________________________________________________________:
yield ___________________________________________________________________
yield _______________________________________________________________________
yield _______________________________________________________________________________
forvalveinx
yieldvalue yieldfrom2
2 to CES
wewanttorotition Cate use K
Cli i i
caseddon’tusek
yieldhelper 2,2I large.SIuswehYohfafition It yieldhelped Few.heipercer
allpartitions Sj dIftyiednecpercc.cl 4ofsizeEk j o
yield.hu
elements
C
K O and j 0
Smallpart in yield helper j k k
k t smallpart
from yieldhelpercj K l
from
yieldhelperCn n
Trememberthe Fron
Similartocourtpartitions
cangiveagood
higpothesisforwhatjandkrepresent
Maytelet j Ethecurrent
numberwe’retryingtopartition couldalsousete
kEthelargestnumberwe’reallowedtopartition
with
smallest
to
yield
fromyieldhelperlan
Whycan’twejustrecorseonyieldpartitions
ideaSaywehave n 6 Thenyieldalluniquepartitionsof5andputifattheend
all uniquepartitionsof4maps23atmeend1 andsoon
Problems Doesn’t guaranteeuniqueness
2 I I l isa validpalliationof5 so
couldget 2 I I I l
111it l is avalidpartitionof4
socouldget4 2
samepartition
BASECASES
similartocountpartitions
if j o thenthereisekactyoneparlition