CSC151-01, Spring 2007 : Exam 2 : Intermediate Scheme

Distributed: Friday, March 16, 2007
Due: 9:00 a.m., Friday, April 6, 2007
No extensions.

Preliminaries

There are four problems on the exam. Some problems have subproblems. Each problem is worth twenty-five (25) points. 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 as restricted by 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.

As a reminder, you may refer to the Scheme manual as well as the course readings:

Kelsey, Richard, Clinger, William, and Rees, Jonathan, eds. (1998). Revised⁵ Report on the Algorithmic Language Scheme [HTML] [PDF]. February 20, 1998.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web (at least not until after I return exams to you). And, in case it's not clear, you may not ask others (in person, via email, via IM, by posting a please help message, or in any other way) to put answers on the Web.

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.

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. In particular, this exam is likely to take you about four to six hours, depending on how well you've learned topics and how fast you work. You should not work more than eight hours on this exam. Stop at eight hours and write There's more to life than CS and you will earn at least 75 points on this exam.

I would also appreciate it if you would write down the amount of time each problem takes. Each person who does so will earn two points of extra credit. Since I worry about the amount of time my exams take, I will give two points of extra credit to the first two people who honestly report that they've spent at least five hours on the exam or completed the exam. (At that point, I may then change the exam.)

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. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Davis (that's me) or Professor Rebelsky.

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. You may not tell other students how long you've spent on the exam.

You must present your exam to me in two forms: both physically and electronically. That is, you must write all of your answers using the computer, print them out, number the pages, put your name on the top of every page, and hand me the printed copy. You must also email me a copy of your exam. You should create the emailed version by copying the various parts of your exam and pasting them into an email message. In both cases, you should put your answers in the same order as the problems. Failure to name and number the printed pages will lead to a penalty of two points. Failure to turn in both versions may lead to a much worse penalty.

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

Just as you should be careful and precise when you write code and documentation, so should you be careful and precise when you write prose. Please check your spelling and grammar. Since I should be equally careful, the whole class will receive one point of extra credit for each error in spelling or grammar you identify on this exam. I will limit that form of extra credit to five points.

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-4306) or on my cell phone (206-383-8798).

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

Problems

Problem 1: Documenting Procedures

Some programmers prefer to give their procedures and variables short names, such as f and x, rather than things like find-in-tree? and tree-of-symbols.

Unfortunately, such short names can obfuscate code. For example, consider the following useful procedure. It is difficult for most programmers to figure out what the procedure does and how it does what it does.

(define r
  (lambda (l)
    (letrec ((c (lambda (p v)
                  (let ((x (if (odd? v) 1 0)))
                    (cons (+ (car p) x) (+ (cdr p) (- 1 x))))))
             (s (lambda (q m)
                  (if (null? m) 
                      (/ (car q) (cdr q))
                      (s (c q (car m)) (cdr m))))))
      (s (cons 0 0) l))))

a. Change the various names in the procedure to clarify the roles of the various things. You should certainly rename r, l, c, p, v, s, q, and m. [5 points]

c. Add introductory comments (the six P's) to explain the purpose (and the other P's) of the procedure. [10 points]

d. Modify the husk to ensure that the procedure's preconditions are met. Report a separate error for each failed precondition. [5 points]

Problem 2: Separating a List

In this exercise, you will document, write, and test a Scheme procedure, (unriffle lst), that takes a list as argument and returns a list of two lists, one comprising the elements in even-numbered positions in the given list, the other comprising the elements in odd-numbered-positions.

> (unriffle (list 'a 'b 'c 'd 'e 'f 'g 'h 'i))
((a c e g i) (b d f h))
> (unriffle (list))
(() ())
> (unriffle (list 'a))
((a) ())
> (unriffle (list 'b))
((b) ())
> (unriffle (list 'a 'b))
((a) (b))

Hint: It is likely that you will need a recursive kernel. If you think carefully about the parameters to that procedure, you are more likely to be successful.

Problem 3: Membership, Revisited

As you may recall, we've regularly seen a member? procedure that can be used to determine whether or not a value appears in a list. Here is a common definition of that procedure.

;;; Procedure:
;;;   member?
;;; Parameters:
;;;   val, a Scheme value
;;;   lst, a list of values
;;; Purpose:
;;;   Determine whether val appears in lst.
;;; Produces:
;;;   is-a-member, a Boolean
;;; Preconditions:
;;;   (none)
;;; Postconditions:
;;;   If there exists a position, p, such that
;;;     (equals? val (list-ref lst p))
;;;   then is-a-member is #t.
;;;   If there is no such position, then is-a-member is #f.
(define member?
  (lambda (val lst)
    (and (not (null? lst))
         (or (equal? val (car lst))
             (member? val (cdr lst))))))

Write a new procedure, (tree-member? val tree), that determines whether or not val appears in tree. You can assume that val is not a pair structure, but rather something with a simpler structure (e.g., boolean, number, string, symbol, or procedure).

You need neither document nor write a test suite for the tree-member? procedure. However, I will evaluate your code with respect to its elegance.

Problem 4: Printing Lists and Other Pair Structures

Here is a description of the algorithm that Scheme uses to print lists and pair structures.

Implement a variant of this strategy in which the list items are separated by commas as well as spaces. That is, write a procedure print that takes a Scheme value as a parameter and checks whether or not it is a pair. If it is not a pair, print can call write to print the value to the screen. If it is a pair, print should print the open paren, print the car, call the helper on the cdr, and print the close paren. The helper, instead of printing a space, should print a comma and a space.

> (print 'a)
a
> (print "hello")
"hello"
> (print (list 'a 'b 'c))
(a, b, c)
> (print (cons "a" (cons 3 #\x)))
("a", 3 . #\x)
> (print (list (list 1 2 3) (list "hello" "goodbye")))
((1, 2, 3), ("hello", "goodbye"))
> (print null)
()

Some Questions and Answers

These are some of the questions students have asked about the exam and my answers to those questions.

General

Problem 1

Problem 2

Problem 3

Problem 4

Errata

Here you will find errors of spelling, grammar, and design that students have noted. Remember, each error found corresponds to a point of extra credit for everyone. I usually limit such extra credit to five points. However, if I make an astoundingly large number of errors, then I will provide more extra credit.

Exam 2: Intermediate Scheme