Perverse and foolish oft I strayed

ABSTRACT

This uses a massively wrong-headed algorithm for sorting to exemplify the use of the backtracking strategy and the branch-and-bound strategy. In addition, brief notes are included on parallel processing approaches: Java theads on multi-core computers and distributed processing through such message passing systems as PVM and MPI.

REFERENCES

• 1: Charles Gounod, "The King of Love My Shepherd Is," The First Book of Baritone/Bass Solos, Joan Frey Boytim, editor (G. Schirmer, 1991), p. 45. Text is by Henry W. Baker, Hymns Ancient and Modern ("srandard edition", London: 1924), p. 197. http://www.cyberhymnal.org/htm/k/i/kinglove.htm gives the text and the music for "St. Columba", a common hymn tune to which it is set.
• 2: The code for such a sort is fairly simple. The following is a Java implementation stripped of documentation. {CODE} The shuffle algorithm above is discussed in Timothy J Rolfe, "Algorithm Alley: Randomized Shuffling", Dr. Dobb's Journal, Vol. 25, No. 1 (January 2000), pp. 113--14. The article is available on-line through http://www.ddj.com/dept/architect/184403979
• 3: http://stdout.org/~adam/psort/---as accessed 2007 December 28.
• 4: The entire backtracking chapter of Sartaj Sahni's Data Structures, Algorithms, and Applications in Java (2nd ed., 2005) is available online: http://www.cise.ufl.edu/~sahni/dsaaj/chapters.htm
• 5: Similarly, the entire branch and bound chapter from the same standard text is available through the above URL.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Performance, Theory

Keywords:
algorithm analysis, backtracking, branch and bound, distributed processing, permutation generation