Introduction to the Design and Analysis of Algorithms
(Textbook. Click for information.)
 CS 3343/3341
 Analysis of Algorithms
 Spring 2012
 Recitation 1
 Circular Queues, Etc.
    Week 1: Jan 17-19
 Due (on time): 2012-01-23  23:59:59
 Due (late):        2012-01-27  23:59:59

Recitation 1 should be submitted following directions at: submissions with deadlines
  • 2012-01-23  23:59:59 (that's Monday, 23 January 2012, 11:59:59 pm) for full credit.
  • 2012-01-27  23:59:59 (that's Friday, 27 January 2012, 11:59:59 pm) for 75% credit.

Questions about Exponentiation. (See the exponentiation page.)

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

  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?

  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.)

  4. Consider the following Θ(n) algorithm to calculate AB 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. [It is trivially true.]

    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') = AB is true, that is, the loop invariant is still true after new values have been calculated for d, a, and b.]

    3. Argue that if the loop invariant it true and if the loop has terminated, then d = AB, so the function returns what it is supposed to.

Questions about Weird Topic 1: WOM Storage.

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

  2. 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.)

Program related to circular queues:

    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.

  1. 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?

  2. In the 3rd edition, your book says to use the following to check for an empty queue:

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

    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.

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

  4. 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.

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate item numbers: 1, 2, 3, etc.

 Contents of email submission for Recitation 1:

Your last name, Your first name; CS 3343; Recitation 1.

1. through 10.: answers to the questions.

For question 9. only, include the entire source code (all source code files) for a queue that uses a size variable. At the end append the results of a run. Finally answer the two questions at the end of 9. (Remember, just a single .txt file, with the parts concatenated together.)

Key goals:

Revision date: 2012-01-02. (Please use ISO 8601, the International Standard.)