CSC 151-02, Fall 2006 : Schedule : Homework 09

Homework 9: Set Intersection

Assigned: Friday, 29 September 2006
Due: Tuesday, 3 October 2006
No extensions!

Summary: In this assignment, you will further explore issues pertaining to documentation, testing, and recursive procedures.

Purposes: To reinforce our discussions of documentation and testing. To give you experience writing tests.

Expected Time: One to two hours.

Collaboration: You may work in a group of any size between two and four, inclusive. You may consult others outside your group, provided you cite those others. You need only submit one assignment per group.

Submitting: Email me your work, using a subject of CSC151 Homework 9.

Warning: So that this exercise is a learning assignment for everyone, I may spend class time publicly critiquing your work.

Assignment

After graduation, you and your colleagues move to Schemeville to found a new company, Sets-R-Us. Your business plan is to develop a library of procedures for doing set operations and sell it to Scheme programmers all over the world (or maybe just computer science professors at Grinnell College). You know that you need thorough documentation and reliable code for your product to sell.

You decide to begin with the set intersection operation. You need to write a procedure, (intersect left right), that takes two lists of symbols as parameters and returns a list of which the elements are precisely those symbols that appear in both left and right. Although left and right might include duplicate symbols, the result of evaluating (intersect left right) should not.  

Note that the above description of intersect does not specify the order in which the symbols will occur in the result; your tests should not assume a particular order.  (In particular, you may use the test-permutation! procedure to test your code.)

a. The above description of the intersect procedure is clearly casual. Write formal documentation for intersect, using the six P's.

b. Write a test suite that will help you and your colleagues test for errors in an implementation of intersect. Note that you should be relatively confident that anything that passes your test suite is correct. (You might also want to be able to use this test suite to convince potential customers that your implementation is correct!) Note also that the test suite should use the unit-test.ss library for testing.

c. Finally, write your own version of intersect.

Helpful Hints

You will likely find it helpful to use a member? predicate, which you should have defined already. If you have difficulty finding your definition, here is one you may use (with proper attribution).

;;; 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.
;;; Author:
;;;   Samuel A. Rebelsky
(define member?
  (lambda (val lst)
    (and (not (null? lst))
         (or (equal? val (car lst))
             (member? val (cdr lst))))))

Important Evaluation Criteria

In evaluating your work, I will ask myself, "Would I buy this code?" I will emphasize (a) the clarity and precision of your documentation, (b) the thoroughness of your tests, and (c) the correctness of your implementation.

I also plan to run most all the tests submitted on all of the implementations submitted. The authors of the test suites that correctly reject the most implementations are likely to receive some extra credit, as are the authors of the implementations that pass all of the test suites (including mine).

And yes, if you all write procedures that pass all of the test suites (including mine), then it is likely that you will all receive extra credit.