INFO 150: A Mathematical Foundation for Informatics

Second Midterm Exam

David Mix Barrington

17 November 2016

Directions:

Answer the problems on the exam pages.
There are four problems, each with multiple parts, for 100 total points. Actual scale was A = 85, B = 70, C = 55, D = 40.
If you need extra space use the back of a page.
No books, notes, calculators, or collaboration.
Numerical answers may be given as expressions using addition, subtraction, multiplication, division, exponentiation, and the factorial function. But expressions such as P(n, k) or C(n, k) must be rewritten to use only these operations. In addition, some of the true/false questions may require you to compute an explicit number, which will be less than 100.

  Q1: 15 points
  Q2: 25 points
  Q3: 30 points
  Q4: 30 points
Total: 100 points

Question 1 (15): Briefly identify the following terms or concepts (3 points each):

(a) for a set C to be the intersection of sets A and B
(b) for a relation R ⊆ A × B to be a function
(c) for a relation R ⊆ A × A to be reflexive
(d) the Sum Rule for computing probabilities
(e) the sample space for a probability problem

Question 2 (25): Let D = {a, b, c, d, e} be a set consisting of the five dogs Arly, Biscuit, Cardie, Duncan, and Ebony. Let K = {k₁, k₂, k₃, k₄} be a set of four kennels. The following four counting problems involve putting these dogs into the kennels.

(a, 5) In how many ways can each dog be assigned a kennel? (Example: Arly and Duncan in k₁, Ebony in k₂, no one in k₃, and Biscuit and Cardie in k₄.)
(b, 5) Suppose Arly, Biscuit, and Ebony are all put in k₄. In how many ways could Cardie and Duncan be put into some of the other three kennels, without their both going in the same kennel? (Example: Cardie in k₂ and Duncan in k₃.)
(c, 5) In how many ways could we choose a set of exactly three of the five dogs to go into k₄?
(d, 10) If more than one dog may go in a kennel, how many ways are there to decide how many dogs are in each kennel? (Example: two in k₁, none in k₂, one in k₃, two in k₄.)

Question 3 (30): These are true/false questions about the scenario of Question 2, with no explanation needed or wanted and no penalty for guessing (3 points each):

(a) Question 2a counts the total number of functions from K to D.
(b) Question 2b counts the total number of one-to-one functions from {c, d} to {k₁, k₂, k₃}.
(c) Question 2c's answer is the number of ways we can choose two dogs that will not go into k₄.
(d) Question 2d's answer is the number of binary strings with exactly five 0's and exactly three 1's.
(e) Every function counted in Question 2a is onto.
(f) Some of the functions counted in Question 2a are one-to-one.
(g) The direct product D × K has more elements than does the power set of K.
(h) If we pick one of the assignments in Question 2a, then the relation R(x, y) meaning "dog x and dog y are put into the same kennel" is reflexive and symmetric but not antisymmetric.
(i) There are exactly 4³ functions counted in Question 2a that have Arly and Biscuit in the same kennel, and also have Cardie and Duncan in the same kennel.
(j) If we put each of the dogs in some kennel, and no kennel is empty, then exactly one kennel must have exactly two dogs in it.

Question 4 (30): For this question we begin with a 52-card deck, containing 13 spades, 13 hearts, 13 diamonds, and 13 clubs. We are dealt three cards without replacement.

(a, 5) What is the expected number of spades in our hand?
(b, 5) What is the probability that our hand contains no spades?
(c, 5) What is the probability that our three cards are of three different suits?
(d, 5) What is the probability that our three cards are all of the same suit?
(e, 10) Are we more likely to have an even number of spades or an odd number of spades in our hand? Or is there a 1/2 probability of each of these outcomes? Explain your answer -- a correct answer with no explanation will get only three points. (Remember that 0 is an even number.)

Last modified 28 November 2016