Discrete Structures Anna Karlin
CSE 321, Spring 2000
Practice Questions
from previous exams
1.
Define a set S of character strings over the alphabet {a,b} by the following rules:
Prove by induction that every string in S has at least as many a's as b's.

ANSWER :

We prove this by strong induction on the length of the string.

Basis :  if length=1, the string has to be "a", so the statement is true
              if length=2, the string is either "ab" or "aa", and in both cases the statement is true

I.H. For all 1<=k<n, strings of size k have at least as many a's as b's.

To show : String of size n (n>=3) has at least as many a's as b's.
Proof :
Let s be a string of size n.
Case #1:
    s can be written as axb, where x is a string in S of size n-2
    By I.H. x has at least as many a's as b's.
    Thus, s has at least as many a's as b's.

Case #2:
    s can be written as xy, where x and y are both in S. Notice that length of x is < n, and length of
    y   is < n
    By I.H. x and y each have at least as many a's as b's.
    Thus, s has at least as many a's as b's.

So, in both cases, s has at least as many a's as b's.
 
 

2.
True or false:
ANSWER : TRUE ANSWER : TRUE ANSWER : FALSE : Pr(A | B) = P(A and B)/ P(B)
  ANSWER : TRUE
 
3.
On the next set of questions, fill in the blanks.
  • The number of subsets of an n element set is
    • 2^n
  • The number of ways of choosing an unordered subset of size k out of a set of size r is


    • C(r,k) = r! / ( k! * (r-k)! )
     

  • The coefficient of x10 in the polynomial (5x+1)100 is

    • 5^10 * C(100,10)
  • The number of different binary relations from a set A of size n to a set B of size m is

    • 2^(m n)
     
  • The number of different reflexive binary relations on a set A of size n is

    • 2^(n^2 - n)
     
  • The number of different undirected graphs (no self loops and no parallel edges) on n vertices is

    • 2^( C(n,2) )
     
    4.
    Define a function g on the non-negative integers by g(0)=2, g(1)=3 and g(n+1)=3g(n)-2g(n-1) for all $n\ge 1$. Use strong induction to prove that for all $n\ge 0$,g(n)= 2n + 1.
    ANSWER : Proof by strong induction on n
    Basis : For n=0, g(0) = 2 = 2^0 +1
                 For n=1, g(1) = 3 = 2^1 + 1
    I.H. For all 0<= k <n, g(k) = 2^k +1
    To show : g(n) = 2^n +1
    g(n) = 3 g(n-1) - 2 g(n-2)
             = 3 (2^(n-1) + 1 ) - 2 ( 2^(n-2) +1 )            By I.H.
             = 2^(n-2) (6 -2) + 1
             = 2^n +1
    5.
    6.
    7. Suppose a biased coin with probability 3/4 of coming up heads is tossed independently 100 times.
    8. A lake contains n trout. 100 of them are caught, tagged and returned to the lake. Later another set of 100 trout are caught, selected independently from the first 100.
    9. At a casino, a two-ball version of roulette is played. Players place their bets as in the regular roulette, and collect winnings for each of the balls, e.g., if a player bets on red, and only one ball lands on red, he breaks even; if both balls land on red he wins his bet, and if none of the balls lands on red, he loses his bet. There are 18 red, 18 black and two green numbers in roulette. We assume that in the two-ball roulette the two balls cannot land on the same number, but they are equally likely to land on any pair of distinct numbers. For simplicity, assume that players only bet on red or black.
    10. A 3-person jury has two rational members, each of whom independently has a probability p of making the correct decision, and a third member who just flips a coin for each decision. The majority decision rules. A one-person jury has probability p of making the correct decision. Which jury has a better probability of making the correct decision? Justify your answer.
    ANSWER
    Pr[correct decision] = Pr[ Majority makes correct decision]
    Let's denote "c" for correct and "i" for incorrect
    Then, Pr[ Majority makes correct decision] = Pr["ccc", "cci", "cic","icc"]
                                                                             = p^2 *1/2 + p^2 *1/2 + p * (1-p) * 1/2 + (1-p) * p * 1/2
                                                                             = p^2 + p (1-p) = p
    Thus, the 3-person jury and the 1-person jury have the same probability of making the correct decision
    11. Consider the 5 letter words over an alphabet of 26 letters.
    12. A pitcher's record is 21 wins and 4 losses. Prove that he must have enjoyed a winning streak of 5 games.
    ANSWER
    It's an application of the pigeon hole principle. The 4 losses divide the season in a set of winning streaks
    (the one before the first loss, the one between the 1st loss and the second loss, etc.). These 5 streaks are our pigeon
    holes. We have 21 wins (pigeons), so there must be a pigeon hole with at least ceiling(21/5) = 5 pigeons in it.
     
    13. A standard deck of 52 cards is shuffled completely (i.e., any of the permutations is equally likely.) What is the probability that no two spades are adjacent in the shuffled deck?
    ANWER
    First, place the 39 non-spade cards. There are 39! ways to do so. Then, insert each spade between two non-spade cards
    (or at the beginning or at the end of the deck). There are 40 places where a spade can be inserted, and so the spades can
    be inserted in P(40,13) ways. Thus, the total number of decks where so two spades are adjacent is 39! * P(40,13) and the
    probability that this happens is 39! * P(40,13) / 52!
    14. Consider an undirected graph on n vertices generated as follows. For each pair of vertices, an edge between those vertices is included in the graph with probability p, and not included with probability 1-p. What is the expected number of edges in the graph?
    ANSWER
    Let X be the total number of edges in the graph
    There are C(n,2) possible pairs of vertices. Let's number them from 1 to C(n,2).
    Let Xi = 1 if i-th pair is chosen to form an edge, and 0 otherwise.
    E(Xi) = 1 * p + 0 ( 1-p) = p
    X = X1+X2+...X(C(n,2))
    E(X) = E(X1) + .... + E(X(C(n,2))) = C(n,2) * p