DOC PREVIEW
Berkeley COMPSCI 70 - CS70 Review - Logic and Induction

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS70 Discrete Mathematics for Computer Science, Summer 2011Review ProblemsLogic and Induction1. True/FalseIn this question, let P and Q be predicates and n ∈ Z+. Which of the following statements are true for allP and Q and which may be false?Do not guess: incorrect answers may receive negative credit.(a) P (1) ∧ Q(2) ∧ [∀n. P (n) ⇒ P (n + 2)] ∧ [∀n. Q(n) ⇒ Q(n + 2)] =⇒ ∀n. ¬P (n) ⇒ Q(n)(b) P (1) ∧ Q(2) ∧ [∀n. P (n) ⇒ P (n + 2)] ∧ [∀n. Q(n) ⇒ Q(n + 2)] =⇒ ¬[∃n. ¬P (n) ∧ ¬Q(n + 1)](c) P (1) ∧ Q(2) ∧ [∀n. P (n) ⇒ P (n + 1)] ∧ [∀n. Q(n) ⇒ Q(n + 2)] =⇒ ∀n. P (n) ⇒ Q(n)(d) P (1) ∧ Q(2) ∧ [∀n. P (n) ⇒ Q(n + 1)] ∧ [∀n. Q(n + 1) ⇒ P (n)] =⇒ ∀n. P (n) ⇒ Q(n)2. Proofs(a) For all n ≥ 1, prove thatnXk=02 · 3k= 3n+1− 1.(b) Guess and prove a formula for1 − 2 + 3 − 4 + · · · + (−1)n−1n.You may give different formulas for the cases when n is odd and when it is even. Note that (−1)n−1is just 1 if n is odd and −1 if n is even.(c) Use induction to prove the following for all n ≥ 1:The number of ways to pick two items out of a given set of n items is n(n − 1)/2.(d) Prove by induction thatPni=02i= 2n+1− 1 for all n ∈ N.Stable Marriage3. TMA Algorithm(a) Consider the set of men M = {m1, m2, m3} with the following preferences on the set of women:• Pm1= {1, 2, 3};• Pm2= {1, 3, 2};• Pm3= {3, 1, 2},and the set of women W = {w1, w2, w3} with the following set of preferences on the set of men:• Pw1= {3, 1, 2};• Pw2= {3, 2, 1};• Pw3= {2, 3, 1}.Run the traditional marriage algorithm on this example. How many times does the main loop run untilreaching a stable matching in this case?(b) Suppose the traditional marriage algorithm is run to produce a man-optimal stable pairing. Supposethen that one of the men moves one of the women to whom he never proposed up higher in his prefer-ence list (but all other preference lists remain unchanged). Then must the pairing remain stable?(c) If man M does not propose to woman W in the traditional marriage algorithm, then can there be astable pairing in which M is matched with W ?Modular Arithmetic4. Prime TripletsThree numbers p, p + 2, p + 4 are a prime triplet if they are all primes. For example 3,5,7 are a prime triplet.Prove that there is no other prime triplet. [Hint: consider an argument modulo 3.]5. RSA(a) If p = 7, q = 13 and e = 5 then what is the private key according to the RSA algorithm?(b) If Alice wants to send the message m = 23, what is the encrypted message?6. Secret SharingThe 4 GSIs and 8 readers for CS70 wanted to share a secret. The secret s, which is a number between 0 and6, is split among them as below. Note that all operations and values are modulo 7.• The number s is split into two parts s1and s2such that s ≡ s1+ s2.• A degree 1 polynomial P1and a degree 2 polynomial P2are constructed such that P1(0) ≡ s1andP2(0) ≡ s2.• The 4 GSIs are given the values P1(1), P1(2), P1(3), P1(4), and the readers are given the valuesP2(1), P2(2), P2(3), P2(4), P2(5), P2(6), P2(8), P2(9).(a) Prove that the secret can be recovered only when at least 2 GSIs and at least 3 readers are present.(b) If 2 GSIs and 3 readers are present, is it always possible to recover the secret?(c) Suppose that 2 GSIs meet and exchange the information that P1(1) ≡ 5 and P1(2) ≡ 0. Also, 3readers exchange the information that P2(2) ≡ 0, P2(3) ≡ 2, and P2(5) ≡ 4. Using this information,find the secret.7. Erasure CodesA communication channel accepts only messages of length m packets. When a length-m message is trans-mitted, up to k of the packets will be lost by the channel.(a) Suppose you want to send a message on this channel. What is the maximum number of messagepackets you can send in one shot (excluding redundant packets) so that the message can be reliablyrecovered by the receiver? Explain your answer.(b) Assume now that m = 5 and k = 2, and suppose you want to send a message consisting of the sixdigits (0, 1, 2, 1, 2, 0). Describe a scheme to reliably send this message. You should give all the detailsrelated to your scheme, but you do not need to explain how the received message is decoded.(c) Now suppose you are told that, working over GF (5), the recipient receives the packets (3, 2, −, 1, −).What is the original message intended by the sender?Updated 12/13/10.Counting and Basic Probability8. A Tale of Two Proofs(a) Prove algebraically thatnr·rk=nk·n − kr − k.(b) Give a combinatorial proof for the above identity.9. ID DQDA UC Berkeley SID number has 8 digits. Every digit can be any number from 0 − 9. How many ways arethere to have:(a) An SID where no number repeats.(b) An SID where every digit is bigger than the previous digit.(c) An SID that is divisible by 3.(d) An SID where at least 1 number repeats.(e) An SID where exactly 1 number repeats exactly once.10. Keeping Count(a) Suppose we roll n dice and are only interested in how many dice came up with each number. Howmany different outcomes are possible?(b) A certain department offers 8 lower level courses L1, L2, · · · , L8and 10 higher level courses H1, H2, · · · , H10.A valid curriculum consists of 4 lower level courses and 3 higher level courses.(i) How many valid curricula are possible?(ii) Suppose that L1is a prerequisite for H1, · · · , H5(i.e. any curriculum that includes one ofH1, · · · , H5must also include L1) and L2and L3are prerequisites for H6, · · · , H10. Now howmany valid curricula are there?(c) The weather on any given day can be sunny, cloudy, rainy, or snowy. Assume four sequential seasons(fall, winter, spring, summer), that a snowy day can happen only during the winter, that a rainy daycannot happen in the summer, and that each season has 90 days. What is the number of all possibledistinct 360-day weather sequences (consecutive days)?11. Flipping a CoinWe flip a biased coin with probability p of getting heads until one of the following events occur:• we get heads;• we flipped the coin three times.(a) Describe the probability space and the probabilities for each point in the space.(b) What is the probability that we are still playing in the third round?(c) Are the events “heads on the second round” and “heads on the third round” disjoint? independent?(d) Given that we flipped more than once and that we did end up with heads, what is the probability thatwe got heads on the second flip? Again, conditioned


View Full Document

Berkeley COMPSCI 70 - CS70 Review - Logic and Induction

Documents in this Course
Notes 1

Notes 1

12 pages

Note 2

Note 2

6 pages

Notes

Notes

6 pages

Notes

Notes

7 pages

Note 10

Note 10

8 pages

n20

n20

10 pages

n19

n19

10 pages

n18

n18

10 pages

n17

n17

6 pages

n16

n16

9 pages

n15

n15

10 pages

n14

n14

9 pages

n13

n13

6 pages

n12

n12

7 pages

n11

n11

6 pages

n10

n10

8 pages

n9

n9

5 pages

n8

n8

7 pages

n7

n7

8 pages

n6

n6

5 pages

n5

n5

8 pages

n4

n4

7 pages

n3

n3

10 pages

n2

n2

7 pages

n1

n1

5 pages

Load more
Download CS70 Review - Logic and Induction
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS70 Review - Logic and Induction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS70 Review - Logic and Induction 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?