Test two key --- Spring 1997 Discrete Structures --- problems 1-6 page one 1. Consider the set A = {a, b, c, d, e}. What about the lists of length 5 over the set A? 0 1 2 3 4 5 5 Recall that Lists[A] = A U A U A U A U A U A U ... and then focus on A which is the set of all lists of length 5, made up of the characters in set A. 5 What is the cardinality of A ? 5 times 5 times 5 times 5 times 5 or 5 to the 5th power, since we have 5 choices for the first character, 5 choices for the second element, etc. 2. What is P(5, 5)? The number of permutations of 5 items taken 5 at a time is: 5! or 5*4*3*2*1 or 120 permutations of these 5 letters. 3. Consider the set of permutations of set A. Store each permutation as a list. Give two distinct permutations that would result in the same binary search tree. and and and and and are SIX distinct permutations that result in ONE and the same binary search tree. c a) What are the two lists (permutations)? / \ b) Draw the single binary search tree either of b d the two lists would create. / \ a e Note that this is a BEST CASE binary search tree, for trees consisting of 5 nodes. How many best case binary search trees of size n=5 are there? How many of the 120 permutations does this set of search trees consume? 4. What would be the worst case performance value for binary search trees consisting of 5 nodes? Show your work please. Example trees from the equivalence class of worst case trees of 5 nodes. (Oh, how tall the trees do grow!) # of comparisons to get to searched for item: e a 1 / \ a b + 2 \ \ d c + 3 / \ b d + 4 \ \ c e + 5 ----- 15 comparisons 15 comparisons divided by 5 successful searches == 15/5 == 3.0 will be average successful search cost for these worst case trees. 5. What would be the best case performance value for binary search trees consisting of 5 nodes? c 1 / \ a d + 2 + 2 \ \ b e + 3 + 3 --------- 11 total comparisons for all five searches, 11/5 = 2 1/5 or 2.2 is the average successful search cost, or average number of comparisons needed to successfully find one of the five items in a best case, balanced, branchy, not too tall, tree. 6. Prove the following by mathematical induction, for all n > 0. 1 + 5 + 9 + ... + (4n - 3) = n(2n - 1) Basis step: Show for n = 1 (4n - 3) = (4 times 1 - 3) = 4-3 = 1 n(2n - 1) = 1(2 times 1 - 1) = 1(2-1) = 1 Shown for n = 1 Inductive step: Assume as the I.H. that the statement holds for n = k, i.e. 1 + 5 + ... + (4k - 3) = k(2k - 1) (Given) Try to show that the statement holds for n = k + 1, i.e. 1 + 5 + ... + (4(k+1) - 3) = (k+1)(2(k+1) - 1) (Goal) What do we start with? Oh yes, the LHS of the (Goal), of the k+1! 1 + 5 + ... + (4k - 3) + (4(k + 1) - 3) = k(2k - 1) + (4(k + 1) - 3) by the (Given), by the I.H. (Inductive Hypothesis) We started with the LHS of the (Goal), the k+1, and we saw the LHS of the (Given), the LHS of the k, or I.H., was part of the LHS of the (Goal). We substituted the RHS of the I.H. here in the LHS of the (Goal). This is known as using the assumption, using the Inductive Hypothesis. And we are always very explicit about what the assumption is (beginning of the inductive step) and then the using of it somewhere in the inductive step of the proof. Now that the substitution is made, we can try to transform the entire equation further forward toward the goal of seeing that it is just the the RHS of the k + 1 step, the (Goal) in disguise. 2 k(2k - 1) + (4(k + 1) - 3) = 2k - k + 4k + 4 - 3 2 = 2k + 3k + 1 = (2k + 1)(k + 1) = (k + 1)(2k + 1) = (k + 1)(2(k+1) - 1) Shown RHS of the k + 1, of the goal, has been reached! The RHS of the goal has been reached by starting with the LHS of the goal, the n = k+1 step. In moving from the LHS to the RHS we used the I.H., seeing k+1 k+1 the LHS hiding in the LHS and substituting RHS for LHS there to k k+1 k k move toward the victorious conclusion of the Ghostbusting expedition, and the entrapment of the slimer in the Ectocontainment system known as inductive proof. It was eventually seen that all along the RHS was hiding in the k+1 LHS k+1 and only needed some assistance from the I.H. to be released, or entrapped, or whatever. There is a moment in Ghostbusters after the slimer up on 12th floor of the Hotel Sedgwick, where our three heroes are in the ballroom and about to successfully entrap their first ever slimer, free floating vaporous apparition, when Dr. Peter Venkman says: Okay, Ray take my right, Egon, take the left side. RHS and LHS reference to inductive proofs, proofs of implications. Who knows? It could be. Or just a reference to the fact that Venkmanization is the center of and the beginning of and the foundation for the entire problem solving or proving process. 8. isBrotherOf is transitive only. John isBrotherOf Mary, but not (Mary isBrotherOf John) is an example of why it is not symmetric. It is not reflexive, in the usual sense of the term. When you ask an only child who happens to be male, if he has any brothers or sisters it would be quite a surprise to hear, yes, just one brother, myself. isFatherOf is not transitive, not reflexive, not symmetric. x isFatherOf y and y isFatherOf z does describe a binary relation, the isGrandFatherOf relation is what ties x and z together here in a binary relationship. isEastOf on the set {Iowa, California, New York} is transitive (New York isEastOf Iowa and Iowa isEastOf California, and indeed, New York isEastOf California), no symmetric relation property and no reflexive property for the isEastOf binary relation. You might want to review your definitions of antisymmetric and irreflexive for the final exam. I will ask about all FIVE properties for any similar questions on the final. -------------------------------------------------------------------------- PLEASE IGNORE THE BigOH, as we DID NOT COVER THIS IN FALL OF 99 DISCRETE. Ignore problem 9.a., but note that 9.b. is useful review of BIG THETA, which we have covered and which will be on the final exam. --------------------------------------------------------------------------- 9. a. Is f(n) = BigOh( g(n) ) when f(n) = 3 2 and g(n) = 1 3 2 n + 3 n -- n 10 Yes, the witnesses c and m that would work are: c = 50 and m = 1 since f(n) <= (50)( g(n) ) for all n >= 1 c m 3 Why choose 50? To get 5 n and thus keep 2 n cubed plus 3 n squared in line..... from the very beginning, n = 1 is the beginning. Other witnesses work too. For example: m = 10 and c = 23 are witnesses too. 23 3 2,000 + 300 = 2,300 <= -- times 10 = 2,300 10 f(n) g(n) 9.b. Is f(n) = BigTheta( g(n) )? Yes, we can find values or witnesses c, d and m to testify to that fact. c g(n) <= f(n) <= d g= m, using c = 1, d = 23, m = 10. Note that we could choose c = 20 but if the function is obviously <= without an assist, we do not need to call in any expert witnesses, c = 1 can step forward and be enough witness. n 9.c. For h(n) = 2 , is f(n) = BigTheta( h(n) )? Nope. Cannot be done! The two functions are NOT equivalent and there are not three witnesses in all the world of Natural numbers that can step forward and establish the fact! 10. Smallest relation on {a, b, c} that is not transitive? Edges set E = { , } is smallest. You have aRb and bRc but you do not have aRc. ---------------- --------------- P Q If you have P and you do not have Q, you do not have a transitive relation or property. If aRb and bRc then aRc is FALSE here. 11. Smallest relation on {a, b, c} that is reflexive and symmetric? -------- Edges set E is too hard to draw using Cobra email graphics, so showing the edges E as a set of ordered pairs, we have: E = { , , } and the needed 3 edges to make the set of 3 vertices into a reflexive relation, i.e. xRx for all x, every one of them! Symmetric, no edges needed, because of the implication definition of symmetry: if xRy then yRx