Sample Final Examination

This is a sample examination. It includes problems similar to those that have appeared on previous in-class final examinations (and, as you may 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 less-extreme?), that determines whether the elements of vec are sorted according to less-extreme?.

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: Whatzitdo?

Topics: code reading, list recursion, higher-order procedures

Consider the following procedure.

(define proc
  (lambda (lst pred?)
    (let kernel ([rest lst]
                 [left 0]
                 [right 0])
      ; (display (list 'kernel rest left right)) (newline)
      (if (null? rest)
          (list left right)
          (kernel (cdr rest)
                  (if (pred? (car rest)) (+ 1 left) left)
                  (if (pred? (car rest)) right (+ 1 right)))))))

a. Suppose we uncommented the line to display intermediate steps. Show the values displayed when evaluating (proc (range 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 surrounded by asterisks; 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: Assigning random groups

Topics: Vectors, lists, pseudo-random values, documentation

The CS department is looking to upgrade from the low-tech method we use to assign groups in CSC 151; instead, we’d like to use a program to randomly assign students to groups of two. Document and write a procedure, (random-groups-of-two roster), that takes a vector of student names and produces a vector of lists, where each list contains the names of two students who will work together in a group. As you might expect, no student may appear in two different groups.

You may assume there are an even number of students in the class.

Here are a few example runs of this procedure:

(define professors (vector "Anya" "Charlie" "Henry" "Jerod" "Mr. Stone" "Peter-Michael" "Sam" "Fahmida"))
  
(define fruits (vector "orange" "grapefruit" "kumquat" "tangerine" "lemon" "lime"))

> (random-groups-of-two professors)
'#(("Mr. Stone" "Sam") ("Fahmida" "Charlie") ("Henry" "Anya") ("Peter-Michael" "Jerod"))

> (random-groups-of-two professors)
'#(("Anya" "Mr. Stone") ("Peter-Michael" "Charlie") ("Fahmida" "Sam") ("Henry" "Jerod"))

> (random-groups-of-two fruits)
'#(("kumquat" "tangerine") ("grapefruit" "orange") ("lime" "lemon"))