Previous   Next

Notes on Exercises

Classifying exercises is an activity fraught with peril because readers of a tutorial such as this come to the material with various levels of knowledge and experience. Nonetheless, guidance is appropriate, so many of the exercises carry one of four annotations to help you decide how to approach them. Exercises that test your understanding of the material are marked with an open triangle, as follows:

Java graphics icon01.gif 9.57 Give the binomial queue that results when the keys E A S Y Q U E S T I O N are inserted into an initially empty binomial queue.

Most often, such exercises relate directly to examples in the text. They should present no special difficulty, but working them might teach you a fact or concept that may have eluded you when you read the text. Exercises that add new and thought-provoking information to the material are marked with an open circle, as follows:

ScreenshotWrite a program that inserts N random integers into a table of size N/100 using separate chaining, then finds the length of the shortest and longest lists, for N = 103, 104, 105, and 106.

Such exercises encourage you to think about an important concept that is related to the material in the text, or to answer a question that may have occurred to you when you read the text. You may find it worthwhile to read these exercises, even if you do not have the time to work them through. Exercises that are intended to challenge you are marked with a black dot, as follows:

• 8.46 Suppose that mergesort is implemented to split the file at a random position, rather than exactly in the middle. How many comparisons are used by such a method to sort N elements, on the average?

Such exercises may require a substantial amount of time to complete, depending on your experience. Generally, the most productive approach is to work on them in a few different sittings. A few exercises that are extremely difficult (by comparison with most others) are marked with two black dots, as follows:

•• 15.29 Prove that the height of a trie built from N random bitstrings is about 2lg N.

These exercises are similar to questions that might be addressed in the research literature, but the material in the tutorial may prepare you to enjoy trying to solve them (and perhaps succeeding). The annotations are intended to be neutral with respect to your coding and mathematical ability. Those exercises that require expertise in coding or in mathematical analysis are self-evident. All readers are encouraged to test their understanding of the algorithms by implementing them. Still, an exercise such as this one is straightforward for a practicing programmer or a student in a coding course, but may require substantial work for someone who has not recently programmed:

Modify Program 1.4 to generate random pairs of integers between 0 and N - 1 instead of reading them from standard input, and to loop until N - 1 union operations have been performed. Run your program for N = 103, 104, 105, and 106 and print out the total number of edges generated for each value of N.

In a similar vein, all readers are encouraged to strive to appreciate the analytic underpinnings of our knowledge about properties of algorithms. Still, an exercise such as this one is straightforward for a scientist or a student in a discrete mathematics course, but may require substantial work for someone who has not recently done mathematical analysis:

Compute the average distance from a node to the root in a worst-case tree of 2n nodes built by the weighted quick-union algorithm.

There are far too many exercises for you to read and assimilate them all; my hope is that there are enough exercises here to stimulate you to strive to come to a broader understanding on the topics that interest you than you can glean by simply reading the text.

Previous   Next