A Question of Identity (1 point)Mind Your Language (12 points)Jom Magrotker and the Order of the Growth (6 points)Under Lock and Key-Value (2 points)MapReduce: Not a Cartographer's Weight Loss Program (6 pts)In Space, No One Can Hear You Stream (10 points)Eeny, Meeny, Miny, Moe (6 points)The Bro and Sis Code (5 points)C-x C-s the Environment (9 points)Iter Vegetables (5 points)Don't Repeat Yourself (6 points)I Can Haz Cycle? (6 points)See OOP Run (6 points)FINAL EXAMINATIONCOMPUTER SCIENCE 61AAugust 9, 2012Instructions: Read Me!• You will be given 180 minutes to work on this exam. Do not start unless told to do so by the teaching staff.• This exam is closed book. Electronic devices (except dedicated timekeepers) must be turned off. You can useone double-sided 8.5” × 11” sheet of notes.• Please write neatly and legibly, because if we can’t read it, we can’t grade it. If you are not sure of your answer,you may wish to provide a brief explanation.• Finally, please take a deep breath and calm down before starting the exam. This exam is not worth having aheart attack for. We hope you do a CS61Awesome job!• Thank you for being an awesome part of this class!0 A Question of Identity (1 point)Fill in the table below. Once you are told to start, write your login at the top of each page.NameLogin cs61a-All of the work on this examis my own. (Please sign.)Question 0 1 2 3 4 5 6Score/1 /12 /6 /2 /6 /10 /67 8 9 10 11 12 Total/5 /9 /5 /6 /6 /6 /801CS61A Summer 2012 Page 2 Login: cs61a-1 Mind Your Language (12 points)Face the Cons-equencesWhat would the STk Scheme interpreter print in response to the following lines of Scheme code?(a) STk> (cons (cons 1 2) (cons 3 (cons 4 5)))Solution: ((1 . 2) 3 4 . 5)(b) STk> (cdr (cons (list 1 2 3) (list 4 5 6)))Solution: (4 5 6)(c) STk> (cdr (cdr (list 3 4 (list (cdr (list 6 7 8)) 9))))Solution: (((7 8) 9))Scheming a Calculated ApproachWe would like to make a few changes to the interpreters for three languages: Calc, Py, and Scheme.Indicate whether the change should be made to the PARSER or the EVALUATOR of the interpreter.You may only choose one of the two.(d) To make Py a lazy language, or a language that would only find the value of expressions whenthese values are needed, we would change:PARSER EVALUATOR(e) To allow Calc to understand infix operations, such as 5 + 2, where the operator is betweenthe operands that it operates on, we would change:PARSER EVALUATOR(f) To change the syntax of Scheme for our interpreter so that <> are used for Scheme lists andexpressions instead of (), and a | is used instead of a . in pairs, we would change:PARSER EVALUATORCS61A Summer 2012 Page 3 Login: cs61a-2 Jom Magrotker and the Order of the Growth (6 points)(a) def collide(n):lst = []for i in range(n):lst.append(i)if n <= 1:return 1if n <= 50:return collide(n - 1) + collide(n - 2)elif n > 50:return collide(50) + collide(49)What is the order of growth in n of the runtime of collide, where n is its input?Θ(1) Θ(log n)Θ(n) Θ(n log n) Θ(n2) Θ(2n) Θ(n·2n) Θ(n2·2n)(b) def crash(n):if n < 1:return nreturn crash(n - 1)*ndef into_me(n):lst = []for i in range(n):lst.append(i)sum = 0for elem in lst:sum = sum + crash(n) + crash(n)return sumWhat is the order of growth in n of the runtime of into_me, where n is its input?Θ(1) Θ(log n) Θ(n) Θ(n log n) Θ(n2) Θ(2n) Θ(n·2n) Θ(n2·2n)(c) def carpe_diem(n):if n <= 1:return nreturn carpe_diem(n - 1) + carpe_diem(n - 2)CS61A Summer 2012 Page 4 Login: cs61a-def yolo(n):if n <= 1:return 5sum = 0for i in range(n):sum += carpe_diem(n)return sum + yolo(n - 1)What is the order of growth in n of the runtime of yolo, where n is its input?Θ(1) Θ(log n) Θ(n) Θ(n log n) Θ(n2) Θ(2n) Θ(n·2n) Θ(n2· 2n)3 Under Lock and Key-Value (2 points)Suppose the following two statements are executed concurrently, in two separate threads, when xhas a value of 5:x = x % 3 x = x + 20The % operator returns the remainder when the first number is divided by the second.(a) What are all of the possible values of x after the two statements are executed?Solution: 22, 1, 2, 25We now create a lock called x_lock and we modify the two threads from before:x_lock.acquire()x = x % 3x_lock.release()x_lock.acquire()x = x + 20x_lock.release()As in the previous question, x has a value of 5.(b) What are now all of the possible values of x after the two threads have executed?Solution: 22, 1CS61A Summer 2012 Page 5 Login: cs61a-4 MapReduce: Not a Cartographer’s Weight Loss Program (6 pts)(a) Given a list of strings wordlist, fill in the blanks in the code below so that it returns a listof two elements, where the first element represents the number of strings with length greaterthan 3, and the second element is the number of strings of length 3 or less. For the list below,for example, the expected answer from the interpreter is [2, 4].>>> wordlist = ["it", "was", "the", "best", "of", "times"]>>> reduce(lambda x, y: [x[0] + 1, x[1]] if y > 3 \else [x[0], x[1] + 1],map(len, wordlist),[0, 0])(b) Tom and Jon want to figure out who won the contest for project 4. They have a file, and eachline of this file is a number that represents the entry that one student in the class votes for. Sincethe file is large, they want to use the MapReduce framework to determine how many votes eachentry has received. They need a mapper and a reducer.What should be the key and the value of each of the key-value pairs produced by the mapper,for each line in the file?Solution: The key should be the entry number and the value should be 1.What should the reducer do with each key and the values associated with that key?Solution: The reducer should sum up all of the values (the 1s) associated with each key.5 In Space, No One Can Hear You Stream (10 points)(a) What are the first five values in the stream returned by the function given below?def my_stream():def compute_rest():return add_streams(stream_filter(lambda x: x%2 == 0,my_stream()),stream_map(lambda x: x+2, my_stream()))return Stream(2, compute_rest)Solution: 2, 6, 14, 30, 62CS61A Summer 2012 Page 6 Login: cs61a-(b) Write a function make_repeated_fn_stream that, given a function f (of one argument),returns a stream such that the element at the ith location (counting from zero) is a function thatwould apply f i times to its argument. In other words, the stream would contain the elementslambda x: x,lambda x: f(x),lambda x: f(f(x)),lambda x: f(f(f(x))), ...Note that these elements are functions, not strings.The doctests