CSE 5311 Section 501 Spring 1998
Homework 2
Due: February 16, 1998, in class

1. Recall that a sorting algorithm is stable if the original ordering for duplicate keys is preserved. Which of the following sorting algorithms are stable, and which are not? Describe a method for making any sorting algorithm stable.
   • Insertion Sort
   • Merge Sort
   • Heapsort
   • Quicksort
   • Counting Sort
2. The Quicksearch Center is hired to design a data structure for storing 20,000 names. The client informs the Center that one-fifth of the names will account for four-fifths of the successful searches, and the remaining four-fifths of the names will account for only one-fifth of the successful searches. (There will also be searches for names not in the data structure at all.) The Center first decides to store all 20,000 names in an open-addressed hash table of size 24,000 using double hashing. Then one of its employees, C. Wizard, suggests splitting the 24,000 locations into two tables, a small table of size 6000 to hold the high-frequency fifth of the names (and to be searched first) and a larger table of size 18,000 to hold the low-frequency four-fifths.
   1. Is Wizard's suggestion a good one? Analyze both proposals with respect to their performance in the case of both successful and unsuccessful searches.
   2. Suppose that the proportions in the statement of the problem are not 1/5 and 4/5 but p and , where . For what values of p, if any, would it make sense to isolate the fraction p of the most frequently occurring keys in a subtable consisting of the fraction p of the available memory?
3. Show the red-black trees that result after successively inserting the keys 1, 2, 3, 5, 7, 6, 4, 8, 10, 9 into an initially empty red-black tree. Show each insert case as it is applied.
4. This programming problem consists of two parts.

   1. Implement the HeapSort and QuickSort algorithms from the textbook in the language of your choice (preferably C or Pascal).

   2. Implement the Test algorithm. Test(n) creates an array of size n containing random numbers in the range , runs HeapSort and QuickSort on this array, and records the running times. This is repeated, and the results are averaged over three trials. The results are output along with the value of (the average case running time of both sorts). You are to run Test for n = 10, 20, 30, 100, 200, 300, 1000, 2000, 3000, and 10000. Plot the running-time results for HeapSort, QuickSort, and , and estimate the value of the constants in the expression for HeapSort and QuickSort. Be sure to label the axes of your plot and show the proper units.

Once you have successfully compiled and executed your program on a UTA machine, send the code to cs5311-turnin@cse. The source code must be submitted by 5:30 p.m. on the due date. In addition to identifying yourself and the homework number in a comment at the top of your code, also include a ``Compile Using'' comment line so we know how to compile your program. Two examples are

/* Compile Using:  gcc file.c -lm */

		and

(* Compile Using:  pc file.p *)

Note on class programs: there will be four programs assigned throughout the semester on the topics of sorting, B trees, minimum spanning trees, and string matching. If you know Java or are interested in learning Java, you may choose to design an interactive animation of one of these algorithms other than the HeapSort/QuickSort program. If you provide a clear and creative Java graphical version of one of the other algorithms, you can submit the code instead of one (and only one) of the assigned programs or to improve your grade for one (and only one) of the assigned programs.

• About this document ...