Answers to Review Questions for Prelim II

CS 280 - Spring 2002

The exam takes place in class on Friday, April 5. I will try to arrive early so that we can start right at 1:25pm.

The use of extra material is not permitted during the exam (i.e., no textbook, no notes, no calculator, etc.).

The exam includes material from readings and lecture through Monday, April 1.  See the Schedule for a list of topics covered in lecture and for the corresponding readings.  The exam will attempt to gauge your knowledge and understanding of course concepts. You shouldn't need to memorize specific code given in the text or in lecture.

The review questions given here are not meant to exhaust the possible topics for exam questions.  Consider reviewing both the homework assignments and the appropriate sections of the text.

Most of these questions are from exams given in previous incarnations of cs280.

Please let me know via email (chew@cs.cornell.edu) if you discover mistakes in my solutions.  Past experience indicates that I may have made some.

  1. The English alphabet contains 5 vowels and 21 consonants.
    1. How many strings of 6 lowercase English letters contain exactly 2 vowels if each letter can be used as often as you like?
      There are C(6, 2) ways to choose the positions for the two vowels.  There are 52 ways to assign vowels to those positions and 214 ways to assign consonants to the remaining positions.  The final answer is thus 52214C(6,2).
    2. How many strings of 6 lowercase English letters contain exactly 2 vowels if no letter is allowed to be used more than once?
      As before, there are C(6,2) ways to choose position for the two vowels.  There are 5*4 ways to assign vowels to these positions and 21*20*19*18 ways to assign consonants to the remaining positions.  The final answer is thus C(6,2)*5*4*21*20*19*18.
  2.  
    1. What's the minimum number of people that must be chosen to be sure that at least 2 have the same first initial?
      There are 26 possible first initials, so we must have two with the same initial if we have 27 people.
    2. What's the minimum number of people that must be chosen to be sure that at least 3 have the same birth month and were born on the same day of the week (Sat, Sun, Mon, etc.)?
      There are 12*7=84 (month, day) pairs.  Each such pair corresponds to a "pigeonhole".  Two people in each hole would require 168 people.  Thus, if we have 169 people there must be at least one pigeonhole with 3 people in it.
    3. Suppose there are 50 people with ages between 1 and 98 (1 and 98 are allowed).  Show that either there are 2 people with the same age or two whose ages are consecutive integers.
      Create 49 pigeonholes by pairing adjacent numbers starting with (1,2) and ending with (97,98).  Since there are 50 people, at least one pigeonhole has two people in it.  These two people are either the same age or their ages are consecutive integers.
  3.  
    1. How many bit strings contain exactly six 0's and nine1's if every 0 must be immediately followed by a 1?
      Since every zero is followed by a 1, you can think of "01" as a single unit; call this unit z.  The question can now be rewritten as: How many strings contain exactly 6 z's and 3 1's?  Thus there are 9 slots to fill and 3 of them must hold 1's.  This is just C(9, 3).
    2. How many solutions are there to the equation x1 + x2 + x3 + x4 = 35, if each xj is a positive integer (i.e., 1 or bigger)?
      This can be thought of as 4 bins into which we must distribute 35 stars given that each bin must hold at least one star.  The 4 bins correspond to 3 bars.  Four stars are used to ensure that each bin has at least one star.  This leaves us with C(3+31, 3) = C(34, 3) possible star/bar strings.
  4.  
    1. Find the number of elements in A1 U A2 U A3 if there are 100 elements in each set and there are 25 common elements in each pair and 10 elements in the intersection of all 3 sets.
      Use Inclusion/Exclusion. |A1 U A2 U A3| = |A1| + |A2| + |A3| - |A1 int A2| - |A2 int A3| - |A1 int A3| + |A1 int A2 int A3| where int is being used to represent the set-intersection operation.  So the answer is 100 + 100 + 100 - 25 - 25 -25 + 10 = 235.
    2. Suppose an experiment consists of choosing one of the elements of A1 U A2 U A3 at random with equal probability (where these three sets have the number of elements and intersections as given in part (a)).  Are the events A1 and A2 independent?
      By definition, A1 and A2 are independent if P(A1 int A2) = P(A1)*P(A2).  We size of our universe is 235, so P(A1 int A2) = 25 / 235 and P(A1) = P(A2) = 100 / 235.  Thus, we compare 25 / 235 with (100 / 235)2.  These are different, so the events are not independent.
  5. The dice in question are standard six-sided fair dice, and rolling a number with more than one die refers to the sum of the numbers showing on the dice.
    1. What is the probability of rolling a 5 with 2 dice?
      There are 4 ways to roll a 5 ((1,4), (2,3), (3,2), (4,1)) out 36 equally likely possible rolls, so the probability is 4 / 36 = 1 / 9.
    2. What is the probability of rolling a 5 with 3 dice?
      You need two ones and a three or you need one one and two twos to roll a 5.  Each of these can be rolled in 3 different ways, so we have 6 / 63 or 1 / 36.
  6. What is the expected sum that appears on 2 dice, where each of the dice is biased so that 3 appear with probability 0.3 and the other 5 numbers all have equal probability?  (For this problem, do the arithmetic to determine the expected value as a number.)
    The expected value for one die is 0.3*3 + (0.7 / 5) * (1 + 2 + 4 + 5 + 6) = 0.9 + 0.14*(18) = 3.42.  For two dice we would have the sum of two such values or 6.84.
  7. How many strings of length n=6 have two consecutive 0's?
    It's easiest to determine how many strings have no consecutive zeros and then subtract.  The number of strings with no consecutive zeros is
    1 string with no zeros +
    6 strings with one zero +
    C(5, 2) = 10 strings with two zeros [the two zeros make 3 bins; the center bin has at least one 1 in it] +
    C(4, 1) = 4 strings with three zeros [the three zeros make 4 bins; the center two each have one 1] =
    21 strings with no consecutive zeros.
    Since there are 26 = 64 strings of zeros and ones, this leaves 43 strings containing two (or more) consecutive zeros.
  8.  
    1. Prove by induction that 7n − 2n is divisible by 5 for all positive integers n.
      Basis: 71 - 21 = 5 which is divisible by 5.
      Induction Hypothesis: 7k - 2k is divisible by 5 for some k.
      Consider 7k+1 - 2k+1.  We can rewrite this as
      7k+1 - 2k+1 = 7(7k - 2k) + 7(2k) - 2(2k) =  7(7k - 2k) + 5(2k).
      The first term is divisible by 5 by the Induction Hypothesis.  The second term obviously has a factor of 5.  Since both terms are divisible by 5 the whole expression is divisible by 5.
    2. What is wrong with the following "proof"? 
      Let A(n) be a proposition "any n numbers are equal". We establish A(n) for all positive n by induction.
      BASIS STEP: A(1) states that one number is equal to itself, which is obviously true. 
      INDUCTIVE STEP. Suppose A(k), i.e., any k numbers are equal (the induction hypothesis). Take an arbitrary set X of k + 1 numbers and remove one of them, say a. By the induction hypothesis, all numbers in the remaining set X−{a} of k numbers are equal to each other. Remove another element b from X. By the induction hypothesis, all numbers from X−{b} are also equal. Therefore all numbers from X are equal to a and to b.
      The induction fails when |X|=2.
  9.  
    1. A soccer team has 20 women in the roster; two of them are goalkeepers. One goalkeeper and 10 field players make a team. How many ways are there to combine a team from those in the roster?
      There are 2 possible goalkeepers and then C(18,10) ways to choose the remaining field players.  The final answer is 2*C(18,10).
    2. Find the coefficient of x4y7 in (3x − 2y)11.
      From the Binomial Theorem, the coefficient is C(11, 4)34(-2)7 = -C(11, 4)3427.
    3. How many ways are there to order letters in the word NEVERTHELESS?
      If the letters were all different, the answer would be 12!, but E occurs 4 times and S occurs twice, so we have to divide by the number of permutation of 4 and 2 items.  The final answer is 
      12! / (4! 2!).
    4. How many solutions are there to the inequality x + y < 19 where x and y are nonnegative integers with x < 15 and y < 15?
      We can change the problem into one involving equality by observing that a solution to x + y < 19 is also a solution to x + y + z = 19, and vice versa.  We now have 19 objects to distribute into 3 bins (i.e., 19 stars and 2 bars), so there are C(21, 2) solutions, but this doesn't take into account the restriction that we want both x and y to be < 15.  We can count how many solutions fail this restriction.  We can start with 16 stars in the x-bin; this leaves 3 more stars to place into 3 bins or C(5,2) solutions.  There are the same number of solutions with 16 stars in the y-bin and these sets of solutions are disjoint.  Thus the final answer is C(21, 2) - 2*C(5, 2) = 210 - 20 = 190.
  10. In bridge, the 52 cards are dealt to four players.
    1. How many different ways are there to deal bridge hands to four players?
      C(52, 13) * C(39, 13) * C(26, 13) * C(13, 13) = 52! / (13!)4.
    2. What is the probability that all four aces went to one hand?
      There are C(48, 9) * C(39, 13) * C(26, 13) * 1 ways for all 4 aces to be in the first player's hand.  Thus there are 4 times this many ways to get all 4 aces into one hand.  The resulting probability is
      4 * C(48, 9) / C(52, 13).
    3. Assume that the player number one got a hand without aces. What is the probability that there is a player who has a hand containing all four aces?
      Restating the question: Find P(a player has all 4 aces | player 1 has no aces).  By the definition of conditional probability, this is the same as
      P(a player has all 4 aces and player 1 has no aces) / P(player 1 has no aces).  From (b), the numerator is 3 * C(48, 9) / C(52, 13).  The denominator is 
      [C(48, 13) * C(39, 13) * C(26, 13)] / [C(52, 13) * C(39, 13) * C(26, 13)].  The denominator can be rewritten as C(48, 13) / C(52, 13).  The final answer is thus 3 * C(48, 9) / C(48, 13).
  11. A pair of fair dice is rolled.
    1. What are the expected values of the minimum m and the maximum M of numbers on the dice?
      There are 11 ways to roll 2 dice that result in a minimum of 1; thus, the P(m=1) = 11/36.  Similarly, P(m=2) = 9/36 and P(m=3) = 7/36 and P(m=4) = 5/36 and P(m=5) = 3/36 and P(m=6) = 1/36.  The expected value of m is thus 11/36 + (2)9/36 + (3)7/36 + (4)5/36 + (5)3/36 + (6)1/36 = [11 + 18 + 21 + 20 + 15 + 6] / 36 = 91/36.  Using similar reasoning, the expected value of M is (1)1/36 + (2)3/36 + (3) 5/36 + (4)7/36 + (5)9/36 + (6)11/36 = [1 + 6 + 15 + 28 + 45 + 66] / 36 = 161 / 36.
    2. Are the random variables m and M independent?
      No.  To be independent, we would need P(m=1 and M=1) = P(m=1) * P(M=1).  But P(m=1 and M=1) is 1/36, while P(m=1)*P(M=1) = (11/36) * (1/36).  These are clearly not equal.
    3. Find the expected value of m + M.
      We know from properties of expected value that E(m+M) = E(m) + E(M).  Thus the answer is (91 + 161) / 36 = 152 / 36.
    4. Find the expected value of m * M.
      Since m and M are not independent, it is not the case that E(m*M) = E(m)*E(M).  One way to work out this problem is to laboriously go through all the probabilities for the possible values of m and M.  There is, however, a shorter way.  Observe that m*M is the same as X*Y where X is the value on one die and Y is the value on the other.  Note that even though m and M are not independent, X and Y are independent.  Thus E(m*M) = E(X*Y) = E(X) * E(Y) = (7/2)(7/2) = 49/4.
  12. How many positive integers with five digits or less have neither their first digit equal to 3 nor their last digit equal to 5?
    There are 105 -1 positive integers with 5 or fewer digits (the -1 is needed because 0 is not a positive integer).  Of these, there are 104 that have 5 digits and have their first digit equal to 3; 103 that have 4 digits; 102 with 3 digits; 10 with 2 digits and 1 with 1 digit.  Thus, there are 11111 numbers with their first digit equal to 3.  There are 104 numbers with 5 or fewer digits that have there last digit equal to 5.  This is almost all we need, but we also need to determine how many number have both their first digit equal to 3 and their last digit equal to 5.  There are 103 such number with 5 digits, 102 with 4 digits, 10 with 3 digits, and 1 with two digits; 1111 all together.  Using inclusion/exclusion, the final answer is 99999 - 11111 - 10000 + 1111 = 79999.
  13. How many positive integers are there less than 10000 such that the sum of their decimal digits is 12?
    This can be restated as: How many solutions are there to w+x+y+z = 12 where each variable is a nonnegative integer < 9?  If we ignore the < 9 restriction, there are 4 bins (i.e., 3 bars) and 12 stars, giving C(15, 3) solutions.  We have to subtract those solutions that include a value greater than 9.  We can put 10 stars into the w-bin, leaving 2 stars to distribute among the 4 bins; thus, there are C(5, 2) solutions where w>9.  Similarly, there are C(5, 2) = 10 solutions where x > 9, 10 solutions where y>9, and 10 solutions where z>9.  Further all of these solutions are disjoint.  Thus the final answer is C(15, 3) - 4*10 = 455 - 40 = 415.
  14. A fair coin is tossed five times.  What is the probability of getting exactly four heads, given that at least one of the tosses is heads?
    P(exactly 4 heads | at least one toss is heads) 
    = P(exactly 4 heads and at least one toss is heads) / P(at least one toss is heads)
    P(exactly 4 heads and at least on toss is heads) = P(exactly 4 heads) = 5/32
    P(at least one toss is heads) = 1 - P(all tails) = 31/32
    Thus the final answer is 5/31.
  15. Some tribe values boys so much that each of their families keeps making kids until they get a boy (after which they relax and make no more kids). On the other hand, no family can a afford having more than five kids.  So if the first five babies in a family are girls, the family stops making children anyway.  Assuming that a boy and a girl are equally likely, consider two random variables X -“the number of boys in a family ”,Y -“the number of girls in a family ”. 
    1. Find the expected values E(X) and E(Y) and compare them.
      E(X) = (1/32)*0 + (31/32)*1 = 31/32
      E(Y) = (1/4)*1 + (1/8)*2 + (1/16)*3 + (1/32)*4 + (1/32)*5 = [8 + 8 + 6 + 4 + 5] / 32 = 31/32.
      The expected values are identical.
    2. Are X and Y independent?
      No.  Observe that Y=5 implies that X=0.
      In more detail, P(Y=5 and X=0) = 1/32 which is not the same as P(Y=5)*P(X=0) = (1/32)2.
    3. Find the expected value E(X+Y).
      This is just E(X) + E(Y) = 31 / 16.
  16. A small grocery store carries 400 items and does 1000 transactions in one day.  For three particular items (bananas, strawberries, and yogurt) we have the following data: Suppose we're interested in how fruit sales affect yogurt sales where fruit, for this store, is either bananas or strawberries.  Find the support and confidence factors for each of the following association rules:
    1. bananas -> yogurt
      Support = 25/1000 = 2.5%.
      Confidence = #(bananas, yogurt) / #(bananas) = 25 / 35 = 5 / 7.
    2. strawberries -> yogurt
      Support = 30/1000 = 3%.
      Confidence = #(strawberries, yogurt) / #(strawberries) = 30 / 45 = 2 / 3.
    3. bananas, strawberries -> yogurt
      Support = 10/1000 = 1%.
      Confidence = #(bananas, strawberries, yogurt) / #(bananas, strawberries) = 10 / 20 = 1 / 2.
    4. fruit -> yogurt
      For this one, we need to know how many transactions involve fruit.  We add #(bananas) to #(strawberries), but we have to subtract #(bananas, strawberries) to avoid overcounting (i.e., inclusion/exclusion).  Thus the total number of fruit transactions is 35 + 45 - 20 = 60.  Similar reasoning is used to determine #(fruit, yogurt) = #(bananas, yogurt) + #(strawberries, yogurt) - #(bananas, strawberries, yogurt) = 25 + 30 - 10 = 45.
      Support = 45/1000 = 4.5%
      Confidence = #(fruit, yogurt) / #(fruit) = 45 / 60 = 3 / 4.