COMP 280 — Exam 3

Twelve problems, each worth 8.25 points:

  1. (1 point)

    Write the Honor Code Pledge, and sign your name.

  2. (8.25 points)

    1. Let R be a relation on a set A. Explain how to use the directed graph representing R to obtain the directed graph representing the inverse relation R-1.

    2. Let R be a relation on a set A. Explain how to use the directed graph representing R to obtain the directed graph representing the complementary relation ¬R. (Note: This is typically notated as R-overbar, but HTML can't represent that notation.)

  3. (8.25 points)

    1. Show that the relation of logical equivalence on the set of all compound propositions is an equivalence relation. What is the equivalence class of F? What is the equivalence class of T?

    2. Let R be the relation on the set of all sets of real numbers such that S R T if and only if S and T has the same cardinality. Show that R is an equivalence relation. What is the equivalence class of the set {0,1,2}? What is the equivalence class of the set of all integers?

  4. (8.25 points)

    1. Let S be the set of subroutines of a computer program. Define the relation R by P R Q if subroutine P calls subroutine Q during its execution. Describe the transitive closure of R.

    2. For which subroutines P does (P,P) belong to the transitive closure of R?

    3. Describe the reflexive closure of the transitive closure of R.

  5. (8.25 points)

    Suppose that a password for a computer system must have at least 8, but no more than 12, characters, where each character in the password is a lowercase English letter, an uppercase English letter, a digit, or one of the six special characters *, >, <, !, +, and =.

    1. How many different passwords are available for this computer system?

    2. How many of these passwords contain at least one occurrence of at least one of the six special characters?

    3. If it takes one nanosecond (1×10-9 sec) for a hacker to check whether each possible password is your password, how long would it take this hacker to try every possible password?

  6. (8.25 points)

    Show that if n is a positive integer, then C(2n,2) = 2C(n,2) + n2

    1. using a combinatorial argument.

    2. by algebraic manipulation.

  7. (8.25 points)

    How many ways are there to travel in xyz space from the origin (0,0,0) to the point (4,3,5) by taking steps one unit in the positive x direction, one unit in the positive y direction, or one unit in the positive z direction? (Moving in the negative x, y, or z direction is prohibited, so that no backtracking is allowed.)

  8. (8.25 points)

    1. Explain what is wrong with the statement that in the Monty Hall Three-Door Puzzle the probability that the prize is behind the first door you select and the probability that the prize is behind the other of the two doors that Monty does not open are both 1/2, because there are two doors left.

    2. Suppose that instead of three doors, there are four doors in the Monty Hall puzzle. What is the probability that you win by not changing once the host, who knows what is behind each door, opens a losing door and gives you the chance to change doors? What is the probability that you win by changing the door you select to one of the two remaining doors among the three that you did not select?

  9. (8.25 points)

    Find each of the following probabilities when n independent Bernoulli trials are carried out with probability of success p.

    1. the probability of no successes

    2. the probability of at least one success

    3. the probability of at most one success

    4. the probability of at least two successes

    5. the probability of no failures

    6. the probability of at least one failure

    7. the probability of at most one failure

    8. the probability of at least two failures

  10. (8.25 points)

    A space probe near Neptune communicates with Earth using bit strings. Suppose that in its transmissions it sends a 1 one-third of the time and a 0 two-thirds of the time. When a 0 is sent, the probability that it is received correctly is 0.9, and the probability that it is received incorrectly (as a 1) is 0.1. When a 1 is sent, the probability that it is received correctly is 0.8, and the probability that it is received incorrectly (as a 0) is 0.2.

    1. Find the probability that a 0 is received.

    2. Use Bayes' Theorem to find the probability that a 0 was transmitted, given that a 0 was received.

  11. (8.25 points)

    1. Find a recurrence relation for the number of ways to lay out a 1×n walkway with slate tiles if the tiles are red, green, or gray, so that no two red tiles are adjacent and tiles of the same color are considered indistinguishable.

    2. What are the initial conditions for the recurrence relation in part (a)?

    3. How many ways are there to lay out a path of seven tiles as described in part (a)?

  12. (8.25 points)

    1. Find the characteristic roots of the linear homogeneous recurrence relation an = 2an-1 - 2an-2. (Note: These are complex numbers.)

    2. Find the solution of the recurrence relation in part (a) with a0=1 and a1=2.

  13. (8.25 points)

    Use generating functions to solve the recurrence relation ak = 5ak-1 - 6ak-2 with initial conditions a0=6 and a1=30.