handout #24

CSE311—Foundations of Computing I
Sample Final Questions

  1. The table below contains English descriptions in terms of x and y of relations on the set Z+ (x being related to y iff the described condition holds). Fill in the table indicating whether each relation is reflexive, symmetric, antisymmetric or transitive.

    Relation reflexive? symmetric? antisymmetric? transitive?
    x - y = 10        
    x - y < 10        
    xy = yx        

  2. Consider the relation R on Z+ composed of all ordered pairs (x, y) for which:
    |x - 2| ≤ |y - 2|
    Is R a partial ordering? Why or why not?

  3. Prove that the difference of the cubes of two integers is always 2 more than a multiple of 6 when the difference of the integers is 2. Be sure to indicate the proof technique you are using to solve this problem.

  4. Prove or disprove that the product of two consecutive integers is never 4 more than a multiple of 7. Be sure to indicate the proof technique you are using to solve this problem.

  5. Prove or disprove that the difference of the squares of two positive integers is prime only if the two integers have a difference of 1 (e.g., 62 - 52 = 11 and 72 - 62 = 13). Be sure to indicate the proof technique you are using to solve this problem.

  6. Prove using induction that in a rooted binary tree of height h, the number of vertices is at most 2h + 1 - 1. Recall that using the definitions of Rosen section 10.1, the height of a rooted binary tree is the length of the longest path from the root to a leaf. As a result, the tree of one vertex has a height of 0. Be sure to indicate what you are doing induction on (edges, vertices, height, etc).

  7. The table below contains English descriptions in terms of x and y of relations on the set Z+ (x being related to y iff the described condition holds). Fill in the table indicating whether each relation is reflexive, symmetric, antisymmetric or transitive.

    Relation reflexive? symmetric? antisymmetric? transitive?
    x + y = 2        
    (x - 5)2 = (y - 5)2        
    xy = 9        
    2x = 3y        
    2 | xy        
    2 | x(y + 1)        
    x mod y = 0        

  8. Prove that there are no three consecutive positive integers such that the cube of the third is the sum of the cubes of the first two. Be sure to indicate the proof technique you are using to solve this problem.

  9. Prove that a number is irrational if its square is irrational. Be sure to indicate the proof technique you are using to solve this problem.

  10. Assuming that the sum of two real-valued variables x and y is a constant c:

    x + y = c
    Prove that the product xy is maximal when x = y. You are not allowed to use calculus. Be sure to indicate the proof technique you are using to solve this problem.

  11. The table below contains English descriptions in terms of x and y of relations on the set Z+ (x being related to y iff the described condition holds). Fill in the table indicating whether each relation is reflexive, symmetric, antisymmetric or transitive. For this problem we define a function power2(n) to be the maximum value m in N such that 2m | n (the highest power of 2 that divides n).

    Relation reflexive? symmetric? antisymmetric? transitive?
    power2(x) = power2(y)        
    power2(x) <= power2(y)        
    x mod 10 = y mod 10        
    x ⋅ y = 48        
    x ⋅ y = 1        
    2 | (x - y)        
    xy < 100        

  12. Show that for an any positive integer n, 4n + 3 and 5n + 4 are relatively prime. (Hint: Use Euclid's algorithm. Do not use induction.)

    1. Consider the following relation over the set of sets.

      R = {(A, B) | A ∩ B ≠ ∅}
      Is R an equivalence relation? Why or why not?

    2. If so, let A = {1, 2, 3}. What is another set in the equivalence class of A? If not, leave this space blank.

  14. Prove the statement: "For any integers a, b, and c, if there exists an integer m such that b is not congruent to c in modulo m, then either a ≠ b or a ≠ c." Be sure to indicate the proof technique you are using to solve this problem.

  15. Prove using mathematical induction that:
    1/(1 ⋅ 3) + 1/(3 ⋅ 5) + 1/(5 ⋅ 7) + 1/(7 ⋅ 9) + ... + 1/((2n - 1)(2n + 1)) = n/(2n + 1)
    Provide a formal definition for the overall proposition being proved (P(n)) using summation notation and indicate the domain for n. Then provide an inductive proof, clearly indicating where you are applying the inductive hypothesis.

  16. Prove that in a rooted binary tree, the number of leaves is one more than the number of vertices with two children. Recall that using the definitions of section 10.1, trees are not allowed to be empty (they have at least one vertex). Be sure to indicate what you are doing induction on (edges, vertices, height, etc).

Stuart Reges
Last modified: Wed Dec 8 17:39:38 PST 2010