INFO 150: A Mathematical Foundation for Informatics

Second Midterm Exam

David Mix Barrington

5 November 2017

Directions:

Answer the problems on the exam pages.
There are four problems, each with multiple parts, for 100 total points. Actual scale was A = 81, B = 67.5, C = 54, D = 40.5.
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: 30 points
  Q3: 30 points
  Q4: 25 points
Total: 100 points

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

(a) the power set of a set
(b) when a partial order is a total order
(c) the identity function from a set to itself
(d) an equivalence relation (you may use either of the two definitions given in the text and lecture, without proving that they are the same)
(e) the Sum Rule With Overlap for counting a union of two finite sets A and B

Question 2 (25): We have a set U = {c, d, m, s, t, w} of six dogs: Cardie, Duncan, Mia, Scout, Toby, and Whistle. We have two subsets of U, the female dogs F = {c, n, s} and the neighborhood dogs N = {c, d, m, w}. Recall that F' and N' are the complements of F and N respectively. In the first four parts of this question we are going to award prizes for Agility (a), Beauty (b), and Obedience (o), each to one of the dogs. (Five points each part.)

(a) In how many ways can we award the three prizes to three different dogs? (So we are counting situations like "Duncan gets a, Cardie gets b, and Scout gets o".)
(b) In how many ways can we choose which three dogs get prizes, if the prizes go to three different dogs? (So we are counting situations like "Mia, Toby, and Whistle get prizes".)
(c) In how many ways can we award the three prizes each to a dog, if it is possible that one dog gets more than one prize? (So we are counting situations like "Mia gets both b and o, and Whistle gets a".)
(d) In how many ways can we decide how many prizes each dog gets, if the three prizes do not necessarily go to three different dogs? (So we are counting situations like "Duncan gets two prizes and Toby gets one".)
(e) In how many ways can we partition U into three sets, each containing one dog in F and one in F'?
(f) In how many ways can we partition U into two sets, each containing two dogs in N and one in N'?

Question 3 (30): Here are ten true/false questions, with no explanation needed or wanted and no penalty for guessing. The first five questions refer to the sets and scenarion of Question 2. (Three points each.)

(a) There exists an injection (a one-to-one function) from U to F.
(b) Not all functions from U to N are surjections (onto functions).
(c) The answer to Question 2(e) is also the number of functions from F to F'.
(d) The answer to Question 2(d) is also the number of binary strings with three 0's and three 1's.
(e) The answer to Question 2(c) is also the number of binary strings with three 0's and five 1's.
(f) Let A = {a}. Then every relation R ⊆ A × A is both antisymmetric and transitive.
(g) Let A = {a}. If R ⊆ A × A is reflexive, then it is both an equivalence relation and a partial order.
(h) Let X, Y, and Z be any three finite sets. Recall that |S| denotes the number of elements in any set S. Then |X ∪ Y ∪ Z| = |X| + |Y ∪ Z| - |X ∩ (Y ∪ Z)|.
(i) The number of possible passwords with one upper-case letter and seven lower case letters (such as fruiTbat) is equal to the number of possible passwords with eight lower-case letters (such as fruitbat).
(j) Let W be a set of 2¹¹ = 2048 distinct words. Then the number of passwords I can make by taking a sequence of four words from W (with replacement, and with order mattering) is 2⁴⁴.

Question 4 (30): Here are two proofs involving sets and functions.

(a, 10) Let X, Y, and Z be any three sets. Prove that X ∪ (Y ∩ Z') is a subset of Y ∪ Z ∪ (X ∩ Z'). Remember that S' denotes the complement of a set S.
(b, 15) Define a function f from N to N as follows. Using Java notation for integer division, let f(n) = 10 * (n/10) + (9 - n%10). So, for example, f(42) = 10 * (42/10) + (9 = 42&10) = 10* 4 + (9 - 2) = 47. Prove that f is an invertible function. (You could prove that it is both one-to-one and onto, or prove that it has an inverse.)

Last modified 25 November 2017