CS 61A Final Exam — May 15, 2009Your namelogin: cs61a–This exam is worth 70 poi nts, or about 23% of your total course grade. The exam contains15 questions.This booklet contains 14 numbered pages including the cover page. Put all answers onthese pages, please; don’t hand in stray pieces of paper. This is an open book exam.When writing proc edures, don’t put in error checks. Assume that you will begiven arguments of the correct type.If you want to use procedures defined in the book or reader as part of yoursolution to a programming problem, you must cite the page number on whichit is defined so we know w hat you think it does.*** IMPORTANT ***Check here if you are one of the people with whom we ar-ranged to replace a missed/missing exam with other examscores:*** IMPORTANT ***If you have made grading complai nts that have not yetbeen resolved , put the assignment name(s) here:READ AND SIGN THIS:I certify that my answers to this exam are all my ownwork, and that I have not discussed the exam questions oranswers with anyone prior to taking this exam.If I am taking t his exam early, I certify that I shall notdiscuss the exam questions or answers with anyone untilafter the scheduled exam time.1–2/93–4/65/46/47/78/69/610–11/412/613/614/615/6total/701Question 1 (4 points):(define (if-false x y)(if x ’true y))For each of the following expressions, sta te t he result in applicative order and in normalorder. If the expression results in an error, just say ERROR; you don’t have t o give theexact message.(if-false (/ 33 0) (/ 33 1))Applicative:Normal:(if-false (/ 33 1) (/ 33 0))Applicative:Normal:Question 2 (5 points):Define a function maxnum that takes a list as argument. The elements of the list might o rmight not include numbers, along with o ther values. If a ny elements are numbers, returnthe largest number. If not, return #f. If an element is a list, don’t look inside it; consideronly top-level elements.> (maxnum ’(20 minutes and 45 seconds after 10 (2009 5 15)))45Use higher-order functions, not recursion!Note: You get 4 points i f your function works only for positive numbers.2Your name login cs61a–Question 3 (4 points):Here are two procedures that use two different algorithms to solve the same problem: Giventwo lists of l ength n as arguments, return true if they have any elements in common, false ifnot. For each procedure, indicate the order of growth in time, and whether the proceduregenerates an iterative or a recursive process.(define (common? ls1 ls2)(cond ((null? ls1) #f)((null? ls2) #f)((equal? (car ls1) (car ls2)) #t)(else (or (common? ls1 (cdr ls2))(common? (cdr ls1) ls2)))))Θ(1) Θ(n) Θ(n2) Θ(2n)Iterative Recursive(define (common? ls1 ls2)(cond ((null? ls1) #f)((member (car ls1) ls2) #t)(else (common? (cdr ls1) ls2))))Θ(1) Θ(n) Θ(n2) Θ(2n)Iterative RecursiveQuestion 4 (2 points):(define my-stream(cons-stream 3 (cons-stream 4 (add-streams my-stream(stream-cdr my-stream)))))> (show-stream my-stream 5)3Question 5 (4 points):Write a procedure sumpath that takes a Tree (with datum and children) of numbers asits arg ument, and returns a tree of the same shape in which each datum is the sum of allthe data between the original datum and the root. For example, in the case below thevalue 5 in the original tree becomes 8 (1 + 2 + 5) in the returned tree:1 1/|\ /|\2 3 4 ---> 3 4 5/ \ \ / \ \3 5 8 6 8 134Your name login cs61a–Question 6 (4 points):(a) Fill in the blanks in the interactions below:(define (swap ls1 ls2)(let ((temp ls1))(set! ls1 ls2)(set! ls2 temp) ) )STk> (define foo (list 1 2 3))fooSTk> (define bar (list ’a ’b ’c))barSTk> (swap foo bar)okaySTk> fooSTk> bar(b) Fill in the blank below:STk> (define x 1)STk> (define y x)STk> (set! x 2)STk> y5Question 7 (7 points):We want t o use OOP la nguage (with define-class) to simulate a “smartphone” thatcombines a cell phone with a phoneboo k, cal endar, etc. Assume that you are given acellphone class, representing a bare-bones cell phone, that accepts a dial message witha phone number as argument.> (define dumb-phone (instantiate cellphone))> (ask dumb-phone ’dial ’555-2368); ... phone dials(a) Define a contact class that is instant iated with a person’s name, address, and phonenumber, and accepts messages name, address, and phone that return the correspondingvalues:> (define bh (instantiate contact ’Brian ’(781 Soda) ’642-8311))> (ask bh ’phone)642-8311This question continues on the next page.6Your name login cs61a–Question 7 continued:(b) Define a smartphone class that takes no instantiation arguments. The message add-contact takes three arguments for name, address, and phone number; it creates a contactobject and adds it to its l ist of contacts. The message call takes a name as argument ,finds the name in the list of contacts, and dials the corresponding phone number.> (define my-phone (instantiate smartphone))> (ask my-phone ’add-contact ’Dan ’(777 Soda) ’642-9595)> (ask my-phone ’add-contact ’Brian ’(781 Soda) ’642-8311)> (ask my-phone ’add-contact ’Mike ’(779 Soda) ’642-7017)> (ask my-phone ’call ’Brian); ... phone dials 642-8311 (using dial method) ...> (ask my-phone ’call ’Alonzo)"Name not found"7Question 8 (6 points):What will the Scheme interpreter print in response to each of the following expressions?Also, draw a “box and pointer” diagramfor the result of each printe d expres-sion. If any expression results in an error, just write “ERROR”; you don’t have to givethe precise message.Hint: It’ll be a lot easier if you draw the box and point er diagram first!(let ((x (list ’a ’b ’c)))(set-cdr! (cdr x) 3)x)(let ((x (list ’a ’b ’c)))(set-car! x (caddr x))(set-car! (cddr x) (car x))x)(let ((x (list ’a ’b ’c)))(set! (car x) (caddr x))x)8Your name login cs61a–Question 9 (6 points):(define x 100)(define y 10)(define s (make-serializer))(define t (make-serializer))(parallel-execute (s (lambda () (set! x (+ x y))))(t (lambda () (set! y (* x y)))))(list x y)What are the possible correct answers for (list x y)?What are the additional possible incorrect answers, if any?Is deadlock possible? Yes No(define x 100)(define y 10)(define s (make-serializer))(define t (make-serializer))(parallel-execute (s (t (lambda () (set! x (+ x y)))))(s (t (lambda () (set! x (* x y)))))) ; x this time!(list x y)What are the possible correct answers for (list x y)?What are the additional possible incorrect answers, if any?Is deadlock
View Full Document
Unlocking...