Algorithm Synthesis: A Comparative Study

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.