CS3343, Spring 2012, Quiz 1                    Your Name:                                                       

  1. (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:

    2. Second burn:

  2. (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    
    End 1st   
    End 2nd    
    End 3rd    
    End 4th    
    End 5th    
    End 6th    

  3. (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?