CPSCI 330: Algorithms

Homework 6

due: April 17, 2007

Do the following problems from your textbook. This assignment may be hand written on lined paper (but please be neat). You may use pen or pencil as long as the markings you make are legible.

For each solution, clearly indicate both (a) the Exercise set it's from, and (b) the number of the problem it's a solution to. It will improve my quality of life if your answers appear in the order in which the problems are assigned.

The Exercises

1. Exercise 7.2: 1.
       Show your work: construct a shift table, and apply the algorithm as in Figure 7.3 in your text (i.e., text on top, pattern beneath, move the pattern down a line every time you increment the text index, i). Compare the efficiency of Horspool's algorithm to the Boyer-Moore algorithm on the same text (i.e., compare your work to Figure 7.3 on p. 263).
2. Exercise 7.2: 2.
       Do this exercise twice: once for Horspool's algorithm and once for the Boyer-Moore algorithm. Show your work, including the Horspool shift table and the good-suffix table, and conclude with a sentence comparing how each algorithm fared on the sample text.
3. This question concerns the Distribution Counting Sort. Suppose we want to sort n items by part number, where a part number is any of 111, 365, 698, or 912.
   1. Why shouldn't we use the DCS algorithm as written to do this sort?
   2. Explain how to modify the DCS algorithm so that we can use a small number of keys of arbitrary data type (e.g., the part numbers listed above) and still sort the data in linear time.
   3. Can the modification you suggested be extended to arbitrary lists? In other words, can we use the DCS to sort any data set in linear time? Justify your answer.
4. Suppose that you want to sort an array of records of Hamilton College students by state of origin. Assume that there's at least one student from each of the 50 U.S. states, every student record has a non-empty U.S. state field, and that there are 2048 records. Would DCS or Quicksort be a better choice? Justify your answer.
5. Same as the previous, but this time you're going to sort by zip code.

[ Return to the CPSCI 330 homepage ]