CS 342		Additional Homework for Chapter 2	Due Mon: Feb 17

1. (to make up for problem 1(e) on page 60).
   Do problems 1(c) and 1(d) on page 60.

2. (To make up for problem 2 on page 60.)
A list of the form ((k1 v1) (k2 v2) (k3 v3) ... (kn vn)) can be thought
of as a binary relation between the keys, ki, and the values, vi.
For example, the list ((4 3) (4 2) (7 6) (6 2) (3 4)) relates the key 4 to
the value 3; it also relates 4 to 2.  The order is not significant
in relations; that is, ((4 3) (4 2) (7 6) (6 2) (3 4)) is the same relation
as ((7 6) (6 2) (4 3) (4 2) (3 4)).  The list () represents the empty relation.
The reverse (or opposite) of a relation relates the values to their keys.
For example, the reverse of the relation ((4 3) (4 2) (7 6) (6 2) (3 4)) is
the relation ((3 4) (2 4) (6 7) (2 6) (4 3)), which relates 3 to 4, 2 to 4,
etc.

A binary relation is a function if if relates each key to exactly one value.
For example, ((4 3) (5 4)) is a function, but ((4 3) (4 2) (7 6) (6 2) (3 4))
is not.

Write programs for the following.

a. (reverse-rel r) takes a relation r and returns its reverse (see above).
For example, (reverse '((4 3) (4 2) (7 6) (6 2) (3 4))) should return
((3 4) (2 4) (6 7) (2 6) (4 3)).

b. (fun? r) tests whether the relation r is a function.
For example, (fun '((4 3) (5 4))) returns T
and (fun? '((4 3) (7 6) (4 2) (6 2) (3 4))) returns ().

c. (one-to-one? r) takes a relation r and tests whether it is a one-to-one
function.  For example, (one-to-one? '((8 3) (4 2) (7 6) (6 2) (3 4)))
returns (), since this relation (which is a function) maps both 4 and 6 to 2.
Another example, (one-to-one? '((8 3) (4 8) (7 6) (6 2) (3 4))) returns T.


3. (to make up for the array problem)
Consider the following function:
(define listoflists->matrix (ll)
  ; requires: each element of ll has the same length
  (cons 'matrix lst))
This function turns a list of lists (such as ((2 3) (4 5))) into an ``matrix'',
by representing the matrix as a list whose car is the symbol matrix
and whose cdr is the original list.
Each element of the original list represents a "row" of the matrix.
We will call such a list a matrix for the purposes of this problem.
Your task is to program the following functions.
a. (matrix-get matr i j) returns the element of the matrix in the ith row
and the jth column,
and the symbol get-error otherwise.
For example, (matrix-get (listoflists->matrix '((3 5) (7 11) (13 17))) 1 2)
returns 5, while (matrix-get (listoflists->matrix '((3 5) (7 11) (13 17))) 2 1)
returns 7.

b. (matrix-size mat) returns a list with the number of rows and the number
of columns, in that order.
For example, (matrix-size (listoflists->matrix '((3 5) (7 11) (13 17))))
returns the list (3 2).

c. (array-update mat i j x) returns a new matrix that is like mat
except that its (i,j)th element is the value of x.
For example, 
(array-get (array-update (listoflists->matrix '((3 5) (7 11) (13 17)))
                         1 2 99)
           1 2)
returns 99.


4. (was extra credit)


5. (to make up for the subst problem)
Write a program (insert-before new old ls) that builds a list obtained
by inserting new before each (top-level) occurrence of the item old in the
list ls.
You may assume that an ``item'' is either a number or a symbol.
For example,
(insert-before 'z 'a '(a b a c a)) returns (z a b z a c z a),
(insert-before 0 1 '(0 1 0 1)) returns (0 0 1 0 0 1)
(insert-before 'strange 'dog '(my dog is fun)) returns (my strange dog is fun),
and
(insert-before 'two 'one '()) returns ().


6. (to make up for problems 5a and 5b on page 61.)
Do problems 5c and 5d on page 61.

7. (to make up for the lolga code problem)
The country lalgo has a secret code that works as follows.
The message, written as a LISP list, such as
(a t t a c k - a t - d a w n),
is transformed twice, first by reversing each half of the list,
(- k c a t t a n w a d - t a),
and then by reversing all sequences of nonvowels
(including - and other punctuation),
in this case yielding
(c k - a t t a w n a t - d a).
Write a LISP function {\tt code} that both encodes messages.
The case of letters does not matter; i.e., {\tt a} vs. {\tt A}.
The vowels are a, e, i, o, and u.

A comment about "reversing each half of a list".  Call the function
that does this "inside-out".  Then (inside-out '()) = (),
(inside-out '(a)) = (a), (inside-out '(a b)) = (a b),
(inside-out '(a b c d)) = (b a d c) and
(inside-out '(a b c d e)) = (b a c e d).
That is, for a list with an odd number of elements,
the middle element is left alone.