Queen’s University School of Computing

CISC 203: Discrete Mathematics for Computing II

Problem Set 3

Due March 15, 2021 by 11:59pm (Kingston time)

Show all your work/steps and explain all your solutions.

Problem set collaboration policy:


1. This problem set is an individual assessment that is meant to replace an in-class test, i.e., you are expected to solve the problems and write your solutions individually. However, it is open book and you are being given an extended period of time to complete it to help you better manage your online learning workload.

2. Do not ask the TAs or other students for help on directly solving the problem set questions. However, you may identify examples or exercises in the course notes that refer to similar concepts or require a similar strategy to solve (identifying such connections between questions demonstrates individual effort in solving the problem), and may ask for help during office hours or on the discussion board to understand those examples.

3. Do not publicly post (e.g., on the discussion board or Microsoft Teams) that “Question X in the problem set is similar to Question Y in the course notes”. It is important that each student becomes familiarized enough with the material to observe such connections on their own.

4. If you encounter any explanations on the discussion board or during office hours that help you to solve a question, add a sentence to your solution(s) (and provide the URL if applicable) to give credit. Failure to do so may result in penalty (when in doubt, no need to ask—just give credit).

5. Questions about clarifying any aspect of the problem set (e.g., to clarify the wording of a question) should be posted on the discussion board topic, so that all students can benefit equally from the answer:

https://discourse.caslab.queensu.ca/c/cisc-203-w21/23.

Your solutions must be prepared in LATEX using the Overleaf template, as follows:

I. Log in using your NetID, by clicking the “Log in through your institution” button at the bottom of this page: https://www.overleaf.com/edu/queensu

II. Access the template here: https://www.overleaf.com/read/ncdhzmmxtkzj

III. Click “Menu” on the top left corner and then on “Copy Project” to create your copy of the template.

IV. When you are finished writing your solutions, download your PDF and submit it on onQ.

    Note: 2 marks (out of 80) in this problem set are reserved for formatting, which consists of correctly entering your name into the LATEX template, removing the sample text/images from it, and formatting your solutions in a way that is readable by the TAs (please be considerate of them), e.g., by inserting line breaks where appropriate. Everybody should be able to get these 2 marks!

1. (a) Let R be a relation on Z and let x, y ∈ Z. Then, x R y if and only if x2 + y2 = 1. Determine if R is a function (and justify your answer).

(b) Suppose 70 students in CISC 203 are members of 11 different WhatsApp groups. Each student is only a member of one group, and each group has at most 15 students in it. Show that there are at least three groups that have at least five students each.

(c) Let A = {1, 2, 3, 4} and B = {5, 6, 7} and let f : A → B by f = {(1, 6),(2, 7),(3, 6),(4, 7)}. Determine (i) dom f and im f; and (ii) whether f is one-to-one and onto (justify your answer).

(d) Let f : R → R by f(x) = 2x + 3. Determine the inverse function f-1(x).

[13 marks]

2. (a) Let A, B, and C be nonempty sets and let f : A → B and g : B → C. Prove the following statement by contrapositive: If g ◦ f is one-to-one, then f is one-to-one.

(b) Let α, β ∈ S6, where . Determine α-1, β-1, α ◦ β, and β ◦ α.

(c) Write α and β from part (b) in cycle notation.

(d) Determine whether α is an odd or even permutation, and whether β is an odd or even permutation. Show your work.

[13 marks]

3. For each statement below, answer “True” or “False”. If you answer “False”, briefly show your reason.

[12 marks]

4. (a) Two equally-skilled League of Legends players, Alice and Bob, decide to play a series of 4 matches. In each match, the probability of Alice winning is 0.5 and the probability of Bob winning is 0.5. What is the probability that Alice will win more matches than Bob?

(b) Suppose that on the due date of this problem set, there is a 30% chance of freezing rain, 10% chance of snow and freezing rain, and 75% chance of snow or freezing rain. What is the chance of snow?

(c) Ulfric, Balgruuf, Elisif, Laila, and Korir agree to convene at a meeting to discuss the future of the province of Skyrim. When they arrive, they are seated randomly at a round table. Assuming that none of them are the same age, what is the probability that they will be seated in descending order of age?

(d) Suppose that you go to the store to purchase three USB drives. There are 20 USB drives on the shelf, but one of them is defective (you do not know which one). If you purchase three USB drives, what is the probability that one of your drives will be the defective one?

(e) Consider a laptop that has a 90% chance of operating reliably and a 10% chance of breaking down throughout a year. Assume that if it breaks down, there is a 60% chance that the laptop will need a $150 repair, 30% chance it will need a $500 repair, and a 10% chance that the laptop will need to be replaced at a cost of $1,500. What is the expected loss in a year?

[20 marks]

5. Jean-Luc and William are sometimes late for their company-wide meeting. Let J be the event that Jean-Luc is late, and W be the event that William is late. For any given day, we have the probabilities . (Hint: If you get stuck, you might find it helpful to refer back to some basic rules of Boolean algebra from Week 1.)

(a) Given that William is late, what is the probability that Jean-Luc is also late?

(b) Are Jean-Luc’s and William’s lateness linked? Justify your answer using probability concepts that we covered.

[10 marks]

6. Suppose that a box contains 5 white marbles and 5 red marbles. Consider the following experiment:

1. Roll a pair of dice, and compute the sum of the two numbers that were rolled.

2. If the sum is less than or equal to 4, randomly select 1 marble from the box.

3. If the sum is greater than or equal to 10, randomly select (without replacement) 2 marbles from the box.

4. If the sum is any value that falls outside the above ranges, do not select any marbles from the box.

(a) Calculate the probability that at least one red marble is removed from the box after performing the above experiment. Show your work.

(b) Calculate the conditional probability that the sum of the dice is greater than or equal to 10, given that at least one red marble is removed from the box after performing the above experiment. Show your work.

[10 marks]