Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CISC 203 - Assignment 3
Due: Thursday November 7 by 2:30 PM
(in the locked CISC 203 drop-off box on Goodwin 2nd floor)
One bonus mark for neatly written student information: Papers that have your name, student number and other information written exactly as requested in the regulations (found at the end), will receive one bonus mark.
1. (3 marks) A deck of cards contains 52 cards and four of the cards are kings (of four different suits).
What is the probability that a randomly selected 5 card poker hand contains exactly two kings? (This is called a “pair of kings”: the hand should not have more than two kings.)
2. (2 marks) Roll two fair dice and let the results be i and j, respectively. Define random variables X1((i, j)) = i and X2((i, j)) = j, that is, X1 is the value of the first die and X2 the value of the second die. Let Y1 = X1 + X2 and Y2 = 3 · X1 − X2.
Show that the random variables Y1 and Y2 are not independent.
Hint. To show a negative result you should give a concrete counter-example for the condition of independence.
3. (3 marks) Let X and Y be independent random variables on sample space S. Recall that V (X) is the variance of X. Prove that
V (X + Y ) = V (X) + V (Y )
Hint. You can assume known that for independent random variables E(XY ) = E(X)E(Y ) (Theorem 34.14 in the text).
4. (3 marks) Let X be a random variable that counts the number of heads that come up when a fair coin is tossed ten times. What is the variance of X?
Justify your answer.
Hint. You can use the equality from question 3.
5. (3 marks) Let Dn be the set of positive divisors of the integer n and consider the partially ordered set (Dn, |) ordered by divisibility. Draw the Hasse diagrams for the following partially ordered sets:
(a) (D6, |)
(b) (D12, |)
(c) (D18, |)
6. (2 marks) Let A = {2, 3, 4, 5, . . .} (= N − {0, 1}) be ordered by setting x ≤ y if x divides y (x, y ∈ A).
(a) Find all minimal elements of the infinite poset A.
(b) Find all maximal elements of the infinite poset A. Justify your answers!
7. An alphabet is a finite set Σ and elements of Σ are called symbols. The set of strings over Σ (denoted Σ∗ ) is defined inductively as follows:
Base step: ε ∈ Σ ∗ (where ε 6∈ Σ is the empty string containing no symbols).
Inductive step: If w ∈ Σ ∗ and b ∈ Σ then wb ∈ Σ ∗ .
The reversal (or mirror-image) of a string w, denoted w R, is the string obtained from w by writing the symbols in reverse order. For example, (abcd) R = dcba (where a, b, c, d are individual alphabet symbols).
The concatenation of strings w1 and w2, denoted w1 · w2, is the string obtained by appending symbols of w2 after the last symbol of w1. Note that w1 · ε = w1 and ε R = ε (where ε is the empty string).
(a) (1 mark) Give an inductive definition of the reversal of a string. Hint. First define the reversal of the empty string. For the inductive step should consider a string of the form w = xb, where x ∈ Σ ∗ and b ∈ Σ and define w R in terms of x R and b.
(b) (3 marks) Using structural induction prove that for all strings x, y, (x · y) R = y R · x R (1) The proof should be based on the inductive definition of strings given in the statement of the question. As part of the proof you can assume known that string concatenation is associative, that is, (wu)v = w(uv) for all strings w, u, v.
Hint. The inductive step can be done on the “second string y”. That is, as the inductive assumption C(y) you can state that (1) holds for string y (and all strings x), and then show that C(yb) must hold where b ∈ Σ.
Regulations on assignments
• The assignment must be based on individual work. Copying solutions from other students is a violation of academic integrity. See the course web site for more information http://research.cs.queensu.ca/home/cisc203/index.html
• At the top of the first page of the assignment, type or write in clear capital letters the following information on four different lines and in the order listed below: – CISC-203 ASSIGNMENT X (where X ∈ {1, 2, 3, 4} is the number of the current assignment) – LAST-NAME, FIRST-NAME (your name as it appears on solus, e.g., “SMITH, NANCY”) – your student number (e.g., “1234 4321”) – your signature (the signature need not be easily readable)
• Bonus mark: Papers that have the above information written exactly correctly and perfectly clearly and legibly will receive one bonus mark. An additional requirement is that it is not permitted to submit more than one copy of the same assignment. The assignment is worth 20 marks. Papers that receive the bonus mark, may get more than 20 marks. For the bonus mark there is no partial credit for incomplete information or unclear handwriting.
• The assignment should be put into the locked CISC 203 drop-off box on the 2nd floor of Goodwin hall by the due date. The assignments must be submitted in hardcopy. Assignments sent by email are not accepted.
• If the submission consists of more than one page, the pages must be stapled together.
• Note: You are asked to write your solutions using non-erasable pen (or to type the solutions). Solutions written in pencil or erasable ink will be marked, but they will not be considered for remarking after the assignments are returned.