ࡱ> pro#` U)bjbj5G5G 7bW-W-!&44484t^5l,D5(5" 6 6 6777CCCCCCC$ FhHPC77"777C 6 6_C???7V 6 6C?7C??AA,iA 65 =Ci*4:zYACC0,DaAH=ZHiAiAbHB77?77777CC[>777,D7777 $$ $ cs150: Final Exam Name: _____________________________________________ Due: Monday, 7 May at 4:55pm Turn in your completed exam to David Evans or to Brenda Perkins in the CS front office. Directions Please be honorable. As long as everyone follows the honor code, take home exams benefit everyone. You are on your honor to follow the letter and spirit of these directions. You do not need to scribble a pledge on your exam to convince us you are honorable, but if you cheat please let us know so it does not unfairly impact other students. Please dont cheat. Work alone. You may not discuss these problems or anything related to the material covered by this exam with anyone except for the course staff between receiving this exam and class Monday. Open resources. You may use any books you want, lecture notes, slides, your notes, and problem sets. You may also use DrScheme or Python, but it is not necessary to do this. You may also use external non-human sources including books and web sites. If you use anything other than the course books, slides, and notes, cite what you used. You may not obtain any help from other humans other than the course staff. Answer well. Answer all questions 1-10. (Please also answer your name correctly, but there are no points for this on the final.) You may either: (1) write your answers on this exam or (2) type and write your answers into the Word document template ( HYPERLINK "http://www.cs.virginia.edu/cs150/exams/final/final.doc" http://www.cs.virginia.edu/cs150/exams/final/final.doc). Whichever you choose, you must turn in your answers printed on paper and they must be clear enough for us to read and understand. You should not need more space than is provided to write good answers, but if you want more space you may attach clearly-marked extra sheets. The questions are not necessarily in order of increasing difficulty, so if you get stuck on one question you should continue on to the next question. There is no time limit on this exam, but it should not take a well-prepared student more than a few hours complete. Full credit depends on the clarity and elegance of your answer, not just correctness. Your answers should be as short and simple as possible, but not simpler. Your programs will be judged for correctness, clarity and elegance, but you will not lose points for trivial errors (such as missing a closing parenthesis). Score: ______ Procedures Questions 1 and 2 ask you to define procedures that solve specified problems. For each question, you may use any programming language that has been mentioned in CS150 (Scheme, Python, Charme, LazyCharme, StaticCharme, Fortran, FP, FL, Java, C, C++, PHP, LISP, or JavaScript). If you use a language other than Scheme or Python, you should clearly state in your answer which language you are using. 1. Define a procedure, xorlist, that takes as input a list, and outputs the result of XOR-ing all elements in the list. The result should be true if the list contains an odd number of true values, and false if the list contains an even number of true values. You may assume a procedure, xor, is defined that takes two inputs and outputs the exclusive or of those inputs. For example, Python: >>> xorlist([True]) True >>> xorlist([]) False >>> xorlist([True, False, True, False, True]) True Scheme: > (xorlist (list #t)) #t > (xorlist null) #f > (xorlist (list #t #f #t #f #t)) #t 2. Define a procedure, findlast, that takes two inputs, a list and a predicate procedure, and outputs the last element in the list for which the predicate procedure applied to that element evaluates to true. If no element in the list satisfies the predicate procedure, findlast should produce null (in Scheme) or None (in Python). For full credit, your procedures running time should be in O(n) where n is the number of elements in the input list. For example, Python: >>> def iseven(n): return n%2 == 0 >>> findlast([1,2,3], iseven) 2 >>> findlast([1,2,3,4], iseven) 4 >>> findlast([1,3], iseven) evaluates to None (which doesnt print out in Python) Scheme: > (findlast (list 1 2 3) even?) 2 > (findlast (list 1 2 3 4) even?) 4 > (findlast (list 1 3) even?) () Running Time Analysis 3. What is the asymptotic running time of the findmiddle procedure defined below? Your answer should define all variables it contains and clearly state all assumptions you use. (define (find-middle lst) (define (find-middle-helper lst n) (if (= n 0) (car lst) (find-middle-helper (cdr lst) (- n 1)))) (find-middle-helper lst (floor (/ (length lst) 2)))) 4. What is the asymptotic running time of the intersect procedure defined below? Your answer should define all variables it contains and clearly state all assumptions you use. (define (contains? lst val) (if (null? lst) #f (if (eq? (car lst) val) #t (contains? (cdr lst) val)))) (define (intersect lst1 lst2) (if (null? lst1) null (if (contains? lst2 (car lst1)) (cons (car lst1) (intersect (cdr lst1) lst2)) (intersect (cdr lst1) lst2)))) Object-Oriented Programming 5. (Exercise 10.3 from the Course Book) Define a new subclass of poscounter where the increment for each next! method application is a parameter to the constructor procedure. For example, (make-var-counter 0.1) would produce a counter object whose counter has value 0.1 after one invocation of the next! method. (You should assume all definitions from Chapter 10.) Computability/Turing Machines 6. Is the Writes-Hash Problem described below computable or uncomputable? Your answer should include a convincing argument why it is correct. Input: A specification of a Turing Machine, T, including its tape, using the Turing Machine description grammar from Lecture 37. Output: Outputs true if running T would ever write a # symbol on the tape; otherwise, outputs false. Lambda Calculus 7. Define a Lambda Calculus term, sub, that corresponds to subtraction. You may assume all the definitions from Lecture 40. Your sub definition should satisfy the following properties: sub 1 zero ( 1 sub 1 1 ( zero sub 2 1 ( 1 sub 2 zero ( 2 sub 5 2 ( 3 Interpreters The next two questions as you to modify the StaticCharme interpreter to support the begin special form. You do not need to modify the interpreter, but if you want to try out your solution you can download the StaticCharme interpreter from  HYPERLINK "http://www.cs.virginia.edu/cs150/final/staticcharme.zip" http://www.cs.virginia.edu/cs150/final/staticcharme.zip. (This has been updated from the version provided in the Exam 2 comments to include the changes to meval and typecheck necessary to support begin expressions, with stub procedures for your answers to question 8 and 9.) 8. Define the evalBegin procedure to implement the evaluation rule for begin. The StaticCharme begin expression should have the same evaluation rule as the Scheme begin expression. 9. Define the typeBegin procedure to implement the type checking rule for begin. The type of a begin expression is an error type if the expression has no subexpressions, or if any of the subexpressions are mistyped. Otherwise, the type is the type of the last subexpression. For example, StaticCharme> (begin (+ 3 #t) 4) Error: Parameter type mismatch: expected (Number Number), given (Number Boolean) StaticCharme> (begin ) Error: No expressions in begin StaticCharme> (begin (+ 3 3) #t #f (* (+ 7 8) 10)) 150 10. a) Explain why it does not make any sense to actually add begin to StaticCharme, unless additional special forms or primitives are also added. b) Explain why LazyCharme does not need a begin special form (even if additional primitives and special forms were added to LazyCharme). These questions are optional and worth no credit, but we appreciate your answers. Do you feel your performance on this exam will fairly reflect your understanding of the course material so far? If not, explain why. In determining your final grade for the course, is there anything you think I should take into account that would not be readily apparent from your recorded performance on the problem sets, quizzes, and exams? Please remember to submit your Official Course Evaluation and return your completed Course Improvement Survey when you turn in this exam. Enjoy your summer and thanks for your contributions to the course!     PAGE  PAGE 12 End of Exam GHef6 7 wkw[NB3h^h^B*\aJphh^B*\aJphh^5B*\aJphh^h; 5B*CJ\phhf8B*OJQJphhf8hf8B*OJQJphhf85B*OJQJph hf8hf85B*OJQJphh; h; B*OJQJphh; B*OJQJph#h; h; 5B*OJQJ\phh; 5B*OJQJ\phhf85B*OJQJ\phhE5B*OJQJ\phHf6 7  *ghv dd@&[$\$gd; $a$gdf8 d[$\$gd; dd[$\$gd'b dd[$\$gd; gd; $d@&[$\$a$gd; dd[$\$^gdf8dd[$\$`gdl~D$a$gd; );)T)7 B  t ~  t   *⧛yk]k]SSSh^B*aJphhS"h; 0J6]aJhS"hf80J6]aJhS"h0J6aJ+jhS"h*6B*UaJphhS"6B*aJphjhS"6B*UaJphhS"B*aJphh'bh'bB*aJphh5 B*aJphhEB*aJphh; h; B*aJphh; h; 5B*\aJph fghmuv)036кЧкsgQgE/E+h]h]5B*OJQJ\^JaJphh]B*\aJph+h]hqZ5B*OJQJ\^JaJphhqZB*\aJphhIh5B*\aJphhAmhf8B*\aJphhf8B*\aJphhO QB*\aJph%h; h; B*CJOJQJaJph+h; h; 5B*CJOJQJ\aJph%hf85B*CJOJQJ\aJphh; h; B*OJQJphh; h; B*aJph  #47Y\gdaMgd;  \]^_`abcwnvҼҬzj]S>4>4hIhB*aJph(hIhhIh5B*OJQJ^JaJphhf8B*aJphh; h; B*aJphh; h; 5B*\aJphhIh5B*\aJphhqZ5B*\aJphhr.B*\aJphh]B*\aJphh5 h]5CJOJQJ^J+h]hIh5B*OJQJ\^JaJph+h]hqZ5B*OJQJ\^JaJphhIhB*\aJphhqZB*\aJph\]^`#$12:]{}?`gd"gd]gdaM<E%&#$$d%d&d'd+D-D/M NOPQgd]"#$19:ABc׾᪝viTiDh5 h"5CJOJQJ^J(h"h]5B*OJQJ^JaJphh"h]B*aJph"h]5B*OJQJ^JaJph(h]h]5B*OJQJ^JaJphh]h]B*aJphh]B*aJphhf8B*aJphhaMB*aJphh"h"6B*aJphh"B*aJphhIhB*aJph(hIhhIh5B*OJQJ^JaJph?AB`cdz,-Gl|snniiiigdigdk dd@&[$\$gdO Q=.&#$$d%d&d'd+D-D/0$M NOPQgdM<&#$$d%d&d'd+D-D/M NOPQgd"gd] cdyz},-'0ƻwi_UAU'hO QhO Q5B*OJQJ\^JphhO QB*\phh"B*\phh"h"5B*\phhi5B*\ph'hihi5B*OJQJ\^JphhiB*\ph!hi5B*OJQJ\^JphhkB*\phhk5B*\ph+hO QhO Q5B*CJOJQJ\aJph%hO Q5B*CJOJQJ\aJphhj#h]5CJOJQJ^J 4Jh &=Q&#$$d%d&d'd+D-D/0$M NOPQgdigdO Qgd'bgdi  %&'()*Pist2Ƴtia]OE]OE]OE]h KOJQJ^Jh Kh K5OJQJ^Jh Kh KB*phh; hEB*phh; hE5B*\phhi5B*\ph%h; 5B*CJOJQJ\aJph%hi5B*CJOJQJ\aJph%hO Q5B*CJOJQJ\aJphhj#hi5CJOJQJ^J%hi5B*CJOJQJ\^Jph+hO QhO Q5B*CJOJQJ\^Jph&'IJ4 p`^p``gd5 p`^p``gdagd'bgdi=L&#$$d%d&d'd+D#-D/0$M NOPQgd KgdEgd KgdO Q 256RWXIJݽwdw\TPKFPBha hE6 h5 6hEhihE5hihi5%h5 5B*CJOJQJ\aJph%hi5B*CJOJQJ\aJphhj#B*phh Khj#5CJOJQJ^Jhah KB*phhaB*phh5 B*phh KCJaJh KOJQJ^Jh Kh K5OJQJ^Jh Kh KOJQJ^JaJ#hMh K5CJOJQJ^JaJJRwx3456FGKjm       {ssg\g\g\U\ jh Kh Kh KmHsHh Kh K5mHsHh Kh K5 h K5h K%h K5B*CJOJQJ\aJphhj#hj#hj#5CJOJQJ^Jhj#B*ph hMh5 5B*OJQJphh5 h5 6B*phhaB*phh5 haB*phh5 6B*phh5 B*phha5B*ph45FG   " . = I J K L `gd Kgd KgdEE  &#$$d%d&d'd+D#-D/0$M NOPQ^` gd=\           " % & ' ( ) * + , . 1 2 3 4 8 9 : ; < @ A B C D E F G H I J K L M N Z [ \ L!߽hihi5OJQJ^Jhi#h; B*CJOJQJ^JaJph!h KhEB*CJOJQJph!h Khj#B*CJOJQJphh Kh K5CJ jh Kh Kh KmHsHh Kh K5mHsHh K5mHsH1L M [ \ ""`#a#gd'bgdd 2( Px 4 #\'*.25@9gd; gd KE  &#$$d%d&d'd+D-D/0$M NOPQ^` gd KL!M!!!!!!!!!""1"6";"D""""""""""""""_#`#a#b#f#g#s#|###ūwwɅg_hbhb5hj#h5 5CJOJQJ^Jh`h`5OJQJ^JhEh'bh; 5 h5 5)h; h'bB*CJOJQJ^JaJphhdh5 hbhb5OJQJ^JhbhMh`hihMh`0J6jhMh`6UhMh`6jhMh`6U%a#b#c#d#y$z$$$$$%0%c%g%h%i%j%gdbgd'bE  &#$$d%d&d'd+D-D/0$M NOPQ^` gd5 ###$f%g%h%i%j%k%n%o%s%%%%%&&&&,&1&&&&&&&&&&&i'j'k'<(>(@(A(B(D(ĿĿħ{lhl~Dh@OJQJ^JaJhWhl~Dh KOJQJ^JaJ h; h K h K5\hl~D h; h; h K hbhb hb5hbhb5 h5 5hj#h5 5CJOJQJ^Jh`h5 5OJQJ^Jhb5OJQJ^Jhbhb5OJQJ^Jhb)j%k%%&&&&&nE %  &#$$d%d&d'd+D-D/0$M NOPQ^` gd5 gd'bE  &#$$d%d&d'd+D "-D/0$M NOPQ^` gdM&&&&&i'j'k'>(?(@(A(B(q=- !&#$$d%d&d'd+D -D/0$M NOPQgd Kgd Kgdl~DE I! &#$$d%d&d'd+D&-D/0$M NOPQ^` gd5 B(C(D((((()))))))~~vtttttt$a$gd K==!&#$$d%d&d'd+D--D/0$M NOPQgd Kgd@=- !&#$$d%d&d'd+D -D/0$M NOPQgd@ D(c(k(l(t(y(}(((((((((((()))))))))!)")()))*)+),)-)3)4)6)7)Ǹ|v|vrn|v|c|hg0JmHnHuh~O%h'b h'b0Jjh'b0JUh*jh*Uh Kh:5h Kh K5#jh Kh K5UmHnHuh Khl~Dh KOJQJ^JaJhh@\hh K\hh K5\hh5\ hZT\ hZT5\hh\&) )!)*)+),)8)9):);)G)H)I)J)K)L)M)N)O)P)Q)R)S)T)U)$a$gd K$a$gdT &`#$gd~O%7)8)9):);)G)H)I)L)Q)R)S)T)U)h Kh:5hah!BhaMhAmh; h:hT5h*h~O%h'b h'b0J 5 01h:p'b/ =!"#$% DyK yK http://www.cs.virginia.edu/cs150/exams/final/final.docyX;H,]ą'cmDyK 8http://www.cs.virginia.edu/cs150/final/staticcharme.zipyK http://www.cs.virginia.edu/cs150/final/staticcharme.zipyX;H,]ą'c@@@ @NormalCJ_HaJmH sH tH N@2N ; Heading 3dd@&[$\$5CJ\aJDA@D Default Paragraph FontRiR  Table Normal4 l4a (k(No List4U@4 ; Hyperlink >*phe@ ; HTML Preformatted7 2( Px 4 #\'*.25@9CJOJQJ^JaJTOT ; schemeinteractionsCJOJQJ^JaJXO"X ; schemeresults0B*CJOJQJ^JaJph33B^@2B ; Normal (Web)dd[$\$.X@A. ; Emphasis6]Ng@QN ; HTML TypewriterCJOJPJQJ^JaJ4 @b4 'bFooter  !.)@q. 'b Page NumberHH l~D Balloon TextCJOJQJ^JaJ U!N      U!b*g v ] Bd 5M\bkA C D V!00*00000000*0@0@0@0@0@0@0@000@0@0@0@0@0@0@0@0@00Hf67*g h v     # 4 7 Y \ ] ^ ` #$12:]{}?AB`cdz,-Gl| 4Jh &'IJ45FG".=IJKLM[\`abcdyz0cghijkijk> ? @ A B C D !!!!!!! !!!*!+!,!8!9!:!;!G!H!I!J!K!L!M!N!O!P!Q!R!S!V!0000(00000000000(00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (00m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m0m@000@000@000@000@0@0@0@0@0@00000000000000000 *g h v     # 4 7 Y \ ] ^ ` #$1:]{}?AB`cdzGl|h 'IJ45FG".=IJKLM[\`abc0chijkijk> ? @ A B C D ;!O!P!V!00W00000000000000000 0X ұ00@00 0S0/0j00000000[ұ00Z00X000000[xӱ00Z00X00000000X Ա0000T00S00S0!0X"Ա@00"0U00Q00S00S@00(0U)pձ0(0T0(0R000000S00000T@0020X3ֱ020W020U@0010R@0010R2lֱ010Q010O0;0o0000000;0o0??0000000;0h0;0g0;0e000000000H0)0H0'000K0d0L0(0M0*0N0+0K0d0K0d0K0d0K0d0K0d000K0d0000000N0<0N0:00@0P@0P0Q0@0Q0>0Q0;P0O0d`0O0d`@0`00@0`0[01000\04@0`@0`00000000000000000000000000000000,00000D  %%%(7 c2J L!#D(7)U)!#$&(*.0\?&4L a#j%&B()U) "%')+,-/T) LU!XX !(!!8NO@N(  t N s *NԔ"` B S  ? U!N d2t) 0 l o 3 6  & - : A w  nvBHaisy (EM,/is  !"%&'(),-.12348;<=@ABCDGH16s|JK!!!!!!!!!! !!!:!;!V!] d w >Aaj>B_.4JPqs #&KQkmX^js!"-.<=H pq*1!!!!!!!!!! !!!:!;!V!333333333333333333333333333333333333333He"7   # Y \ 2:]?ABcdz &a6EGK.Lz!!!!!!!!!! !!!:!;!F!V!t Lc l !!!!!!!!!! !!!:!;!V!2es6CDu^`.^`.pp^p`.@ @ ^@ `.^`.^`.^`.^`.PP^P`.2es vPwddw@ho}TiC)a-S89w0 Hwdd6/N@ho} '"YwddY[@ho}Vv^wddC)a@ho}Ciwdd~JL|wdd@ho} 21Ami5 bbRE"S"C$~O%r.94ro6f8!Bl~D KO QTZTqZ'b/mi]jnmd*]k@fn0TEMag^; j#:WyPIh=\;`aM@|U!@UnknownGz Times New Roman5Symbol3& z Arial7&  Verdana?5 z Courier NewGNimbusMonL-ReguGNimbusSanL-Regu5& zaTahoma"1hT&U&P&%<%<!4d!!2QHX ?; 2 cs150: Exam 1 evans Oh+'0  8 D P \hpxcs150: Exam 1  Normal.dotevans3Microsoft Office Word@^в@)@A*@Fd*%՜.+,D՜.+,P  hp  Computer Science Department<! cs150: Exam 1 Title 8@ _PID_HLINKSAL j"8http://www.cs.virginia.edu/cs150/final/staticcharme.zip e7http://www.cs.virginia.edu/cs150/exams/final/final.doc   !"#$%&'()*+,-./013456789;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^`abcdefhijklmnqRoot Entry Fلi*sData 21Table:HWordDocument7bSummaryInformation(_DocumentSummaryInformation8gCompObjq  FMicrosoft Office Word Document MSWordDocWord.Document.89q