CSE 321 final exam study guide: Spring 2001

These are final exam questions from previous offerings for the course. Since lecture topics vary from year to year, some of the questions relate to material that was not presented this year. The final will cover all the material presented in class: 1.1-1.3, 2.3-2.4, 3.1-3.3, 4.1-4.5, 6.1-6.4, 7.1-7.4 Related material presented in class such as the direct proof rule, existential & universal specialization & generalization rules; methods for inductive proofs on recursively defined sets and the linearity of expectation are also covered.
  1. Show that the proposition p-> ((q-> (r-> s)) -> t) is a contingency WITHOUT constructing its full truth table.

  2. Using the universe of integers for all quantifiers express the following English sentences in predicate logic using the predicates, P, E, and L where P(x) means `x is prime', E(x) means `x is even', and L(x,y) means `x < y'.

  3. In an undirected graph G, we define dist(v,w) to be the length of the shortest path from v to w. Show that for vertices x, y, z, we have dist(x,z)<= dist(x,y) + dist(y,z).

  4. Let G=(V,E) be a directed graph. Define a relation R on E by (e_1,e_2) is an element of R iff e_1 and e_2 lie on a common simple circuit. (Recall that a simple circuit is a path that starts and ends at the same vertex, and does not repeat any edges).

  5. Let R be a relation on a set A. Is the transitive closure of R always equal to the transitive closure of R^2 ? Prove or disprove.

  6. Prove that in the graph below, there are exactly 2^n paths of length 2n between vertex A and vertex B for n>= 1.

         *   *   *   *
        / \ / \ / \ / \ /   \
     A *   *   *   *   * ... * B
        \ / \ / \ / \ / \   /
         *   *   *   *
    
          (n diamond shapes in a row)
    
  7. The formula ~(p -> ~q) -> (r -> (~s -> t)) is false for exactly one assignment to p, q, r, s and t. Find this assignment WITHOUT constructing a truth table.

  8. Determine the number of strings over {a,b,c} of length 100 that have exactly 98 a's.

  9. Suppose that you are working on a True-False test with 10 questions. Let p_i be the probability that you get answer i correct. Assume that the probabilities are independent.

  10. Give an example of a relation which is not reflexive, not symmetric, not anti-symmetric, and not transitive. (You are to give one relation that lacks all of these properties, not separate relations for each property.) Justify your answer.

  11. Give three different equivalence relations on the set {a,b,c,d}.

  12. Let G be a directed graph with n vertices. Show that if G has a path of length greater than n, then G has a cycle.

  13. Give a pair of non-isomorphic undirected graphs each with six vertices where every vertex has degree exactly two.

  14. Let G=(V,E) be an undirected graph. The complement of G, G' is defined as the graph G'=(V,E') where E'={(v,w) | v is in V, w is in V, v!= w, (v,w) is not in E}. Give an example of a graph G such that both G and G' contain Hamiltonian circuits.

  15. Let G=(V,E) be a graph with |V| >= 5. Prove that if G is 2-colorable (bipartite), then G' (its complement) is not 2-colorable.

  16. The following terms are used in the propositional calculus. Give a one sentence definition for each of the terms.

  17. Give logical expressions for the following statements. Use quantifiers, connectives, and the predicates P(x) and H(x) which mean ``x passed the class'' and ``x turned in all of the homework''.

  18. Consider the English alphabet, which consists of 5 vowels and 21 consonants.

    You may express your answers as products of integers.
  19. Suppose that propositions p_1, p_2, ... , p_{n+1} are independently assigned random truth values, where the probability that p_i is true is 1/2.

  20. Let A={x, y, z}, B={1, 2, 3 ,4}, and C={a, b, c}. Let R be the following relation from A to B: R={(x,1), (x,2), (y,2), (y,3), (z,3)}, and S be the following relation from B to C: S={(1,a), (2,a), (2,b), (3, b), (4,b), (4,c)}. Compute the composition of R and S.

  21. Suppose R_1 and R_2 are transitive relations on a set A. Is the relation R_1 UNION R_2 necessarily a transitive relation? Justify your answer.

  22. Suppose R is the relation on the integers where xRy if and only if x = y+1. Describe the relation that is the transitive closure of R.

  23. Let the relation L be defined on the integers by x L y if |x| < |y| or (|x| = |y| and x <= y).

  24. For which values of n does K_n contain an Eulerian circuit. (K_n denotes the complete graph on n vertices, K_n is undirected.) Justify your answer.

  25. Let G=(V,E) be the undirected graph that has as its vertices the set of integers, and edges: E = {(x,x+3)| x is an integer}. Describe the connected components of G.

  26. How many edges do the following undirected graphs contain.

  27. Translate the following English sentences into predicate logic where the universe is the set of people and the allowable predicates are: S(x) : x is a student F(x,y) : x and y are friends O(x,y) : x is older than y

  28. Suppose that n >= 3 and p_1,..., p_n are propositions that are true or false independently with probability exactly 1/2. Justify your answers.

  29. In each of the following questions a relation R is defined. Assume that each R is defined over some natural set A. For each of the following properties, circle ALL those properties that ALWAYS apply and X out those properties that do NOT apply at least some of the time.

            [R] Reflexive
            [S] Symmetric
            [A] Antisymmetric
    	[T] Transitive
    
    You do not need to justify your answers.
  30. Here is a recursive definition of a "forest", a kind of undirected graph.

    Prove by induction that every forest with v vertices and e edges has exactly v-e connected components.
  31. Suppose that R is a relation on a set A. Prove or disprove: If R^2 is reflexive then R must be reflexive.

  32. Let R be the relation { (3,2), (3,4), (1,3), (2,1)} defined on the set {1,2,3,4,5}.
  33. Let n be a positive integer. A perfect matching on a set of 2n vertices is an undirected graph with n edges, such that each vertex has degree exactly 1. For example, there is one perfect matching on any set of two vertices (with edge set {{1,2}} if the vertices are {1,2}), and three distinct perfect matchings on four vertices (with edge sets {{1,2},{3,4}}, {{1,3},{2,4}}, and {{1,4},{2,3}} if the vertices are {1,2,3,4}). Prove by induction that the number of perfect matchings on 2n vertices is the product of the odd numbers less than 2n (so for n=2 it is 1x3).

  34. As part of its effort to make U.S. paper money harder to counterfeit, the U.S. Treasury has decided to redesign the 1, 5, 10, 20, and 50 dollar bills. However, people have grown tired of seeing boring presidents on the bills so the Treasury Department is looking for more appealing candidates to appear on these 5 different bills. They have narrowed the field of available candidates to seven actors {a_1,...,a_7}, eight basketball players {b_1,...,b_8}, six cartoon characters {c_1,...,c_6}, and five disc jockeys {d_1,...,d_5}. (These four sets are pairwise disjoint, so there are 26 candidates in all.) Please JUSTIFY your answers for each of the following questions about the possible choices the Treasury Department might make. (Answers in the form of arithmetic expressions involving only +,*,-,/ and !, are acceptable for full credit.)

  35. To qualify for championships in certain games or sports there are sometimes "round-robin tournaments" in which each team plays a exactly one game against each other team. Suppose that n>= 2 teams played a round-robin tournament and assume that there were no ties (i.e. each game had a winner.)

  36. In stud poker (as opposed to draw poker), 4 of the 5 cards in the poker hand are dealt 'face up' so that everyone can see them and one card is 'face down' so that nobody can see it. Suppose that we start with a perfectly shuffled deck so that the cards are equally like to be in any order. EXPLAIN your answers to each of the following questions:

  37. In the land of Garbanzo, the unit of currency is the bean. They only have two coins, one worth 2 beans and the other worth 5 beans.

  38. Let R be the relation { (1,2), (3,4), (1,3), (2,1) } defined on the set {1,2,3,4,5}.

  39. If R is a relation on a set A then we say that R is {\em total} if and only if FORALL x in A THERE EXISTS y in A, xRy. Prove that if R is symmetric and total then its transitive closure is also reflexive, i.e. R^+=R^*.

  40. For each n>= 0 define T_n>, the 'complete 3-ary tree of height n' as follows: Prove by induction that for each n>= 0, T_n has exactly (3^{n+1}-1)/2 vertices.
  41. Suppose that you have a rectangular cake which you need to cut into n rectangles of equal size by successively cutting the cake into chunks. Show that no matter how you do it you need to make exactly n-1 cuts in the cake (where a single cut is a straight line cut of one chunk, i.e. you are NOT allowed to line up several chunks and cut them at once.) (Hint: induction may help.)