CS3343, Spring 2012, Quiz 1, Answers         Your Name:                                                       

  1. (5) (WOM storage) Suppose a "first generation burn" gives physical bits "001". Then suppose a "second generation burn" give physical bits of "101". The formula for recovering the information bits reads:

    The 3-bit stored value   < a , b , c >  represents the 2-bit value
        < a ⊕ b , a ⊕ c >,  where ⊕ is exclusive-or.

    In each of the two cases above, show what information bits are recovered by the formula. (Don't just give the answer, but show how the formula leads to the answer.)

    1. First burn:       < 0, 0, 1 > represents < 0 ⊕ 0, 0 ⊕ 1 > = < 0, 1 >
    2. Second burn: < 1, 0, 1 > represents < 1 ⊕ 0, 1 ⊕ 1 > = < 1, 0 >
  2. (6) (Fast exponentiation) Consider the function from class for fast exponentiation (see below). Suppose this is called with expon(3, 14). Trace through the function showing the values of the given variables at the end of each loop iteration. (If you like, you can just write 34 instead of 81, etc. Also, you may not need all 6 lines shown below.)

    // expon: fast exponentiation
int expon(int a, int b) {
   int d = 1;
   while(b > 0) {
      if (b%2 == 1) d = d*a;
      b = b/2;
      if (b > 0) a = a*a;
   }
   return d;
}
    		      
    Iteration             a                          b                          d             
    Start 3 14 1
    End 1st 32 = 9 7 1
    End 2nd (32)2 = 34 = 81 3 1 * 32 = 32 = 9
    End 3rd (34)2 = 38 = 6561 1 32 * 34 = 36 =
    9 * 81 = 729
    End 4th 38 = 6561 0 36 * 38 =
    314 = 729 * 6561
    = 4782969
    End 5th No 5th loop   
    End 6th No 6th loop   

  3. (4) (Ternary Search) Given integers x and y, with x < y, binary search uses the formula (x + y) / 2 for an integer roughly half the way from x to y. With ternary search, what formula did we need for an integer roughly one-third of the way from x to y?

    Halfway from x to y is x + (y - x) / 2 = x + y/2 - x/2 = (x + y)/2

    One-third of the way from x to y is x + (y - x) / 3 = x + y / 3 - x / 3 = (2 * x + y) / 2