### Discrete Mathematics for Computer Science - Spring 2005 Review Questions and Information on the Final

The final will concetrate on the material from the second half of the course, but will also include some material from before the midterm. You may bring ONE PAGE OF NOTES. Some things you probably want on your page of notes:
• DeMorgan's Laws
• Negation of quantifiers
• Defintion of O(), Big-Theta().
• Bound on the n-th Harmonic Number
• Definition of C(n,k)
• Binomial Theorem
• Pascal's Identity
• Definition of transitive relation
• Euler's Formula

Review some proofs by induction, pidgeon-hole proofs, and combinatorial arguements for identites involving C(n,k) such as Theorem 4 on page 333. For practice, you can look at the following problems:

• Page 293, question 27.
• Page 311, question 33c.
• Page 319, question 21.
• Page 325, question 23.
• Page 333, question 21a.
• Page 556, question 43.
• Page 612, question 13.

• How many possible relations r:A->A are there which are equivalence relations with exactly two equivalence classes?
Answer: (2|A| /2)-1, since an equivalence relation with exactly two equivalence classes divides the elements of A into two subsets, so each pair of complementary subsets corresponds to an equivalence relation with two classes. We subtract one because the pair of compelementary subsets consisting of all of A and the empty set defines an equivalence relation with only one class.

• Consider the recurrence relation T(n) = T(floor(sqrt(n))) + m, where m is a constant. Give the best O() bound you can on T(n), and prove your result by induction.
Answer: First we need to figure out what bound to go for. We can write n=2x, so that n = log2x. Then the recurrence relation looks like:
T(x) = T(x/2) + m
We have seen in other problems that solution to this is O(log(x)), so the solution to the recurrence in terms of n should be O(log(log(n))). So we will prove using strong induction that T(n) is O(log(log(n))).
Basis step: T(4) is a constant, which is O(log(log(4)))= O(1).
Induction step: The inductive assumption is that T(i) is O(log(log(i))), for all 4 <= i <= n-1. Using this, we show that T(n) is O(log (log (n))).
T(n) = T(floor(sqrt(n))) + m <= c log(log(sqrt(n))) + m
by the inductive assumption, and
c log(log (sqrt(n))) + m = c log(log(n)) - c + m
This will be < c log(log(n)) if we choose any c > m. So T(n) is O(log (log (n)) using explict constants k=4 and c>m.