INFO 150: A Mathematical Foundation for Informatics

Practice for Second Midterm Exam

David Mix Barrington

11 November 2016

Directions:

Answer the problems on the exam pages.
There are four problems, each with multiple parts, for 100 total points. Scale will be determined after the exam but a good guess is A = 90, C = 60.
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.

  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 A to be a subset of a set B
(b) for a function from A to B to be onto
(c) for a relation R ⊆ A × A to be antisymmetric
(d) the Product Rule for counting (finding the size of sets)
(e) for two events to be independent

Question 2 (25): Let T = {s, m, l} be a set of three dog treats (small, medium, and large) and let D = {a, b, c, d, e} be a set of five dogs (Arly, Biscuit, Cardie, Duncan, and Ebony}. Answer the following counting problems involving giving these treats to these dogs.

(a, 5) In how many ways could the treats be given to the dogs if no dog can get more than one treat (Example: small treat to Duncan, medium to Ebony, and large to Cardie)
(b, 5) In how many ways could the treats be given to the dogs if we also allow a dog to get more than one treat (Example: small and large to Arly and medium to Biscuit)
(c, 5) If no dog gets more than one treat, how many ways are there to choose which dogs get a treat? (Example: Arly, Cardie and Duncan get treats)
(d, 10) If dogs may get more than one treat, how many ways are there to choose which dogs get how many treats? (Example: Biscuit gets two and Ebony gets one.)

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 2b counts the total number of functions from T to D.
(b) Question 2a counts the total number of one-to-one functions from T to D.
(c) Let R ⊆ D × D be the set of pairs (x, y) such that dogs x and y get the same number of treats. Then R is an equivalence relation.
(d) The power set of D has exactly 25 elements.
(e) The direct product T × D has exactly 3⁵ elements.
(f) There exists an onto function from T to D.
(g) There are exactly 2¹⁵ relations from T to D (relations R ⊆ T × D).
(h) Question 2d counts the number of ways to add five non-negative integers to get 3, such as "0+1+0+2+0 = 5".
(i) Question 2c counts the power set of D.
(j) No function from T to D has an inverse.

Question 4 (30): In this problem we "throw 3D6", which means that we throw three independent fair six-sided dice, numbered {1, 2, 3, 4, 5, 6}, and add the results.

(a, 5) What is the expected value of the sum of the three dice?
(b, 5) What is the probability that the sum is 18?
(c, 5) What is the probability that the sum is 7?
(d, 10) What is the probability that the sum is odd? Justify your answer (there are several different valid ways to do so). A correct answer with no justification will get only 3 points.

Last modified 11 November 2016