Assignment 4: Sets and Functions

Due 04.Feb.17 (Tue) 17:00

Before you tackle the homework, remind yourself of our general hw policies.

1. (1pt) A question has been posted on the class newsgroup, with the title "hw04 question (2003spring)" "you've found the hw04 newsgroup question"; find and answer it. (Answer on your hw04 solution, not by replying to the newsgroup!)

2. (1pt) Hmm, I've received no feedback at all, so far. Find the class feedback form, and submit it. If you have nothing to say at the moment that's fine, just don't type a thing. You are encouraged to leave specific comments like

   If hwXX, problem YY had been phrased '...', I would have understood what it was asking for much more easily.

   Verification question (for us to grade): What is the last question on the form? (Just the three words).

3. (2 pts) Take the learning style assessment survey. (If you've already taken this assessment in the past, you don't need to repeat it.)
   Verification-question (for us to grade): Of your four resulting scores, how many of of them are even numbers?

   (You do not need to report which classification you are, though you are welcome to. We just want you aware of the fact that learning styles and teaching styles may jibe worse or better for individuals; this lets you provide better constructive feedback for the prof!)

4. (4pts) The deferred hw03 problem 12.
5. (3pts) The deferred hw03 problem 13.
6. (6pts) The deferred hw03 problem 14.

7. (5pts) For the set implementation given in Lecture 10, write the functions

   ;; set-: Set, Set --> Set
   ;; Return the set-difference of A and B
   ;;
   (define (set- A B) ...)
   
   ;; cross-product: Set, Set --> Set
   ;; Return the cartesian cross-product of A and B.
   ;; NB See text "cartesian product";
   ;;    this is not the cross-product from 3-d vector calc.
   ;;
   (define (cross-product A B) ...)
   

   (For your test cases, feel free to experiment with drscheme's new test-suite tool.)

   As throughout comp210, good code should strive to meet the definition as closely as possible. (For instance, compare the code for set-union and set-intersection with the book's definition of union and intersection.)

   One note: since cartesian products deal with ordered pairs, you'll need to decide how to represent these in your program. You have some latitude on this.

   (In general, lists are a perfectly acceptable representations of tuples. Still, distinguish between functions that accept/return tuples from those that work on lists -- just as you'd distinguish between functions that return colors vs strings, even if you happen to represent colors as strings of red-green-blue values.)

   One remote caution: in scheme, the name "pair?" is built-in, but it does not mean a-list-of-exactly-two-elements; it's actually just another name for cons?. (If curious, check help-desk for "improper list".) Fortunately this shouldn't be an issue; if you define-struct pair, then the built-in name is shadowed with the new structure-checking-predicate, as you'd expect.

8. (42pts) Section 1.6 (p.85), #16. (Fourth edition -- Section 1.4: #14) Your proofs should be well-structured and clear. (Cf. the equivalent-definitions-of-subset proof from lecture.)
9. (24pts) Section 1.6 (p.86) #26. (Fourth edition -- Section 1.4: #24)
10. (2pts) Section 1.7, # 2. (Fourth edition -- Section 1.5: #2)
11. (1pt ) Section 1.7, #10. (Fourth edition -- Section 1.5: #8)
12. (4pts) Section 1.7, #18. (Fourth edition -- Section 1.5: #16) Prove this from the definitons. You may use the set-identities from the chapter if you like, or (as in lecture) the fact that two sets are equal iff they are subsets of each other. (It's reminiscent of the difference between proof-by-algebra and proof-by-inference rules.)
13. (2pts) Section 1.7, #32. (Fourth edition -- Section 1.5: #30) Consider a Venn diagram, reminiscent of p.92 fig.5.
14. (3pts) Section 1.7, #38. (Fourth edition -- Section 1.5: does not exist ("DNE"))
15. (2pts) Section 1.7, #40. (Fourth edition -- Section 1.5: #38)
16. (3pts) Section 1.7, #50. (Fourth edition -- Section 1.5: #48)