Algorithm synthesis : a comparative study

In early 1986, one of us (D.M.S.) was constructing an artificial intelligence system to design algorithms, and the other (A.P.A.) was getting started in program transformations research. We shared an office, and exchanged a few papers on the systematic development of algorithms from specifications. Gradually we realized that we were trying to solve some of the same problems. And so, despite radical differences between ourselves in research approaches, we set out together to see what we could learn from these papers. That's how this book started: a couple of graduate students trying to cope with The Literature. At first, there was just a list of papers. One of us (D.M.S.) tried to cast the papers in a uniform framework by describing the problem spaces searched, an approach used in artificial intelligence for understanding many tasks. The generalized problem space descriptions, though useful, seemed to abstract too much, so we decided to compare papers by different authors dealing with the same algorithm. These comparisons proved crucial: for then we began to see similar key design choices for each algorithm. This book presents a uniform framework for presenting and comparing derivations of algorithms, and applies this framework to analyze various derivations found in the literature for seven algorithms. The authors have selected algorithms for which multiple derivations exist. The framework developed abstracts from individual presentation styles and notations to focus on what was accomplished at each step of a derivation, and on the rationale for each design choice. Charts for each presentation capture this information using informal and readable conventions, while the composite graphs and associated text highlight important similarities and differences about a group of presentations for each of the seven algorithms. This indepth study of the diversity of algorithm derivations attempts to identify issues in the areas of design goals, languages, derivation structure, implementations, and presentation style. The seven algorithms studied are: insertion sort, quicksort, cartesian set product, depth-first search in a directed graph, Schorr-Waite graph marking, n-queens, and convex hull. The book will be of interest to computer science researchers and practitioners and to applied mathematicians with specific interests in the areas of programming systems, program transformations, algorithm design, automatic programming, software engineering, and artificial intelligence. Front Matter....Pages i-ix Introduction....Pages 1-7 Insertion Sort....Pages 8-23 Quicksort....Pages 24-38 Cartesian Set Product....Pages 39-46 Depth-First Search....Pages 47-62 Schorr-Waite Graph Marking....Pages 63-77 N -Queens....Pages 78-94 Convex Hull....Pages 95-103 Design Space: The Final Frontier....Pages 104-111 Back Matter....Pages 112-118