=========================preview======================
(comp170)[2009](s)final~PPSpider^_10156.pdf
Back to COMP170 Login to download
======================================================
COMP170: Discrete Mathematical Tools for Computer Science
Spring 2009
Final Exam
21 May 2009, 12:30C3:00pm, Rm 3007

Instructions
1.
This is a closed-book exam consisting of 11 questions.

2.
Please write your name, student number and email address on the cover page of the answer booklet.

3.
Please sign the honor code statement on the second page of the answer booklet.

4.
All answers must be put on the answer booklet. Only the answer booklet needs to be handed in at the end of the exam.

5.
In the answer booklet each question starts on a new page. This is for clarity and is not meant to imply that your answer needs to .ll up all the space provided.

6.
Unless otherwise speci.ed, you must always explain how you derived your answer. A number without an explanation will be considered an incorrect answer.

7.
Your answers may be written in terms of binomial coe.cients and falling factorials.

For example, 53 + 42 may be written instead of 16, and 53 instead of 60. Calculators may be used for the exam.

8.
Please do not use the nPk and nCk notation. Use nk and nk instead.

9.
Please put your student ID card on the desk so the TA can check it.

10.
All mobile phones must be turned o. completely during the exam or else you will be disquali.ed.


1.
n2n3 +3n2 + n
i2
= .
6
i=1
2. For any real number r .= 1,
n.1
. n
i 1 . r
r = .
1 . r
i=0
3. For any real number r .= 1,
. n+1 + r
nnrn+2 . (n + 1)r
iri = .
(1 . r)2
i=1
4. For any real number 0 <r< 1,
r(r + 1)
i2 i
r = .
(1 . r)3
i=1
5. Inclusion-exclusion theorem:
nn
PEi =(.1)k+1 P (Ei1 Ei2 Eik )
i=1 k=1 i1,i2,...,ik: 1i1<i2<<ikn
6. f(n)= O(g(n)) if there exist some integer n0 > 0 and some real number c> 0 such that .n n0,f(n) c g(n).
For each of the following parts, is the statement true or false?
You need to prove your answer, or else you will receive no mark even if the answer
(true or false) is correct.

(a)
Let n and k be nonnegative integers such that 0 k n. The identity

nk = nk k! always holds.

(b)
Let A and B be two .nite sets and f be an injective function from A to B. Then the size of B must be larger than that of A, i.e., |B| > |A|.

(c)
Because 1571 and 3534 are relatively prime, i.e., gcd(1571, 3534) = 1, we can set p = 1571 and q = 3534, n = pq, T =(p . 1)(q . 1) and so on to generate a public key and a secret key for using the RSA cryptosystem.

(d)
Let U be a universe consisting of all students, CS(x) be a predicate for x is a Computer Science student, and APlus(x) be a predicate for x gets an A+ grade. The statement there exists a Computer Science student who gets an A+ grade can be expressed as the following quanti.ed logical statement:


.x U CS(x) . APlus(x) .
(e) Let A and B be two events in some sample space S, and A be the complement of A in S. The conditional probabili