[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]

**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`

.

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.

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

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

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.

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 `

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:
*firstname* *lastname* *people*)

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

[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.)

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! `

that swaps the elements at the specified indices in the vector.
*vec* *index1* *index2*)

c. Write `selection-sort`

by stepping through the vector from
largest index to smallest, repeatedly swapping the largest remaining
element into the current position.

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

tortoisesteps through the list one element at a time, letting us accumulate each element along the way. Theharesteps 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`

.

Thursday, 23 November 2000

- Started thinking about exam.

Sunday, 26 November 2000

- Wrote questions (on paper).

Tuesday, 28 November 2000

- Created first part of exam page.

Wednesday, 29 November 2000

- Filled in remaining details.
- Fixed a few bugs after comments from students.

Monday, 4 December 2000

- Added a few notes.

[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]

**Disclaimer** Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.

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

Source text last modified Mon Dec 4 19:54:16 2000.

This page generated on Mon Dec 4 19:57:18 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu