Exam 3

Distributed: Tuesday, November 28, 2000
Due: 11 a.m., Tuesday, December 5, 2000
Free extension until Friday, December 8, 2000
Those taking the free extension may not have their exams graded before the end of the semester.

This page may be found online at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Exams/exam.03.html.

• Preliminaries
• Problems
  • Problem 1: Documenting Procedures
    • Notes
  • Problem 2: Binary Search, Revisited
  • Problem 3: Searching for Multiple Keys
    • Notes
  • Problem 4: Selection Sort
  • Problem 5: Splitting Lists with Rabbits and Turtles

Preliminaries

There are five problems on this exam. Each problem is worth twenty points. For convenience, some questions are divided into sections. 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. If you write down the amount of time you spend on each question, I'll give you three points of extra credit.

This examination is open book, open notes, open mind, open computer, open Web. 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. It is likely to take you about five to ten hours, depending on how well you've learned topics and how fast your work. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted.

You must include the following statement on the cover sheet of the examination. Please sign and date the statement. Note that the statement must be true; if you are unable to sign the 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.

I have neither given nor received inappropriate assistance on this examination. I am not aware of any other students who have given or received inappropriate assistance on this examinatino.

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'll have no chance of finishing the exam.'' You may also summarize these policies.

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 (a plain text file, please). Put your answers in the same order that the problems appear in. If you give an example of one of "Sam's easy to misinterpret scribbles" (that is, the scrawl I write on the board) along with the actual meaning and the interpreted meaning, I'll give you three points of extra credit.

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 yo u 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.

Problems

Problem 1: Documenting Procedures

Full 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 may-precede?)
    (letrec 
      ((helper1 (lambda (alpha beta)
                  (if (may-precede? alpha beta) alpha beta)))
       (helper2 (lambda (guess rest)
                  (if (null? rest) guess
                      (helper2 (helper1 guess (car rest))
                               (cdr rest))))))
      (helper2 (car stuff) (cdr stuff)))))

Notes

[4 Dec 2000] What do stuff, may-precede?, guess and rest exactly mean?

The problem is left intentionally vague; you're supposed to figure out what all the names represent and what the procedure does.

You can guess something about the form of stuff given that the operations car and cdr are applied to it. You can guess that may-precede? is a predicate from its name. You can tell its arity from the code.

Problem 2: Binary Search, Revisited

One disadvantage of the binary search procedure given in search.ss 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 index of the first value 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, space by space.

You will need to modify the code to the existing binary search and not simply call binary search.

Problem 3: Searching for Multiple Keys

While we've successfully found ways to search lists based on single keys (e.g., using search-list-for-keyed-value), we don't have a clear mechanism for searching lists for values that match on multiple keys. For example, when I'm looking through a phone book for a person, I probably want someone whose last name and first name match.

Consider the problem of writing a procedure, (lookup-person firstname lastname people) that is to scan a list of people for one with given first name and last name. There are at least for techniques we can use:

• We can write it from scratch, ignoring all the effort spent on search-list-for-keyed-value.
• We can write a new version of search-list-for-keyed-value that takes two keys and two get-key operations as parameters. The implementation of lookup-person will then call the new version of the general procedure.
• We can implement lookup-person by first filtering the list based on one key and then use the basic search-list-for-keyed-value to get the second key.
• We can combine the first name and last name into a single key and write an appropriate get-key operation that returns a combined first and last name.

a. Write the "from scratch" version. Call it lookup-person-a.

b. Write the new version of search-list-for-keyed-value (with two keys and two get-keys as parameters). Implement lookup-person-b using that procedure.

c. Write lookup-person-c by filtering and then searching. You can find a simple filtering procedure in filter.ss.

d. Write lookup-person-d with one call to search-list-for-keyed-value by combining the two keys into a single key and writing an appropriate get-key

e. In a few sentences, indicate which of the techniques you prefer and why.

Notes

[4 Dec 2000] I originally had lookup-person take two parameters, a first name and a last name. I've since updated it to take three (also a list of people to look through). Either solution is okay.

[4 Dec 2000] You can use the vector of students from search.ss. (Or, more precisely, use that vector converted to a list.)

Problem 4: Selection Sort

Although we emphasized selection 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 largest element of the vector in the last place, the next largest in the second-to-last place, and so on and so forth.

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

;;; Procedure:
;;;   index-of-largest
;;; 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 largest value in the
;;;   range between start and end.
;;; Produces:
;;;   iol, An integer that serves as the index of the largest value.
;;;   The largest value is one for which (may-precede? x y)
;;;   holds for every value x in the subvector.
;;; 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,
;;;     (may-precede? (vector-ref vec i) (vector-ref vec iol))
;;;     holds.
;;;   Does not affect the vector
;;;   Does not read input or write output.

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

c. Write selection-sort by stepping through the vector from largest index to smallest, repeatedly swapping the largest remaining element into the current position.

Problem 5: Splitting Lists with Rabbits and Turtles

One of my colleagues has said that he doesn't like my version of split because it requires us to step through the list twice: once to find the length and once to extract the first half of the list. After many years of thought, he came up with the split procedure that you saw in the lab on merge sort. Before that, he had a much different technique. Here's a paraphrase.

I use a ``tortoise and hare'' strategy. My recursive helper procedure steps through the list in two ways. The tortoise steps through the list one element at a time, letting us accumulate each element along the way. The hare steps through the list two elements for every one the tortoise visits. Hence, when the hare reaches the end of the list, we've accumulated half of the list.

Implement this tortoise-and-hare version of split.