Fundamentals of CS I (CS151 2001S)

Exam 3

Distributed: Friday, 4 May 2001
Due: 9 a.m. Friday 11 May 2001
No extensions.

This page may be found online at


There are four problems on the exam. Each problem is worth the same number of points. Some problems may be broken up into subproblems. The point value associated with a problem does not necessarily correspond to the complexity of the problem or the time required to solve the problem.

This examination is open book, open notes, open mind, open computer, open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than that limitation, you should feel free to use all reasonable resources available to you. As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately.

This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. It is likely to take you about five to ten hours, depending on how well you've learned topics and how fast your work. I would appreciate it if you would write down the amount of time each problem takes. I expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. Since I worry about the amount of time my exams take, I will give three points of extra credit to the first two people who honestly report that they've spent at least eight hours on the exam. (At that point, I may then change the exam.)

Over the past few weeks, I've designated a few talks (some CS talks; some convocation talks) as extra credit. Please indicate which, if any, of those talks you've attended.

You must include both of the following statements on the cover sheet of the examination. Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. Note also that ``inappropriate assistance'' is assistance from (or to) anyone other than myself or our teaching assistant.

1. I have neither received nor given inappropriate assistance on this examination.
2. I am unaware of any other students who have given or received inappropriate assistance on this examination.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing the exam.'' You may also summarize these policies. You may not tell other students which problems you've finished.

Answer all of your questions electronically and turn them in in hardcopy. That is, you must write all of your answers on the computer and print them out. You should also email me a copy of your exam by copying your exam and pasting it into an emal message. Put your answers in the same order that the problems appear in. Make sure that your solution confirms to the format for laboratory writeups

In many problems, I ask you to write code. Unless I specify otherwise in a problem, should write working code and include examples that show that you've tested the code.

You should fully document all of the primary procedures (including parameters, purpose, value produces, preconditions, and postconditions). If you write helper procedures (and you may certainly write helper procedures) you should document those, too, although you may opt to write less documentation. When appropriate, you should also include short comments within your code. You should also take care to format your code carefully.

Just as you should be careful and precise when you write code, so should you be careful and precise when you write prose. Please check your spelling and grammar.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by emphasizing your answer and including a clear set of work that you used to derive the answer.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem you have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

I will also reserve time at the start of classes next week to discuss any general questions you have on the exam.


Problem 1: Documenting Procedures

Fully document the following procedure. You should include not only the introductory six Ps but also short descriptions of the purpose of the helpers.

(define fun
  (lambda (stuff check?)
        ((helper1 (lambda (alpha beta)
                    (if (check? alpha)
                        (list (cons alpha (car beta))
                              (cadr beta))
                        (list (car beta)
                              (cons alpha (cadr beta))))))
         (helper2 (lambda (acc rest)
                    (if (null? rest) 
                        (list (reverse (car acc)) 
                              (reverse (cadr acc)))
                        (helper2 (helper1 (car rest) acc)
                                 (cdr rest))))))
      (helper2 (list null null) stuff))))

I have purposely chosen vague names for parameters and helpers (e.g., alpha and beta). You may, but need not, rename them. Note that you can guess some aspects of the parameters by how they are used. For example, both car and cdr are applied to stuff and check? ends with a question mark.

Problem 2: Binary Search, Revisited

One disadvantage of the binary search procedure given in is that it doesn't necessarily deal appropriately with vectors in which the same key can occur in multiple values. For example, if we are searching through a phone book, there might be more than one person with a last name of Smith.

Update binary-search so that it returns the number of values in the vector with a matching key.

Your solution should rely primarily on the divide-and-conquer approach of binary search. You may not simply find some value in the vector with a matching key and then look backwards and forwards, space by space.

You will need to modify the code and documentation for the existing binary search and not simply call that procedure.

You should test your updated procedure, although you need not show me the results of your tests.

Problem 3: Selection Sort

Although we emphasized insertion sort and merge sort in lab, we did discuss other sorting methods in class. One of the natural sorting methods is selection sort, which involves repeatedly finding the smallest remaining element and putting it at the proper place in the list or vector. That is, you put the smallest element of the vector in the first place, the next smallest in the second place, and so on and so forth.

a. Write a procedure, index-of-smallest, that finds the index of the smallest value in a portion of a vector.

;;; Procedure:
;;;   index-of-smallest
;;; Parameters:
;;;   vec, a vector
;;;   start, the index of the first element in a range
;;;   end, the index of the last element in a range
;;;   may-precede?, a predicate that allows us to determine whether
;;;     one element may precede another
;;; Purpose:
;;;   Identifies the index of the smallest value in the
;;;   range between start and end, inclusive.
;;; Produces:
;;;   ios, An integer that serves as the index of the smallest value.
;;; Preconditions:
;;;   0 <= start < (length vector)
;;;   start <= end < (length vector)
;;;   may-precede? may be applied to any pair of elements in 
;;;     the vector
;;; Postconditions:
;;;   For all integers, i, between start and end, inclusive
;;;     (may-precede? (vector-ref vec ios) (vector-ref vec i))
;;;     holds.
;;;   Does not affect the vector
;;;   Does not read input or write output.

b. Document, write, and test a proceduce, (swap! vec index1 index2) that swaps the elements at the specified indices in the vector.

c. Document, write, and test a selection-sort procedure that steps through the vector from smallest index to largest, repeatedly swapping the smallest remaining element into the current position.

Problem 4: A Book Object

Sarah and Steven Schemer have contracted to implement a simple library system. Their employer has heard the buzzword of object-oriented programming and wants the entry for each book implemented as an object. Sarah and Steven successfully slept through the succinct but satisfying summary of such stuff. (That is, they have no idea how to create an object in Scheme.) So, they've hired you as a subcontractor to help. (It's okay that they've hired you since the work is not for class.)

Their employer likes to know the following for each book:

As you might guess, the author, title, and library of congress number of a book cannot change. However, the value and condition of the book can change. In addition, the library might choose to add or delete the categories associated with a book. For example, they might initially classify Experiments in Java as both a Travel Book and a Book by a Faculty Member. Later, they might realize that it's actually a book about programming and want to remove the "Travel Book" classification but add "Programming".

Document, write, and test a make-book procedure that creates a book object. It should accept messages to get all the component values, to change appropriate component values, and to display the book as HTML.

For example,

> (define eij
    (make-book "Samuel A. Rebelsky"
               "Experiments in Java"
               (list "Books by Grinnell Faculty" 
                     "Travel Guides")))
> (eij ':get-author)
"Samuel A. Rebelsky"
> (eij ':set-author!)
"book: invalid message"
> (eij ':get-value)
> (eij ':set-value! 10)
> (eij ':get-value)
> (eij ':get-categories)
("Books by Grinnell Faculty" "Travel Guides")
> (eij ':delete-category! "Travel Guides")
> (eij ':get-categories)
("Books by Grinnell Faculty")



Thursday, 3 May 2001 [Samuel A. Rebelsky]

Friday, 4 May 2001 [Samuel A. Rebelsky]


Disclaimer: I usually create these pages on the fly. This means that they are rarely proofread and may contain bad grammar and incorrect details. It also means that I may update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This page was generated by Siteweaver on Thu May 3 23:08:29 2001.
This page may be found at
You may validate this page's HTML.
The source was last modified Thu May 3 22:56:13 2001.