Answers to Review Questions for the Final Exam

CS 280 - Spring 2002

Please let me know via email (chew@cs.cornell.edu) if you discover mistakes in my solutions.  Past experience indicates that I may have made some.

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)
      tautology
      [(p or q) -> r]  <->  [(p -> r) or (q -> r)]
      not a tautology (p=T, q=F, r=F)
    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.
      (p or ¬q or r) and (¬p or q or r)
    3. Can such a proposition P be constructed using connectives and and or only?  If yes, do.  Otherwise, show why not.
      No.  Every proposition built from and and or is false when all the atoms are false.
  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)
      Everybody loves somebody.
      (there exists x) L(x, b)  ->  L(m, b)
      If somebody loves Bob then Mary loves Bob.
      (for all x) (L(x,m)  ->  ¬L(b, x))
      Bob does not love anyone who loves Mary.
      L(b,b)  ->  ¬L(b, m)
      If Bob loves himself then he doesn't love Mary.
    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)
      The first is equivalent to the third.  The second is equivalent to the fourth (both are equivalent to True).
  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
      d, e, f, g, j are true
  4.  
    1. How many one-to-one functions from {a, b, c, d} onto {1, 2, 3, 4, 5} are there?
      None.  To be one-to-one and onto the sets must have the same number of elements.
    2. How many one-to-one functions f from {1, 2, 3, 4, 5} onto itself are there such that f = f -1?
      This can happen only when items are swapped in pairs.  There is one function where none are swapped.  There are C(5, 2) where a single pair is swapped.  There are C(5, 2) * C(3, 2) / 2 where two pairs are swapped.  The solution is the sum of these: 1 + 10 + 15 = 26.
    3. Let f be function.  Which of the following are true?
      f(A intersect B) = f(A) intersect f(B)
      False.  Let A be the interval [0, 1] and B be the interval [2, 3].
      f(A union B) = f(A) union f(B)
      True.  Consider y in f(A union B).  By definition, there exists an x in A union B such that f(x) = y.  Note that x is in A or x is in B.  If x is in A then y=f(x) is in f(A).  If x is in B then y=f(x) is in f(B).  In either case, y is in f(A) union f(B).  Consider y in f(A) union f(B).  Similar arguments show that y is in f(A union B).
      f -1(C intersect D) = f -1(C) intersect f -1(D)
      True.  Consider x in f -1(C intersect D).  By definition there exists a y in C and in D such that f(x)=y.  By definition, f -1(C) contains x and f -1(D) contains x.  Similar arguments show the other direction.
      f -1(C union D) = f -1(C) union f -1(D)
      True.  Consider x in f -1(C union D).  By definition there exists a y in C or in D such that f(x)=y.  In either case, x is in f -1(C) union f -1(D).  Other direction is similar.
      f(A) = f(A)
      False.
      f       -1(C) = f -1(C)
      True.  x in f -1(C) iff f(x) in C iff not(f(x) in C) iff not(x in f -1(C)) iff x in 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
      True for a, b, d, and e.
  6.  
    1. Use the Euclidean Algorithm to find gcd(111, 2222).
      gcd(111, 2222) = gcd(111, 2) = gcd(1, 2) = 1
    2. Find the inverse of 6 modulo 11.
      2
    3. Find a positive integer x such that x = 3(mod 9) and x = 5(mod 10).
      75
  7.  
    1. Perform the following operations on binary numbers.
      11011 + 10110 = 110001
      11011 * 10110 = 1001010010
      11011 / 10110 =    (find a quotient and a remainder) 11011 = 1*10110 + 101
    2. Transform (11011)2 into decimal.
      1 + 2 + 8 + 16 = 2710.
    3. How many bits can the binary expansion of a six decimal digit number have?
      Anywhere from 17 to 20 bits.
  8.  
    1. Determine which of the following propositions are tautologies. Show why.
      (p → ¬q) → ( ¬q → p)
      Not a tautology.  Consider p and q both false.
      [(p or q) → r] ↔ [(p → r) and (q → r)]
      Tautology.  Can show by manipulating propositions or by truth table.
    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.
      ( ¬p and  ¬q and r) or (p and  ¬q and r).  This is equivalent to ( ¬q and r).
    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.
      No.  Note that P is false when p, q, and r are all true.  But any combination of and and →  is always true.
  9.  
    1. Let L(x, y) be x loves y. Write the following as formal sentences with quantifiers.
      Everybody loves somebody.  (for all x)(there exists y)L(x, y)
      Everybody loves everybody.  (for all x)(for all y) L(x, y)
      Somebody loves everyone.  (there exists x)(for all y) L(x, y)
      Somebody loves someone.  (there exists x)(there exists y) L(x, y)
    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. 
      The middle two are equivalent and the first is equivalent to the last.  Here's a proof for the first and last: (for all x)(A(x) →B)
      <=> (for all x) [       ¬A(x) or B]   by def of →
      <=> (for all x) [      ¬A(x)] or B    by cases (B true or B false)
      <=>  [¬(there exists x) A(x)] or B   by negation of quantifiers
      <=> (there exists x) A(x)       → B   by def of →
  10. Which of the following are always true (A, B, C are arbitrary sets)?  Yes/No answers.
    1. if A subset B and B subset A then A = B
      True
    2. Ø elementOf {Ø}
      True
    3. Ø elementOf A
      False
    4. Ø subset A
      True
    5. if A != B and B != C then A != C
      False
    6. A-B = (Ac - Bc)c
      False (consider A=B)
    7. (A - B) intersect (B - A) = Ø
      True
    8. Ø x A = Ø
      True
    9. A x B = B x A
      False
    10. A union B = A union B
       False
  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?
    We know that f(f(f(x))) = x.  This can only happen if f(x)=x or if x is part of a 3-cycle (i.e., x maps to f(x) which maps to f(f(x)) which maps to x and x, f(x), and f(f(x)) are all different).  There are only 5 elements, so there is only room for one 3-cycle.  How many possible 3 cycles are there?  There are C(5, 3) ways to choose 3 element.  Once those elements are chosen there are 2 ways to form them into a 3-cycle (i.e., 1→2→3 is different from 1→3→2, but is the same as 2→3→1).  So there are 2C(5, 3) = 20 ways to have a 3-cycle; plus we have one more for no 3-cycles.  Thus the total number of functions is 21.
  12. Yes-No answers. Is it true that n2 is O(g(n)), if g(n) is 
    n   No
    n3    Yes
    n log n   No
    2n    Yes
    n!   Yes
    n2log n    Yes
    n2 + log n    Yes
    n2 / log n   No
    (n4 +1)/(n2 +1)    Yes
    (n4 +1)/(n +1)   Yes
  13. Find 520001 (mod 143). The answer should be a standard integer between 0 and 143.
    Ideally, we'd like to use Fermat's Little Theorem [ ap-1 = 1 (mod p) for p prime], but 143 is not prime since 143 = 11*13.  Note though that, by Fermat's Little Theorem, 510 = 1 (mod 11) and 512 = 1 (mod 13).  Thus 520001 = 5 (mod 11) and 520001 = 59 (mod 13).  Further, 52 = 25 = 12 = -1 (mod 13), so 520001 = 59 = 5(52)4 = 5(-1)4 = 5 (mod 13).  In other words, 520001 - 5 is divisible by both 11 and 13.  This implies that 520001 - 5 is divisible by 143, so the final answer is 5.
  14.  
    1. Perform the following operations on binary numbers: 
      1101 + 1011 = 11000
      1101 ·1011 = 10001111
      1101/1011 = (find a quotient and a remainder)
      1101 = 1011*1 + 10
    2. Transform (1101)2 into decimal.
      1 + 4 + 8 = 13
    3. Transform (1101)10 into binary.
      1101 = 1024 + 64 + 8 + 4 + 1 = (100 0100 1101)2.
  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,   Possible
      S(n) holds for all n ≥1, but S(0) is false,    Possible
      S(n) is false for all n ≥0,    Possible
      S(n) is true for all n ≤100 and false for all n >100,    Not possible
      S(n) is false for all n ≤100 and true for all n >100.   Possible
    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     No
      b      No
      c      No
      ab      Yes
      abb      No
      aabb     Yes
  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? 
      We can receive 8 from freshmen, 5 from sophomores, 8 from juniors, and 8 from seniors without getting 9 from any one group.  If we get one more, we have have at least 9 from some group so the answer is 8+5+8+8+1 = 30.
    2. How many bit strings are there of length 10 with two or more 1’s in the string?
      There are 210 bit strings.  Of these 1 has no ones and 10 have exactly one 1.  So the answer is 1024 - 10 -1 = 1013.
  17.  
    1. Find the number of positive integer solutions of x + y + z ≤100.
      We use a standard trick to convert this inequality into an equality: introduce a new variable w.  The problem becomes: Find the number of solutions to w + x + y + z ≤ 100 subject to the constraints that w>0 and x, y, and z are > 1.  Consider w, x, y, and z as bins.  Bins x, y, and z each start out holding one star.  We now have 97 stars to distribute into 4 bins (i.e., 3 bars).  Thus the answer is C(100, 3).
    2. A hostess wishes to invite 6 dinner guests. In how many ways can she place them on 6 distinguished seats?
      6! = 720
    3. The same question for a round table with indistinguishable seats.
      We place one guest.  Now there are 5! = 120 ways to place the remaining guests.
  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?
      15/36 = 5/12.
    2. one of those numbers is strictly less than the other one?
      This is always true except when doubles are rolled.  Answer: 30/36 = 5/6.
    3. the product of those numbers is even given that their sum equals 6?
      There are 5 ways for the sum to be 6 [(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)].  Of these 2 have an even product.  The answer is 2/5.
  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 ?
      Let X be the random variable representing the number of children.  We can list all the patterns that can occur: BG, GB, BBG, GGB, BBBG, GGGB, BBBBG, GGGGB, GGGGG, BBBBB.  The probability for each pattern is 1/2i where i is the length of the pattern.  So E(X) =  2(1/4 + 1/4) + 3(1/8 + 1/8) + 4(1/16 + 1/16) + 5(1/32 + 1/32 + 1/32 + 1/32) = 1/8[8 + 6 + 4 + 5] = 23/8.
      E(X2) = 4(4/8) + 9(2/8) + 16(1/8) + 25(1/8) = (16 + 18 + 16 + 25)/8 = 75/8.
      V(X) = E(X2) - E(X)2 = 75/8 -(23/8)2 = 71/64.
    2. girls ?
      Let B and G be the random variables for number of boys and number of girls, respectively.  We know that E(X) = E(B+G) = E(B) + E(G).  By symmetry E(B) = E(G).  Thsu E(G) = 23/16.
      E(G2) = 02(1/32) + 12(1/4 + 1/4 + 1/8 + 1/16 + 1/32) + 22(1/8) + 32(1/16) + 42(1/32) + 52(1/32) = (0 + 23 + 16 + 18 + 16 + 25)/32 = 98/32.
      V(G) = E(G2) - E(G)2 = 255/256.
  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?
    Use inclusion/exclusion.  Let A be the event "divisible by 2", B be the event "divisible by 3", and C be the event "divisible by 5".
    P(A union B union C) = P(A) + P(B) + P(C) - P(A intersect B) - P(A intersect C) - P(B intersect C) + P(A intersect B intersect C) = (500 + 333 + 200 - 166 - 100 - 66 + 33)/1000 = 734/1000.
  21. Give an example of a relation R that is 
    1. symmetric, not reflexive 
      R = {(x, y) | x = -y}
    2. reflexive, symmetric, not transitive.
      R = {(x, y) |  |x-y| = 1}
  22.  
    1. How many vertices and edges does the graph Q5 have? 
      The number of vertices doubles each time the dimension increases, so there are 25 = 32 vertices.  Each vertex has degree 5, so the number of edges is 32*5/2 = 80.
    2. A graph has 7 vertices, 3 of them of degree two and 4 of degree one. Is this graph connected? Why?
      No.  We can count the number of edges: (6 + 4) / 2 = 5.  A tree on 7 vertices has 6 edges, so the graph cannot have spanning tree and thus it cannot be connected.
  23. Which of the following graphs are planar? (Answer only)
    K5     Not planar
    Q3     Planar
    K2,5     Planar
    K3,5     Not planar
    K4,5     Not planar
  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.     Possible
      There is an integer M > 0 such that S(n) is true for all n < M and false for all n > M.     Impossible due to S(0).  The problem statement requires S(0) to be false.
      S(n) is true for all n.     Impossible due to S(0)
      There is an integer M > 0 such that S(n) is false for all n < M and true for all n > M.   Impossible
    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   All belong except this one.
      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.
      The year 2000 has 366 days (it's a Leap Year).  Answers are 1, 367, and 733, resepctively.
    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?
      52037.
  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?
      The panel must have 2 people who are both mathematicians and computer scientists.  Of the remainder 8 are mathematicians only and 10 are computer scientists only.  The committee can include both of the two dual-career people, one of the two dual-career people or none of the two dual-career people.  The answer is
      C(8, 1) C(10, 3) + 2 C(8, 2) C(10, 4) + C(8, 3) C(10, 5).
    2. Find the number of positive integer solutions of x + y < 100.
      We convert this to w + x + y = 100 where w > 0, x > 0 , and y > 0.  Thus, we have 98 items to place into 3 bins (i.e., two bars).  The answer is C(100, 2) = 4950.
  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).
      There are 26 = 64 possible ways to have a family of 6 children.  Of these there are just 2 ways to avoid having both a girl and a boy.  Answer: 62/64 = 31/32.
    2. What is the most likely number of boys?
      Let B be the random variable for the number of boys.
      E(B) = 0(1/64) + 1(6/64) + 2(C(6, 2)/64) + 3(C(6, 3)/64) + 4(C(6, 4)/64) + 5(C(6, 5)/64) + 6(1/64)
      = (6 + 30 + 60 + 60 + 30 + 6)/64 = 192/64 = 3.
      Alternately, let G be the random variable for the number of girls.  We know 6 = E(B+G) = E(B) + E(G).  By symmetry E(G) = E(B) = 3.
    3. Find the probability of having at least one girl given the first three children are boys.
      Let A be the event "at least one girl" and let B be the event "the first 3 are boys".  We want to find P(A|B) = P(A intersect B) / P(B) = [(3 + 3 + 1)/64] / [8/64] = 7/8.
  28. A fair die is rolled until the sum of the spots exceeds 2.  What is the expected number of rolls?
    The only way to use 3 rolls is to roll 1, 1, and then anything.
    Two rolls are used by 1, anything>1.
    Two rolls are used by 2, anything.
    One roll is used by anything>2.
    Expected number of rolls = 3(1/6)(1/6) + 2(1/6)(5/6) + 2(1/6) + 1(4/6) = (3 + 10 + 12 + 24)/36 = 49/36.
  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?
    Let A be the event "is divisible by 2", B be the event "is divisible by 3", and C be the event "is divisible by 5".  Observe that the event we want is (A union B union C) - C and that C is a subset of (A union B union C).  Thus we want P(A union B union C) - P(C).
    P(A union B union C) - P(C) = P(A) + P(B) - P(A intersect B) - P(A intersect C) - P(B intersect C) + P(A intersect B intersect C)
    = (50 + 33 - 16 - 10 - 6 + 3)/100 = 54/100.
  30. Give an example of a relation on {a, b, c} wich is
    1. reflexive, not symmetric
      The standard < works here.
    2. irreflexive, symmetric
      The not-equal relation works here.
    3. reflexive, symmetric, not transitive
      R = {(a, a), (b, b), (c, c), (a, b), (b, a), (b, c), (c, b)}
  31.  
    1. Reorder the words in this phrase lexicographically.
      in, lexicographically, phrase, Reorder, the this, words
    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)?
      Use {a, b, c, d} where d<b and d<c.  This results in a, b, and c maximal, while a and d are minimal.  There is no greatest elements or least element.
  32.  
    1. Indicate all possible vertex degrees occurring in the following graphs: K3, C17, K3,5, Q4.
      2, 2, (3, 5), 4
    2. Is there a simple graph with exactly 3 vertices of degree 3?
      Yes (there have to be some other vertices of odd degree as well).
    3. Is there a simple graph with 10 vertices and 46 edges?
      No. The complete graph on 10 vertices has C(10, 2) = 45 edges.
    4. Is there a connected graph with 100 vertices, 96 of them of degree two and 4 of degree one?
      No.  Such a graph would have [(2*96) + 4 ] / 2 = 98 edges.  A spanning tree on 100 vertices needs 99 edges, so such a graph cannot be connected.
  33. Which of the graphs in 32a are planar (answers only)?
    planar, planar, not planar, not planar
  34.  
    1. Represent (p → ¬p) → ( p → q) using an ordered rooted tree.
      Trivial.
    2. What is the prefix form of the expression (x - y)2 - (x + y)2?
      Represent as a tree and traverse the tree in preorder.
    3. What is the value of the prefix expression - * 1 / 6 2 3?
      zero