472
Relations, Functions, and Matrices
section 5.6
1. 37 ≡ 15 (mod 11)
2. When searching a hash table for a particular target
value, first apply the hash function to the value to
obtain the hash table index, then examine the table
entry at that index. If the table entry stored there
matches the target value, the search was successful;
if not, the search fails.
3. A Caesar cipher with a shift k = 5 will encode “W”
as “B.”
4. In the RSA algorithm, the public key is (n, e). Security derives from the difficulty of computing
w(n).
5. The check digit in the ISBN-10 0-321-18059-3 is
correct.
section 5.7
1. Two matrices that do not have the same dimensions
cannot be added.
2. If a and b are square matrices, then a # b = b # a.
3. The usual algorithm for matrix multiplication is
Θ(n
3
).
4. The process of Gaussian elimination reduces the
augmented matrix of a system of n linear equations
in n unknowns to the n × n identity matrix.
5. If a and b are square Boolean matrices, then
a × b = b × a, where a × b denotes the Boolean product.
o n t h e c o m p u t e R
For Exercises 1–17, write a computer program that
produces the desired output from the given input.
1. Input: The elements in a finite set S and a list of
ordered pairs representing a binary relation on S
Output: Statement indicating whether the relation
is one-to-one, one-to-many, many-to-one, or manyto-many
2. Input: The elements in a finite set S and two lists of
ordered pairs representing two binary relations on S
Output: The ordered pairs in the union and in the
intersection of the two relations, and the ordered
pairs in the complements of each relation
3. Input: The elements in a finite set S and a list of
ordered pairs representing a binary relation on S
Output: Statement of which properties—reflexive,
symmetric, transitive, and/or antisymmetric—the
relation has
4. Input: The elements in a finite set S and a list of
ordered pairs representing a binary relation on S
Output: Reflexive, symmetric, and transitive closures of the relation
5. Input: The elements in a finite set S and a list of ordered pairs representing a partial ordering on S
Output: A list of all minimal and maximal elements
6. Input: The elements in a finite set S and a list of
ordered pairs representing a partial ordering on S
Output: A list of any least or greatest elements.
Note that this task is more difficult than that in Exercise 5.
7. Input: The elements in a finite set S, a list of ordered pairs representing an equivalence relation
on S, and an element x of S
Output: The members of [x]
8. Input: Array representations of relation tables and
appropriate input data for restrict, project, and join
operations
Output: Array representations of the resulting relation tables
9. Input: The elements in a finite set S and a list of
ordered pairs representing a partial ordering on S
Output: Sequence representing the total ordering
that results from doing a topological sort (Hint:
Reuse some of your code from Exercise 5.)
10. Input: The elements in a finite set S and in a finite
set T, and a list of ordered pairs representing a binary relation on S × T
Output: An indication of whether the relation is a
function from S to T and if so, whether it is onto or
one-to-one or both