Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Ordering block designs : gray codes, universal cycles and configuration orderings
Dewar M., Stevens B., Springer Publishing Company, Incorporated, New York, NY, 2012. 218 pp.  Type: Book (978-1-461443-24-7)
Date Reviewed: Jan 23 2013

A combinatorial block design is a mathematical object used in various engineering fields, such as experimental design, coding theory, and software testing, but also in other areas like tournament scheduling. A block design generally consists of a set of points P and a set of subsets of P, called blocks. The blocks are chosen to satisfy certain properties, such as symmetry or balance, which might be useful for an application. For example, in software testing, the points are all the possible input values. Since it might not be possible to run all input value combinations to test a new software version in one session, it becomes necessary to consider systematic differences of the value combinations in the various test runs. It might also be necessary to order the blocks, or parameter subsets, to systematically track down errors.

This monograph focuses on ordered blocks where the difference between adjacent blocks is minimal. In coding theory, code with this property is known as Gray code (after Frank Gray, physicist and researcher); many of the results of coding theory can be used for ordering block designs. After a brief introduction, chapter 2 presents a good overview of designs in general and block designs in particular, especially the important class of balanced incomplete block designs. The authors next discuss binary and combinatorial Gray codes (chapter 3), and present more details on different orderings and configurations of block designs (chapter 4).

In chapter 5, three different types of designs are discussed, and the existence of Gray codes and so-called universal cycles is proven for certain designs. This is the longest chapter in the book, and mathematically the most difficult one. Readers more oriented to applications may skip to chapter 6, the last chapter, where ordering block designs is applied to different problems, such as the correction of failures in redundant arrays of independent storage disks, the scheduling of game tournaments, reliability testing, and statistical experiments. Chapter 6, together with the background information in chapter 2, will interest engineers and scientific experimenters. The remainder of the book is only of interest to mathematical researchers in the field of combinatorial design theory.

Each chapter includes some problem exercises (no solutions given) and a list of references. The authors have taken great care in explaining the mathematical formulae, using figures where applicable. Nonetheless, the presentation is dense and rigorous. This is not a book for beginners or readers looking for an introduction to combinatorial design.

Reviewer:  Klaus Galensa Review #: CR140856 (1304-0287)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
Combinatorics (G.2.1 )
Numerical Algorithms (G.1.0 ... )
Numerical Algorithms And Problems (F.2.1 )
Would you recommend this review?
Other reviews under "Combinatorics": Date
The hardness of counting full words compatible with partial words
Manea F., Tiseanu C.  Journal of Computer and System Sciences 79(1): 7-22, 2013. Type: Article
Apr 22 2014
Analytic combinatorics in several variables
Pemantle R., Wilson M.,  Cambridge University Press, New York, NY, 2013. 400 pp. Type: Book (978-1-107031-57-9)
Feb 21 2014
Approximation algorithms for a minimization variant of the order-preserving submatrices and for biclustering problems
Hochbaum D., Levin A.  ACM Transactions on Algorithms 9(2): 1-12, 2013. Type: Article
Jun 17 2013

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2014 ThinkLoud, Inc.
Terms of Use
| Privacy Policy