Sample Final Examination

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 trees. As the sample exam suggests, problems may involve code reading and code analysis in addition to code writing.

Although the sample policies indicate that you may not discuss the actual final exam, you should feel free to discuss this sample final examination with anyone you'd like.

Policies for the Final Examination

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 on blank pieces of paper and then staple them together. You may use additional blank pieces of paper as scratch, provided you turn them in at the end of the examination.

3. You have received a cover sheet for this exam with a number on it. Please write your name on the cover sheet. Please write your number (not your name) on each of the non-scratch pages you turn in.

4. 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.

5. 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 DrRacket.

6. Other people may be taking this exam (or a similar exam) at another time. You may not discuss this examination with anyone.

7. After you have completed the examination, please write, sign, and date the following statements on the cover sheet:

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.

If you do not feel that you can sign either of these statements, please arrange to meet with me as soon as possible.

8. Please arrange the remaining sheets in order by problem number, make sure you've written your number and the page number on the top of each sheet, and then staple them together without the cover sheet.

9. Please turn in this examination, the cover sheet, the stapled pages, your notes (if used), and your scrap paper.

Problem 1: Is it sorted?

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, (vector-sorted? vec may-precede?), that determines whether the elements of 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

Problem 2: What does it do?

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?

Problem 3: Is it efficient?

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 0 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?

Problem 4: What is a nest?

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")