(Textbook. Click for information.)

CS 3343/3341  Analysis of Algorithms  Spring 2012  Recitation 1  Circular Queues, Etc.     Partial Answers

Questions about Exponentiation. (See the exponentiation page.)

1. As we did in class, work through the example of 2²⁷ = 1342 17728 by hand.

   
   2^27:
   First build the table:
            2^0 = 1
            2^1 = 2<-- use
           (2^1)^2 = 2^2 = 4<-- use
           (2^2)^2 = 2^4 = 16
           (2^4)^2 = 2^8 = 256<-- use
           (2^8)^2 = 2^16 = 65536 <-- use
           (2^16)^2 = 2^32 = 8 589 934 592 (not needed or wanted here)
   
   27 = 2^4 + 2^3 + 2^1 + 2^0 = 16 + 8 + 2 + 1 = 1 1 0 1 1 (base 2)
   (This shows which table entries to use above, marked "<-- use".)
   
   2^27 = 2^16 * 2^8 * 2^2 * 2^1 = 65536*256*4*2 = 134 217 728
   

2. Look at the exponentiation algorithm from class (on the page above). Suppose you wanted to print the exponent b in binary, by additions/modifications to the algorithm. Say or show how to do this. Are there any obstacles? The bits are created inside the program by "b%2", but if printed directly they come out backwards.

3. Look up the "Modular-Exponentiation" algorithm in your textbook, page 957 (3rd ed.), page 879 (2nd ed.). This is certainly similar to the algorithm from class, since it also calculates an integer to an integer power. The "Modular" in the title means that during each calculation, they divide by a number n and take the remainder. (In the algorithm they write mod n, but we must write % n in Java or C.) Just ignore this part. Aside from this, the book's algorithm differs from the one in class (at the link above) in several significant ways. Describe the differences. (Say how it works in some strikingly different way.) Aside from the fact that the book's algorithm is taking % n at each stage (which you were told to ignore), the biggest difference is that the bits of b are handled from most significant to least, the opposite of the class algorithm. Because of this the calculations have to be altered. Also the book assumes the bits are given as an input. Finally, the book includes a variable c to help with the correctness proof. [Note that the two algorithms have the same complexity and performance.]

4. Consider the following Θ(n) algorithm to calculate A^B for positive integers A and B. (This is the standard method to raise A to the power B: just multiply A by itself B times.)

   // exps: slow exponentiation int exps(int A, int B) { int a = A, b = B; int d = 1; while(b > 0) { d = d*a; b = b--; } return d; }

   One loop invariant for this function is:

   d*ab = AB

   1. Argue that this loop invariant is true at the start of the loop. Trivially true, since d = 1, a = A, and b = B.

   2. Argue that the loop invariant is true at the end of each iteration of the loop. [Use d', a', and b' for the new values of d, a, and b at the end of each iteration of the loop. Then show that (d')*(a')^(b') = A^B is true, that is, the loop invariant is still true after new values have been calculated for d, a, and b.]
      (d')*(a')^(b') = (d*a)*(a)^(b-1) = d*a^b = A^B.

   3. Argue that if the loop invariant it true and if the loop has terminated, then d = A^B, so the function returns what it is supposed to. On termination, b must be 0, so d*a^b = d*a⁰ = d, but the loop invariant says that d*a^b = A^B, so we can conclude that at termination d = A^B, and this is what is returned.

      [I left the following important fourth part off]

   4. Argue that the loop will terminate. Initially we must have b >= 0, though that isn't stated here. (Clearly, if b < 0, it will keep decreasing forever -- well, until overflow.) If b = 0, the loop doesn't execute, but the right answer is returned. If b > 0, repeated decreasing b by 1 will eventually get to 0.

Questions about Weird Topic 1: WOM Storage.

5. Suppose you have the following information as bits: 01 11 10 11 00 10. Show the result of burning this to storage in the manner of the topic. Then burn the following information as a second generation and show the result: 10 01 00 11 10 10.

6. Show that the formula involving xor lets you recover the original first two information bits correctly, both first and second generations (01 and 10). (See the xor page.)

Study the circular queue programmed following the pseudocode in your text (page 234-235, 3rd ed., or pages 201-203, 2nd ed.). This page gives the implementation in Java and in C. The two programs are very similar and they produce exactly the same output.

See pseudocode for information about your text's pseudocode.

7. Your book says that it "shows one way to implement a queue of at most n - 1 elements using an array Q[1..n]". Why can't you have n elements in this queue, since the array has room for n elements? If all n elements were used, then a full queue and an empty queue would each pass both tests for full and empty, so it wouldn't work.

8. In the 3rd edition, your book says to use the following to check for an empty queue:
   empty queue: head == tail

   It says to use the following to check for a full queue:

   full queue: head == tail + 1, or both head == 1 and tail == n

   Amazingly the 2nd edition of your text says to use just head == tail + 1 to check for a full queue. This was an error in the 2nd edition. To make matters more confusing, my isempty() function uses head == (tail + 1) % n.

   Give an example to show how the condition head == tail + 1 can fail at detecting a full queue, either in the book's algorithm or in my coded version of the algorithm. In the book's terms, if the head is at 1 and the tail is at n, this would be a full queue, but the 2nd edition didn't check this. Similarly with arrays from 0 to n-1, if the head is 0 and the tail is n-1, this is full, but we need to take (tail + 1) % n, which equals 1, to check for this.

9. Modify the Java code or the C code (or both) to add an extra variable size to the queue. Initially size is 0 and this indicates an empty queue. When you add to the queue, you should increment size and decrement size when you remove an element. For the isfull() and isempty() functions you should only use the size variable. Run the same test main program. Do you get the same output? Should you get the same output? The most important thing is to use "size == n" to check for a full queue, not "size == n -1".

10. People might (and do) argue against using this size variable, saying that it takes up one more storage cell, uses an extra variable, and makes the code more complicated. I can think of two distinct (completely separate) advantages to the use of size. If you can, say what they are. The biggest advantage is that you can use all n elements of the queue. In a real queue, the queue elements would be an arbitrary type of arbitrary size. Plus the whole idea of using only n-1 queue elements and using a ridiculous test for a full queue and even a confusing test for an empty queue is bad. It has confounded generations of CS students, all to save one variable. [Note that without the size variable, you still don't have to count the queue elements to determine the size, but you can use a formula involving head and tail (though even that is confusing).]