CS14 SPRING 2001

WRITTEN ASSIGNMENT 4

Assigned: May 25, 2001

Due: June 3, 2001

 

  1. Heaps
    1. Show the result of inserting 6, 4, 15, 2, 10, 11, 8, 1, 13, 7, 9, 12, 5, 3 and 14 one at a time, into an initially empty heap.
    2. Show the result of building a heap with the same input, using the following algorithm;
      3.

      // read all the data into an array H

      for (int i = n/2; i > 0; i--)

      heapify (H, i); // heapify the subheap rooted at i.
    3. Show the result of performing 3 extract-max operations on the heap.

     

  2. Trees revisited.

    3. A level-order traversal of a tree prints out the nodes of the tree by row, and within each row from left to right. In a heap, which is a complete binary tree stored in an array, this is easily accomplished by printing out the contents of cells 1…2 of the array.

    Describe a scheme for performing a level-order traversal of a general binary tree (not necessarily complete, stored as treenodes with left & right pointers).

     

  3. Sorting
    1. Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using InsertionSort.
    2. Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6 using MergeSort.
    3. A good selection of the pivot for quicksort is the median of the first, last and middle elements. Sort 3, 1, 4, 1, 5, 9, 2,6, 5, 3, 5 using quicksort with median-of-three partitioning. Cut off the recursion when a sub-array has three or fewer elements.

     

  4. Miscellaneous
    1. Given an array of n elements containing only 0s and 1s, give a linear algorithm to sort the array (rearrange the array so that all the 0 elements appear first, followed by all the 1 elements). You may only use a constant amount of additional storage (no copying into another array of size n).
      2.
    2. (Bonus) Repeat part (a) for an array where each element is either 0, 1, or 2.