INFO 150: A Mathematical Foundation for Informatics

Final Exam

David Mix Barrington

16 December 2016

Directions:

Answer the problems on the exam pages.
There are five problems, each with multiple parts, for 120 total points. Actual scale was A = 105, C = 75.
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: 20 points
  Q3: 25 points
  Q4: 30 points
  Q5: 30 points
Total: 120 points

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

(a) for an integer x to be a divisor of y and for x to be a multiple of y.
(b) disjoint events and independent events in probability
(c) a symmetric relation and an antisymmetric relation
(d) the zero matrix and the identity matrix
(e) a simple graph without cycles and a tree

Question 2 (20): To help with the anxiety of final exams, students Xavier, Yolanda, and Zhang (the set {x, y, z}) have each been given the opportunity to pet one of the four trained therapy dogs Arly, Biscuit, Cardie, or Duncan (the set {a, b, c, d}). Here are four counting and probablity problems about the assignment of students to dogs.

(a, 5) In how many ways can each student be assigned a dog, if each student pets one dog and no two students pet the same dog? (Example: Xavier pets Biscuit, Yolanda pets Arly, and Zhang pets Cardie.)
(b, 5) If each student pets exactly one dog, and no two students pet the same dog, how many possibilites are there for the set of dogs who are petted? (Example: {b, c, d}.)
(c, 5) If each of the three students independently chooses a dog at random, with an equal probability of choosing each dog, what is the probability that no two students choose the same dog?
(d, 5) If each student chooses a dog and more than one student may choose the same dog, how many possibilities are there for the number of students petting each dog? (Example: Two students pet Cardie and one pets Duncan.)

Question 3 (25): In the scenario of Question 2, let the predicate P(u, v) denote the statement "student u pets dog v". We no longer assume that each student pets only one dog.

(a, 5) Translate the statement "Xavier pets Cardie if and only if either Yolanda pets Biscuit or Zhang pets Duncan" into a logical compound statement.
(b, 5) Write a quantified statement that says "Some student pets two different dogs".
(c, 5) Translate the quantified statement "∀v: ∃u: P(u, v)" into English. Note that the type of u is "student" and that the type of v is "dog".
(d, 10) Explain carefully in English why, if the statement of part (c) is true, then that statement of part (b) must also be true.

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

(a) If the relation P of Question 3 is a function, then the statement of Question 3 (c) must be true.
(b) If the relation P of Question 3 is a function, the statement of Question 3 (b) may or may not be true.
(c) If the students pick dogs as in Question 2 (c), then the probability that neither Xavier nor Zhang pet Cardie is less than 1/2.
(d) If the students pick dogs as in Question 2 (c), then the probability that Yolanda and Zhang pet the same dog is 1/4.
(e) If x is any odd integer, then x³ - 2x² + 3x - 4 is an even integer.
(f) Let P(x) be a property of positive integers. If P(1) is false, and for any n such that P(n) is true, there is a positive integer m such that P(m) is true and m < n, then P(x) cannot be true for any positive integer x.
(g) In the Nim game with five piles containing 3, 4, 5, 6, and 7 stones respectively, the first player has a winning strategy that begins by taking all three stones from the first pile.
(h) In a simple graph (an undirected graph with no loops or parallel edges) with n nodes, there cannot be more than 2n - 1 edges.
(i) Let G be any graph that has at least three nodes and where every node has even degree. Then G contains a cycle that includes every edge exactly once.
(j) Let G be the directed graph representing a relation R ⊆ A × A. If there is an edge from x to y in G, there is also an edge from x to y in the graph representing the transitive closure of R.

Question 5 (30): Consider the directed multigraph G with nodes A, B, and C and directed edges from A to A, from A to B, from B to B, and from B to C, and with two directed edges from C to C. Note that this directed graph has out-degree two at every vertex. Let M be the adjacency matrix of G.

Also consider a Markov process P with the same states A, B, and C, where the probability of transitioning on each edge of G is 1/2. (Thus from C, for example, the probability of going to C is 1.) Let Z be the matrix of this Markov process.

(a, 5) Write down the matrices M and Z.
(b, 5) Compute the matrices M² and M³.

(c, 10) Prove, by induction on n for all n with n ≥ 1, that the matrix Mⁿ is given by:


		  1    n     2^n - n - 1
		  0    1       2^n - 1
		  0    0         2^n

(d, 5) Write down the matrix Z³. You might be able to use the relationship between the matrices M and Z to save yourself some calculation.
(e, 5) If you start the Markov process in state A, what is the probability that six steps later, you will be in state C?

Last modified 9 January 2017