EXAM 3 SAMPLE ANSWERS - SPRING 2012
VERSION A

1. (a) C, B, D, A
   (b) link
   (c) B
   (d) A
   (e) packet number, destination address
   (f) TCP
   (g) 2**16
   (h) 2**128 = 16**32

2. (a) 24t
   (b) 3t
   (c) 3t for first set + 9t for additional 9 sets = 12t
   (d)                  -------------
       -----------[ ]--|             |--
       \      /        |             |
       -----------[ ]--|  4-input    |--
       \ \  / /        |  Butterfly  |
       -----------[ ]--|  Network    |--
       \ \/\/ /        |             |
       -----------[ ]--|             |--
       \/\/\/\/         -------------
       /\/\/\/\         -------------
       -----------[ ]--|             |--
       / /\/\ \        |             |
       -----------[ ]--|  4-input    |--
       / /  \ \        |  Butterfly  |
       -----------[ ]--|  Network    |--
       /      \        |             |
       -----------[ ]--|             |--
                        -------------
   (e) A connects to Y while B connect to X. A tries to connect to
       X to complete a circuit but gets blocked forever, and B tries to
       connect to Y to complete a circuit and gets blocked forever.

3. (a) rand(8)
       rand(5) + 7
       rand(8)*2 - 2
       3**rand(6)
       primes[rand(11)]
   (b) 1 = black, 0 = white:
       111 110 101 100 011 010 001 000
        1   0   0   0   0   1   1   1
   (c) 1
       number != 10
       number > maximum
       spin()

4. (a) ELECTIVE
   (b) RUBY
   (c) 
       (Note: o is a one-way function that is commutative and associative)
       B o a = A o b
       (g o b) o a = (g o a) o b
       g o (b o a) = g o (a o b)   (associative property)
       g o (a o b) = g o (a o b)   (commutative property)
       
       Since o is a one-way function, it is very hard to compute
       a from K = a o B, or to compute b from K = b o A.

   (d) C = (M**e ) % n
                A     A
       M = (C**e ) % n
                A     A

5. (a) A
   (b) no (if he is healthy, the contagious? function must return false)
   (c) def healthy?(matrix, i, j)
           if matrix[i][j] == 4 then
               return true
           else
               return false
           end
       end
   (d) def contagious?(matrix, i, j)
           if matrix[i][j] == 1 or matrix[i][j] == 2 then
               return true
           else
               return false
           end
       end
   (e) 100, 35
   (f) i = 0, i = 24, j = 0, j = 19