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.

  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?
    2. How many strings of 6 lowercase English letters contain exactly 2 vowels if no letter is allowed to be used more than once?
  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?
    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.)?
    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.
  3.  
    1. How many bit strings contain exactly six 0's and nine1's if every 0 must be immediately followed by a 1?
    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)?
  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.
    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?
  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?
    2. What is the probability of rolling a 5 with 3 dice?
  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.)
  7. How many strings of length n=6 have two consecutive 0's?
  8.  
    1. Prove by induction that 7n − 2n is divisible by 5 for all positive integers n.
    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.
  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?
    2. Find the coefficient of x4y7 in (3x − 2y)11.
    3. How many ways are there to order letters in the word NEVERTHELESS?
    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?
  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?
    2. What is the probability that all four aces went to one hand?
    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?
  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?
    2. Are the random variables m and M independent?
    3. Find the expected value of m + M.
    4. Find the expected value of m * M.
  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?
  13. How many positive integers are there less than 10000 such that the sum of their decimal digits is 12?
  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?
  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.
    2. Are X and Y independent?
    3. Find the expected value E(X+Y).
  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
    2. strawberries -> yogurt
    3. bananas, strawberries -> yogurt
    4. fruit -> yogurt