Homework 4 (due 4/30)
CSC 202

We finished Section 3.1 on relations and covered some material from Section 3.2. We started talking about searching in databases using linear search (Chapter 4). Next week we will finish Chapter 4 and continue by talking about puzzles, games, and combinatorics.

The midterm will be 5/7 for in-class students; for DL students, I will open registration sometime this week.

If you have any questions you want me to go over in preparation for the midterm, please send them to me by the end of the week (Sunday is fine).

Submission: you can submit the homework to me either by hardcopy in class or email it to me.

1. [Relations, 15pt] For each of the following relations R(x,y), state whether it is (a) reflexive, (b) symmetric and/or (c) transitive.

For each of the three properties briefly argue that the relation has the property or give a counterexample showing that it does not.

2. [Equivalence Classes, 10pt] Consider the relation R(x,y) = "|x| = |y|" over the universe of the real numbers, where |x| is the absolute value of x. E.g. |-3.5| = 3.5 and |19.3| = 19.3.

  1. [5pt] Show that R is an equivalence relation.
  2. [5pt] What are the equivalence classes of R?

3. [SQL Queries, 30] For each SQL query, please submit your SQL and a printout of the resulting table. Be careful writing both of these, and make sure you double-check that your output is what you expect it to be.

  1. [10pt] For each course, list how many undergraduate students are enrolled in this course (you do not need to list courses in which no undergraduate students are enrolled).
  2. [10pt] Find students that have joined more than one student group.
  3. [10pt] Find the president of the oldest student group.

4. [Relations, 12] On the natural numbers, {1,2,3, ...} we define a new relation a « b if a occurs in b as a sequence of digits. E.g. 3118 « 7131184 and 98 « 9820, but neither 1 « 928 nor 32 « 302.

  1. [6pt] Check whether « is reflexive, anti-symmetric and transitive and argue that it is or is not. Is it an ordering relation?
  2. [2pt] Is « total or partial? (Argue, or give counterexample).
  3. [4pt] A minimal element in an ordering is an x such that there is no y below x, that is, if y « x then y = x. What are the minimal elements of « ?

5. [Extra Credit] Suppose we have two sets A and B ordered by some ordering relation ≤. Show that the relation ≤ on A x B defined as

(a,b) ≤ (c,d) if a ≤ c, or a = c and b ≤ d

is an ordering relation of A x B (intuitively: first order by A, then by B). Hint: show ≤ on A x B is reflexive, anti-symmetric and transitive.

6. [Extra Credit] The pair (x,y) can be defined using just sets in such a way that (a,b) = (c,d) if and only if the sets belonging to (a,b) and (c,d) are the same. A first attempt might be to define (x,y) as {x,y}, but that does not work as we know, since (x,y) <> (y,x) but {x,y} = {y,x}. (The point of this exercise is that pairs are not really necessary, they can be defined using sets, rather like and can be defined using or and not.)

7. [Extra Credit] If you find any typos and mistakes in the lecture notes, please let me know.
Marcus Schaefer
Last updated: April 24th, 2007.