Final Exam Practice Questions (and answers)

DISCLAIMER: THESE QUESTIONS DO NOT NECESSARILY REPRESENT WHAT WILL BE ON THE MIDTERM.

Answers will be posted Thursday night.

1. Each of the following are proposed as rules of inference. Prove or disprove their validity.

       (a)  p V q      (b)  (p & q) -> r
            not p            not r
           ------           ------------
            q               not p
   

2. Write the following in English and state our opinion as to whether they are true or false (showing that you understand what they mean). N(x) = "x is a nerd" C(x) = "x works with computers" M(x) = "x is a man" F(x) = "x is friendly"
   Universe = people
   1. for-all x [N(x)-> ¬ F(x)]
   2. there-exists x [C(x) & ¬ M(x)]
   3. ¬ there-exists x [C(x) & ¬ N(x)]
   4. ¬ for-all x [N(x) -> C(x)]
3. Prove using the rules of inference or disprove. If proving, label each step.

   (a)  Duke is a labrador retriever.
        All labrador retrievers like to swim.
        Therefore Duke likes to swim.
   UNIVERSE = dogs
   (b)  All even numbers that are also greater than 2 are not prime.
        2 is an even number.
        2 is prime.
        Therefore some even numbers are prime.
   UNIVERSE = numbers
   (c)  If it is hot today or raining today then it is no fun to snow ski today.
        It is no fun to snow ski today.
        Therefore it is hot today.
   UNIVERSE = days.
   (d) It is not fun to snow ski today if it is too warm or raining today.
       It is too warm today.
       Therefore it is not fun to snow ski today.
   UNIVERSE = days.
   

4. Answer the following counting questions.
   1. How many possible assignments are there for the logical expression (p V q) & (¬ p V r)?
   2. You have 3 textbooks worth $100 and 3 textbooks worth $50. How many ways can you sell enough textbooks to make $200 exactly? (Hint: consider the possible cases)
   3. You are planning a dinner party. There are 6 possible appetizers, 5 possible main courses, and 4 possible desserts. How many ways can you choose 3 appetizers, 2 main courses, and 3 desserts?
   4. Same setup as above, how many ways can you choose 6 things total (any combination of appetizers, main courses, desserts that adds up to 6).
   5. How many binary strings of length n contain exactly 3 ones (assume n >= 3)?
   6. How many license plates of 3 letters and 3 numbers contain the letters "c" and "s"
   7. Given 10 2-digit numbers,what is the probability that no 2 are the same? I.e., figure how many ways can you pick 10 that are all different and then divide by the total number of possible 2 digit numbers.
5. True or False. Explain.
   1. Any relation is also a function.
   2. Any function is also a relation.
   3. All functions have inverses.
   4. f(x):Z^+ -> positive-evens ; f(x) = 2x ; is bijective.
6. Give an example of an equivalence relation.
7. Consider the following recurrence relation:

      t(n) = t(n-1) + 2n-1
      t(1) = 1
   

   1. Guess a closed form formula by looking at small values.
   2. Here is a wrong formula: t(n) = n^2 - n . Try to prove it by induction and show the proof fails.
   3. Prove your guessed formula by induction.
8. Using the fact: "if c|a then there exists integer k such that c*k = a" Prove:
   1. If 2|n then 2|n-2.
   2. If c|a and c|b then c|(a-b).
   3. If c|a and c|b then c|a mod b. Use this fact too: a = (a div b)*b + (a mod b). This is extra credit.
9. Prove or disprove. State whay type of proof used.
   1. If 9 is prime then 9 is not divisible by 3.
   2. If x is prime then x^2 is positive.
   3. For all integers a and b, if a divides b*p, where p is a prime, then a divides b.
10. Determine tightest possible bound for each function. Prove that the function is O(bound), Omega(bound), and theta(bound).
    1. f(n) = 1 + 2 + ... + n
    2. f(n) = 2*log_2{n/2} + 2
    3. f(n) = 3n^2 + 4n - 5
    4. f(n) = n!/(n-2)!
    5. f(n) = 3n log n - 2n - 3log n.