Functional Problem Solving (CSC 151 2014F) : Assignments
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
This is a sample examination. It includes problems like those that have appeared on previous in-class final examinations (and, as you'll note, on recent take-home examinations). It also includes the standard examination policies. These problems are not intended to give a comprehensive view of topics. For example, there is likely to be at least one problem on objects and at least one problem on trees. As the sample exam suggests, problems may involve code reading and code analysis in addition to code writing.
1. This is a closed book examination. You may not rely on notebooks, papers, textbooks, computers, colleagues, or anything similar. You may, however, refer to one 8.5 x 11 inch, double sided, hand-written, set of notes that you brought to this exam.
2. This is also a paper examination. Answer all problems in pen or pencil in an examination booklet. You may use pages in the back of the booklet or any blank space in this packet as scratch paper.
3. There are four problems on this exam. They are not necessarily of equal difficulty.
Four correct or mostly-correct solutions will earn you an A. Three correct or mostly-correct solutions will earn you a B. Two correct or mostly-correct solutions will earn you a C. One correct or mostly-correct solution will earn you a D. Zero correct or mostly-correct solutions will earn you an F. Failure to attempt the exam will earn you a 0.
Partially-correct solutions may or may not earn you a higher grade, at the discretion of the grader.
4. Many of the problems ask you to write Scheme code. Although you need not write correct working Scheme code, your code should be of sufficient quality that the grader can be confident that you would be able to make it work correctly with minimal effort when given access to MediaScheme.
5. Other people may be taking this exam (or a similar exam) at another time. You may not discuss this examination with anyone.
6. Please turn in this examination, the booklet, and your notes (if used).
7. After you have completed the examination, please write and sign the following statements:
I have neither received nor given inappropriate assistance on this examination.
I am not aware of any other students who have given or received inappropriate assistance on this examination.
Topics: Sorting, vectors, higher-order procedures.
Some of you observed in class that it can be pretty time-consuming to
call vector-insertion-sort!
on a vector that is
already sorted. We might want to test whether a vector is already
sorted, before we go to all the effort of sorting it.
Write a predicate, (
,
that determines whether the elements of vector-sorted?
vec
may-precede?
)vec
are
sorted according to may-precede?
.
For example,
>
(define fruits (vector "apple" "banana" "orange" "pear" "pineapple"))
>
(define numbers (vector 56 73 84 42 128))
>
(vector-sorted? fruits string-ci<=?)
#t
>
(vector-sorted? numbers <=)
#f
Topics: Code reading, List recursion, Higher-order procedures
Consider the following procedure.
(define proc (lambda (lst pred?) (let kernel ([rest lst] [left null] [right null]) ; (display (list 'kernel rest left right)) (newline) (if (null? rest) (list (reverse left) (reverse right)) (kernel (cdr rest) (if (pred? (car rest)) (cons (car rest) left) left) (if (pred? (car rest)) right (cons (car rest) right)))))))
a. Suppose we uncommented the line to display intermediate steps.
Show the values displayed when evaluating (proc (iota 10) odd?)
.
b. What does the procedure proc
do?
c. What preconditions must be met in order for the procedure
proc
to work?
Topics: Code tracing, List recursion, efficiency
We regularly use the reverse
procedure that,
given a list, returns a list of the same values, but in the
opposite order.
Let's consider two different ways in which the reverse
procedure could be defined.
(define list-reverse-1 (lambda (lst) (if (null? lst) null (list-append (list-reverse-1 (cdr lst)) (list (car lst)))))) (define list-reverse-2 (lambda (lst) (let kernel ([reversed null] [remaining lst]) (if (null? remaining) reversed (kernel (cons (car remaining) reversed) (cdr remaining))))))
Here are short traces of each procedure in action. (The procedure currently being evaluated is in italics; not every step is shown.)
(list-reverse-1 (list 1 2 3)) => (list-append (list-reverse-1 (list 2 3)) (list 1)) => (list-append (list-append (list-reverse-1 (list 3)) (list 2)) (list 1)) => (list-append (list-append (list-append (list-reverse-1 (list)) (list 3)) (list 2)) (list 1)) => (list-append (list-append (list-append null (list 3)) (list 2)) (list 1)) => (list-append (list-append (list 3) (list 2)) (list 1)) => (list-append (list 3 2) (list 1)) => (list 3 2 1) (list-reverse-2 (list 1 2 3)) => (kernel null (list 1 2 3)) => (kernel (cons 1 null) (list 2 3)) => (kernel (list 1) (list 2 3)) => (kernel (cons 2 (list 1)) (list 3)) => (kernel (list 2 1) (list 3)) => (kernel (cons 3 (list 2 1)) null) => (kernel (list 3 2 1) null) => (list 3 2 1)
The first of these also requires the list-append
procedure.
;;; Procedure: ;;; list-append ;;; Parameters: ;;; front, a list of size n ;;; back, a list of size m ;;; Purpose: ;;; Put front and back together into a single list. ;;; Produces: ;;; appended, a list of size n+m. ;;; Preconditions: ;;; front is a list [Unverified] ;;; back is a list [Unverified] ;;; Postconditions: ;;; For all i, 0 <= i < n, ;;; (list-ref appended i) is (list-ref front i) ;;; For all i, <= i < n+m ;;;; (list-ref appended i) is (list-ref back (- i n)) (define list-append (lambda (front back) (if (null? front) back (cons (car front) (list-append (cdr front) back)))))
Let's trace a sample call to list-append
(list-append (list 0 1 2) (list 3 4 5)) => (cons 0 (list-append (list 1 2) (list 3 4 5))) => (cons 0 (cons 1 (list-append (list 2) (list 3 4 5)))) => (cons 0 (cons 1 (cons 2 (list-append null (list 3 4 5))))) => (cons 0 (cons 1 (cons 2 (list 3 4 5)))) => (cons 0 (cons 1 (list 2 3 4 5))) => (cons 0 (list 1 2 3 4 5)) => (list 1 2 3 4 5)
a. About how many calls to cons
do you
expect there to be when reversing a list of length 4 with
list-reverse-1
? Why?
b. About how many calls to cons
do you
expect there to be when reversing a list of length 4 with
list-reverse-2
? Why?
c. About how many calls to car
do you
expect there to be when reversing a list of length 4 with
list-reverse-1
? Why?
d. About how many calls to car
do you
expect there to be when reversing a list of length 4 with
list-reverse-2
? Why?
e. Repeat a-d with a list of length 8.
f. Which version of reverse
do you prefer? Why?
Topics: Higher-order procedures, numeric recursion.
Some of you have observed that it is tedious to use the
o
to compose the same function with itself several
times. For example, it is tedious to write
(image-variant picture (o rgb-darker rgb-darker rgb-darker rgb-darker rgb-darker))
to apply the rgb-darker
function five times to each
pixel in an image.
Write a new procedure, nest
, as follows.
nest
takes two parameters, a unary
procedure f
and an integer
n
. The value produced is a new procedure that
results from composing together n
copies of
f
.
Note that n
must be at least 1 for
nest
to make sense. Verify this
precondition using husk-and-kernel style.
Here are some examples using nest
.
>
(define plus5 (nest (l-s + 1) 5))
>
(plus5 6)
11
>
(define list5 (nest list 5))
>
(list5 6)
(((((6)))))
>
(nest list 0)
n must be at least 1, given 0>
(define duplicate (lambda (val n) ((nest (l-s cons val) n) null)))
>
(duplicate "hello" 5)
("hello" "hello" "hello" "hello" "hello")