Problem 1(a)(b)(c)(d)(e)Problem 2(a)(b)(c)Problem 3Problem 4(a)(b)Problem 5Problem 6(a)(b)Problem 7(a)(b)Problem 8(a)(b)Problem 9Problem 10Problem 11(a)(b)(c)Problem 12(a)(b)Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science December 21 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised December 22, 2005, 1118 minutes Final Examination Your name: Circle the name of your Tutorial Instructor: David Hanson Jelani Sayan This exam is closed book, but you may have a one page, two-sided personal crib sheet. There are 12 problems totaling 200 points. Write your solutions in the space provided, if need be running over to the back of the page. Total time is 180 minutes. GOOD LUCK! DO NOT WRITE BELOW THIS LINE Problem Points Grade Grader 1 15 2 20 3 15 4 15 5 15 6 15 7 20 8 20 9 15 10 15 11 15 12 20 Total 200 Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld.Final Examination Your name: 2 Problem 1 (15 points). Induction Suppose S(n) is a predicate on natural numbers, n, and suppose ∀ k ∈ N S(k) −→ S(k + 2). (1) If (1) holds, some of the assertions below must always (A) hold, some can (C) hold but not always, and some can never (N) hold. Indicate which case applies for each of the assertions by circling the correct letter. (a) (3 points) A N C (∀ n ≤ 100 S(n)) ∧ (∀ n > 100 ¬ S(n)) (b) (3 points) A N C S(1) −→ ∀ n S(2n + 1) (c) (3 points) A N C [∃ n S(2n)] −→ ∀ n S(2n + 2) (d) (3 points) A N C ∃ n ∃ m > n [S(2n) ∧ ¬ S(2m)] (e) (3 points) A N C [∃ n S(n)] −→ ∀ n ∃ m > n S(m)3 Final Examination Your name: Problem 2 (20 points). State Machines We will describe a process that operates on sequences of numbers. The process will start with a sequence that is some permutation of the length 6n sequence (1, 2, . . . , n, 1, 2, . . . , 2n, 1, 2, . . . , 3n). (a) (5 points) Write a simple formula for the number of possible starting sequences. If (s1, . . . , sk) is a sequence of numbers, then the i and jth elements of the sequence are out of order if the number on the left is strictly larger the number on the right, that is, if i < j and si > sj. Otherwise, the ith and jth elements are in order. Define p(S)::= the number of “out-of-order” pairs of elements in a sequence, S. From the starting sequence, we carry out the following process: (*) Pick two consecutive elements in the current sequence, say the ith and (i + 1)st. I. If the elements are not in order, then switch them in the sequence and repeat step (*). II. If the elements are in order, remove both, resulting in a sequence that is shorter by two. Then pick another element and remove it as well. If the length of the resulting sequence is less than three, the process is over. Otherwise, reverse the sequence and repeat step (*). This process can be modelled as a state machine where the states are the sequences that appear at step (*).4 Final Examination Your name: (b) (5 points) Describe a simple state invariant predicate that immediately implies that if this process halts, then the final state is the sequence of length zero. (Just define the invariant; you need not prove it has the requisite properties.) (c) (10 points) Prove that this process always terminates by defining a nonnegative inte-ger valued derived variable that is strictly decreasing. (Just define the variable, you need not prove it has these properties.)�5 Final Examination Your name: Problem 3 (15 points). Equivalence Relations and Random Variables A random variable, X is said to match a random variable, Y , iff X and Y are on the same sample space and Pr {X = Y } = 0. Prove that “matches” is an equivalence relation. Hint: Note that Pr {X = Z} = Pr {[X = Z] [X = Y ]} + Pr {[X = Z] [X = Y ]}.� � ∩ � � ∩6 Final Examination Your name: Problem 4 (15 points). Planarity. (a) (8 points) Exhibit two planar drawings of the same 5-vertex graph in which a face in one drawing has more edges than any face in the other drawing. (b) (7 points) Prove that all planar drawings of the same graph have the same number of faces.7 Final Examination Your name: Problem 5 (15 points). Inclusion-exclusion A certain company wants to have security for their computer systems. So they have given everyone a name and password. A length 10 word containing each of the characters: a, d, e, f, i, l, o, p, r, s, is called a cword. A password will be a cword which does not contain any of the subwords ”fails”, ”failed”, or ”drop”. Use the Inclusion-exclusion Principle to find a simple formula for the number of pass-words.8 Final Examination Your name: Problem 6 (15 points). Number Theory and Induction (a) (5 points) Seashells are used for currency on a remote island. However, there are only huge shells worth 210 dollars and gigantic shells worth 312 dollars. Suppose islander A owes m > 0 dollars to islander B. Explain why the debt can be repaid through an exchange of shells provided A and B both have enough of each kind. (b) (10 points) Give an inductive proof that the Fibonacci numbers Fn and Fn+1 are rela-tively prime for all n≥ 0. The Fibonacci numbers are defined as follows: F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 (for n ≥ 2).9 Final Examination Your name: Problem 7 (20 points). Combinatorial Identities (a) (10 points) Give a combinatorial proof that n� �� n i = n2n−1 (2)i i=1 for all positive integers, n. (b) (10 points) Now use the fact that the expected number of heads in n tosses of a fair coin is n/2 to give a different proof of equation (2).10 Final Examination Your name: Problem 8 (20 points). Generating Functions Let an be the number of ways to fill a box with n doughnuts subject to the following constraints: • The number of glazed doughnuts must be odd. • The number of chocolate doughtnuts must be a multiple of 4. • The number of plain doughnuts is 0 or 2. • The number of sugar doughnuts is at most 1. (a) (8 points) Write a generating function for each of the four doughnut types: G(x) = C(x) = P (x) = S(x) = (b) (12 points) Derive a closed formula for an.11 Final Examination Your name: Problem 9 (15 points). Conditional Probability There are 3 children of different ages. What is the probability that at least two are boys, given that at least one of the two youngest children is a boy? Assume that each child is
View Full Document
Unlocking...