General

  1. Do you give partial credit for answers on tests? yes
  2. I believe I heard that the tests are open-book.  Is this true? yes

 

Section 2.3:

  1. Page 111, 13.  You went over this question in class.  You indicated that the expression for number of comparisons if the element is found in the list is (3n+4)/2.  I don’t see how you get this.

    I understand that if the element is not in the list that the worst case (2n+2 comparisons) must be used.  I also understand that if the element is in the list, 2i+1 comparisons must be used, where i = the element position.  Furthermore, I understand that in order to determine the average number of comparisons required when the element is in the list, the (sum from i=1 to n of (2i+1))/n must be used.  I just don’t understand how you get (3n+4)/2 from this.  Can you explain it?

 

If the element is in the list, we assume with equal probability of 1/n it is in the ith position. That is, with probability 1/n, it is the first element and the number of comparisons is 3, and with probability 1/n, it is in the second element and the number of comparisons is 5, etc. Consequently, the average number of comparisons is (3+5+…+(2n+1))/n = n+2 to find the element if the element is in the list. The number of comparisons is 2n+2 if the element is NOT in the list. Thus, given that ½ of the time the element is in the list and one half of the time the element is NOT in the list, the average number of comparisons is ½*(n+2) + ½*(2n+2) = (3n+4)/2.

 

Section 3.3:

  1. Page 210, 21.  The answer to this question is 5 Î S, and x + y Î S if x, y Î S.  How does this answer the question?  As far as I can tell, the solution does not state that only multiples of 5 are in S, does it?  My answer to this problem was, “F(1) = 5.  F(n) = F(n-1)+5.”  I assume this is wrong because I provided a recursive functional definition instead of a set definition, right?
     
    Correct. Your definition is for the function F(n)=5*n, not for the set S that contains positive integers that are multiples of 5. The answer in the back gives a correct recursive definition of the set. "5 is in S" defines the initial element in the set. "x+y is in S if x and y are in S" is the recursive rule that defines all other elements in the set.

    Follow-up:

    Would this also be a valid definition: 5     Î S and if x Î S, x + 5 Î S? Yes

  2. Page 210, 23.  Is the following definition (stolen from #21) a valid answer?  0 Î S and 2 Î S, and x + y Î S if x, y Î S

No. This only defines the set of non-negative even numbers. The answer in the back is correct.

 

Chapter 3, Review Questions:

1.      Page 227, 12-b.  I got through the basis step but can’t complete the inductive step.  Here is my solution so far:

Basis:  F(3):  2 >= (1.618)1
Induction:  F(n+1):  fn+1 >= alphan-1
                                    fn + fn-1 >= alphan-2 * alpha

Where do I go from here?  I can replace fn with alphan-2 but I don’t see where to go from there because I see no relationship between “+ fn-1” and “*alpha.”

 

This problem’s solution is on Example 6, page 205. It is a hard problem because you need to know alpha2 = alpha + 1.

 

2.      Questions 18-20, which you specified that we should do, seem to apply to section 3.5, which we did not cover.  Are we responsible for the content of this section?

 

No – you can skip these problems.

 

Section 4.1:

  1. Page 242, 13.  Why do they count the empty string as a valid element of this set?  The question asks, “How many bit strings with length not exceeding n, where n is a positive integer, consist entirely of 1s?”  The empty string consists of no bits.  How can it be comprised “entirely of 1s?”  The same question applies to problem 15.

 

The empty string can be considered consisting of, vacuously, entirely of 1’s although it contains zero 1’s.

Section 4.3:

  1. Page 258, 22.  Are these answers correct?  a) C(16, 5) – C(9, 5) = 4,242.  b) C(16, 5) – C(9, 5) – C(7,5) = 4,221.  Correct!

 

Section 5.1:

  1. Page 316, 9-c.  I’m having problems creating equations to express the nth term of a recurrence relation.  Are there any rules or tips that will help?

 

9-c requires you to find a “solution” of a recurrence relation. The only solution technique covered in Section 5.1 is to use “iterative” substitutions as discussed in Example 5. For this problem, the recurrence relation is an = an-1 + n (from 9-b) so using the principle of iterative substations, we have an = an-1 + n = (an-2 + (n-1)) + n = (an-3 + (n-2)) + (n-1) + n = a0 + 1 + 2 + 3 … + (n-2) + (n-1) + n = 0 + 1 + 2 + 3 … + (n-2) + (n-1) + n  = (n**2+n)/2.

 

  1. Page 316, 13-c.  We could determine a5, a6, …, a10 using the recurrence relation, but is there a better way?  For example, should we be able to convert the recurrence relation, an = 2an-1 + an-5 to a formula?  I’m not sure how to do this?

 

Section 5.2 covers more solution techniques to solve a recurrence relation to obtain a formula. The recurrence relation an = 2an-1 + an-5 is not solvable using the simple iterative substitution method, so this problem only asks you to solve a5, a6, etc using the recursive definition.

 

  1. Page 317, 17.  I have no idea how to get the recurrence relation for this problem.  I worked the problem but got a completely different answer than the one given in the back of the book.

 

This problem is similar to the example on the lecture slide.  The example I covered was for strings of length n that contain 3 consecutive 0’s. Problem 17 is for strings of length n that contains 2 consecutive 0’s. Use the same solution technique covered in the lecture to solve this problem.

 

  1. Page 317, 19.  I don’t know how to determine the recurrence relation.  I can intuit the relation by examining the results of the initial conditions and the first few values (e.g., a0-a4) but I can’t rely on this.

 

This problem is similar to Example 6 on page 313. Use the same solution technique there to solve this problem.

 

  1. Page 317, 21.  First, if there are 0 stairs, there are 0 ways to climb those stairs.  Why is a0 = 1?  Second, the answer indicates that the recurrence relation is an = an-1 + an-2 for n >=2.  If I consider a4, I get that there are 4 ways to climb the steps: {1-1-1-1, 1-2, 2-1, 2-2}.  This answer does not agree with the formula, however.  If one follows the formula, one gets 5 for a4.  What am I missing?

 

a0 = 1 because there is one way to climb 0 steps, i.e., do nothing.

a1 = 1 because there is one way to climb 1 step.

a2 = 2 because there are two ways to climb 2 steps, i.e., 1-1 and 2.

a3 = 3 because there are three ways to climb 3 steps, i.e., 1-1-1, 1-2 and 2-1.

a4 = 5 because there are five ways to climb 4 steps, i.e., 1-1-1-1, 1-1-2, 1-2-1, 2-1-1 and 2-2.

 

Thus the recursive relation an = an-1 + an-2 for n >=2 is correct. This is because to climb n steps, you can either start with one step and climb (n-1) steps or start with two steps and climb (n-2) steps.

 

  1. I skipped 25-35 because I didn’t know how to approach these problems.

 

#25 and #27 are considered “hard” (with *). However, you should try #35, the solution of which is similar to Example 7 on page 314.

Section 6.1:

  1. Page 380, Example 16.  I don’t understand how they arrived at 2**(n(n-1)) reflexive relations.  From page 377, “a relation R on a set A is called reflexive if (a, a) Î R for every element a Î A.”  I would think, therefore, that the number of reflexive relations on a set with n elements would be determined by the number of elements in the set, n, because the number of reflexive relations is |B| where B is {(b1, b1), (b2, b2), …,  (bn, bn)}.  What am I missing?

 

A relation is a set. So {(b1, b1), (b2, b2), …, (bn, bn)} is only one relation that is reflexive since it satisfies the definition. The set can be expanded by adding another pair, say, (b1, b2). The resulting set {(b1, b2), (b1, b1), (b2, b2), …,  (bn, bn)} is still reflexive. So the question essentially asks for how many ways you can add “other” pairs into {(b1, b1), (b2, b2), …,  (bn, bn)} such that the resulting set is still reflexive. Since there are n**2 – n = n(n-1) other pairs and each pair has two choices to be added or not to be added into {(b1, b1), (b2, b2), …,  (bn, bn)}, the number of ways is 2**(n(n-1)), i.e., the number of reflexive relations is 2**(n(n-1)).

Section 1.3:

  1. Page 34, 13-f – I think the answer in the back of the book is incorrect.  Shouldn’t the disjunction be a conjunction? 

    Yes, you are right. It should be a conjunction.

Section 1.5:

  1. Page 55, #45-c – The back of the book indicates that the answer should be {0, {0}}.  Shouldn’t the answer be {{0}, {{0}}}?

    No, the answer at the back is correct. A={0} and {A}={{0}}.  Therefore the union of these two sets will contain all elements in these two sets. The elements in these two sets are 0 and {0}, so the union set is {0,{0}}

 

Chapter 1 Summary:

  1. Page 94, 5-c – My answer to this question is “no.”  Is this answer correct?

    This question is a bit tough but the answer is yes. See exercise 34 and 36 in Section 1.2 on page 20.

  2. Page 95, 17-b – How can the sum be computed without specifying n?

    n is a variable indicating the upper bound, so the sum is 2**0 + 2**1 + ... + 2**n = 2**(n+1) - 1 based on the formula for geometric progression (Example 12 on page 74).

 

  1. Page 95-20 – Is this correct?  n! * 2n * 8nn-3 * 2n

    No, it is O(n**(n-2) * 2**n).  The reason is that the first product term yields O(n! * 2**n) and the second product term yields O(n**(n-2) * 2 **n) but n**(n-2) dominates n! so the second product term dominates the first product term and thus the Big-O is O(n**(n-2) * 2**n).

 

Section 3.1

  1. Page 184, 39.  The statement is obvious to me, so I don’t know how I can prove it other than to say that there is no integer that you can multiply by another integer that is > 1 or < -1 that will yield a result of 1.

    The proof is trival. You can prove by contradiction that m is neither 1 nor -1 then it is impossible for mn=1, so m must be either 1 or -1. In the former case, n=1 and the latter case n=-1. QED.

  2. Page 185, 45.  I don’t know how to solve this problem.
     
    Use direct proof.

    (a) If x is a positive number then let x = n**2 + m + epsilon where n is the largest perfect square integer less than x, m is a nonnegative integer and epsilon is between (0,1).  Then the equality holds since both sides yield sqrt(n**2 + m).

    (b) use a similar proof as in part a except considering x = n**2 - m - epsilon where n is the smallest perfect square integer greater than x.


  3. Page 184, 27.  I don’t know how to solve this problem.
     
    See example 18 on page 176 for a similar proof.

 

Section 3.2

 

  1. Page 201, #47.  I don’t understand this problem.

    The problem wants you to point out the error in using the induction proof. A proof likes this can be due to errors in the basis step or in the inductive step. In this problem, the error is in the inductive step where it says "the set of first n horses and the set of last n horses overlap, ...". This is not true for example when you consider n+1=2 horses. Obviously the first one horse and the last one horse are disjoint and have no overlap.

  1. Page 199, 5.  How do you find the formula for the sequence of numbers presented?

    It's a geometric progression with r=1/2. Use the formula in Example 12 on page 74.


  2. How does the second principle of mathematical induction (page 197) differ from mathematical induction (page 187)?

     They are equivalent. You may find the 2nd principle easier to apply for some questions such as the "stamp" problem in Example 14 on page 199.
     

Section 3.3:

  1. Page 210, 16 and 17.  These two questions require matrix algebra.  Are we responsible for knowing this?  Specifically, are we responsible for the calculation of determinants?

    No. You can safely pass these two questions.