ECE 332:202, Discrete MathematicsExam 2Spring 2007Exam Type: BInstructions: The exam consists of two parts. The first part is 20 multiple choice questions (at 4 points each).The second part is a single “long” question (worth 20 points). Fill in the bubble answer sheet for the first part,and write your answer to the long question following that problem. You will turn in the bubble answer sheet andthe answer to the long question.Multiple Choice1. Find the length of a shortest path and a shortest path in the graph below from a to z.abcdzjihef32325763624455577244g4(a) Length 11, path (a, b, c, g).(b) Length 19, path (a, e, f, g, z).(c) Length 12, path (a, b, c, d, z).(d) Length 10, path (a, b, c, d, z).2. Consider an alphabet A,B,C,D. When we transmit a letter it is sometimes corrupted by noise. Assume thatthere is a probability p = 0.1 of error. To protect the communication from errors, instead of transmittingonce, we transmit the same letter three times in a row (e.g. to send C we send CCC). The receiver will decodethe message by deciding the letter that occurs the most. If there is no single letter that is most frequent,then the message is not decoded. For example, CBC will be decoded as a ’C’. What is the probability thatthe receiver correctly decodes a transmission?(a) (0.9)3(b) (0.1)2(c) (0.9)3+ 3(0.9)2(0.1)(d) 1 − (0.1)33. Suppose we have a bit value of 0 with probability p, and a value of 1 with probability 1 − p. A measure ofthe randomness of this event is H(p) = −p log2p − (1 − p) log2(1 − p). Find the value for p which makesH(p) maximum.(a) p = 0.5(b) p = 0(c) p = 1(d) p =√2/24. An unfair coin gives heads with probability p. If the coin is flipped 5 times, what is the probability of having3 heads and 2 tails?(a) p3(1 − p)2(b)¡52¢p3(1 − p)2(c)¡53¢p5(1 − p)2(d) p35. Professor Smith has a class of 40 people. Is there a greater than 50% chance that two or more people havethe same birth date in this class? (Assume that the likelihood of a birth is equal for each of the 365 days ina year, and that there are no twins in the class).2(a) Yes(b) No(c) Not enough information is provided to answer this question6. How many 5-permutations are there of 11 distinct objects?(a) 11! + 5(b) 11 · 5(c) 11!/5!(d) 11 · 10 · 9 · 8 · 77. Scooby DooT Mhas come upon a haunted house and would like to decide whether to enter the house. Todo so, he decides to use a strategy involving a biased coin, which has probability of heads as34and a fair6-faced dice. Scooby Doo will roll the fair 6-faced dice and will decide to flip the biased coin only when aneven number results from the roll of the dice. After that, only if the flip happens and the result is a HEADS,will Scooby decide to stay away from the haunted house. What is the probability that Scooby decided tostay away from the haunted house?(a)312(b)512(c)14(d)388. Determine the number of strings that can be formed by rearranging the letters SCHOOL? (Note: Becareful, there are two O’s!)(a) 6!/2!(b) 6!(c) 2! · 6!(d) None of the above answers9. How many integer solutions are there to the equation x1+ x2+ x3= 15 subject to the constraints thatx1≥ 1, x2≥ 1, x3≥ 1?(a)¡12+3−112¢(b) 15 · 3(c)¡123¢(d) None of the above answers10. Find the number of terms in the expansion of (w + x + y + z)12.(a) C(12 + 4 − 1, 12)(b) C(12 + 4, 12)(c) C(12, 4)(d) None of the above answers11. Find the coefficient of s6t6in (2s − t)12.(a) −59136(b)¡126¢(c) 59136(d) −¡126¢12. An urn contains two black balls and three white balls. Two balls are selected at random from the urn withoutreplacement, and the sequence of colors is noted. What is the probability that the second ball is white?3(a)35(b)12(c)34(d) None of the above13. In the graph that follows, give an explanation for why there is no path from a back to a that passes througheach edge exactly once.ABCD(a) There are vertices of odd degree, namely {B, D}.(b) There are vertices of even degree, namely {A, C}.(c) There are vertices of even degree, namely {B, D}.(d) There are vertices of odd degree, namely {A, C}.14. Determine how many strings can b e formed by rearranging the letters ABCDE so that the letters ACE aretogether but may be in any order.(a) 3! · 3!(b) 5!/3!(c) 5!(d) 5! · 3!15. How many 8 bit strings contain three 0’s in a row and five 1’s?(a) 6(b) 8!/3!(c) 3! · 5!(d) 1216. A card is selected at random from a normal deck of 52 cards. What is the probability that it is a QUEEN?(a)14(b)113(c)152(d) None of the above answers17. What is the probability of getting three heads when I flip a fair coin three times?(a) 1/8(b) 1/3(c) 3/8(d) None of the above answers18. How many ways are there to choose 5 items out of a set of 8 distinct items?(a) 8 · 5(b)¡85¢4(c)8!5!(d) None of the above answers19. Let A and B be events and P (A) denote the probability of an event A. Which of the following statementsis generally not true?(a) P (A ∪ B) = P (A) + P (B) − P (A ∩B)(b) P (AC) = 1 − P (A)(c) P (A ∩ B) = P (A)P (B)(d) None of the above20. How many ways can four hands of cards, containing five cards each, be dealt from a deck of 52 cards?(a)¡5220¢(b) 5 ·¡524¢(c)52!5!5!5!5!32!(d)52!5!5!5!5!5Long Problem:(20 pts) Determine whether or not the graph below contains a Hamiltonian cycle. If there is a Hamiltoniancycle, then show it; otherwise, give an argument that shows why there is no Hamiltonian