Test #3, CS 255, May 3, 2006

There are 150 points on the test.

 

  1. (30 points) Express your answer to each of the following using O-notation (Θ-notation where appropriate)
    1. What is the expected number of rounds of the SYNCH-CCP algorithm?
    2. What is the expected number of rounds of the ASYNCHRONOUS-CCP algorithm?
    3. What is the expected number of rounds of the BYZANTINE AGREEMENT protocol discussed in class?
    4. What is the worst-case number of recursive calls, as a function of the length of n, in the Extended Euclidean algorithm for finding reciprocals mod n?
    5. What is the worst-case number of recursive calls as a function of the length of the exponent in the exponentiation algorithm that works by repeated squaring?
    6. What is the depth of a bitonic sorter that sorts n elements?

  2. (20 points) Trace how the algorithm of Problem 1.5 finds 1011 mod 998.

  3. (20 points) Trace how the Extended Euclidean algorithm finds the reciprocal of 30 mod 107.

  4. (20 points) Suppose that in the ASYNCHRONOUS-CCP algorithm, processor 0's initial choice of a random bit is 0 and processor 1's choice is 1.
    1. (15 points) How does the algorithm proceed from then on? If there are any further cases where a processor chooses a random bit, you may decide for yourself what that bit is, as long as you indicate that a random choice has been simulated.
    2. (5 points) Recall that in the ASYNCHRONOUS-CCP algorithm, the two processors are supposed to agree upon a single bit. How do the processors determine which bit has been agreed upon?

  5. (15 points) Trace the behavior of the Byzantine Agreement protocol if 80% of the processors are good and have an initial b value of 1, and the other good processors have a bit value of 0.

  6. (15 points) Why would it be a bad idea, in the ASYNCHRONOUS-CCP algorithm, to assume that the two processors are initially inspecting different registers?

  7. (15 points) Show how a sorting network for n=8 would sort the sequence (8,5,4,7,6,9,2,3). Make sure to show both outputs of every comparator.

  8. (15 points) One possibile function for public key encyption is the function that takes a key k and a message M and encrypts the message as fk(M) = k+M. Why would it be a bad idea to use this function in a public key encryption scheme?