CMPU-145, Spring 2013
Practice Problems 

1. A.  If f:A -> B and g:B -> C are both injective functions then
       their composition, gof:A -> C is also injective (proven in
       class).  However, if g is not injective, then gof might not be
       injective either, even if f is.  Given an example that
       demonstrates this possibility.  (Use a small set A.)

   B.  Suppose f:A -> B and g:B -> A are functions such that for
       each a in A, g(f(a)) = a.  Circle the statements below that
       MUST be true; cross out the ones that MIGHT be false.

       	    *  f is injective
	    *  f is surjective
            *  g is injective
	    *  g is surjective

   C.  Write down one of the statements that MIGHT be false here: _______
       Give a counter-example that demonstrates that it can indeed be false.


2.  We have looked at the properties of a relation being REFLEXIVE, 
    SYMMETRIC and TRANSITIVE.  Here's a new one:

       A binary relation R over a set A is SERIAL if and only if
       for every x in A, there is some y in A such that (x,y) is in R.

    A.  Give an example of a relation R over the set {1,2,3} that
    	is serial but not reflexive.

    B.  TRUE or FALSE.  If f:A -> A is a function, then it must be 
                        a serial relation.

    C.  Prove that if a binary relation R over some set A is reflexive
    	then it must also be serial.

    D.  Prove that if a binary relation R over some set A is serial,
        symmetric and transitive, then it must also be reflexive.


3.  A relation R over a set A is called EUCLIDEAN if:

          whenever (a,b) and (a,c) are in R, then so is (b,c).

    NOTE:  This is NOT the same thing as being transitive!!

    Give an example of a relation over the set {1,2,3,4,5} that is
    Euclidean, but is NOT transitive.


4.  Define a Scheme function, called LISTERINO, that takes two integer
    inputs, N and TOTAL.  It should return as its output a list of 
    fractions, as illustrated below:

       > (listerino 4 5)
       (1/4 2/3 3/2 4)
       > (listerino 6 7)
       (1/6 2/5 3/4 4/3 5/2 6)

    Notice that the value of N is the value of the first denominator
    in the output list, and that subsequent denominators decrease by 1
    each time.  Notice that TOTAL is the sum of the numerator and
    denominator of any fraction in the output list.