CSC 477/677 Assignment 3

Due date, October 18, 2005, 11:00 AM.

1. Apply quicksort to sort the list D,I,V,I,D,E,A,N,D,C,O,N,Q,U,E,R. Show the array at each step. An example. However, you do not have to use colors. In fact, you do not have to show each step; only steps where items are actually moved within the array. For the example, this would be your answer.
   To make it easier to grade, always pick the first item in the array to be the pivot item. (This is normally not a good choice.)
2. What sorting algorithm do you think would be best in each of the following situations? Explain.
   1. You are given many thousands of lists, each of which is very small. In fact, their average size is 1. (You need to sort each list separately.)
   2. You have a list of donors that you want to alphabetize. This list was formed by concatenating lists of donors from each of the 50 states. Each state list was sorted. The total number of names is approximately 100,000.
3. We will implement a min-heap of letters as an array, as shown in class. Start with an empty heap, and perform the following operations:
   Insert(G);
   Insert(N);
   Insert(B);
   Insert(H);
   Insert(M);
   Insert(R);
   Insert(V);
   Insert(C);
   DeleteMin;
   DeleteMin;
   DeleteMin;
   What will the array be after those operations? Show the array at each step.
4. A binary search tree is set to empty, and then the following letters are added in this order: A,L,G,O,R,I,T,H,M,S. Draw a picture of the resulting binary search tree.
5. Prove that there is no algorithm for solving the following problem:
   "Given 13 coins, all but one of which are the same weight, find which coin is not of that same weight, and whether it is heavier or lighter than the others, in only three weighings with a balance scale." The problem is described in detail here. Don't look at this hint until you've at least tried to work it yourself.