Textbook.

CS 3343/3341  Analysis of Algorithms  Fall 2012  Recitation 8  Exam Review      Week 7: Oct 16-18  Due (on time): 2012-10-16  23:59:59  Due (late):        2012-10-17  23:59:59

Notice: You are allowed to bring ONE SHEET of paper to the exam with whatever you like printed or written on it (both sides).

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(10) in terms of logs base e (natural logs).

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

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.

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.

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.

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.

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.