Note:

• The questions below are samples of the types of questions that will appear on Test #2 of I201/C251.
• It is doubtful that all these questions could be answered within one class’s worth of time, therefore, expect some subset of the questions that appear below.

1. Draw a tree diagram to show all the possible ways of answering a 3 question True/False quiz, starting with question #1.
   Answer:
   
   
2. Product Rule: How many license plates can be made with 3 letters and followed by 3 digits? Think AND.
   
   26*26*26*10*10*10

   Sum Rule: Only type one letter. How many different letter 'A' can be made using 5 different character fonts? Think OR.
   
   1+1+1+1+1
   
   Sum Rule: Only type one letter. How many different letters can be made using 5 different character fonts? Think OR.
   
   26+26+26+26+26

3. Sum and Product Rule: How many license plates can be made with 3 letters and followed by 2 digits or 2 letters and followed by 3 digits?

   26*26*26*10*10 + 26*26*10*10*10

4. How many 8-bit strings start with 00 and end with 111.
   Another way is to think of 8-bit string 00xxx111, which has 2³=8 different strings formed by xxx.
   
   
   Rule of Inclusion-Exclusion: How many 8-bit strings start with 00 OR end with 111?  Think Union.
   
   |A U B| = |A|+|B|-|AÇB| = 64+32-8 = 84
       A = 00xxxxxx |A|=2⁶=64
       B=xxxxx111, |B|=2⁵=32
       AÇB= 00xxx111, |AÇB|=2³=8
   
5. What principle should be used to answer the following question: “If there are 50 people in a room, then there is at least one month that has more than one person born in that month. What is the minimum number of people born in that month?”
   Use that principle to solve the “50 people in a room” question, above.
   Answers:
• pigeonhole principle
• épeople/monthsù = one month has at least this many people
  • If all 12 months had 4 people, 48 of the 50, the 2 remaining people could be born in different months making a month with at least 5.
  • é50/12ù  = 5

What is the minimum number of people to invite to have at least 3 people born the same month?

Answers:

éN/12ù  = 3

By pigeonhole principle, need 1 more than 2 people in each of 12 months:    N people = 2*12+1

é(2*12+1)/12ù  = é25/12ù  =  é2 1/12ù  = 3

or

By pigeonhole principle, need 2 people in each of 12 months plus 1 extra in any month:    N people = 2*12+1

é((3-1)*12+1)/12ù  = é25/12ù  =  é2 1/12ù  = 3

6. Of the following, which are “combination” problems, and which are “permutation” problems:
• How many ways are there to select the 1^st, 2^nd, 3^rd, and 4^th places from a field of 25 contestants?
  Answer: permutation, order matters.
  
• Five people arrive at a Coke machine to purchase a drink, how many different ways might those five people arrive at the machine?
  Answer: permutation, order matters
  
• How many hands of five cards can be dealt from a regular deck of cards?
  Answer: combination, order does not matter
  
• How many ways to have three 1's anywhere in an 8-bit string?
  Answer: combination, order does not matter, all 0's are the same, all 1's are the same. 00000111 same as 00000111
  
• How many ways can the string ABCDEFGH have ABC anywhere in the string?
  Answer: permutation, order does matter, ABCDEFGH is different than HABCDEFG
  
• How many ways to have three 1's at the low end of an 8-bit string?
  Answer: Not combination or permutation but product rule. There are 2⁵ ways for remaining 5 bits.

  xxxxx111
  
  

7. Apply based on your answer to 6 (above) apply C(n, r) or P(n, r) to come up with the actual number that answers the questions asked.
   Answers:
• P(25, 4) = 25!/(25-4)!
  
• P(5, 5) = 5!/(5-5)!
  
• C(52, 5) = 52!/5!(52-5!)
  
• C(8, 3) = 8!/3!(8-3)!
  
• P(6,6) = 6!/(6-6)!
  
8. With respect to combinations and permutations, when does order not matter and when does it matter? Give examples of each.
   Answers:
• Combination – order does not matter; example: being dealt a hand of cards, the hand is the same no matter what order the cards were dealt.
  
• Permutation – order does matter; example: who comes in 1^st, 2^nd, and 3^rd in a race
  
9. In mathematical probability, what do the following mean: Experiment; Sample Space; Successful Outcomes; p(E), where E = the set of successful outcomes; p(s) where s ÎS.
   Answers:

   • Experiment (in probability theory) - a procedure that yields one of a set of possible outcomes
     
   • Sample Space - All Possible Outcomes
     • A mathematical set containing all the possible outcomes of a probability experiment
     • S is often used to denote the sample space
       
   • Successful Outcomes
     • A mathematical set containing all the possible outcomes that meet some criteria for success
     • The criteria for success is determined prior to executing the experiment
     • E is often used to denote the set of successful outcomes
     • E Í S
       
   • Definition
     • If S is a finite sample space (i.e., a finite set of all possible outcomes from an experiment)
     • All outcomes in S are equally likely to occur when the experiment is executed
     • E is a set containing all the successful outcomes, and E Í S
     • Then the probability function, denoted as p(E) = |E| / |S|

   see the following web pages

for more:
• http://homepages.ius.edu/jholly/c251/notes/Chapter6/IntroDiscreteProb.htm
• http://homepages.ius.edu/jholly/c251/notes/Chapter6/ProbAssignment.htm
  
10. What is the probability that a card selected from a deck of cards is a King?
    Answer: 4 Kings (4 out of 52 cards) so 4 /52
    
    What is the probability that a card selected from a deck of cards is a Spade?
    Answer: 13 Spades (13 out of 52 cards);  13/52
    
    What is the probability that a card selected from a deck of cards is a King or a Spade?
    Answer: Use principle of inclusion-exclusion;

    4 Kings (4 out of 52 cards),
    13 Spades (13 out of 52 cards),
    however, 1 card is in both sets (i.e., King of Spades); so (4 + 13 – 1)/52
    
    A = King = {KS, KD, KH, KC}
    B = Spade = {AS, 2S, 3S, 4S, 5S, 6S, 7S, 8S, 9S, 10S, JS, QS, KS}
    
    |A U B| = |A|+|B|-|AÇB| = 4 + 13 - 1 = 16
    
    

11. In probability what is the result of evaluating the following:

    

    Answer: 1
    

12. In probability what is the meaning of the following: uniform distribution?, a fair experiment, a biased experiment, an equally likely outcome.
    Answer:
    
    • uniform distribution -

      for sample space S

      size |S| = n

      "s Î S : p(s) = 1/n

      which means all the outcomes in S are equally likely

    • equally likely - when each element in S (the sample space) has the same probability of being the outcome of an experiment
      
    • biased - when some elements in S have higher probability of being the outcome of an experiment as compared to other elements in S
      
    • fair - a probability experiment where any outcome in S is equally likely to occur
      
      For more, see - http://homepages.ius.edu/jholly/c251/notes/Chapter6/ProbAssignment.htm
      
13. In probability, what is the formula for evaluating the following: p(E | F)?
    Answer:

    Conditional probability, the probability of E given F

    E and F events and p(F) > 0

    p( E | F ) = p( E Ç F ) / p( F )

    For more, see - http://homepages.ius.edu/jholly/c251/notes/Chapter6/CondProb.htm

Fair coin is flipped five times

Determine the Conditional Probability

1. given the first flip is heads
2. AND exactly four heads appear?

Answer:

S, coin flipped five times, 2⁵ = 32 possible outcomes.

|S| = 32

F, given the first flip is heads, H.

|F| = 2⁴ = 16

p(F) = |F| / |S| = 16/32 = 1/2

E, exactly four heads appear in 5 tosses.

E = {HHHHT, HHHTH, HHTHH, HTHHH, THHHH}

|E| = C(5,4) = 5!/4!(5-4)! = 5!/4! = 5

E Ç F = {HHHHT, HHHTH, HHTHH, HTHHH}

p( E Ç F )

= |E Ç F| / |S|

= 4/32 = 1/8

p( E | F )

= p( E Ç F ) / p( F )

= 1/8 / 1/2 = 2/8 = 1/4

14.    Flip a fair coin 2 times.

t is drawn from the 2² possible outcomes of flipping a coin 2 times.

t Î {HH,HT,TH,TT}

What is X(t), the random variable for the number of tails that occur for outcome t?

Answer

t	X(t)
HH	X(HH)= 0
HT	X(HT)= 1
TH	X(TH)= 1
TT	X(TT)= 2

t is drawn from the 2² = 4 equally likely possible outcomes of flipping a coin 2 times.

X(t), the random variable for the number of tails that occur for outcome t.

Complete X(t) and the X(t) distribution, p(t).

Answer

t	X(t)	p(t) X(t) distribution
HH	X(HH)= 0	p(X=0) = 1/4
HT, TH	X(HT)=X(TH)= 1	p(X=1) = 2/4
TT	X(TT)= 2	p(X=2) = 1/4

Above is a diagram of a function.

· What is the domain of the function?

· What is the range of the function?

· In probability this function has a special name, what is it?

· What is the probability distribution for this function?

Answers:

· Domain = {HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}

· Range = {0, 1, 2, 3}

· Random Variable

· {(3, 1/8), (2, 3/8), (1, 3/8), (0, 1/8)}

t	X(t)	X(t) distribution p(t)
HHH	X(HHH)= 3	p(X=3) = 1/8
HHT HTH THH	X(HHT)= X(HTH)= X(THH)=2	p(X=2) = 3/8
HTT THT TTH	X(HTT)= X(THT)= X(TTH)=1	p(X=1) = 3/8
TTT	X(TTT)=0	p(X=0) = 1/8

15. What is the formula for the Expected value of a random variable?

    

16. What is the E(X), the expected value of X, for the random variable in #14.
    
    Answer: (p(HHH) * X(HHH)) + (p(HHT) * X(HHT)) + … + (p(TTT) * X(TTT))
    
    = (1/8 * 3) + (1/8 * 2) + (1/8 * 2) + (1/8 * 2) + (1/8 * 1) + (1/8 * 1) + (1/8 * 1) + (1/8 * 0)
    
    = (1/8 * 3) + (3/8 * 2) + (3/8 * 1) + (1/8 * 0)
    
    = 3/8 + 6/8 + 3/8
    
    = 12/8
    
    = 1.5
    

    t	X(t)	X(t) distribution p(t)	p(t)*X(t)
    HHH	X(HHH)= 3	p(X=3) = 1/8	1/8*3 = 3/8
    HHT HTH THH	X(HHT)= X(HTH)= X(THH)=2	p(X=2) = 3/8	3/8*2 = 6/8
    HTT THT TTH	X(HTT)= X(THT)= X(TTH)=1	p(X=1) = 3/8	3/8*1 = 3/8
    TTT	X(TTT)=0	p(X=0) = 1/8	1/8*0 = 0
    Sum			12/8 = 1.5

17. Conditional probability
    Conditional probability, the probability of E given F

    E and F events and p(F) > 0

    p( E | F ) = p( E Ç F ) / p( F )

    What is the probability of flipping exactly 2 heads given that the first of 3 flips is a head?
    
    S = {HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}
    
    F = first flip is a heads = {HHH, HHT, HTH, HTT}
    
        p(F)=|F|/|S|=4/8=1/2
    
    E = exactly 2 heads = {HHT,HTH,THH}
    
        E Ç F = {HHT, HTH}
    
        p(E Ç F) = |E Ç F| / |S| = 2/8=1/4
    
    p(E|F) = (1/4) / (1/2) = 1/2
    

18. Bayes Theory

    4% of computers are infected with the NasTeaSmell virus, p(Infected).
    
    97% of infected computers test positive when scanned for viruses, p(Positive | Infected) .
    
    2% of computers not infected test positive when scanned for viruses, p(Postive | Infective).

    Infected is event random computer is infected with the NasTeaSmell virus.
        p(Infected) = .04
    
        p(Infected) = .96 

    Positive is event random computer tests positive for NasTeaSmell virus.
    
        p(Positive | Infected) = .97
        p(Postive | Infected) = .03
    
        p(Postive | Infective) = .02
        p(Postive | Infected) = .98
    
    What is the probability a computer testing positive is infected?

    p(Infected|Postive) =

                           p(Postive | Infected) p(Infected) 
    _________________________________________________

               [p(Positive | Infected) p(Infected) + p(Postive | Infected) p(Infected)]

    =  .97*.04/[.97*.04+.02*.96]

     = .669

     __________________________

    Box 1 has 2 green and 7 red balls, 9 total.
    Box 2 has 4 green and 3 red balls, 7 total.

    Pick a ball from Box 1 or Box 2.

       Red is red ball drawn
       One is Box 1 picked

    p( One ) = 1/2
    p( One) = 1/2

    p( Red | One) = 7/9 
    p( Red | One) = 3/7

    p(One | Red) is probability picked from Box 1 given red ball drawn.

    p(One | Red) =

                           p(Red | One) p(One) 
    ____________________________________

               [p(Red | One) p( One ) + p(Red | One) p(One)]

                                =

                  7/9 * 12 
    ___________________

               [7/9 * 1/2 + 3/7 * 1/2]

    Recurrences

19. Find a₃ term of:

    a_n = a_n-1 + a_n-2

    a₁ = 3

    a₀ =4

    a₂ = 3+4=7
    
    a₃ = a₂ + a₁ =  7+3 = 10
    

20. Show that {a_n} is a solution to

    a_n = -4a_n-1 + 5a_n-2 if a_n = 1

    a_n = -4(1) + 5(1) = -4 + 5 = 1

    Show that the sequence {a_n} is a solution of the recurrence relation a_n = -3a_n-1+ 4a_n-2 if

    a_n = (-4)ⁿ

    a_n-1 = (-4)^n-1
    
    a_n-2 = (-4)^n-2

    an =	-3an-1+ 4an-2
    	= -3*(-4)^n-1+ 4*(-4)^n-2	Substitute
    	= (-4)^n-2 (-3*-4+4)	(-4)^n-1 is  -4*(-4)^n-2
    	= (-4)^n-2 16
    	= (-4)^n-2 (-4)^2
    	= (-4)^n

21. Find the solution for the recurrence relation:

    a_n = 3a_n-1

    a₀ =4

    a_n = 3a_n-1= 3(3a_n-2) = ... = 3^n-1(3a_n-n) = 3ⁿa₀ = 3ⁿ(4)

    
    

22. Find the solution for the recurrence relation:

    a_n = 3 + a_n-1

    a₀ =4
    
    a_n = 3 + a_n-1= 3 + (3+ a_n-2) = ... = 3(n-1)+(3 + a_n-n) = 3n + a₀ = 3n + 4

23. Compound Interest

    11% interest compounded annually

    P₀ = $10,000

    Find P₁ P₂ P₃

    P₁ = P₀ + 0.11P₀ = 1.11P₀

    P₂ = P₁ + 0.11P₁ = 1.11P₁ 

    P₃ = P₂ + 0.11P₂ = 1.11P₂ 

    Find Recurrence relation

    P_n = P_n-1 + 0.11P_n-1 = 1.11P_n-1

    Find closed form of P_n

    Pn	= 1.11Pn-1	Recurrence
    	=  1.11(1.11Pn-2)	Substitute      Pn-1= 1.11Pn-2
    	= 1.11(1.11(1.11Pn-3))	Substitute      Pn-2= 1.11Pn-3
    	:	Observe pattern
    	= 1.11^nPn-n
    	= 1.11^nP0	Closed form solution

    P_n = 1.11ⁿP₀

    Find amount in 30 years.

    Initial conditions

    P₀ = $10,000   

    P₃₀ = 1.11³⁰ * $10,000 = $228,922.97

24. Exercise 3, page 527.
    a

    	1	2	3	4
    1
    2		1	1	1
    3		1	1	1
    4

    transitive

    b

    	1	2	3	4
    1	1	1
    2	1	1
    3			1
    4				1

    reflexive, symmetric, transitive

    c

    	1	2	3	4
    1
    2				1
    3
    4		1

    symmetric

    d

    	1	2	3	4
    1		1
    2			1
    3				1
    4

    antisymmetric

    e

    	1	2	3	4
    1	1
    2		1
    3			1
    4				1

    reflexive, symmetric, antisymmetric, transitive

    f

    	1	2	3	4
    1			1	1
    2			1	1
    3	1			1
    4

    none

    

    

25. Exercise 5, page 536. Table 8, composite key with Airline field.
    
26. Exercise 11, page 536. Table 8, s_{Destination="Detroit"}?
    
27. Exercise 17, page 536. Table 8, P_1,4?
    
28. Exercise 19, page 536. Tables 9 and 10, J₂?
    
29. Exercise 1, page 542. Represent relation from set of tuples as zero-one matrix.
    
30. Exercise 3, page 542. Represent relation from zero-one matrix as set of tuples.
    
31. Exercise 21, page 543. Draw the digraph of a relation from  a zero-one matrix.
    
32. Exercise 1, page 553. Find the reflexive and symmetric closures.

    a

    	0	1	2	3
    0	1	1
    1		1	1
    2	1		1
    3	1			1

    b

    	0	1	2	3
    0		1	1	1
    1	1	1	1
    2	1	1	1
    3	1

    
    

33. Exercise 25a, page 554.

M^[2]R	1	2	3	4
1	1	0	1	0
2	0	1	0	1
3	1	0	0	0
4	0	1	0	0

=

MR	1	2	3	4
1	0	1	0	0
2	1	0	1	0
3	0	0	0	1
4	1	0	0	0

¤

MR	1	2	3	4
1	0	1	0	0
2	1	0	1	0
3	0	0	0	1
4	1	0	0	0

M^[3]R	1	2	3	4
1	0	1	0	1
2	1	0	1	0
3	0	1	0	0
4	1	0	1	0

=

M^[2]R	1	2	3	4
1	1	0	1	0
2	0	1	0	1
3	1	0	0	0
4	0	1	0	0

¤

MR	1	2	3	4
1	0	1	0	0
2	1	0	1	0
3	0	0	0	1
4	1	0	0	0

M^[4]R	1	2	3	4
1	1	0	1	0
2	0	1	0	1
3	1	0	1	0
4	0	1	0	1

=

M^[3]R	1	2	3	4
1	0	1	0	1
2	1	0	1	0
3	0	1	0	0
4	1	0	1	0

¤

MR	1	2	3	4
1	0	1	0	0
2	1	0	1	0
3	0	0	0	1
4	1	0	0	0

MR*	1	2	3	4
1	1	1	1	1
2	1	1	1	1
3	1	1	1	1
4	1	1	1	1

=

MR	1	2	3	4
1	0	1	0	0
2	1	0	1	0
3	0	0	0	1
4	1	0	0	0

v

M^[2]R	1	2	3	4
1	1	0	1	0
2	0	1	0	1
3	1	0	0	0
4	0	1	0	0

v

M^[3]R	1	2	3	4
1	0	1	0	1
2	1	0	1	0
3	0	1	0	0
4	1	0	1	0

v

M^[4]R	1	2	3	4
1	1	0	1	0
2	0	1	0	1
3	1	0	1	0
4	0	1	0	1