CIS352 Spring 2020 — Final Exam (Part 1)
SU ID: _____________________ Name: ________________________ Links to all parts: Part 1 Part 2 Part 3
Fill out your SU ID and email this part to Jack Vining (jcvining@syr.edu) when you finish
Instructions:
1. This exam has three parts, each consisting of 4 problems.
2. This exam is “open everything except collaboration”
a. You may refer to your old notes
b. You may use DrRacket
c. You may google for anything on demand
d. You may not collaborate with your friends
e. You may not post questions to StackOverflow / freelancr / etc…
3. Please ask us clarification questions, but please do not ask us help questions (e.g., asking help on how to debug your code).
4. Unless specified otherwise, you may use any standard built-in Racket function / form / etc…
5. Each problem is worth 10 points
6. The entire exam is worth 120 points
7. The exam will be graded out of 100 points (no extra credit)
8. Work each part in its corresponding document.
9. Use Google Docs’ “copy” feature to make yourself a copy of the
exam.
10. Fill out your SU ID and name at the top of each part
11. Then email to
a. Part 1 — Jack Vining (jcvining@syr.edu) b. Part 2 — Yihao Sun (ysun67@syr.edu)
c. Part 3 — Kris Micinski (kkmicins@syr.edu)
[10 points] Problem 1 (Beta Reduction)
Consider the following term in the calculus
● [3] For the above term, how many different -reductions are possible? This question is asking you how many distinct beta reductions are achievable in one step from the original term, not asking you to perform more than one step of beta.
● [5] Perform each possible reduction and show the result
(Either upload a picture here or just write out as text)
● [2] What is the -normal form obtained by fully-reducing this term?
[10 points] Problem 2 (Basic Recursive Design Principles)
● [5] Using tail-recursion, write a function, (double l), which multiplies every element of
the list l by 2. Correct answers using direct-style recursion will receive 3⁄5 points. (double ‘()) ;; ‘()
(double ‘(1 2 3)) ;; ‘(2 4 6)
Hint: You may want to define a tail-recursive “helper function” called by double
● [5] Write a function, (argmin l f), which returns the element in l which minimizes the function f (assumed to take and return numbers). You may use either direct or tail recursion.
(argmin ‘(-2 0 2) (lambda (x) (+ 1 (* x x)))) ;; returns 0
[10 points] Problem 3 (S-expression-based data and higher-order functions)
Consider that we represent binary trees as follows:
(define (number-tree? l)
(match l
[’empty #t]
[(? number? n) #t]
[`(,(? number? root) ,(? number-tree? e0) ,(? number-tree? e1)) #t]))
;; Examples
(number-tree? ’empty)
(number-tree? ‘(2 empty 3))
(number-tree? ‘(10 (5 empty empty) (15 empty empty)))
● [6 points] Write a function (map-tree t f) that takes a tree t along with a function f, and returns the same tree as t but where every number n in tree t has been replaced with (f n)
○ (map-tree '(10 (5 empty empty) (15 empty empty)) (lambda (x) (- x)))
;; should return ‘(-10 (-5 empty empty) (-15 empty empty)
(define (map-tree t f)
0)
● [4 points] Write a function f for which the output of (map-tree t f) over some arbitrary tree t does not necessarily satisfy the number-tree? predicate:
(define (f x) 0)
[10 points] Problem 4 — Pattern Matching
Write a Racket match pattern that will match the following
For example:
● A list of length at least one that begins with the symbol x
○ `(x ,others …)
● [1] The symbol foo
● [3] A list that begins with the symbols x and y (followed by any other elements)
● [3] A list of odd length
● [3] A list whose elements sum to 300
Hints:
● Read the match documentation, try examples in DrRacket
● ((listof f) l) returns true if f is true of every element of the list l
● `(,x …) matches a list and binds it to x
● `(,(? number? x) ,(? number? y)) matches a list consisting of two numbers x and y