CMPU-145, Spring 2013
Lab 4
Feb. 25, 2013


Begin by extracting the definitions of the following functions
that were seen in class today:

  REFLEXIVE?
  SYMMETRIC?
  FLATTEN
  CROSS-PRODUCT

Note that several of these functions make extensive use of DOLIST and
destructive programming.  This is for convenience.  They are not
necessarily very efficient because they continue processing even after
they have already figured out what the answer should be.

1.  Define a function, called TRANSITIVE?, that takes a list-of-pairs
    representing a relation.  It should return #t if that relation is
    transitive; #f otherwise.  In addition, in the case of a
    non-transitive relation, it should print out information about all
    violations of the transitivity property, as illustrated below.

    > (transitive? '((1 2) (2 3) (1 3) (4 4)))
    #t
    > (transitive? '((1 2) (2 3) (4 4)))
      (1 2), (2 3); but not (1 3)
    #f
    > (transitive? '((1 2) (2 3) (3 2) (4 4)))
      (1 2), (2 3); but not (1 3)
      (2 3), (3 2); but not (2 2)
      (3 2), (2 3); but not (3 3)
    #f

    NOTE:  Even when it prints out such information, the output of
           the function must be a boolean (i.e., #t or #f).

    HINT:  Use two DOLISTs, one nested inside the other, to walk
           through all possible pairs of pairs from the relation.


2.  Define a function, called EQUIV-RELN?, that takes two inputs:
      LIST-O-PAIRS, a list of pairs representing a relation over some set A,
      THE-SET-A, a list representing the set A.
    It should return #t if that relation is an equivalence relation.

    HINT:  This is easy given all the functions that have already
           been defined.

    > (equiv-reln? '((1 1) (2 2) (3 1)) '(1 2 3))
    #f
    > (equiv-reln? '((1 1) (1 2) (2 1) (2 2) (3 3)) '(1 2 3))
    #t


3.  Recall from class the theorem that says that any partition of a
    non-empty set A determines an equivalence relation over A.  For
    example, the partition {{1},{2,3}} of the set {1,2,3} determines
    the equivalence relation {(1,1),(2,2),(2,3),(3,2),(3,3)}.

    Define a function, called PARTITION->EQUIV-RELN, that takes a
    list-of-lists representing a partition of some set as its only
    input.  It should return a list of pairs representing the desired
    equivalence relation, as illustrated below.

      > (partition->equiv-reln '((1 2) (3) (4 5)))
      ((2 2) (2 1) (1 2) (1 1) (3 3) (5 5) (5 4) (4 5) (4 4))

    HINT:  Notice which pairs are needed for the first subset in
           the partition.  Then look at which pairs are needed
           for the second subset.  Etc.

    HINT:  Think about how you can let CROSS-PRODUCT and FLATTEN
           do all of the work for you!

    HINT:  What should (partition->equiv-reln) '((1 2 3))) return?


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

When you are done, ask a coach to come over to check your work.
Then submit using submit145 as usual.