INFO 150: A Mathematical Foundation for Informatics

Practice for Final Exam

David Mix Barrington

9 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 1 (15): Briefly identify and distinguish the following terms or concepts (3 points each):

(a) A tautology and a contradiction
(b) The implication p → q and the equivalence p ↔ q
(c) A one-to-one function and an onto function
(d) A graph (in the book's usage) and a simple graph
(e) A walk (in the book's usage) and a path

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.
(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.
(c) If R is a partial order and both (x, y) and (y, x) are elements of R, then x must equal y.
(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.
(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).
(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.
(g) Every tree with one or more edges has at least one vertex with degree two or more.
(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.
(i) In the matrix of a Markov process, the entries in each column always add to 1.
(j) In the matrix of an n-state Markov process, the sum of all the entries in the matrix must be n.

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.)
(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.)
(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.)
(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?
(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.

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.
(b, 5) Write a quantified statement that says "There exist two dogs who are engaged in different activities".
(c, 5) Translate the quantified statement "(∃x:¬E(x, bar)) → (E(a, swi) ∧ E(d, cha))" into English.
(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.)

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.
(b, 5) Compute the matrix A⁴.
(c, 5) Each of nine entries in A⁴ counts a paritcular set. What is that set, for each entry?
(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?
(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.)

Last modified 9 December 2016