HKUST – Department of Computer Science and Engineering COMP 2711: Discrete Math Tools for CS – Spring 2012

#

Final Examination
Date: 25 May 2012 Time: 16:30–19:30 Venue: HALL

Name: Email:
Instructions

Student ID: Lecture and Tutorial:

• This is a closed book exam. It consists of 9 questions and 19 pages. • Please write your name, student ID, email, lecture section and tutorial on this page. • For each subsequent page, please write your student ID at the top of the page in the space provided. • Please sign the honor code statement on page 2. • Answer all the questions within the space provided on the examination paper. You may use the back of the pages for your rough work. The last three pages are scrap paper and may also be used for rough work. Each question is on a separate page. This is for clarity and is not meant to imply that each question requires a full page answer. Many can be answered using only a few lines. • Unless otherwise specified you must always explain how you derived your answer. A number without an explanation will be considered an incorrect answer.

Questions 1 2 3 4 5 6 7 8 9 Total Points 10 11 10 10 12 10 15 10 12 100 Score

Student ID:

As part of HKUST’s introduction of an honor code, the HKUST Senate has recommended that all students be asked to sign a brief declaration printed on examination answer books that their answers are their own work, and that they are aware of the regulations relating to academic integrity. Following this, please read and sign the declaration below.

I declare that the answers submitted for this examination are my own work. I understand that sanctions will be imposed, if I am found to have violated the University regulations governing academic integrity. Student’s Name: Student’s Signature:

2

Student ID:

Problem 1: [10 points] 1. Consider the recurrence below defined for n ≥ 0. T (n) = 1 4T (n − 1) + 6 if n = 0 if n > 0

Give a closed-form, exact solution to the recurrence. You only have to give the solution. You do not need to show how you derived it. 2. Prove the correctness of your solution by induction.

Solution: 1. By iterating the recurrence, we get: T (n) = 4n + 6 2. We need to prove: T (n) = 3 · 4n − 2. (1) 4n − 1 = 3 · 4n − 2. 4−1

Base case: When n = 1, T (0) = 1 = 3 · 40 − 2. Equation (1) is true. Inductive step: Now consider n > 1. Assume Equation (1) is true for the case of n − 1, i.e., T (n − 1) = 3 · 4n−1 − 2. For the case of n, we have T (n) = 4T (n − 1) + 6 = 4(3 · 4n−1 − 2) + 6 = 3 · 4n − 2.

(induction hypothesis)

By the weak principle of mathematical induction, we conclude that Equation (1) is true for all n ≥ 0.

Grading: 5, 5 .

3

Student ID:

Problem 2: [11 points] Let a be a non-negative real number and n be a non-negative integer that is a power of 3. Consider a function T (n) given by T (n) = 1 aT ( n ) + n2 3 if n = 1 if n > 1

1. Find a closed-form expression for T (n) by iterating the recurrence. Show the steps. 2. For which values of a is each of the following equations true? (i) T (n) = O(n2 )? (ii) T (n) = O(n2 log n)? (iii) T (n) = O(n3 )? For this part, it is not necessary for you to justify your answers.

Solution: 1. Let n = 3h for some integer h. If h > 1, we have

T (n) = = = =

T (3h ) aT (3h−1 ) + 32h a(aT (3h−2 ) + 32(h−1) + 32h a2 T (3h−2 ) + a32(h−1) + 32h . . . = ah T (3h−h ) + ah−1 32 + ah−2 34 + . . . + a32(h−1) + 32h 9 9 9 = ah (1 + + ( )2 + . . . + ( )h ) (∗) a a a 9 h+1 1 − (a) = ah assume a = 9 9 1 − (a)

=

ah+1 − 9h+1 a−9 aalog3 n − 9n2 = a−9 log3 a an − 9n2 = a−9

When a = 9, T (n) = ah (h + 1) = alog3 n (log3 n + 1) = nlog3 a (log3 n + 1) = n2 (log3 n + 1). 4

2. When a < 9, T (n) = When a = 9, T (n) = n2 (log3 n + 1) = O(n2 log n). When 9 < a ≤ 27, T (n) = anlog3 a − 9n2 = O(nlog3 a ) = O(n3 ) a−9 9n2 − anlog3 a = O(n2 ). 9−a

Note that when T (n) = O(n2 ) is true, T (n) = O(n2 log n) is also true; and when T (n) = O(n2 log n) is true, T (n) = O(n3 ) when a < 27 is also true. So the final answers are: • T (n) = O(n2 ) when a < 9 • T (n) = O(n2 log n) when a ≤ 9 • T (n) = O(n3 ) when a ≤ 27

Grading: 5, 6. For Part 1, 3 points for reaching (*), 1 point for a formula that involves only n, 1 for separating the case a = 9. For Part 2, 2 points for each sub-question. Note that a < 9 is also correct for (ii), but the bound is not tight. So give 1. For (iii), a ≤ 9 is also correct, but the bound is not tight. Give. 1

5

Student ID:

Problem 3: [10 points] Let n ≥ 1 be an integer that is a power of 2. Consider a function T (n) such that T (1) = 1 and, for n > 1, T (n) ≤ 8T (n/2) + 3n2 + 2n + 7. Prove that T (n) = O(n3 ). Solution: It suffices to show that there exist constants n0 , c1 > 0 and c2 > 0 such that T (n) ≤ c1 n3 − c2 n2 for all n > n0 . Set n0 = 0. Base case (n = 1): T (1) = 1 ≤ c1 13 −c2 12 = c1 −c2 . This is true when c1 ≥ c2 +1. Assume T (n) ≤ c1 n3 − c2 n2 is true for n = 2i where i = 0, · · · , j − 1. For n = 2j , T (n) ≤ ≤ = ≤ = ≤ 8T (n/2) + 3n2 + 2n + 7 8(c1 n3 /8 − c2 n2 /4) + 3n2 + 6n + 7 c1 n3 − c2 n2 − c2 n2 + 3n2 + 6n + 7 c1 n3 − c2 n2 − c2 n2 + 3n2 + 6n2 + 7n2 c1 n3 − c2 n2 + (16 − c2 )n2 c1 n 3 − c2 n 2 , when 16 − c2 ≤ 0.

By the principle of MI, we have proved that T (n) ≤ c1 n3 − c2 n2 when n0 = 0, c2 ≥ 16 and c1 ≥ c2 + 1. Thus, T (n) = O(n3 ).

Grading: 3 points if stronger inductive hypothesis is attempted, 2 points for the base case, 2 points if correct logic is employed for specifying the constraints, 3 points if the rest is correct.

6

Student ID:

Problem 4: [10 points] This question involves two bags of balls and two players. The first bag contains 1 red ball and 9 blue balls and the second bag contains 9 red balls and 1 blue ball. The two players are Tom and Jerry. They each pick one ball from one of the bags. Let Et be the event that the ball picked by Tom is red and Ej be the event that the ball picked by Jerry is red. 1. Tom picks one ball from the first bag and puts it back. Then Jerry picks one ball from the same bag. What are P (Et ), P (Ej ), and P (Ej |Et )? 2. Tom randomly chooses one bag, picks one ball from that bag and puts it back. Then Jerry picks one ball from the same bag. What are P (Et ), P (Ej ), and P (Ej |Et )? Explain how you obtain your answers. Note that if we know the bag from which Tom and Jerry pick the balls, Et and Ej are independent. The independence is not true if we do not know the bag. Solution:
1 1. Because there are 1 red ball and 9 blue balls in the first bag, P (Et ) = 10 . Because Tom puts his ball back to the bag, there are also 1 red ball and 9 1 blue balls in the first bag when Jerry picks his ball. So, P (Ej ) = 10 . 1 1 1 1 P (Ej |Et ) = P (Ej ∩ Et )/P (Et ) = P (Ej )P (Et )/P (Et ) = 10 × 10 / 10 = 10 .

2. Let B1 be the event that Tom picks the first bag, and B2 be the event that Tom picks the seond bag. We have 1 1 9 1 1 × + × = . 2 10 2 10 2

P (Et ) = P (B1 )P (Et |B1 ) + P (B2 )P (Et |B2 ) =

Because Tom puts his ball back to the bag, Jerry faces exactly the same situation as Tom. So, P (Ej ) = 1 . 2 Next consider P (Ej ∩ Et ): P (Ej ∩ Et ) = P (B1 )P (Ej ∩ Et |B1 ) + P (B2 )P (Ej ∩ Et |B2 ) = P (B1 )P (Ej |B1 )P (Et |B1 ) + P (B2 )P (Ej |B2 )P (Et |B2 ) 1 1 1 1 9 9 × × + × × = 2 10 10 2 10 10 82 = . 200 So, P (Ej |Et ) = P (Ej ∩ Et )/P (Et ) =
82 1 / 200 2

=

82 . 100

It is interesting to note that, in this case, P (Ej |Et ) = P (Ej ). 7

Grading: 4 (1, 1 2); 6 (1.5, 1.5, 3) .

8

Student ID:

Problem 5: [12 points] The professor of a class of n students is lazy and lets his students to grade their own homework. After the answer sheets are collected, he hands them back to the students randomly for grading. Each student gets one homework to grade. Tom, Jerry and Spike are three students in the class and they are friends. Let Ett be the event that Tom grades his own homework, and Et3 be the event that Tom grades the homework of one of the three friends (i.e., Tom, Jerry and Spike). The events Ejj , Ess , Ej3 and Es3 are defined similarly. 1. What is P (Ett )? 2. What is P (Ett ∪ Ejj ∪ Ess )? 3. What is P (Et3 )? 4. What is P (Et3 ∪ Ej3 ∪ Es3 )? Explain how you obtain your answers. Solution: 1. Similar to the backpack problem, a distribution of answer sheets to the students (outcome) is a permutation of [1, 2, ..., n]. Among all the n! equallylikely outcomes, Tom gets his own sheet in (n − 1)! of them. Therefore 1 P (Ett ) = (n−1)! = n n! 2. Using the same reasoning in part (1):
1 P (Ett ) = P (Ejj ) = P (Ess ) = n P (Ett ∩ Ejj ) = P (Ett ∩ Ess ) = P (Ejj ∩ Ess ) =

(n−2)! n!

=

1 n(n−1)

P (Ett ∩ Ejj ∩ Ess ) =

(n−3)! n!

=

1 n(n−1)(n−2)

Then, by the principle of inclusion and exclusion, P (Ett ∪ Ejj ∪ Ess ) = P (Ett ) + P (Ejj ) + P (Ess ) −P (Ett ∩ Ejj ) − P (Ett ∩ Ess ) − P (Ejj ∩ Ess ) +P (Ett ∩ Ejj ∩ Ess ) 3 1 3 − + = n n(n − 1) n(n − 1)(n − 2) 3(n − 1)(n − 2) − 3(n − 2) + 1 = n(n − 1)(n − 2) 2 3n − 12n + 13 = n(n − 1)(n − 2) 9

3. There are (n − 1)! outcomes where Tom gets his own homework. (Part (1)) Similarly, there are (n − 1)! outcomes where Tom gets Jerry’s homework. There are also (n − 1)! outcomes where Tom gets Spike’s homework. In total, there are 3(n − 1)! outcomes where Tom gets the homework of one of the three friends. 3 Hence, P (Et3 ) = 3(n−1)! = n n! 4. P (Et3 ) = P (Ej3 ) = P (Es3 ) =
3 n

Consider Et3 ∩ Ej3 . This is the event where Tom and Jerry both get any two of the three friends’ homework copies. There are 3 · 2 = 6 different possibilities. For each possibility, there are (n − 2)! corresponding outcomes. Therefore, the total number of outcomes for this event is 6(n − 2)!. 6 P (Et3 ∩ Ej3 ) = P (Et3 ∩ Es3 ) = P (Ej3 ∩ Es3 ) = 6(n−2)! = n(n−1) n! Consider Et3 ∩ Ej3 ∩ Es3 . This is the event where Tom, Jerry, and Spike all get one of the three friends’ homework copies. There are 3! = 6 different possibilities. For each possibility, there are (n−3)! corresponding outcomes. Therefore, the total number of outcomes for this event is 6(n − 3)!. 6 P (Et3 ∩ Ej3 ∩ Es3 ) = 6(n−3)! = n(n−1)(n−2) n! Then, by the principle of inclusion and exclusion, P (Et3 ∪ Ej3 ∪ Es3 ) = P (Et3 ) + P (Ej3 ) + P (Es3 ) −P (Et3 ∩ Ej3 ) − P (Et3 ∩ Es3 ) − P (Ej3 ∩ Es3 ) +P (Et3 ∩ Ej3 ∩ Es3 ) 9 18 6 − + = n n(n − 1) n(n − 1)(n − 2) 9(n − 1)(n − 2) − 18(n − 2) + 6 = n(n − 1)(n − 2) 2 3(3n − 15n + 20) = n(n − 1)(n − 2)

Grading: 2, 3, 2, 5 .

10

Student ID:

Problem 6: [10 points] Consider throwing m balls into n boxes. The probability of each 1 ball ending up in any given box is n . Let X be the number of balls in the first box and Y be the number of boxes that are empty. 1. What is E(X)? 2. What is V (X)? 3. What is E(Y )? Show the steps of your calculations. Solution: 1. E(X): This is a Bernoulli trials process with m trials and probability 1 success. Thus, by Theorem 5.12, E(X) = m n = m n
1 n

of

Alternative solution: Let Xi be the indicator random variable such that Xi = 1 if the i-th ball is in the first box, Xi = 0 otherwise. Obviously, X = m Xi . For 1 ≤ i ≤ m, i=1 1 E(Xi ) = P (ball i in the first box) = n . Therefore, m E(X) = E( i=1 m

Xi ) E(Xi )

= i=1 m

= i=1 1 n

m = n
1 2. V (X): This is a Bernoulli trials process with m trials and probability n of success. Thus, by Theorem 5.X (or L18:Theorem #2 for L2), V (X) = 1 1 m n 1 − n = m(n−1) . n2

Alternative solution: V (X) = V ( m Xi ) = m V (Xi ) since Xi and Xj are independent for i=1 i=1 i = j. 1 For 1 ≤ i ≤ m, V (Xi ) = (0 − E(Xi ))2 n−1 + (1 − E(Xi ))2 n = n 2 n−1 + (n−1) = n(n−1) = n−1 n3 n3 n3 n2 Therefore, V (X) = m n−1 = m(n−1) i=1 n2 n2 11

3. E(Y ): Let Yi be the indicator random variable such that Yi = 1 if box i is n empty, Yi = 0 otherwise. Obviously, Y = i=1 Yi . n−1 m . n

For 1 ≤ i ≤ n, E(Yi ) = P (box i is empty) = Therefore, n E(Y ) = E( i=1 n

Yi ) E(Yi )

= i=1 n

= i=1 n−1 n n−1 n m m

= n

Grading: 3, 3, 4.

12

Student ID:

Problem 7: [15 points] Consider a student who does an online practice test. He starts by getting a set of 10 problems from the computer. If he can solve at least 9 of the 10 problems, he stops. Otherwise, he continues by getting another set of 10 problems, and so on. Let X be the total number of problem sets that he works on. There are two scenarios regarding the probability p that he can solve each problem: (1) p = 0.8 and does not change over time, and (2) p = 0.8 for the first problem set, p = 0.9 for the second problem set, and p = 1.0 thereafter. 1. What is P (X = 1) in Scenario 1? Show the steps of calculation. 2. What is E(X) in Scenario 1? Explain your answer. 3. What is E(X) in Scenario 2? Show the steps of calculation. 4. In which scenario is V (X) larger? Answer this question based on your intuition. There is no need to calculate V (X).

Solution: 1. Test binomial distribution X = 1 means the student worked only 1 problem set, and then stopped. He needs to solve at least 9 of 10 problems in this first problem set. That is to say, he needs to solve 9 of 10 problems or solve all the 10 problems. Therefore, 10 9 P (X = 1) = p (1 − p) + p10 = 10 × 0.89 × 0.2 + 0.810 = 0.3758 9 2. Test expected time until first success X models the number of sets of problems (trials) the student tries (per1 forms) until the first success, so E(X) = probability of success . In Scenario 1, the probability of success (i.e., solve at least 9 out of 10 problems) does not change. Therefore, it is equal to P (X = 1) = 0.3758. 1 1 Consequently, E(X) = probability of success = 0.3758 = 2.6420 3. Test brute-force calculation of expectation In Scenario 2, the possible values for X are {1, 2, 3}. Let Yi be the event that the student can solve at least 9 of the 10 problems in ith problem set. P (Y1 ) = P (X = 1) = 0.3758 10 P (Y2 ) = (0.9)9 (1 − 0.9) + (0.9)10 = 10 × 0.99 × 0.1 + 0.910 = 0.7362 9 P (Y3 ) = 1 And then, we know P (X = 1) = 0.3758 13

¯ P (X = 2) = P (Y2 )P (Y1 ) = 0.7362 × (1 − 0.3758) = 0.4595 ¯ ¯ P (X = 3) = P (Y3 )P (Y2 )P (Y1 ) = 1 × (1 − 0.7362) × (1 − 0.3758) = 0.1647 Therefore, E(X) = 1 × 0.3758 + 2 × 0.4595 + 3 × 0.1647 = 1.7889 4. Answer: Scenario 1. Test intuitive understanding of variance.

Grading: 3, 3, 6, 3.

14

Student ID:

Problem 8: [10 points] Let n be a positive integer. Give a combinatorial proof of the following identity, 2n 2 =2 n + n2 2

An algebraic proof of this identity will not be accepted as a solution. Solution: - Left side: select two items from 2n items. - Right side: split 2n items into two parts, each containing n items. We have n ways to select two items from the first part, and n ways to select two 2 2 items from the second part. Moreover, there are n2 ways to select two items such that one is in the first part and the other in the second part. Observe that 2 n + n2 is total the number of ways to select two items from 2n items 2 (all possible cases: (i) the two items are in the first part, (ii) the two items are in the second part, (iii) one item is in the first part and the other in the second). Both left and right hand side are counting the number of ways to select two items from 2n items, so they are equal. Grading: 2 points for the left side, 3 points for attempting to split the 2n items, and 5 points for a correct explanation for the right side.

15

Student ID:

Problem 9: [12 points] Let a, e and n be three positive integers. 1. Describe the repeated squaring method for computing ae mod n. 2. Let T (e) be the number of multiplications carried out in repeated squaring. Prove that T (e) = O(log e). Solution:

1. Algorithm (a) Find 0 ≤ k1 < k2 ≤ . . . ≤ kt , such that e = 2k1 + 2k2 + . . . + 2kt • • • • To do this, first obtain the binary representation of e. Then scan the binary representation from right to left. The ki are just the locations of 1’s. Example: e = 50. Binary representation: 110010. The ki ’s: k1 = 1, k2 = 4, k3 = 5.

(b) Calculate: I0 = a and, for all i = 1, 2, . . . , kt , Ii = (Ii−1 )2 mod n (c) Calculate: ae mod n = (((Ik1 · Ik2 ) mod n) · · · Ikt ) mod n 2. Complexity • At Step 2, kt multipliations are performed. • At Step 3, no more the kt multiplication are performed. • So, T (e) ≤ 2kt . • On the other hand, e = 2k1 + 2k2 + . . . + 2kt ≥ 2kt • so, kt ≤ log2 e. (**) (***) (*)

• Hence T (e) ≤ 2kt ≤ 2 log2 e. • Therefore, T (e) = O(log e).

Grading: Algorithm: 6 points, 2 for each step, ok if the method for finding ki ’s is not described. Complexity analysis: 6 points, 2 for (*), 2 for (**), 2 for (***)

16