Directions: submit hardcopies of your solution to the written questions (W). Each question is worth 10 points.

1. (W) A file contains only colons, spaces, newlines, commas, and digits in the following frequency: colon (100), space (605), newline (100), comma (705), 0 (431), 1 (242), 2 (176), 3 (59), 4 (185), 5 (250), 6 (174), 7 (199), 8 (205), 9 (217). Construct the Huffman code.

2. (W) Draw the binary heap that results from this series of inserts into an initially empty heap: Insert 10 12 1 14 6 5 8 15. Show the result of performing two DeleteMin operations on the resulting heap. Show, separately, the result of each individual insert/delete.

3. (W) Draw the binomial heap that results from this series of inserts into an initially empty heap: Insert 10 12 1 14 6 5 8 15. Show the result of performing two DeleteMin operations on the resulting heap. Show, separately, the result of each individual insert/delete.

4. (W) Sort the sequence 3,1,4,1,5,9,2,6,5 using insertion sort. Show the intermediate results for each step of the algorithm.

5. (W) Sort the sequence 3,1,4,1,5,9,2,6 using mergesort. Show the intermediate results for each step of the algorithm.

6. (W) What is the running time (big O) for mergesort when the input is in sorted order? When the input is in reverse order? Briefly explain.

7. (W) A sorting algorithm is stable if elements with equal keys are left in the same order as they occur in the input. Which of the following are stable: insertion sort, mergesort, quicksort. Briefly explain.

8. (W) Below is pseudocode for BubbleSort.

   for i = 0 : n-2
        for j = n-1 downto i+1
             if( A[j] < A[j-1] ) then
                  swap( A[j], A[j-1] );
        end
   end
   

   where A is an array of n elements. What is the run-time complexity of BubbleSort? Briefly justify your answer.

9. (W) Below is pseudocode for SelectionSort.

   for i = 0 : n-2
        select the smallest element among A[i], ..., A[n-1]
        replace this element with A[i]
   end
   

   where A is an array of n elements. What is the run-time complexity of SelectionSort? Briefly justify your answer.

10. (W) Give the recurrence relation for the following code fragment that describes its run-time complexity. Solve this recurrence relation.

         int test( int n ) {
              int i;
              if( n == 1 )
                   return(n);
              else {
                   i = i + 1;
                   return( test(n-1) + n );
              }     
         }