Evaluating Algorithmic Design Paradigms
The authors present formal models for some of the known algorithmic design paradigms. Ideally, a formal model of a paradigm should: include all or nearly all of the known algorithms intuitively classified as examples of the technique; Capture the intrinsic characteristics of the paradigm; be useful in lower bounding the limits of the technique through proofs of negative results for all algorithms in the formal model. In an algorithm design class, they are taught the basic algorithm paradigms such as divide-and-conquer, greedy algorithms, backtracking and dynamic programming. The paradigm is taught by an intuitive example together with a number of counter examples. Intuitive formulations, while easy to understand, do not allow one to answer the following natural questions.