Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Problems in programming
Vitek A., Tvrdy I., Reinhardt R., Mohar B. (ed), Martinec M., Dolenc T., Batagelj V. (ed), John Wiley & Sons, Inc., New York, NY, 1991. Type: Book (9780471930174)
Date Reviewed: Aug 1 1992

The first part of this book presents general considerations about programs: program correctness, program documentation, program robustness and safe programming, program style, software tools, and user interfaces. The second part contains programming problems from Slovenian competitions, indexed by letters giving their domains. The third part is the most important: it gives solutions to these problems. The problems are arranged by topics: straightforward problems, computational problems, recursive functions, reordering, graphs, real-time process control, computer graphics, and miscellaneous.

Each chapter begins with a short presentation of the domain and bibliographical references. For each problem, the authors give a program written in Pascal and indications about the solution, ranging in length from a few lines to several pages. The programs are written with good programming style and are pretty printed. Some programs are quite clever.

The intent of the book is to develop programmers’ skills through examples of elegant solutions for a wide variety of problems. This purpose is certainly good, but I wonder if the authors have achieved their goal. They insist on program correctness, which is a good thing. They say that it is practically impossible to prove the correctness of a large program, however, and thus you will not find proofs in the book, even for programs of ten lines. You will not find a loop invariant. The authors say that writing and testing a program is an unsatisfactory method, and thus “the program must be written to be as correct and as robust as possible at the first attempt,” but they do not say how this can be done or offer any examples to help the reader.

The most difficult thing in programming is to invent a reasonable algorithm to solve a problem. Most of the algorithms given in the book are smart, but nothing is said about how they have been discovered or created. In some cases, the documentation is just a paraphrase of the program. Documentation may be completely lacking: “Heapsort” is given without a word about where it came from or any reference to binary trees. Nothing is said of possible previous versions of a program, which were less clever or clear, having been improved to give the final form. Will that help the reader to develop her or his own creativity?

Some problems have cleverer solutions than those given in the book. For the well-known problem of swapping two parts of a vector (224D), for which the reader is asked to give a solution with the minimum number of swaps, the authors give a solution that moves each element of the vector twice, using 3n/4 swaps. A solution is known with one move for each element; when both parts have the same length, an obvious solution with n/2 swaps exists. Does the reader have any chance to find the trick on which the solution in the book is based? The book also presents the well-known problem of “lucky numbers.” The solution given uses a long array from which elements are deleted: two distinct solutions exist that do not use this array. This is the problem with smart programming: either you see the trick, and are lucky, or you do not see it, and are puzzled. Reading tricks does not help to invent them.

Many exercises consist of figuring out what a given commentless program computes. What can be learned from these examples is that, given any program, it is possible to say what it computes. It is well-known that, even for short, simple programs, this problem is far more difficult than proving that the program is correct relative to its specification. This kind of exercise is unfair.

Most of the exercises on recursion are pure mathematical problems on implicit functions and have nothing to do with programming. The problems on real-time systems are more interesting. The comments about the solutions are good lectures in the field of concurrence and synchronization of processes.

The main interest of the book is that it is a collection of exercises, some of which are excellent and interesting. It can serve as a resource to teachers of programming.

Reviewer:  J. Arsac Review #: CR116063
Bookmark and Share
 
General (D.1.0 )
 
 
Code Inspections And Walk-Throughs (D.2.5 ... )
 
 
Error Handling And Recovery (D.2.5 ... )
 
 
Pascal (D.3.2 ... )
 
 
Validation (D.2.4 ... )
 
 
Design (D.2.10 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "General": Date
KNOs: KNowledge acquisition, dissemination, and manipulation Objects
Tsichritzis D., Fiume E., Gibbs S., Nierstrasz O. ACM Transactions on Information Systems 5(1): 96-112, 1987. Type: Article
Nov 1 1987
Programmer perceptions of productivity and programming tools
Hanson S. (ed), Rosinski R. Communications of the ACM 28(2): 180-189, 1985. Type: Article
Jul 1 1985
The craft of computer programming
Jensen C., Warner Books, Inc., New York, NY, 1985. Type: Book (9789780044638148)
Dec 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy