Directions: Do not spend too much time on any one problem. Try to give as short an answer as you can that still fully answers the question.

---

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

   2. Derive the formula in part a (or get it from scratch), by writing first y = log_3/2(x). Use the definition of logarithm to write this as a power. Finally, take the log base e of both sides to get the formula asked for in part a.
      [ (3/2)^y = x
      log_e[(3/2)^y] = log_e(x)
      y * log_e(3/2) = log_e(x)
      y = log_e(x) / log_e(3/2) ]

   ---

2. (20) This problem is concerned with WOM storage. Here is the basic encoding table for this storage.

   Information	First Generation Burn	Second Generation Burn
   00	000	111
   01	001	110
   10	010	101
   11	100	011

   Here is the XOR formula for recovering 2-bit information from 3-bit encoded data:

   The 3-bit stored value   < a , b , c >  represents the 2-bit value     < a ⊕ b , a ⊕ c >,  where ⊕ is exclusive-or.

   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: 11 01 01 01 10 10.
      [ 1st gen. burn: {001,010,001,100,000,010}
       2nd gen. burn: {011,110,001,110,010 or 101,010}]

   2. Use the XOR formula to recover the 2-bit information values from the following 3-bit coded values:

            <1,1,0> and <0,1,0>).
      [<1,1,0>is an encoding for: < 1⊕1, 1⊕0 > = < 0, 1 >
       <0,1,0>is an encoding for: < 0⊕1, 0⊕0 > = < 1, 0 > ]

   ---

3. (20) 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 Θ. [Worst-case performance is Θ(n²). This performance occurs with a sorted or reverse sorted array, but with many other orders as well, although a vanishingly small percentage of all possible orders. Your text suggests picking the pivot element at random, interchanging it with the rightmost element, and proceeding as with their partition. Alternatively, we mentioned in class that one could randomize the entire array, although this would be more time-intensive. The expected time of these "randomized" quicksorts is Θ(n * log(n)).]

   ---

4. (25) Let array locations A[0], ..., A[7] hold numbers A = {9,8,7,6,5,4,3,2}. 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 A above. (This is not the full quicksort, but just the first call to partition.) You must trace the actions of partition on this array carefully. After this single call to partition, answer the questions:

   1. What is the initial index of the pivot element? What is its value?
      [Init pivot index: 7, Init pivot value: 2 ]
   2. Where does the pivot end up? (What is its index at the end?)
      [Pivot ends up in index 0, at the far left; there's nowhere else it could be. ]
   3. How many non-trivial interchanges are there? (Interchanges of two distinct elements.)
      [During execution, i is never incremented inside the loop, so there are no interchanges inside the loop. At the end there is a single non-trivial interchange of A[0] with A[7], putting 2 at the beginning and 9 at the end. ]
   4. How many empty interchanges are there? (Interchanges of an element with itself.)
      [ 0, see above ]
   5. What value is returned by this call to partition?
      [ returns the index of the final location of the pivot, namely 0 ]
   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.
      [ left sub-array empty, pivot is in location A[0], and right sub-array is A[1] to A[7]: {8,7,6,5,4,3,9} ]
   7. Suppose we continue with the quicksort algorithm beyond this initial call to partition. Briefly describe with this specific example how the rest of the sorting goes, until the array is sorted.
      [ Below, the underlined numbers are input to the next call to partition
      {9,8,7,6,5,4,3,2} (1st call, moves 2 to beginning, 1 non-empty interchange)
      {2,8,7,6,5,4,3,9} (2nd call, drops 9 from consideration, empty interchanges)
      {2,8,7,6,5,4,3,9} (3rd call, moves 3 to left, 1 non-empty interchange)
      {2,3,7,6,5,4,8,9} (4th call, drops 8 from consideration, empty interchanges)
      {2,3,7,6,5,4,8,9} (5th call, moves 4 to left, 1 non-empty interchange)
      {2,3,4,6,5,7,8,9} (6th call, drops 7 from consideration, empty interchanges)
      {2,3,4,5,6,7,8,9} (7th call, moves 5 to left, 1 non-empty interchange) ]

   ---

5. (15) Is an array in reverse sorted order (all values strictly decreasing) always a max-heap? Explain very carefully. (No credit for just "Yes" or "No".) [For full credit, you needed something besides "yes, because it satisfies the heap property". You could say that because the parent of i has index floor(i/2), the index of a parent comes before that of its children and is therefore bigger. Similarly, the children of node i are at 2*i and 2*i+1, so they come after i in the array and are therefore smaller in value. Thus the heap property is satisfied.]

   ---

6. (20) Suppose an array A has locations A[1], ..., A[6] equal to {12,5,8,2,10,14}. Show step-by-step the process of making this array into a max-heap. [Starting with A[3]=8 and moving on to A[2] and A[1], we need to Max-Heapify.
   Original: {12,5,8,2,10,14}
   After Max-Heapify(A,3): {12,5,14,2,10,8}
   After Max-Heapify(A,2): {12,10,14,2,5,8}
   After Max-Heapify(A,1): {14,10,12,2,5,8}, and done.]

   ---

7. (25) 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. 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. (Just remove one element, and stop.) [A[1], ..., A[9] = {25,13,20,8,7,17,2,5,4}
   Set max=A[1]=25.
   Interchange A[1] and A[9].
   Set heapsize--, so that effectively A[9] is not part of the heap.
   Now have: {4,13,20,8,7,17,2,5}
   Do Max-Heapify(A,1):
   First interchange A[1] and A[3] to get: {20,13,4,8,7,17,2,5}
   Then interchange A[3] and A[6] to get: {20,13,17,8,7,4,2,5}
   A[6] is a leaf, so return max and done.]

   ---

8. (25) Suppose we have an array A holding 100 distinct integers, in locations A[0], ..., A[99]. We wish to pick 75 of these elements at random, with no repetitions, and place them in an array B, in locations B[0], ..., B[74]. At the end we should have 75 distinct elements in B, chosen at random from A.
   1. What is wrong with the following algorithm to do this (a basic problem with the algorithm, not some perceived syntax error or the like)?

      int[] A = new int[100]; // 100 distinct ints are already // inserted into A int[] B = new int[75]; insert(A, B); void insert(int[] A, int[] B) { for (int i = 0; i < 75; i++) { // Random(a,b) returns // random int r, a<=r<=b B[i] = A[Random(0,99)]; } }

      int A[100]; // 100 distinct ints are already // inserted into A int B[75]; insert(A, B); void insert(int A[], int B[]) { int i; for (i = 0; i < 75; i++) { // Random(a,b) returns // random int r, a<=r<=b B[i] = A[Random(0,99)]; } }

      
      

   2. Give a method to correct the problem in (a) above efficiently. [There are several different methods. You should make clear exactly what you intend to do. One way uses a function void randomize(int[] A) { ... } which will rearrange the elements of A into random order. You should not give the code for randomize, but you can assume that it is available. ] [ Inside insert and before the for loop, or before calling insert, you can add a call randomize(A); to randomize the contents of A. That's all that is needed. Putting the call randomize(A); inside the for loop, say at the end, doesn't work, because each randomize could produce anything, and duplicates would still be possible.

      There are a large number of other ways to do this.]

   ---

9. (30) For this question we want to calculate a function as we did with square root, reciprocal, and log base 2. This time the function is f(x) = 2^x, that is, 2 to the power x. This problem is only concerned with the normalization and denormalization. Separately, we would use a series to calculate 2^x for 0 <= x <= 1, but that isn't part of this problem.

   You are to draw the square diagram similar to the ones we had in the other 3 examples. Remember that we are implementing the function 2^x. Start with x in the upper left corner. Then the "normalized" value x0 is found by taking floor(x) and subtracting it from x. (Here floor(x) is the largest integer value less than or equal to x.) For example, if x = 7.3, then x0 = 0.3, and if x = -5.6, then x0 = 0.4.

   1. Explain the the second example above: if x = -5.6, why is x0 = 0.4?
      [ floor(-5.6) = -6, so x - floor(x) = -5.6 - (-6) = -5.6 + 6 = 0.4 ]

   2. Carefully fill in the rest of the diagram, using variables, rather than specific numbers. (One key step is determining the denormalization formula.)

      x = input double, m = floor(x) * = node value * - m x --------------------> x0 = x - m | | | | | | | | * | | * 2 | | 2 | | | | | | V V x x0 (x - m) x / m 2 <--------------------- 2 = 2 = 2 / 2 m * (times) 2

   3. Trace through the diagram using the initial value x=6.5, and carrying specific numbers all the way through the diagram. (Remember that a positive number to the 0.5 power is just the square root of the number.)

      6.5 = input double, 6 = floor(6.5) * = node value * - 6 6.5 --------------------> 0.5 = 6.5 - 6 | | | | | | | | * | | * 2 | | 2 | | | | | | V V 6.5 0.5 (6.5 - 6) 6.5 / 6 2 <---------------------- 2 = 2 = 2 / 2 6 * (times) 2 Here 26.5 is computed by normalizing 6.5 to 0.5, calculating 20.5, and denormalizing by multiplying by 26 = 64. Thus 26.5 = 20.5 (times) 26. We would use a series to calculate 20.5, and just as before, we only need to calculate 2x for 0 <= x <= 1. For very large x or for negative x with large absolute value, the series wouldn't work, so this normalization is necessary. Finally, we would get 20.5 = 1.41421356 (using the series), and 26.5 = 1.41421356 * 64 = 90.50966799 (using the normalization/denormalization). (In at least some places, this is the way 2x is actually calculated.)