CMPU-145, Spring 2013
Asmt. 2 
Due:  Wednesday, Feb. 20 @ 1:30 p.m.


PAPER-N-PENCIL PART  (does not need to be submitted electronically)

1.  Recall the definitions of reflexive, symmetric and transitive relations.
    Let A = {1,2,3}.

    (a) Give an example of a binary relation R1 over A that is
        reflexive and symmetric, but not transitive.

    (b) Give an example of a binary relation R2 over A that is
        reflexive and transitive, but not symmetric.

    (c) Give an example of a binary relation R3 over A that is
        symmetric and transitive, but not reflexive.

    NOTE:  A relation is a set of ordered pairs.  That's the
           form that each answer to parts (a) - (c) should be in.

     
2.  Prove that the intersection of two transitive relations must be transitive.


3.  Give an example of two relations, R and S, over the set A = {1,2,3}
    such that R and S are transitive, but the UNION of R and S is not 
    transitive.

    NOTE:  Again, give your answer as a set of ordered pairs.


PROGRAMMING PART  (must be submitted electronically & turn in printouts)

4.  Define a function called CARTESIAN-PRODUCT that takes two lists,
    LISTY and LISTZ, as its inputs.  It should return a list of pairs
    representing the cartesian product of the input lists as illustrated
    below.

      > (cartesian-product '(1 2 3) '(a b))
      ((1 a) (1 b) (2 a) (2 b) (3 a) (3 b))
      > (length (cartesian-product '(1 2 3) '(1 2 3 4 5)))
      15

    NOTE:  The order of the pairs in the output list does not matter.

    Note how the LENGTH function can be used to facilitate testing of
    this function on longer lists.
 
    HINT:  You may wish to define a helper function, HELPY, that
           takes two inputs, Y and LISTZ.  It should return as its
	   output a list of ordered pairs, where Y is the first element
	   of each ordered pair; and the second elements are drawn from
	   LISTZ, as shown below.  But there are many different ways
	   of solving this problem.

      > (helpy 2 '(a b c d))
      ((2 a) (2 b) (2 c) (2 d))
      > (helpy 3 '(a b c d e))
      ((3 a) (3 b) (3 c) (3 d) (3 e))

      Now, if LISTY is (1 2 3); and LISTZ is (a b c d) consider:

        (helpy 1 (a b c d)) ==> ((1 a) (1 b) (1 c) (1 d))
        (helpy 2 (a b c d)) ==> ((2 a) (2 b) (2 c) (2 d))
        (helpy 3 (a b c d)) ==> ((3 a) (3 b) (3 c) (3 d))

      In this case, how would you combine the above results?  Would
      you use CONS, LIST, APPEND or something else?

   -------------------------
    
     When your CARTESIAN-PRODUCT function is working, make sure that
     your definitions file is nicely formatted, and that you have
     enough TESTER expressions to demonstrate that your function works
     correctly, and that your interactions are nicely formatted, then
     you should save your interactions as a plain text file (use "Save
     Other..." --> "Save Interactions as Text").  

        Print out your definitions and interactions files using
        the ENSCRIPT command, as demonstrated below:

             enscript  -2jr  my-defns-file.txt

             enscript  -2jr  my-inters-file.txt

        Also, submit your asmt2 directory:

             submit145  asmt2  my-asmt-2-directory


===============

That's it!!