CS 61A Structure and Interpretation of Computer ProgramsFall 2013 Final SolutionsINSTRUCTIONS• You have 3 hours to complete the exam.• 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 three official 61A study guides attached to the back of this exam.• Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provide abrief explanation.• Fill in the information on this page using PERMANENT INK. You may use pencil for the rest of the exam.Last nameFirst nameSIDLoginTA & section timeName of the person toyour leftName of the person toyour rightAl l the work on this examis my own. (please sign)For staff use onlyQ. 1 Q. 2 Q. 3 Q. 4 Total/24 /10 /20 /26 /802THIS PAGE INTENTIONALLY LEFT BLANKLogin: 31. (24 points) What a Value!(a) (10 pt) For each of the following Python expressions, write the value to which it evaluates, assuming thatexpressions are evaluated in order in a single interactive session. Answers may depend on previouslines; be careful to keep track of bindings from names to values! The first two rows have beenprovided as examples. If evaluation causes an error, write Error. If evaluation never completes, writeForever. If the value is a function, write Function.Assume that you have started Python 3 and executed the following statements:def outer (f):x = 0def inner (g):nonlo cal xx , y = g(x) , f ( x)return f(x , y )return innerdef add (a , b =2):return a+ bdef grow (c ):return sum ( range (c , c +2))h1 , h2 = outer ( add ), outer ( add )Expression Evaluates to5*5251/0Errorgrow(5)11list(map(str, map(grow, range(3, add(3)))))[’7’, ’9’]h1(grow)3outer(grow)(add)Errorh1(grow) + h2(add) + h2(grow)194(b) (8 pt) Each of the following expressions evaluates to a Stream instance. For each one, write the valuesof the three elements in the stream. The first value of the first stream is filled in for you.Assume that you have started Python 3 and executed the following statements, in addition to the Streamclass statement on your final study guide.def m(t ):def compute_rest ():return m( t . rest . rest )return Stream (t . rest . first +1 , co mp ut e_ rest )s = lambda t: Stream (t , lambda : s ( t +2))t = s (1)u = m ( t)Stream Has the first three elementst1, 3 , 5u4 , 8 , 12m(u)9 , 17 , 25(c) (6 pt) For each of the following Scheme expressions, write the Scheme value to which it evaluates. Thefirst three rows are completed for you. If evaluation causes an error, write Error. If evaluation nevercompletes, write Forever. Hint: No dot should appear in a well-formed list.Assume that you have started the Project 4 Scheme interpreter and evaluated the following definitions.( define f ( lambda ( x y ) ( g ( cons x y )) ))( define g ( mu (z) ( list (h x ) y z )))( define h ( mu (y) ( if (> y 0)(+ x (h (- y 1)))1)))Expression Evaluates to(* 5 5)25’(1 2 3)(1 2 3)(/ 1 0)Error’((1 . (2 3 . (4))) . 5)((1 2 3 4) . 5)(cons 1 (list 2 3 ’(car (4 5))))(1 2 3 (car (4 5)))(f 2 3)(5 3 (2 . 3))Login: 52. (10 points) Good Game(a) (8 pt) In the box below, write the final value to which each numbered blank would have an arrow in theenvironment diagram. Blank 0 is completed for you. In addition, fill in the parent annotations for allfunctions and frames that have non-global parents.You may wish to fill in the diagram, but only the numbered values and parent annotations will be scored.Hint: The pop method removes and returns the last element of a list.Note: There is another question at the bottom of this page.Global framegfunc g(g) ________________Return ValueReturn ValueReturn Valuescfunc s(g) ________________func h(s) ________________f1: g _________________gf2: s _________________f3: h _________________hgs12435Write each value as it would be displayed by the Python interpreter1. _______________12. _______________23. _______________34. _______________45. _______________5h01. _______________0[1, 2, [3, 4]][1, 3][6, 1][8, 7, 6][7, 6][[6], [1, 3]]def g(g): def h(s): nonlocal g g = [s.pop(), g[0]] s = s[1:] return [s[1:], g] return hdef s(g): return [8, 7] + gc = g([3, 4, 5])h = [1, 2, [3, 4]]c(s([6, 1])) # Aparent=f1parent=f1(b) (2 pt) What value would result from evaluating c(s([6, 1])) another time after executing the code above?If evaluation causes an error, write Error. If evaluation never completes, write Forever.[[6], [1, 1]]63. (20 points) Equality(a) (4 pt) Fill in the blanks in the implementation of paths, which takes as input two positive integers xand y. It returns the number of ways of reaching y from x by repeatedly incrementing or doubling. Forinstance, we can reach 9 from 3 by incrementing to 4, doubling to 8, then incrementing again to 9.def inc (x ):return x +1def double (x ):return x *2def paths (x , y ):""" Return the number of ways to reach y from x by repeate dincr em en ti ng or doubli ng .>>> paths (3 , 5) # inc ( inc (3))1>>> paths (3 , 6) # double (3) , inc ( inc ( inc (3)))2>>> paths (3 , 9) # E .g. , inc ( double ( inc (3)))3>>> paths (3 , 12) # E. g ., double ( double (3))6>>> paths (3 , 16) # E. g ., double ( double ( inc (3)))11>>> paths (1 , 8) # E .g. , double ( inc ( inc ( double (1))))10>>> paths (3 , 3) # No calls is a valid path1"""if x > y:return 0elif x == y:return 1else :return paths ( inc (x), y) + paths ( double (x), y)(b) (2 pt) Write one of <=, >=, or != in each blank below such that the following statements are true for allpositive integers x, y, and z. If it is not possible to do so, write X in the blank.paths(min(x, y), z) >= paths(max(x, y), z)paths(x, z) >= paths(x, y) * paths(y, z)Login: 7(c) (4 pt) Fill in the blanks in the implementation of pathfinder, a higher-order function that takes anincreasing function f and a positive integer y. It returns a function that takes a positive integer x andreturns whether it is possible to reach y by applying f to x zero or more times. For example, 8 can bereached from 2 by applying double twice. A function f is increasing if f (x)> x for all positive integers x.def pa th fi nd er (f , y ):""" Return a functi on fi nd_from that takes x and returns whether repeatedlyapply ing the increasi ng func tion f to x can reach y.>>> f = pat hfinder ( double , 8)>>> { k : f ( k) for k in (1 , 2 , 3, 4, 5)}{1: True , 2: True , 3: False , 4: True , 5: False }>>> g = pat hfinder ( inc , 3)>>> { k : g ( k) for k in (1 , 2 , 3, 4, 5)}{1: True , 2: True ,