Problem Set III, for Monday, April 20

Mathematics 61

Analysis of Algorithms (online or page 168 in DM6e):

• 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 DM6e 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, page 60 in DM6e):

• 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 DM6e):

• Exercise 2.   Use induction.   (There may also be a non-induction solution.)

Sequences and Strings (page 63 in Discrete Source, page 112 in DM6e):

• 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.

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.