# Using induction to design algorithms

@article{Manber1988UsingIT, title={Using induction to design algorithms}, author={Udi Manber}, journal={Commun. ACM}, year={1988}, volume={31}, pages={1300-1313} }

An analogy between proving mathematical theorems and designing computer algorithms provides an elegant methodology for designing algorithms, explaining their behavior, and understanding their key ideas.

#### 24 Citations

How to design dynamic programming algorithms sans recursion

- Computer Science
- SIGA
- 1998

We describe a method, which we call the Pruning Method, for designing dynamic programming algorithms that does not require the algorithm designer to be comfortable with recursion.

Loop invariants and mathematical games

- Computer Science
- SIGCSE '95
- 1995

This paper describes how to illustrate the concept of combining loop invariants with algorithm analysis and design with mathematical games and emphasizes the links between heuristic search strategies, pattern exploration, induction, and invariant construction. Expand

From specific problem instances to algorithms in the introductory course

- Computer Science
- SIGCSE '94
- 1994

The technique is a more formal and systematic approach to programming based on generalizing a pattern after studying and expanding on a sequence of specific problem instances that develops the algorithm and justification of its correctness together. Expand

Proof methods and greedy algorithms

- 2008

This lecture in some ways covers two separate topics: (1) how to prove algorithms correct, in general, using induction; and (2) how to prove greedy algorithms correct. Of course, a thorough… Expand

Induction and Recursion ... and Reduction

- Computer Science
- 2014

In this chapter, I lay the foundations for your algorithm design skills with procedural (or functional) abstraction and object orientation. Expand

Searching by Elimination

- Computer Science
- MPC
- 1989

This work presents a way of program derivation that is applicable to a wide class of searching problems and yields very elegant programs. Expand

Constructing Programs as Executable Attribute Grammars

- Computer Science
- Comput. J.
- 1992

Attributes grammars provide a formal yet intuitive notation for specifying the static semantics of programming languages and consequently have been used in various compiler generation systems. Their… Expand

Algorithms - Design Techniques and Analysis

- Computer Science
- Lecture Notes Series on Computing
- 1999

This book advocates the study of algorithmDesign techniques by presenting most of the useful algorithm design techniques and illustrating them through numerous examples. Expand

Use of the W/AGE CASE tool in artificial intelligence

- Computer Science
- [Proceedings 1989] IEEE International Workshop on Tools for Artificial Intelligence
- 1989

The authors give two examples of the use of a novel approach for building input language processing intensive programs in a lazy pure functional programming language. The proposed approach relies on… Expand

#### References

SHOWING 1-10 OF 20 REFERENCES

Introduction to algorithms - a creative approach

- Computer Science
- 1989

Algorithms Involving Sequences and Sets, Algebraic and Numeric Algorithms, Parallel Al algorithms, and NP-Completeness. Expand

Combinatorial problems and exercises

- Mathematics
- 1979

Problems Hints Solutions Dictionary of the combinatorial phrases and concepts used Notation Index of the abbreviations of textbooks and monographs Subject index Author index Errata.

The Science of Programming

- Computer Science
- Text and Monographs in Computer Science
- 1981

Describes basic programming principles and their step-by- step applications and shows how to apply them to real-world problems. Expand

Algorithm design: A recursion transformation framework

- Computer Science
- 1988

This book surveys the most important algorithms and data structures in use in computers today and attempts to trace the origins and development of each algorithm. The author discusses the approaches… Expand

The Design and Analysis of Computer Algorithms

- Computer Science
- 1974

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs. Expand

On the recursive programming techniques

- Computer Science
- CACM
- 1964

One of the books you can enjoy now is recursive programming techniques here and it is your own time to continue reading habit. Expand

Computational geometry: an introduction

- Computer Science, Mathematics
- 1985

This book offers a coherent treatment, at the graduate textbook level, of the field that has come to be known in the last decade or so as computational geometry. Expand

Multidimensional divide-and-conquer

- Mathematics, Computer Science
- CACM
- 1980

Multidimensional divide-and-conquer is discussed, an algorithmic paradigm that can be instantiated in many different ways to yield a number of algorithms and data structures for multidimensional problems. Expand

Implementing mathematics with the Nuprl proof development system

- Mathematics, Computer Science
- 1986

This ebook presents full variant of this ebook in DjVu, PDF, ePub, doc, txt forms, and on the website you may read guides and different art eBooks online, either downloading or downloading. Expand

The Art of Computer Programming

- Computer Science
- 1968

The arrangement of this invention provides a strong vibration free hold-down mechanism while avoiding a large pressure drop to the flow of coolant fluid. Expand