[an error occurred while processing this directive]

Homework 5: Sets and Functions

Due 05.Feb.22 (Tue)

Before you tackle the homework, remind yourself of our general hw policies. In addition, here are some Q&A's about this homework.

Reading in Rosen: 1.5 ("Methods of Proving Theorems"), 1.6, 1.7, 7.1 (skim), and 7.3 (digraphs only).

  1. (2pts) Section 1.5, #26 (Q closed under ⋅).
  2. (3pts) Section 1.5, #28 ((Q-{0})⋅(R-Q) ⊆ (R-Q) ?).
  3. (2pts) Section 1.5, #64 (Q closed under expt?).
  4. (2pts) Section 1.7, # 2 (Sophomores taking Discrete Math).
  5. (1pt ) Section 1.7, #10 (Solve for A,B given A-B, etc.).
  6. (4pts) Do one of the following two proofs:
    1. Section 1.7, #18 (set- right-distributes over itself).
      You may reason directly from the definition of set-difference and set-equality. Alternately, although we aren't coverint it, you may use the set-identities from the chapter if you like. (These two approaches are reminiscent of the proof-by-algebra vs proof-by-inference rules.)
    2. Section 1.6 (p.85), #16 (Does P(A)=P(B) ⇒ A=B ?). Prove your answer.
      (Hint: use proof-by-contradiction -- that is, RAA, though you don't need to give an inference-style proof.)
  7. (2pts) Section 1.7, #32 (Symm. difference associative?).
    Note you only need answer yes/no. To figure it out, you might consider using a Venn diagram, reminiscent of p.92 fig.5.
  8. (3pts) Section 1.7, #38 (big-union, big-intersect examples).
    (Making your answers concise means using the vocabulary/def'ns at hand.)
  9. (2pts) Section 1.7, #40 (bit-set representations).
  10. (3pts) Section 1.7, #50 (Multisets).
  11. (4pts) Section 1.6 (p.86) #26 (A×B ≠ B×A when ...).
    Your proofs should be well-structured and clear. (Cf. the equivalent-definitions-of-subset proof from lecture.) You may want to phrase this using 'if' rather than 'when', to make the premises clear. Does your proof use all its premises?

  12. (Extra Credit 2pts) 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) ...)
    You may write your code in scheme (procedural), scheme (object-oriented), or java. Turn in a hardcopy of your code (including sufficient test cases). If your code does not pass all test cases, say so.

    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.) If your functions are much longer than two lines (Scheme) or six lines (Java), you are being unnecessarily complicated.

    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, fixed-length lists or arrays/vectors are perfectly acceptable representations of tuples. Still, distinguish between functions that accept/return tuples from those that work on lists/arrays/vectors -- 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.

  13. Extra Credit (2pts) Generalize the previous code for cross-product to take any number of sets as inputs.
    (Handling variable number of inputs in Java and Scheme)
  14. (2pts) Section 7.1, #2 (Divides on {1,2,3,4,5,6}).
    For 2b, instead draw the graph (as in class and the second half of Section 7.3.)
  15. (3pts) Section 7.1, #4 and #10 (properties of taller?, bornSameDay?, etc).
    Group your answers together, for #4 and #10.
    16. [an error occurred while processing this directive]