Review Questions for the Final Exam

CS 280 - Spring 2002

The Final Exam takes place at noon on Tuesday, May 14, in our regular classroom (Olin 155). I will try to arrive early so that we can start right at noon.  Although the final exam will be somewhat longer than the two prelims, I do not expect that you will need the entire 2.5 hours allotted by the registrar for the final exam.  The final exam is worth 30% of your final grade; the homework is worth 30%; and the two prelims are each worth 20%.

The use of extra material is not permitted during the exam (i.e., no textbook, no notes, no calculator, etc.).

The exam includes material from readings and lecture throughout the semester, although the material covered since Prelim II will be stressed more heavily.  See the Schedule for a list of topics covered in lecture and for the corresponding readings.  The exam will attempt to gauge your knowledge and understanding of course concepts. You shouldn't need to memorize specific code given in the text or in lecture.

The review questions given here are not meant to exhaust the possible topics for exam questions.  Consider reviewing the previous Review Questions, Prelims I and II, the homework assignments, and the appropriate sections of the text.

Most of these questions are from exams given in previous incarnations of cs280.

  1.  
    1. Determine which of the following propositions are tautologies.  Show why.
      (p -> (not p)) -> (p -> q)
      [(p or q) -> r]  <->  [(p -> r) or (q -> r)]
    2. Write down a proposition P over the variable p, q, r such that P is false only when p, q, r have truth values false, true, false or true, false, false, respectively.
    3. Can such a proposition P be constructed using connectives and and or only?  If yes, do.  Otherwise, show why not.
  2.  
    1. Let L(x, y) be x loves y, b be Bob, m be Mary.  Give English language translations of the following symbolic sentences (do not use variables in the answer).
      (for all x) (there exists y) L(x,y)
      (there exists x) L(x, b)  ->  L(m, b)
      (for all x) (L(x,m)  ->  ¬L(b, x))
      L(b,b)  ->  ¬L(b, m)
    2. Which of the following sentences are logically equivalent?  In principle, you have to determine equivalence for all 6 pairs of sentences.
      (there exists x)(A(x) -> B(x))
      (there exists x)(A(x)  ->  (for all y)A(y))
      (for all x)A(x)  ->  (there exists x)B(x)
      (there exists x)B(x)  or  (for all y)¬B(y)
  3. Which of the following are true (A and B are arbitrary sets)?  Yes/No answers. The symbols for set operations are difficult in html, so the notation here is odd.
    1. if A subset B and B={Ø} then A=B.
    2. if A subset B and B={Ø} then A=Ø.
    3. Ø elementOf A
    4. Ø subset A
    5. (A union Bc)c = B intersect Ac
    6. A intersect B = (Ac union Bc)c
    7. (A - B) intersect (B - A) = Ø
    8. if A x B = Ø then A=Ø and B=Ø
    9. A subset A x A
    10. A x A = A for some A
  4.  
    1. How many one-to-one functions from {a, b, c, d} onto {1, 2, 3, 4, 5} are there?
    2. How many one-to-one functions f from {1, 2, 3, 4, 5} onto itself are there such that f = f -1?
    3. Let f be function.  Which of the following are true?
      f(A intersect B) = f(A) intersect f(B)
      f(A union B) = f(A) union f(B)
      f -1(C intersect D) = f -1(C) intersect f -1(D)
      f -1(C union D) = f -1(C) union f -1(D)
      f(A) = f(A)
      f -1(C) = f -1(C)
  5. Yes/No answers.  Is it true that n2 is O(g(n)) if g(n) is
    1. 100n2 + 101n
    2. n3
    3. n log n
    4. n2log n
    5. n2 + log n
  6.  
    1. Use the Euclidean Algorithm to find gcd(111, 2222).
    2. Find the inverse of 6 modulo 11.
    3. Find a positive integer x such that x = 3(mod 9) and x = 5(mod 10).
  7.  
    1. Perform the following operations on binary numbers.
      11011 + 10110 =
      11011 * 10110 =
      11011 / 10110 =    (find a quotient and a remainder)
    2. Transform (11011)2 into decimal.
    3. How many bits can the binary expansion of a six decimal digit number have?
  8.  
    1. Determine which of the following propositions are tautologies. Show why.
      (p → ¬q) → ( ¬q → p)
      [(p or q) → r] ↔ [(p → r) and (q → r)]
    2. Write down a proposition P over the variables p, q, and r such that P is true only when p, q, r have truth values FFT or TFT.
    3. Can such a P be constructed using the connectives and and → only (no truth constants for T and F are allowed)? If yes, do so. Otherwise show why not.
  9.  
    1. Let L(x, y) be x loves y. Write the following as formal sentences with quantifiers.
      Everybody loves somebody.
      Everybody loves everybody.
      Somebody loves everyone.
      Somebody loves someone.
    2. Which of the following sentences are logically equivalent (answer only)? In principle you have to determine the equivalence of all 6 pairs of sentences.  Assume B does not contain x.
      (for all x)(A(x) →B),
      (for all x)A(x) →B,
      (there exists x)(A(x) →B),
      (there exists x)A(x) →B. 
  10. Which of the following are always true (A, B, C are arbitrary sets)?  Yes/No answers.
    if A subset B and B subset A then A = B
    Ø elementOf {Ø}
    Ø elementOf A
    Ø subset A
    if A != B and B != C then A != C
    A-B = (Ac - Bc)c
    (A - B) intersect (B - A) = Ø
    Ø x A = Ø
    A x B = B x A
    A union B = A union B
  11. How many one-to-one functions f from {1, 2, 3, 4, 5 }onto itself are there such that f ◦f ◦f is the identity function?
  12. Yes-No answers. Is it true that n2 is O(g(n)), if g(n) is 
    n 
    n3 
    n log n 
    2n 
    n!
    n2log n 
    n2 + log n 
    n2 / log n 
    (n4 +1)/(n2 +1) 
    (n4 +1)/(n +1)
  13. Find 520001 (mod 143). The answer should be a standard integer between 0 and 143.
  14.  
    1. Perform the following operations on binary numbers: 
      1101 + 1011 = 
      1101 ·1011 = 
      1101/1011 = (find a quotient and a remainder)
    2. Transform (1101)2 into decimal.
    3. Transform (1101)10 into binary.
  15.  
    1. Suppose that S(n) is a proposition involving a nonnegative integer n, and suppose that if S(k) is true then so is S(k + 2). Which of the following are possible (answer only)? 
      S(n) holds for all n ≥0, 
      S(n) holds for all n ≥1, but S(0) is false, 
      S(n) is false for all n ≥0, 
      S(n) is true for all n ≤100 and false for all n >100, 
      S(n) is false for all n ≤100 and true for all n >100.
    2. A collection S of strings of characters is defined recursively by (1) the empty string is in S and (2) if X belongs to S then so does aXb. Which of the following belong to S (Yes-No answers): 
      a 
      b 
      c 
      ab 
      abb 
      aabb
  16.  
    1. A questionnaire is sent to 13 freshmen, 5 sophomores, 15 juniors, and 20 seniors. A student won’t necessarily return his/her questionnaire. How many questionnaires must be received to ensure getting 9 from the same class? 
    2. How many bit strings are there of length 10 with two or more 1’s in the string?
  17.  
    1. Find the number of positive integer solutions of x + y + z ≤100.
    2. A hostess wishes to invite 6 dinner guests. In how many ways can she place them on 6 distinguished seats?
    3. The same question for a round table with indistinguishable seats.
  18. Two fair dice are rolled. What is the probability that
    1. the number on the first die is strictly less than the number on the second die?
    2. one of those numbers is strictly less than the other one?
    3. the product of those numbers is even given that their sum equals 6 ?
  19. A couple agrees to keep having children until they have at least one boy and one girl, but not more than 5 children. Assume that boys and girls are equiprobable and that the births are mutually independent. What is the expected value and variance of the number of 
    1. children ?
    2. girls ?
  20. An integer is randomly selected from 1 to 1000. What is the probability that it is divisible by 2 or by 3 or by 5?
  21. Give an example of a relation R that is 
    1. symmetric, not reflexive 
    2. reflexive, symmetric, not transitive.
  22.  
    1. How many vertices and edges does the graph Q5 have? 
    2. A graph has 7 vertices, 3 of them of degree two and 4 of degree one. Is this graph connected? Why?
  23. Which of the following graphs are planar? (Answer only)
    K5
    Q3
    K2,5
    K3,5
    K4,5
  24.  
    1. Suppose that S(n) is a proposition involving a nonnegative integer n, and that if S(k) is false for all k<n then so is S(n).  Which of the following are possible (answers only).
      S(n) is false for all n.
      There is an integer M > 0 such that S(n) is true for all n < M and false for all n > M.
      S(n) is true for all n.
      There is an integer M > 0 such that S(n) is false for all n < M and true for all n > M.
    2. A collection S of strings of characters is defined recursively by (1) a belongs to S and (2) if Xa belongs to S then so do Xaa and Xb.  Which of the following belong to S?
      b
      aa
      ab
      abb
      aab
  25.  
    1. How many students must be in a class to guarantee at least k students with the same birthday in the year 2000?  Answer for k=1, k=2, and k=3.
    2. A multiple choice exam has 20 questions, each with 5 possible answers, and 7 additional questions, each with 3 possible answers.  How many different answer sheets are possible?
  26.  
    1. In how many ways can a committee of 3 mathematicians and 5 computer scientists be selected from a panel of 20 having 10 mathematicians and 12 computer scientists?
    2. Find the number of positive integer solutions of x + y < 100.
  27.  
    1. Find the probability that a family with six children has a boy and a girl (sexes of children are assumed equiprobable and independent).
    2. What is the most likely number of boys?
    3. Find the probability of having at least one girl given the first three children are boys.
  28. A fair die is rolled until the sum of the spots exceeds 2.  What is the expected number of rolls?
  29. An integer is randomly selected from 1 to 100.  What is the probability that it is divisible by 2 or by 3, but not by 5?
  30. Give an example of a relation on {a, b, c} wich is
    1. reflexive, not symmetric
    2. irreflexive, symmetric
    3. reflexive, symmetric, not transitive
  31.  
    1. Reorder the words in this phrase lexicographically.
    2. Find the smallest possible poset having exactly two minimal elements and exactly three maximal elements.  Does it have a greatest element and a least element (answers only)?
  32.  
    1. Indicate all possible vertex degrees occurring in the following graphs: K3, C17, K3,5, Q4.
    2. Is there a simple graph with exactly 3 vertices of degree 3?
    3. Is there a simple graph with 10 vertices and 46 edges?
    4. Is there a connected graph with 100 vertices, 96 of them of degree two and 4 of degree one?
  33.  Which of the graphs in 32a are planar (answers only)?
  34.  
    1. Represent (p → ¬p) → ( p → q) using an ordered rooted tree.
    2. What is the prefix form of the expression (x - y)2 - (x + y)2?
    3. What is the value of the prefix expression - * 1 / 6 2 3?