This chapter is from the book
This chapter is from the book
This chapter is from the book
Notes on the Exercises
The exercises in this set of books have been designed for self-study as well as for classroom study. It is difficult, if not impossible, for anyone to learn a subject purely by reading about it, without applying the information to specific problems and thereby being encouraged to think about what has been read. Furthermore, we all learn best the things that we have discovered for ourselves. Therefore the exercises form a major part of this work; a definite attempt has been made to keep them as informative as possible and to select problems that are enjoyable as well as instructive.
In many books, easy exercises are found mixed randomly among extremely difficult ones. A motley mixture is, however, often unfortunate because readers like to know in advance how long a problem ought to take — otherwise they may just skip over all the problems. A classic example of such a situation is the book Dynamic Programming by Richard Bellman; this is an important, pioneering work in which a group of problems is collected together at the end of some chapters under the heading “Exercises and Research Problems,” with extremely trivial questions appearing in the midst of deep, unsolved problems. It is rumored that someone once asked Dr. Bellman how to tell the exercises apart from the research problems, and he replied, “If you can solve it, it is an exercise; otherwise it’s a research problem.”
Good arguments can be made for including both research problems and very easy exercises in a book of this kind; therefore, to save the reader from the possible dilemma of determining which are which, rating numbers have been provided to indicate the level of difficulty. These numbers have the following general significance:
Rating Interpretation
00 An extremely easy exercise that can be answered immediately if the material of the text has been understood; such an exercise can almost always be worked “in your head,” unless you’re multitasking.
10 A simple problem that makes you think over the material just read, but is by no means difficult. You should be able to do this in one minute at most; pencil and paper may be useful in obtaining the solution.
20 An average problem that tests basic understanding of the text material, but you may need about fifteen or twenty minutes to answer it completely. Maybe even twenty-five.
30 A problem of moderate difficulty and/or complexity; this one may involve more than two hours’ work to solve satisfactorily, or even more if the TV is on.
40 Quite a difficult or lengthy problem that would be suitable for a term project in classroom situations. A student should be able to solve the problem in a reasonable amount of time, but the solution is not trivial.
50 A research problem that has not yet been solved satisfactorily, as far as the author knew at the time of writing, although many people have tried. If you have found an answer to such a problem, you ought to write it up for publication; furthermore, the author of this book would appreciate hearing about the solution as soon as possible (provided that it is correct).
By interpolation in this “logarithmic” scale, the significance of other rating numbers becomes clear. For example, a rating of 17 would indicate an exercise that is a bit simpler than average. Problems with a rating of 50 that are subsequently solved by some reader may appear with a 40 rating in later editions of the book, and in the errata posted on the Internet (see page iv).
The remainder of the rating number divided by 5 indicates the amount of detailed work required. Thus, an exercise rated 24 may take longer to solve than an exercise that is rated 25, but the latter will require more creativity. All exercises with ratings of 46 or more are open problems for future research, rated according to the number of different attacks that they’ve resisted so far.
The author has tried earnestly to assign accurate rating numbers, but it is difficult for the person who makes up a problem to know just how formidable it will be for someone else to find a solution; and everyone has more aptitude for certain types of problems than for others. It is hoped that the rating numbers represent a good guess at the level of difficulty, but they should be taken as general guidelines, not as absolute indicators.
This book has been written for readers with varying degrees of mathematical training and sophistication; as a result, some of the exercises are intended only for the use of more mathematically inclined readers. The rating is preceded by an M if the exercise involves mathematical concepts or motivation to a greater extent than necessary for someone who is primarily interested only in programming the algorithms themselves. An exercise is marked with the letters “HM” if its solution necessarily involves a knowledge of calculus or other higher mathematics not developed in this book. An “HM” designation does not necessarily imply difficulty.
Some exercises are preceded by an arrowhead, “▶”; this designates problems that are especially instructive and especially recommended. Of course, no reader/student is expected to work all of the exercises, so those that seem to be the most valuable have been singled out. (This distinction is not meant to detract from the other exercises!) Each reader should at least make an attempt to solve all of the problems whose rating is 10 or less; and the arrows may help to indicate which of the problems with a higher rating should be given priority.
Several sections have more than 100 exercises. How can you find your way among so many? In general the sequence of exercises tends to follow the sequence of ideas in the main text. Adjacent exercises build on each other, as in the pioneering problem books of Pólya and Szegö. The final exercises of a section often involve the section as a whole, or introduce supplementary topics.
Solutions to most of the exercises appear in the answer section. Please use them wisely; do not turn to the answer until you have made a genuine effort to solve the problem by yourself, or unless you absolutely do not have time to work this particular problem. After getting your own solution or giving the problem a decent try, you may find the answer instructive and helpful. The solution given will often be quite short, and it will sketch the details under the assumption that you have earnestly tried to solve it by your own means first. Sometimes the solution gives less information than was asked; often it gives more. It is quite possible that you may have a better answer than the one published here, or you may have found an error in the published solution; in such a case, the author will be pleased to know the details. Later printings of this book will give the improved solutions together with the solver’s name where appropriate.
When working an exercise you may generally use the answers to previous exercises, unless specifically forbidden from doing so. The rating numbers have been assigned with this in mind; thus it is possible for exercise n + 1 to have a lower rating than exercise n, even though it includes the result of exercise n as a special case.
Exercises
▶1. [00] What does the rating “M15 ” mean?
2. [10] Of what value can the exercises in a textbook be to the reader?
3. [HM45] Prove that every simply connected, closed 3-dimensional manifold is topologically equivalent to a 3-dimensional sphere.
The men that stood for office, noted for acknowledged worth,
And for manly deeds of honour, and for honourable birth;
Train’d in exercise and art, in sacred dances and in song,
All are ousted and supplanted by a base ignoble throng.
— ARISTOPHANES, The Frogs (405 B.C.)
Here mine aduice, shall be to those Artificers that will profite in this,
or any of my bookes nowe published, or that hereafter shall be,
firste confusely to reade them thorow; then with more iudgement,
and at the thirde readinge wittely to practise. So fewe thinges shall be vnknowen.
— LEONARDE DIGGES, A Boke named Tectonicon (1556)
Now I saw, tho’ too late, the Folly of
beginning a Work before we count the Cost,
and before we judge rightly of our own Strength to go through with it.
— DANIEL DEFOE, Robinson Crusoe (1719)