CS 70 Discrete Mathematics for CSSpring 2000 Wagner Sample FinalYou will have three hours for the final itself. This sample final is similar in style and scope to the actualfinal; however, it is rather longer than the actual final. The exam is open-book, open-notes. We have notassigned points to the questions (but we will do this for the final itself).1. (?? pts.) The longest common subsequence problemIn this question, we will need an induction principle for pairs of strings over an alphabet Σ. We say thata pair of strings (a0, b0) is “less than” another pair (a, b), written (a0, b0) ≺ (a, b), if |a0|+|b0| < |a|+|b|,where |a| denotes the length of string a ∈ Σ∗. Our induction principle is the following, where P(·, ·) isa proposition that applies to pairs of strings:• if ∀a, b ∈ Σ∗[∀a0, b0∈ Σ∗, (a0, b0) ≺ (a, b) ⇒ P(a0, b0)] ⇒ P(a, b)then ∀a, b ∈ Σ∗P(a, b).Now consider the following problem. A subsequence of a string a is any sequence that can be obtainedby deleting one or more (not necessarily consecutive) letters from a, leaving the order of the remainingletters unchanged. A longest common subsequence (written lcs) of two strings a and b is a sequence ofmaximum length that is a subsequence of both a and b. Thus for example a lcs of a = GACTTACCCAGTand b = GTTATGTACA is GATTACA; a lcs of a = ATT and b = GCG is the empty stringλ.Suppose we want to compute a lcs of two given strings, a and b. [This problem arises, for example,in DNA analysis and in file comparison utilities.] To make the notation simpler, we’ll actually justcompute the length of a lcs (which is essentially the same problem). Here is a suggested algorithm:algorithm lcs length(a,b)if a =λor b =λthen return(0)else if head(a) = head(b) then return(max{1+lcs length(tail(a), tail(b)), lcs length(a, tail(b)), lcs length(tail(a), b)})else return(max{lcs length(a, tail(b)), lcs length(tail(a), b)})Your task is to prove that this algorithm is correct, using the induction principle above.(a) Write down the proposition P(a,b) that you need to prove for all a, b ∈ Σ∗.(b) What are the base cases for the induction principle in this application? [Hint: There are infinitelymany of them!](c) Prove ∀a, b P(a, b) using the induction principle given above. Be careful to justify each step inyour argument.2. (?? pts.) Propositional logicProve each of the following statements:1(a) Given n propositional variables, there are exactly 3nlogically distinct (nonequivalent) 1-CNFexpressions. [Reminder: k-CNF is a restriction of CNF in which each clause has exactly kliterals.](b) If A |= B, then A |= B∨C, for any Boolean expressions A, B, C.(c) If the terms of a DNF expression D1are a subset of the terms of a DNF expression D2, thenD1|= D2. [Reminder: a term is a conjunction of literals.](d) Suppose D1, D2are DNF expressions with the property that, for every term Tiof D1, there is aterm Tjin D2such that the literals of Tjare a subset of the literals of Ti; then D1|= D2.(e) For every Boolean expression, there is an equivalent Boolean expression that uses only the NORoperator. [Hint: Use induction over Boolean expressions.]3. (?? pts.) A 300-year-old puzzleConsider the following game played by our old friends Alice and Bob. Alice rolls six fair dice andwins $1 if she gets at least one six (and wins nothing otherwise). Bob rolls twelve fair dice and wins$1 if at least two of them come up six (and wins nothing otherwise).(a) What is the expected number of sixes rolled by Alice?(b) What is the expected number of sixes rolled by Bob?(c) Which of the two players, if any, has a higher chance of winning something? [Hint: You mayfind it easier to calculate the probability of not winning.][Note: Apparently the great man of letters, Samuel Pepys, asked Sir Isaac Newton the question inpart (c) above way back in 1693. Despite years of effort, Newton was unable to convince Pepys of thecorrect answer.]4. (?? pts.) Probability; short answersLet X and Y be integer-valued random variables on the same probability space, with expectationsE(X) = E(Y) = 1. Which of the following statements is/are always true about X and Y? If you believethe statement to be true, give a brief justification referring to results from class; otherwise, give asimple counterexample.(a) E(2X +Y) = 3.(b) E(XY) = 1.(c) Var(2X) = 4Var(X).(d) Var(X +Y) = Var(X) + Var(Y).(e) Pr[X ≥ 3] ≤13.(f) Pr[X ≥ 3] ≤14Var(X).(g) Pr[X ≥ 1] > 0.(h) Pr[X ≥ 0∨Y ≥ 0] ≤ Pr[X ≥ 0] + Pr[Y ≥ 0].(i) Pr[X ≥ 0∧Y ≥ 0] ≤ Pr[X ≥ 0] × Pr[Y ≥ 0].(j) If Var(X) > Var(Y) then Pr[|X| > |Y|] > 0.5. (?? pts.) Decomposition of variancesThe number of job offers received by graduating seniors at Berkeley is determined largely by theirdepartment. Suppose that, among students graduating from department A, the number of job offersreceived has meanµ0and varianceσ20. Among students graduating from all other departments, theCS 70, Spring 2000, Sample Final 2number of job offers received has meanµ1and varianceσ21. Students graduating from department Aconstitute a fraction p of all graduating seniors at Berkeley, so the mean number of job offers amongall graduates is pµ0+ (1− p)µ1. In this problem, we will see how the variance of the number of joboffers among the population of all Berkeley graduates can also be found from the above quantities, andthat it decomposes as a sum of a “between-department” variance term, and two “within-department”variance terms.Suppose a graduating senior is chosen uniformly at random. Let the r.v. X denote the number of joboffers received by this senior, and define the r.v. Z byZ =(µ0if the senior is from Department A;µ1otherwise.[Note that E(Z) = E(X); you might find it helpful to verify this.]Show thatVar(X) = Var(Z) + pσ20+ (1− p)σ21.The first term on the right-hand side is the “between-department” variance, and the last two terms arethe “within-department” variances.6. (?? pts.) Arithmetic/polynomials; true or falseFor each of the following statements, say whether the statement is true or false. You need not provideany justification for your answer; however, you may be awarded partial credit for an incorrect answerif you attempt a justification. (And, of course, an attempt at a justification may help you to find anerror in your reasoning.)(a) For all integers a, b, d, if ad = bd mod n then a = b mod n(b) For all integers a, b, d, if ad = bd mod n then a = b modngcd(n,d).(c) For all
View Full Document
Unlocking...