INFO 150: A Mathematical Foundation for Informatics

Solutions to Practice Final Exam

David Mix Barrington

13 December 2016

Directions:

Answer the problems on the exam pages.
There are five problems, each with multiple parts, for 120 total points plus 5 extra credit. Scale will be determined after the exam but a good guess is 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.

  Q1: 15 points
  Q2: 30 points
  Q3: 30 points
  Q4: 25 points
  Q5: 20+5 points
Total: 120+5 points

Question text is in black, solutions in blue.

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

(a) A tautology and a contradiction
A tautology is a compound proposition that is true for any values of its atomic variables. A contradiction is a compound proposition that is false for any values of its atomic variables.
(b) The implication p → q and the equivalence p ↔ q
The statement p → q is true unless p is true and q is false. The statement p ↔ q is true if p and q are either both true or both false.
(c) A one-to-one function and an onto function
A one-to-one function is one where no two inputs map to the same output. An onto function is one where every output is mapped to by at least one input.
(d) A graph (in the book's usage) and a simple graph
Both are undirected, meaning they have only undirected edges. The book's "graphs" may have loops and parallel edges, but its "simple graphs" may not.
(e) A walk (in the book's usage) and a path
The book's "walks" are any sequences of edges where the start of each edge (except the first) is the end of the previous edge. Their "paths" are walks that never reuse a vertex.

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

(a) If a proposition p is false and the implication "p → q" is true, then the proposition q must be false.
FALSE. If p is false, p → q is true whatever the value of q.
(b) If I have a (finite) set of one or more odd positive integers, and I multiply all the elements of the set together, the result must be odd.
TRUE. The product of any two odd positive integers is odd, so if we keep multiplying until we have a single integer, every product will be the product of two odd positive integers and thus will be odd.
(c) If R is a partial order and both (x, y) and (y, x) are elements of R, then x must equal y.
TRUE. This is the antisymmetric property, which all partial orders have.
(d) If I have a set of four dogs and a set of four activities, there are exactly C(4, 4) = (4×3×2×1)/(1×2×3×4) ways to assign each dog a different activity.
FALSE. There are P(4, 4) = 4! = 1×2×3×4 ways to do this.
(e) If I deal three cards from a 52-card deck without replacement, the probablity that all three will be the same rank (for example, all sevens or all jacks) is (3/51)×(2/50).
TRUE. For the second card, 3 of the remaining 51 cards have the same rank as the first. If this happens, 2 of the remaining 50 cards have that rank.
(f) If I throw three fair independent dice ("throw 3D6"), the chance that the sum will be 4 is the same as the chance that the sum will be 17.
TRUE. The only way to get 4 is with two 1's and one 2, three out of the 6³ = 216 possible throws. The only way to get 17 is with two 6's and one 5, also 3/216 probability.
(g) Every tree with one or more edges has at least one vertex with degree two or more.
FALSE. The tree with one edge and two vertices does not have this property.
(h) If I have a tree with one or more edges, and I delete one of the edges, the resulting graph may still be a tree.
FALSE. Deleting the edge does not delete any nodes. The resulting graph will no longer be connected -- if we delete an edge from x to y, there can be no path remaining from x to y, because this would have made a cycle with the deleted edge, and trees have no cycles.
(i) In the matrix of a Markov process, the entries in each column always add to 1.
FALSE. The entries in each row add to 1. But it's possible, for example, that every state goes to state 1 with probability 1. Then the column for state 1 has entry 1 in every position, so its sum is n rather than 1. And the other columns all sum to 0, not 1.
(j) In the matrix of an n-state Markov process, the sum of all the entries in the matrix must be n.
TRUE. Each row sums to 1, and there are n rows.

Question 3 (30): Let D = {a, b, c, d} be a set of four dogs (Arly, Biscuit, Cardie, and Duncan}. Let A = {barking, chasing, swimming, wrestling} be a set of four activities. The first three parts of this question are counting problems involving assigning activities to the dogs. The last two parts deal with a similar counting problem.

(a, 5) In how many ways can we assign one activity to each dog, assuming that more than one dog can be assigned the same activity? (Example: Arly is barking, Biscuit is wrestling, Cardie is swimming, and Duncan is barking. Another example: Arly is swimming, Biscuit is chasing, Cardie is wrestling, and Duncan is barking.)
The number is 4⁴ = 256, as we have four choices for each dog and we multiply these four copies of 4 together.
(b, 5) Suppose that exactly two of the dogs are barking and the other two are wrestling. How many of the assignments in part (a) have this property? (Example: Arly and Cardie are barking, while Biscuit and Duncan are wrestling.)
We choose a set of two of the four dogs to be barking. There are C(4, 2) = 6 ways to do this. For each one of these ways, there is only one way to have the other two dogs wrestling. So the answer is 6×1 = 6.
(c, 5) In how many ways can we assign a number of dogs to each activity? (Example: two dogs are barking, none are chasing or swimming, and two are wrestling.)
This is a "stars and bars" problem. Each such assignment can be identified with a binary string of four 0's (for the four dogs) and three 1's (for the barriers between the activities. There are C(7, 3) = (7×6×5)/(1×2×3) = 35 such strings.
(d, 5) Now suppose there are n dogs rather than four, where n can be any positive integer. What is now the answer to the problem in part (a), as a function of n?
We have n different choices from among the four activities, so we multiply together n 4's to get 4ⁿ.
(e, 10) Prove your answer to part (d) by induction. That is, explain why it is correct for n = 1, and then prove that it is true for arbitrary n using the assumption that it is true for all m smaller than n.
For the base case, if there is one dog and four activities, there are clearly four choices for that dog's activity. Assume that for n-1 dogs, there are 4^n-1 choices of activities. We now add an n'th dog, whom we'll call X. Dog X has four choices of activity, and for each choice there are 4^n-1 ways for the other dogs to choose their activities. By the Product Rule, the total number of choices is 4^n-1 × 4 = 4ⁿ.

Question 4 (25): With the same four dogs and four activities as in Question 3, let E(x, y) be a predicate meaning "dog x is engaged in activity y".

(a, 5) Translate the logical statement "E(c, bar) → (E(d, wre) ∨ E(b, wre))" into English.
"If Cardie is barking, then either Duncan or Biscuit (or both) are wrestling."
(b, 5) Write a quantified statement that says "There exist two dogs who are engaged in different activities".
"∃u:∃v:∃x:∃y:E(u, x) ∧ E(v, y) ∧ (x ≠ y)" The type of u and v is "dog", and the type of x and y is "activity".
(c, 5) Translate the quantified statement "(∃x:¬E(x, bar)) → (E(a, swi) ∧ E(d, cha))" into English.
"If there is a dog that is not barking, then Arly is swimming and Duncan is chasing."
(d, 10) Explain why, if the statements of parts (a) and (c) are both true, the statement of part (b) is also true. You may use English! (Hint: Argue by cases, as either Cardie is barking or Cardie is not barking.)
Suppose that Cardie is barking. Then by statement (a), either Duncan or Biscuit is wrestling. We can take dog u in statement (b) to be Cardie, and take dog v to be the dog who is wrestling. Then those two dogs are engaged in different activities, and statement (b) is true.
Now suppose that Cardie is not barking. Then there exists a dog who is not barking, so by statement (c) we know that Arly is swimming and Duncan is chasing. We can take dog u in statement (b) to be Arly and dog v to be Duncan -- they are engaged in different activities, so statement (c) is true.

Question 5 (20+5): Let G be a directed graph with vertex set {a, b, c} and edge set {(a, b), (a, c), (b, a), (b, b), (c, b), (c, c)}. Let A be the adjacency matrix of G and let M be the one-step probability matrix for the Markov process where every edge of G has weight 1/2.

(a, 5) Write down the matrices A and M.


      0  1  1
      1  1  0
      0  1  1

(b, 5) Compute the matrix A⁴.

First we compute A² which is:


     1  2  1
     1  2  1
     1  2  1

Then we square this again to get:


     4  8  4
     4  8  4
     4  8  4

(c, 5) Each of nine entries in A⁴ counts a paritcular set. What is that set, for each entry?
The (i, j) entry of A⁴ counts the number of paths of length 4 in the graph from node i to node j. So there are 4 paths to a, 8 paths to b, and four paths to c from each of the three nodes.
(d, 5) If we start the Markov process in state a, what is the probability that we will be in state b four steps later? Is the answer the same or different if we start in state c?
Each path has probability (1/2)⁴ = 1/16, so the 8 four-step paths counted by the matrix have total probability 8/16 = 1/2. The answer is the same for each of the three possible start nodes, since all the rows of A⁴ are the same.
(e, 5XC) If we start the Markov process in state a, what is the probability that we will be in state b 100 steps later? Explain your answer. (Hint: I do not expect you to compute M¹⁰⁰, though that could answer the question in principle.)
The probability is still 1/2. After 98 turns, the process will be at one of the three nodes. But in the last two turns, wherever it starts, it has a 1/4 probability to go to either a or c, and a 1/2 probability to go to b.

Last modified 13 December 2016