Problem Set III, for Monday, October 22

Mathematics 61

Analysis of Algorithms (online or page 168 in Discrete Mathematics):

Exercise 11. Support your answer.
Exercise 12. Support your answer. (Remember how to find the sum of a geometric series? See page 4 in Discrete Source or page 56 in Discrete Mathematics for a reminder.)
Exercise 51. Note that the function values are positive. If the statement is always true, explain why. If not, give a specific counterexample.
Exercise 58. (The point of this exercise is to demonstrate that subtraction of equivalence classes is not well defined.)
Let f(n) = 5n + 8 and let g(n) = n lg n (where lg n is the logarithm base-2 function). Determine whether f is O(g) and whether g is O(f).

Mathematical Induction (page 8 in Discrete Source or page 60 in Discrete Mathematics):

Exercise 6.
Exercise 25.
Assume that R is a transitive relation. Let R^n be the composition of R with itself, n times. Use induction and the definition of composition to prove that for each positive integer n,
whenever x R^n y then x R y.
(In other words, we want to show that R^n is a subset of R.)

Strong Form of Induction and the Well-Ordering Property (page 17 in Discrete Source or page 69 in Discrete Mathematics):

Sequences and Strings (page 63 in Discrete Source or page 112 in Discrete Mathematics):

Exercise 128. Use strong induction on the length of alpha (which must be even). There are three cases:
Case I: The length is 0.
Case II: The first and last letters in alpha are different.
Case III: The first and last letters in alpha are the same. In this case, seek an initial segment of alpha that has a balance between a's and b's.

Note: Problem Set III will be returned after the first midterm. Answers are posted as usual.

There are two online supplements for Analysis of algorithms, one on growth rates and one on preorder relations.

Click here for answers in .pdf format.