Textbook.

CS 3343/3341  Analysis of Algorithms  Fall 2012  Recitation 8  Exam Review      Partial Answers

1. Suppose you have the following information as bits: 01 10 01 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 (on top of the previous information) and show the result: 10 11 01 01 10 10. [ See WOM Storage.]

2. Use the XOR formula to recover the original first two information bits correctly, both first and second generations (01 and 10).

3. Write log_3/2(x) in terms of logs base e (natural logs). [log_3/2(x) = log_e(x)/log_e(3/2).]

4. Let n be an integer (picture a large one). Let dd(n) stand for the number of decimal digits in n, and let bd(n) stand for the number of binary digits in n. We stated in class that:

          dd(n) = log₁₀(n), and
          bd(n) = log₂(n).

   Using the above formulas, derive a formula that has the form:

         dd(n) = c * bd(n), where
         c = log_x(y).

   Here x and y are constants that you must determine. (Not just the answer, but say where the answer comes from.) [The constant c is the conversion factor from the number of binary digits to the number of decimal digits. Of course, 1/c converts the other way.] [The ratio:

    dd(n)     log10(n)          log10(n)
   ------- = ---------- = ------------------  =  log10(2)
    bd(n)     log2(n)      log10(n) / log10(2)
   
   
    dd(n)  =  bd(n) * log10(2)
   

5. For your text's basic Quicksort algorithm, give the worst case performance, in terms of Θ. Give a specific example of an array for which the worst case is realized. Explain the simple alteration to the basic quicksort algorithm that guarantees an expected better performance. Give this expected better performance in terms of Θ.

6. Here is pseudocode for the partition function of quicksort from your text:

   partition(A, p, r) x = A[r] // pivot i = p - 1 // nothing small so far for j = p to r - 1 // handle each elt in turn if A[j] <= x // found one for small side i = i + 1 // find a place for it exchange(A[i], A[j]) // put small one in exchange(A[i+1], A[r]) // move pivot to middle return i + 1 // return pivot location

   Carry out by hand one call of the above partition function on the array. (This is not the full quicksort, but just the first call to partition.) You must trace the actions of partition on this array carefully (or run a program to do it -- you won't be able to run a program for this kind of question on the test). (Here we assume that the array locations are A[0], ..., A[7], and that this first call to partition is q = Partition(A, 0, 7);)

         A = {1,2,3,4,5,6,7,8}.

   After this single call to partition, answer the questions:

   1. What is the initial index of the pivot element? What is its value?
   2. Where does the pivot end up? (What is its index at the end?)
   3. How many non-trivial interchanges are there? (Interchanges of two distinct elements.)
   4. How many empty interchanges are there? (Interchanges of an element with itself.)
   5. What value is returned by this call to partition?
   6. What is the result after this single call to partition? Identify the left sub-array of the partition and the right sub-array of the partition.

   [In the function, the variable j takes values 0, 1, 2, ..., 6. Each time j increments, i is incremented also. So each of these 7 iterations results in an empty exchange. Then the final exchange is exchange(A[7], A[7]), also empty. So A[7] = 8 is the pivot. All elements stay where they were. 7 trivial (empty) exchanges, and 0 non-trivial exchanges. The index 7 is returned by this call to partition. The left sub-array goes from index 0 to index 6, and the right subarray is empty.]

7. Some median question ...

8. Suppose an array A has locations A[1], ..., A[9] equal to {5,13,2,25,7,17,20,8,4}. Show step-by-step the process of making this array into a heap.

9. Suppose an array A has locations A[1], ..., A[9] equal to {25,13,20,8,7,17,2,5,4}. This is a max-heap. Show just the first two steps of the progress of heapsort on this array, starting to sort it into increasing order. At each of the two steps indicate also the value of heapsize. [Here are diagrams showing the course of heapsort acting on this array: heapsort.]

10. Suppose an array A has locations A[1], ..., A[11] equal to {20,16,8,14,11,7,4,10,12,6,3}. This is a max-heap. As one of the 2 steps of a priority queue, show step-by-step the process of removing the maximum element and restoring the heap property.[Here are steps done by hand (trying not to make mistakes):

    Initial:  {20,16,8,14,11,7,4,10,12,6,3}
    Save max: max = 20
    Exchange: {3,16,8,14,11,7,4,10,12,6,20}
    Decrement heapsize:   { 3,16,8,14,11,7,4,10,12,6 | 20}
    Result of maxheapify: {16,14,8,12,11,7,4,10, 3,6 | 20}
    

11. Suppose an array A has locations A[1], ..., A[10] equal to {18,15,9,11,10,6,2,8,1,7}. This is a max-heap. As one of the 2 steps of a priority queue, show step-by-step the process of inserting the element 16 into this heap and restoring the heap property. (This uses the Heap-Increase-Key function.)

12. Mimic what we did for square root to find the cube root. We start with r > 0. We want r^1/3. We will normalize into the interval [1/8,1] by dividing by 8ⁿ for suitable n. Do up the square diagram, with r, r0=r/8ⁿ, r0^1/3, and r^1/3 in the four corners (clockwise). Finish up all the other details about the diagram, following the pattern for square root.
    
    Click box or here for full size image.

    [Some of you wrote 8^n/3 for the denormalizing factor, without simplifying it to 2ⁿ. But this misses a big reason for the whole approach: that it's efficient to multiply or divide by a power of 2 on our hardware. The reason for choosing 8ⁿ for normalizing was to achieve this simple denormalizing factor.]

13. Continuing the problem above, show how to use Newton's Method to find r^1/3. Use the function f(x) = r - x³. You need to know that f ' (x) = - 3 * x². Don't write any code, but just produce the Newton's iteration formula. If r=27 and x0=2.9, calculate by hand the next approximation x1.

The above calculation shows that if we start with x0 = 2.9, within 0.1 of the cube root of 27 which is 3, then the next approximation x1 = 3.0034879, within about 0.0035 of the cube root.

Just ran a quick program:

#include <stdio.h>
int main() {
   double x0=2.9, x1, r=27;
   int i;
   for (i = 0; i < 10; i++) {
     x1 = (2./3.)*x0 + r / (3.*x0*x0);
     printf("i:%2i, r: %.4f, x1: %.16f\n", i, r, x1);
     x0 = x1;
   }
}
i: 0, r: 27.0000, x1: 3.0034879112168054
i: 1, r: 27.0000, x1: 3.0000040488977464
i: 2, r: 27.0000, x1: 3.0000000000054645
i: 3, r: 27.0000, x1: 3.0000000000000000