INFO 150: A Mathematical Foundation for Informatics

Final Exam

David Mix Barrington

20 December 2017

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) two relatively prime integers and two prime integers
(b) the union of two sets and the intersection of two sets
(c) the expected value and the most likely value of a random variable
(d) a directed graph and an undirected graph
(e) integer matrix multiplication and boolean matrix multiplication

Question 2 (20): The web site WeRateDogs^TM provide numerical ratings of dogs based on photographs, and publishes these at twitter.com/dog_rates. Recently they provided ratings for a set of five dogs: Ali, Cardie, Duncan, Toby, and Whistle (the set {a, c, d, t, w}). All of the ratings were integers in the set {11, 12, 13, 14, 15}. We define r(x) to be the rating of dog x, and assume that r is a function.

(a, 5) In how many ways can each dog be assigned a rating from this set, with no restrictions? (Example: r(a) = 11, r(c) = 15, r(d) = 15, r(t) = 12, r(2) = 13.)
(b, 5) In how many ways could the dogs be assigned ratings, if two dogs are rated 14 and the other three are all rated 12? (Example: r(a) = r(t) = 14, r(c) = r(d) = r(w) = 12.)
(c, 5) If each dog is independently given a random rating, with all five ratings in the set being equally likely, what is the probability that each dog gets a different rating?
(d, 5) How many possiblities are there for the number of dogs that get each rating? (Example: Two dogs get 11, one gets 12, and two get 14.)

Question 3 (25): In this problem we will translate and reason with statements about the scenario of Question 2, using the function r defined there and the usual arithmetic, equality, and comparison symbols for integers.

(a, 5) Translate the statement "If Cardie's rating equals Duncan's, then Toby's rating is less then both Ali's and Whistle's" into a logical compound statement.
(b, 5) Translate the quantified statement "∀x:∀y: (r(x) = r(y)) → (x = y)" into English. Note that the type of x and y is "dog".
(c, 5) Write a quantified statement that says "Some dog was rated 14, and exactly one dog was rated higher than that dog."
(d, 10) Explain carefully in English why, if the statement of part (b) is true, then that statement of part (c) must also be true. You may quote facts from lecture and the book if you do so clearly.

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 Cardie's rating is chosen at random from the given set, with every choice equally likely, it is more likely than not to be prime.
(b) If a, b, and c are any three odd integers, then the integer ab + ac + bc must be odd.
(c) If I assume two statements p and q, and derive a contradiction, then I have proved (¬p) ∧ (¬q).
(d) Let p, q, and r be three propositions. If p ∧ q and r → ((¬p) ∨ (¬q)) are both true, then r must be false.
(e) It is possible that the function r of Questions 2 and 3 is one-to-one, but not onto.
(f) If Cardie and Duncan are given ratings independently, with each rating equally likely, then the probability that their ratings are different is P(5, 2)/5² = 20/25 = 0.8.
(g) There exists an undirected graph with three vertices of degree three, two vertices of degree 4, and no other vertices.
(h) If each of the five dogs is given a rating independently, with each rating in the set being equally likely, then the expected value of the sum of the five ratings is 65.
(i) Let H be a directed graph, with no self-loops, where every node has at least one edge out of it and at least one edge into it. Let x and y be any two nodes in H. Then there must be a path in H from x to y.
(j) Consider the two-player game where we have a pile of stones and each player on her move may take one, two, or three stones. The goal is to take the last stone. If we start with 19 stones, the first player's best move is to take three.

Question 5 (30): In this problem we study a Markov process derived from a simplified, one-player adaptation of the dreidel game traditionally played at Hannukah celebrations. At any time the Player has zero, one, or two chocolate coins. On each turn she spins the dreidel, which gives one of four outcomes with equal probability. She may gain or lose a coin based on this outcome:

If she has no coins, she does not gain or lose, whatever the outcome.
If she has one coin, one outcome has her lose it, one keeps her state the same, and two have her gain a coin.
If she has two coins, one outcome has her lose a coin and the other three keep her state the same.

We will define M to be the Markov process for this game, with state set {0, 1, 2}, and Z to be the transition matrix of M, with Z_ij being the probability of going from state i to state j in one step. We also define A to be the matrix such that A_ij is the number of outcomes (out of four) that take state i to state j in one step. Note that for any i and j, Z_ij = A_ij/4. We can also consider A to be the adjacency matrix of a directed multigraph G, which has node set {0, 1, 2} and has A_ij directed edges from node i to node j.

(a, 5) Write down both the matrices A and Z.
(b, 5) Compute the matrices A² and Z². (You can save a lot of calculation by using the relationship between the two.)
(c, 10) Prove, by induction on n for all n with n ≥ 1, that the last two entries of the first row of Zⁿ are both zero. (That is, (Zⁿ)₀₁ = (Zⁿ)₀₂ = 0.) What is the meaning of this fact in terms of the Markov process?
(d, 5) Write down the matrix Z³. You might be able to use the relationship between the matrices A and Z to save yourself some calculation.
(e, 5) If you start the Markov process in state 1, what is the probability that five steps later, you will be in state 2?

Last modified 14 January 2018