DOC PREVIEW
U of I CS 421 - Midterm

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1CS421 Fall 2005 MidtermThursday, October 13, 2005• You have 75 minutes to complete this exam.• This is a closed-book exam.. You are allowed one 3inch by 5 inch card of notesprepared by yourself. This card is not to be shared. All other materials, besidespens, pencils and erasers, are to be away.• Do not share anything with other students. Do not talk to other students. Do notlook at another student’s exam. Do not expose your exam to easy viewing byother students. Violation of any of these rules will count as cheating.• If you believe there is an error, or an ambiguous question, you may seekclarification from myself or one of the TAs. You must use a whisper, or writeyour question out. Speaking out aloud is not allowed.• Including this cover sheet and rules at the end, there are 13 pages to the exam.Please verify that you have all 13 pages.• Please write your name and NetID in the spaces above, and also at the top ofevery page.Name:NetID:ProblemsPossible PointsPoints Earned12345678910691015141710109122CS 421 Midterm Name:____________________________________1. (6 pts total) Suppose that the following code is input into OCaml:let x = “Hello, ”;;let polite y = x^y;;let x = “Hi, ”;;let z = polite “Mr. Jones”;;let x = 3.2For each of the following circle the correct choice.a. (2 pts) z will have a value of1) “Hi, Mr. Jones” 2) “Hello, Mr. Jones”b. (2 pts) The declaration let x = 3.2; will cause a type error.1) true 2) falsec. (2 pts) x will have an end value of1) “Hi” 2) 3.22. (9 pts total)a. (3 pts) Write an OCaml function f:int -> int -> int that adds the square ofits first argument to 2 times its second argument. Pay attention to the typegiven.3CS 421 Midterm Name:____________________________________2. (cont.) What is the result of each of the following applications:b. (2 pts) f 7;;c. (2 pts) f 5 3;;d. (2 pts) f (4,2);;4CS 421 Midterm Name:____________________________________3. (10 pts total) Given the following OCAML datatype:type int_seq = Null | Snoc of (int_seq * int)a, (5 pts) Write a recursive function fold : (int -> ‘a -> ‘a) -> ‘a -> int_seq -> ‘athat folds a function over an int_seq, with a given value for the base case.b. (5 pts) Using the function fold, and no other recursion, write a functionprod: int_seq -> int that returns the product of all the elements in a list. Theproduct of Null is 1. You should haveprod (Snoc (Snoc (Snoc (Null, 2), 3) , 5)) = 305CS 421 Midterm Name:____________________________________4. (15 pts total) Below I have given you an outline for the type derivation of thefollowing expression:let rec f = fun x -> x in f 7Please complete the derivation by giving the results that go in the lettered blanks.Put your answers next to the corresponding letters below the type derivationoutline____________________ ___________________ _______________________ (#5)__ |- (#6)__: (#7)__ (#8)__ |- (#9)__: (#10)__ (#11)__ |- (#12)__: (#13)______________________ _____________________________________________(#1)__ |- (fun x -> x):(#2)__ (#3)___ |- (f 7):(#4)________________________________________________________________________{ } |- (let rec f = fun x -> x in f 7) :int(#1) ________________________________________________________________(#2) ________________________________________________________________(#3) ________________________________________________________________(#4) ________________________________________________________________(#5) ________________________________________________________________(#6) ________________________________________________________________(#7) ________________________________________________________________(#8) ________________________________________________________________(#9) ________________________________________________________________(#10) ________________________________________________________________(#11) ________________________________________________________________(#12) ________________________________________________________________(#13) ________________________________________________________________6CS 421 Midterm Name:____________________________________5. !(14 pts total) G!i!v!e! !a! (most general) !u!n!i!f!i!e!r! !f!o!r! !t!h!e! !f!o!l!l!o!w!i!n!g! !u!n!i!f!i!c!a!t!i!o!n! !problem.!!Capital !l!e!t!t!e!r!s! !(A,B,C,D) d!e!n!o!t!e! !v!a!r!i!a!b!l!e!s! !o!f! !u!n!i!f!i!c!a!t!i!o!n!.! !The lower-case letters(f, l, n, p) are constants or term construcutors. (f and p have arity 2, s has arity 1,and n has arity 0 (is a constant).) S!h!o!w! !y!o!u!r! !w!o!r!k! !b!y! !l!i!s!t!i!n!g! !t!h!e! !o!p!e!r!a!t!i!o!n!!p!e!r!f!o!r!m!e!d! !i!n! !e!a!c!h! !s!t!e!p! !o!f! !t!h!e! !u!n!i!f!i!c!a!t!i!o!n! !a!n!d! !t!h!e! !r!e!s!u!l!t! !o!f! !t!h!a!t! !s!t!e!p!.! !!!{( f (A,B) = f (A, p(A,A))); (f (s(A), s( p(A,A))) = f(C,D)) ; (s(C) = s(s(n)))}7CS 421 Midterm Name:____________________________________6. (17 points) Given the following lambda expression:(λ x. λ y. x y x) (λ u. λ v. λ w. v u w) ((λ s. s) (λ t. t))a. (5 pts) Evaluate this term as fully as possible using only Eager Evaluation:b. (5 pts) Evaluate this term as fully as possible using only Lazy Evaluation:8CS 421 Midterm Name:____________________________________(7 cont)c. (6 pts) Reduce this term to αβ-normal form: (You may omit explicit mentionor use of congruence closure)9CS 421 Midterm Name:______________________________7. (10 pts total)a. (4 pts) In the style of Church numerals, write the lambda term that representsthe constructor for pairs (comma). Your answer, if applied to a and b shouldreturn the representation of the the pair (a,b).b. (6 pts) Write the lambda term the represents the function which takes a pair(a,b) and returns the pair (b,a),8. (10 pts total)a. (5 pts) Write a regular expression over the alphabet {a,b,c} generating exactlythe set of all strings over {a,b,c} such that all the a’s (if there are any) occurbefore any of the c’s (if there are any).b. (5 pts) Write a regular expression over the alphabet {0,1} generating exactlythe set of all binary strings with an occurrence of 111 and a later occurrence of000.10CS 421 Midterm


View Full Document

U of I CS 421 - Midterm

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Midterm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?