This homework assignment is also available in PDF.
Assigned: Friday, 29 September 2006
Due: Tuesday, 3 October 2006
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 8.
Warning: So that this exercise is a learning assignment for everyone, I may spend class time publicly critiquing your work.
Your TA, Emily Jacobson, remembers with fondness writing a procedure,
(intersect left right), which takes two
lists of symbols as arguments and returns a list of which the elements
are precisely those symbols that are elements of both
right. (Although symbols can appear multiple times in
left and right, no symbol may appear more than once in the result.)
She's told me that she'd like you to share her joy.
a. Emily's description is clearly casual. Write formal documentation
intersect, using the six P's.
b. Although Emily's version was perfect, I recall that many of her
colleagues had a few subtle bugs in their implementations. Write a
test suite that would help her colleagues (and yours) determine whether
or not the implementation contains errors. Note that you should be
relatively confident that anything that passes your test suite is
correct. Note also that the test suite should use the
unit-test.ss library for testing.
To help you write this test, we have added another keyword to
takes two parameters, an expression and a list. It then evaluates
the expression and compares the result to the list. If the expression
evaluates to a permutation of the list, it considers the test successful.
If not, it considers the test a failure.
c. Write your own version of
You will likely find it helpful to use a
which you should have defined already. If you have difficulty finding
your definition, here's mine:
;;; 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))))))
In evaluating your work, 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.
Wednesday, 27 September 2006 [Samuel A. Rebelsky]
Monday, 2 October 2006 [Samuel A. Rebelsky]
test-permutation!(and updated the library appropriately).
I usually create these pages
on the fly, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Thu Nov 30 21:42:52 2006.
The source to the document was last modified on Mon Oct 2 08:29:34 2006.
This document may be found at
You may wish to validate this document's HTML ; ;Samuel A. Rebelsky, firstname.lastname@example.org
http://creativecommons.org/licenses/by-nc/2.5/or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.