INFO 150: A Mathematical Foundation for Informatics

Solutions to Final Exam

David Mix Barrington

Exam given 16 December 2016

Solutions posted 10 January 2017

Directions:

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

Exam text is in black, solutions in blue.

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

  • 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.

  • 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.

  • 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):

  • 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.

    Last modified 10 January 2017