Answers to Review Questions for Prelim I

CS 280 - Spring 2002

Three mistakes have been corrected: 

The exam takes place in class on Friday, February 22. I will try to arrive early so that we can start right at 1:25pm.

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 through Monday, February 18.  See the Schedule for a list of topics covered in lecture and for the corresponding readings; the topics and readings are also summarized below.  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  topics covered on the exam (and the corresponding sections of the text) include:

The review questions given here are not meant to exhaust the possible topics for exam questions.  Consider reviewing both the homework assignments and the appropriate sections of the text.

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.

  1. For each of the following statements, make the statement into a proposition, determine its negation, and write a sentence that corresponds to the negation.  An answer based on the strategy of using the phrase "It is not the case that" followed by the original sentence is not acceptable.  If the sentence has more than one interpretation then determine the result for each reasonable interpretation.  Remember that a propositional function can use more than a single variable.
    For most of these, there is more than one correct answer.
    1. Every email is written by an annoying and ridiculous student.  (This sentence was suggested by one of the CS280 students in an email question.)
      This sentence can be interpreted as "Every email is written by a single student who is both annoying and ridiculous," and also as "Every student that wrote an email is both annoying and ridiculous." 
      Let P(x,y) represent "x is an email written by student y". 
      Let Q(y) represent "student y is annoying". 
      Let R(y) represent "student y is ridiculous". 
      Under the first interpretation the sentence is: 
      (there exists y) ( Q(y) and R(y) and (for all x) P(x,y) ). 
      Its negation is: (for all y) ( not Q(y) or not R(y) or (there exists x) (not P(x,y)) ). 
      Rewriting to make it an implication: 
      (for all y) ( not(Q(y) and R(y)) or (there exists x) (not P(x,y)) ) 
      (for all y) ( (Q(y) and R(y)) -> (there exists x) (not P(x,y)) ). 
      Or in words: "For all students that are ridiculous and annoying there exists some email that they did not write." 
      Under the second (and, I think, more reasonable interpretation) the sentence is: 
      (for all x) (for all y) (P(x,y) -> (Q(y) and R(y))).  Rewriting to remove the implication: 
      (for all x) (for all y) ( not P(x,y) or (Q(y) and R(y)) ).  Its negation is: 
      (there exists x) (there exists y) ( P(x,y) and (not Q(y) or not R(y)) ). 
      Or in words: "There is a student who sent an email and that student is either not ridiculous or not annoying."
    2. Every Friday something is due for CS280.
      Let F(x) represent "the day x is a Friday".
      Let D(y, x) represent "y is due for CS280 on day x."
      One interpretation of the sentence is:
      (for all x)( F(x) -> (there exists y)D(y, x) )
      We replace the implication (to make negation easier), getting 
      (for all x)( (not F(x)) or (there exists y)D(y,x) ).  Negating, we get
      (there exists x)( F(x) and (for all y)(not D(y,x)) ).  In English, this is: "There is a Friday on which nothing is due."
    3. No cow has 5 legs and a cow has 4 more legs than no cow; thus, a cow has 9 legs.
      Let L(x, y) represent "cow x has y legs".
      Let M(n, y) represent "n cows have y legs".
      The sentence can be written as:
      ( (not (there exists x) L(x, 5)) and (for all y)(M(0,  y) -> M(1, y+4)) ) -> M(1, 9).
      Writing the sentence in this way makes it clear that the original sentence confuses "no cow" meaning "not (there exists a cow)" with "no cow" meaning "zero cows".  Negation is straightforward once the implications have been converted to or-clauses.
    4. There is a kid of age 5 who doesn't like chocolate.
      Let A(k, x) represent "kid k is age x".
      Let C(k) represent "kid k likes chocolate."
      The sentence can be written as:
      (there exists k)(A(k, 5) and (not C(k))).  Negating, we get:
      (for all k)((not A(k, 5) or C(k)).  We can recognize this as an implication:
      (for all k) (A(k, 5) -> C(k)).  As an English sentence, this is:
      "All 5-year-old kids like chocolate."
       
  2. Chinese Remainder Theorem
    For these examples, the inverses can be found easily using simple trial-and-error because the moduli are so small.
    1. x = 3 (mod 5)
      x = 2 (mod 7)
      x = 1 (mod 9)    What is x?
      We need the inverse of 7*9 = 63 = 3 (mod 5).  The inverse is 2.
      We need the inverse of 5*9 = 45 = 3 (mod 7).  The inverse is 5.
      We need the inverse of 5*7 = 35 = 8 (mod 9).  The inverse is 8.
      Thus 2*63 is 1 mod 5, but zero for the other two moduli.
      Similarly 5*45 is 1 mod 7 and zero otherwise; 8*35 is 1 mod 9 and zero otherwise.
      A solution is thus 3*2*63 + 2*5*45 + 1*8*35 = 378 + 450 + 280 = 1108.  The Chinese Remainder Theorem tells us there is only one solution between 0 and 5*7*9=315.  1108=163(mod 315), so 163 is the final answer.
    2. x = 4 (mod 5)
      x = 5 (mod 6)
      x = 6 (mod 7)    What is x?
      We need the inverse of 6*7 = 42 = 2 (mod 5).  The inverse is 3.
      We need the inverse of 5*7 = 35 = 5 (mod 6).  The inverse is 5.
      We need the inverse of 5*6 = 30 = 2 (mod 7).  The inverse is 4.
      A solution is thus 4*3*42 + 5*5*35 + 6*4*30 = 2099, but we want to stay below 5*6*7=210.  2099 mod 210 = 209, so 209 is the final answer.
       
  3. Suppose we represent x as the ordered quadruple (x mod 7, x mod 8, x mod 9, x mod 11).
    1. What is the quadruple corresponding to 57?
      (1, 1, 3, 2)
    2. What is the quadruple corresponding to 23?
      (2, 7, 5, 1)
    3. What is the quadruple corresponding to 23*57?
      It's easiest to find this by multiplying the two previous quadruples, resulting first in (2, 7, 15, 2) and then in (2, 7, 6, 2) (i.e., the 3rd entry is reduced modulo 9).
    4. What is the largest number that can be conveniently represented using this scheme?
      To decode a quadruple, we need to use the Chinese Remainder Theorem.  This result will be unique only for numbers between 0 and 7*8*9*11.  Thus the largest number that can be represented is 7*8*9*11 - 1 = 5543.
       
  4. Solve for x in each of the following  linear congruences:
    1. 15 x = 3 (mod 17)
      We need the inverse of 15 (mod 17).  The gcd pairs we get when using Euclid's Algorithm are
      gcd(15, 17)
      = gcd(15, 2)
      = gcd(1, 2)
      = gcd(1, 0)=1.
      Working backward on this list, we have
      1= 1(2) - 1(1) = 1(2) - 1(15 - 7*2) = 8(2) - 1(15) = 8(17-15) -1(15) = 8(17) -9(15).
      Thus the inverse of 15 (mod 17) is -9 = 8 (mod 17).  Multiplying each side of the original equation by the inverse, we get
      x = 24 = 7 (mod 17).
    2. 123 x = 2 (mod 16)
      We can rewrite this equation as
      11 x = 2 (mod 16).  The inverse (mod 16) of 11 is 3.  Multiplying through by the inverse, we get
      x = 6 (mod 16).
    3. 57 x = 33 (mod 95)
      We need the inverse of 57 (mod 95).  The gcd pairs using Euclid's Algorithm:
      gcd(57, 95)
      = gcd(57, 38)
      = gcd(19, 38)
      = gcd(19, 0) = 19.  Thus, 57 does not have a multiplicative inverse (mod 95) because for the inverse to exist, the gcd must be one.  We can show that there is no possible solution: If a solution existed then we would have 57x - 33 = 95 k, for some k, by definition of congruence.  This can be rewritten as 33 = 57x - 95k.  But this is impossible (assuming x and k are integers) since the right side is divisible by 19 and the left side is not.
    4. 27 x = 11 (mod 88)
      We need the inverse of 17 (mod 88).  The gcd pairs:
      gcd(27, 88)
      = gcd(27, 7)
      = gcd(6, 7)
      = gcd(6, 1) = 1.
      Working backward, we have
      1 = 0(6) + 1(1) = 0(6) + 1(7 - 6) = 1(7) - 1(6) = 1(7) - 1(27 - 3*7) = 4(7) - 1(27)
      = 4(88 - 3*27) - 1(27) = 4(88) - 13(27).
      Thus the inverse of 27 (mod 88) is -13.  Multiplying through by the inverse, we get
      x = -143 = 33 (mod 88).
       
  5. (from CS280, Problem Set  4, Fall 2000)
    A good algorithm is one for which the number of basic operations on an input n can be bounded by a function proportional to (log n)c, for some fixed exponent c (i.e., like c =1 or c =2).  A bad algorithm is one for which such a bound does not hold; intuitively, it’s an algorithm for which the running time on input n scales more like n than like the number of digits in n.  Thus, we saw that the elementary-school algorithms for addition and multiplication are good algorithms.  Much less obviously, Euclid’s Algorithm for greatest common divisors is a good algorithm.  On the other hand, to find the prime factors of a number n, the approach of trying all possible divisors is a bad algorithm; indeed, no good algorithm is known for factoring, and it’s suspected that no good algorithm exists. RSA can clearly be broken by a bad algorithm —simply factor the public key by brute force.  The real question is, can it be broken by a good algorithm?  Let’s explore this idea in more detail...
    1. The phone rings one day and you pick it up.  The voice at the other end says, “Hello, is this Professor Rivest?”  You mean to say “No,” but for some reason you say “Yes ”instead; the next thing you know, people from a mysterious company arrange to fly you out to the West Coast to advise them on their security system. “We have a system where we put 100 agents out in the field,” they explain to you, in a sub-basement surrounded by electromagnetic shielding.  “Each agent announces an RSA public key, and then they use the RSA cryptosystem to send messages to each other using these public keys.  We ’re not concerned about whether the agents know each other’s private keys or not —we ’re all on the same team, after all —but we’re very worried about outsiders learning the private keys. “Here’s the basic code we planned to use to assign a public key to each agent: 
      Method I: 
          For i =1 , 2 , ,...,100 
              Generate a prime number pi. 
              Generate a prime number qi.
              Use pi and qi to compute private and public keys for agent i.
      End 
      “After looking at this for a while, we thought: ‘Isn’t Method I sort of wasteful of primes?’ So we came up with Method II:
      Method II: 
          First generate prime numbers p1,p2,...,p101 
          For i =1 , 2 , ,...,100 
              Use pi and pi+1 to compute private and public keys for agent i. 
      End 
      “Notice how we only use about half as many primes in Method II.  But we’re worried that Method II is somehow insecure —that if our enemies knew we were using Method II to compute keys, they could compute the private keys from the public keys by a good algorithm.”  So here’s the question: show that in fact the company’s fears are well-founded.  Given a set of 100 public keys known to be generated by Method II, show how to compute the 100 corresponding private keys by a good algorithm. (Note. The point is that, in trying to break the keys, you know that Method II was used, but you (obviously) don ’t know at the outset what the primes p1,p2,...,p101 are.  Also, here is a crucial thing: your good algorithm is allowed to have a factor proportional to the number of agents in its running time, since this is simply the (small) constant 100.)
      Suppose we are an adversary trying to determine the private keys.  Each public key looks like a pair (e, n) where n is a product of two large primes.  But because the primes are re-used, we should be able to find a pair of public keys (e, n) and (e', n') such that n and n' share a prime factor.  Once we have n and n', we can use Euclid's Algorithm to determine the prime factor that they have in common.  Since there are only 100 public keys, we can try all pairs (there are 4950 such pairs), using Euclid's Algorithm to find common factors.  Once all the prime factors are known we can generate all private keys and read any message we want.
    2. Your discovery that Method II is insecure causes much uproar; but when this dies down, they remember another method for generating public keys they want to tell you about. “Basically, here’s how it goes.  For each agent i we start with a fresh prime number pi   Now we need a second prime qi to complete the construction of the keys.  So we start at 1+pi, and test each natural number in order for primality until we first find one that is prime.  We use this as the second prime qi.  If we try 2 log pi numbers and none of them is prime, then we decide this is taking too long and start over with a new choice of pi —but in practice this rarely happens. 
      Unfortunately, this method (call it Method III) is also insecure.  Given a set of 100 public keys known to be generated by Method III, show how to compute the 100 corresponding private keys by a good algorithm.
      For this version, we know that for a given public key (e, n), the prime factors of n are two primes that are very close to each other.  So we can find the integer closest to sqrt(n) and then test all pairs of nearby integers to find the prime factors of n.  We know that we don't need to check any integers further than 2 log(sqrt(n)) from sqrt(n).  Rewriting this, we see that we need to check at most log n integers below sqrt(n) and at most log n integers above sqrt(n).  If we try all pairs of such integers, we see that we need (log n)2 divisibility tests.  Thus, we have a good algorithm.
       
  6. Give a big-O estimate for each of the following functions.  Use a simple function of smallest possible order.
    1. n log(n2 + 1) + n2.
      is O( n2 )
    2. n log(n2 + 1) + n.
      is O( n log n )
    3. 22 log n + 100 n.
      is O( n2 )
    4. (n2 + n log n)(n2 + n log n).
      is O( n4 )
    5. (n log n)(n2 log n + n + log n).
      is O( n3 (log n)2 )
       
  7. Some number theory problems:
    1. (from CS280, Problem Set 3, Fall 2000) A triple prime sequence is a sequence of three natural numbers (a, b, c)  such that b=a+2, c=b+2, and each of a, b, and c is a prime number.  For example, (3, 5, 7) is a triple prime sequence, but (1, 3, 5) is not since 1 is not prime.  Consider the following claim: (3, 5, 7) is the only triple prime sequence.
      Decide whether the claim is true or false and justify your answer with a proof.
      Consider a triple prime sequence (a, b, c).  This can be rewritten as (a, a+2, a+4).  Taking this (mod 3), we get (a, a+2, a+1) mod 3.  Note that one of these three numbers must be divisible by 3.  The only prime divisible by 3 is 3; thus (3, 5, 7) is the only triple prime sequence.
    2. (from CS280, Problem Set 3, Fall 2000) An infinite arithmetic progression is a set of natural numbers of the form a, a+b, a+2b, a+3b, a+4b,...  Consider the following claim: There is an infinite arithmetic progression, all of whose elements are prime numbers.
      Decide whether the claim is true or false and justify your answer with a proof.
      Consider the term a + a*b.  This term appears in any such sequence, but it cannot be prime because it's divisible by a.  Thus, no such sequence can consist entirely of prime numbers.
    3. (from CS280, Problem Set  4, Fall 2000)  We use fn to represent the nth Fibonacci number where f1=f2=1.  Consider the following claim: For every n > 2, the greatest common divisor of fn and fn-1 is equal to one.
      Decide whether the claim is true or false and justify your answer with a proof.
      Suppose the claim is false.  Let fk-1 and fk be the first pair that have a divisor d > 1.  By definition, fk-2 = fk - fk-1.  Note that the right side of this equation is divisible by d, so the left side must also be divisible by d.  This contradicts our assumption that  fk-1 and fk are the first pair that are divisible by d.  Thus there can be no such pair fk-1 and fk that have a common divisor.  In other words, adjacent pairs of Fibonacci numbers have a gcd of 1.
    4. Can the perfect square of a natural number end with 2?  Is it possible to write the square of a natural number using only the digits 2, 3, 7, and 8 (repetitions are allowed)?
      We can check all 10 possible digits that might appear in the units position and square them to see what happens.  The only possible units digits for a square are 0, 1, 4, 5, 6, and 9.  Thus, a perfect square cannot end with 2, 3, 7, or 8.
    5. Find a number (not depending on n) such that when it's added to (n2-1)1001(n2+1)1000 the result is divisible by n.
      Working modulo n: (n2-1)1001(n2+1)1000 = (-1)1001(+1)1000 = -1 (mod n).  So to make the original term divisible by n, we just add one.
       
  8. We use the phrase 6 ones to represent the number that is written as a string of six ones (i.e., 111111).  Reduce the following fractions to lowest terms:
    To reduce a fraction to lowest terms, we divide numerator and denominator by the gcd.
    1. 6 ones / 10 ones
      gcd(6 ones, 10 ones) = gcd(6 ones, 4 ones) = gcd(2 ones, 4 ones) = 2 ones = 11.  Dividing by 11, we get 10101 / 101010101.
    2. 57 nines / 102 nines
      gcd(57 nines, 102 nines) = gcd(57 nines, 45 nines) = gcd(12 nines, 45 nines)
      = gcd(12 nines, 9 nines) = gcd(3 nines, 9 nines) = 3 nines = 999.  Dividing by 999, we get
      19 '001's / 34 '001's.
    3. 10 twos / 27 twos
      This time the gcd is 1 two = 2.  Thus, the reduce fraction is 10 ones / 27 ones.
       
  9. Some problems on Induction:
    1. You are to tear paper into pieces, but only two kinds of tearing are allowed.  Given a piece of paper, you can tear it into either 4 or 6 new pieces.  Show that, following these rules and starting with a single piece of paper, it's possible to create any number of pieces greater than 8.
      Basis: We can create 9, 10, or 11 pieces.  To create 9, we first create 6 then divide one of the 6 pieces into 4.  To create 10, we first make 4 pieces then choose two of those pieces and divide them each into 4.  To create 11, we first make 6 pieces then we divide one of those pieces into 6.
      Induction Hypothesis: It's possible to make any number of pieces p for 8 < p < n.
      We need to show how to make n pieces.  If n is 9, 10, or 11 then we can proceed as described in the Basis Case.  Otherwise, consider n-3.  By the Induction Hypothesis, there is a way to make n-3 pieces.  We tear paper to make n-3 pieces then we choose one of those pieces and tear it into 4, producing three more pieces, making n pieces all together.
      Note that the Basis had to include 3 subcases for the induction work.
    2. Prove that every integer greater than 8 can be written as 3m+5n for some nonnegative integers m and n.
      This is really just a restatement of the previous problem.
    3. Find all integers n such that 2n > n!.  Use induction to prove that you've found all such integers.
      We can try numbers until we find that 2n < n!.  Then we use Induction to show that 2n < n! for all larger n.  Trying numbers, we get: 0, 1, 2, 3, with failure at 4.  Claim 2n < n! for all n > 4.
      Basis: 16 < 24, so it holds for n = 4.
      Induction Hypothesis: 2k < k! for some k > 4.
      Consider k+1.  2k+1 = 2* 2k < 2*k! by the Induction Hypothesis.
      Further, 2*k! < (k+1)*k! = (k+1)!.  Thus, 2k+1 < (k+1)! and the claim is proved.
    4. Use induction to show 2n > n2 for n > 4.
      Basis:  For n=5, we have  25 = 32 > 25 = 52.
      Induction Hypothesis: 2k > k2 for some k > 5.
      Consider 2k+1.  2k+1 = 2*2k > 2k2 by the Induction Hypothesis.  Assume, for the moment, that we know k2 > 2k +1; using this fact, we have:
      2*2k > 2k2 > k2 + 2k +1 = (k+1)2.  At this point, we're done, all except for showing that k2 > 2k +1.  This can be done by using a separate induction proof.