skip to main content
article
Free Access

Using induction to design algorithms

Published:01 November 1988Publication History
Skip Abstract Section

Abstract

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.

References

  1. 1 Aho, A., Hopcroft, J., and Ullman, J. The Design and Analysis of Computer Algorithms. Addison Wesley, Reading, Mass., 1974. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. 2 Bates, J.L., and Constable, R.L. Proofs as programs. ACM Trans. Prog. Lang. and Syst. 7, 1 (Jan. 1985), pp. 113-136. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. 3 Beckenbach, E., and Bellman, R. An Introduction to Inequalities. New Mathematical Library, Random House, 1961.Google ScholarGoogle Scholar
  4. 4 Bently, J.L. Multidimensional divide-and-conquer. Commun. ACM 23, 4 (April 1980), 214-229. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. 5 Burge, W.H. Recursive Programming Techniques, Addison Wesley, Reading, Mass., ~975. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. 6 Constable, R.L. et al. Implementing Mathematics with the Nuprl Proof Development System. Prentice Hall, Englewood Cliffs, N.J., 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 7 Dijkstra, E.W. A Discipline of Programming. Prentice Hall, Englewood Cliffs, N.J., 1976. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. 8 Gries, D. The Science of Programming, Springer-Verlag, New York, 1981. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 9 King, K.N., and Smith-Thomas, B. An optimal algorithm for sinkfinding, Inf. Proc. Letters 14, 3 (1982), pp. 109-111.Google ScholarGoogle ScholarCross RefCross Ref
  10. 10 Knuth, D.E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. 2nd ed., Addison Wesley, Reading, Mass., 1981. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. 11 Lovasz, L. Combinatorial Problems and Exercises, North Holland, 1979.Google ScholarGoogle Scholar
  12. 12 Manber, U. Introduction to Algorithms--A Creative Approach. Addison Wesley, Reading, Mass., 1989, to appear. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. 13 Paull, M.C. Algorithm Design--A Recursion Transformation Framework, John Wiley and Sons, New York, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. 14 Polya, G. How to Solve It. 2nd ed., Princeton University Press, 1957.Google ScholarGoogle Scholar
  15. 15 Preparata, F., and Shamos, M.I. Computational Geometry, Springer- Verlag, New York, 1985. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. 16 Shamos, M.I., and Hoey, D. Closest-point problems, In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, (Berkeley, Calif., Oct. 1975). 1975.Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Using induction to design algorithms

                    Recommendations

                    Reviews

                    Marguerite Elizabeth Saacks Giguette

                    The author presents a technique that uses mathematical induction to design algorithms. By using induction, he hopes to show a relationship between theorems and algorithm design that students will find intuitive. The author illustrates his approach with solutions to a number of well-known problems. His detailed explanations of these solutions are relatively easy to follow. The author first presents a complexity analysis for each solution, which helps to call attention to the usefulness of this strategy. The only background needed is a knowledge of mathematical induction. The references are good and give the reader a way to investigate this technique further. Overall, this paper is good. It is understandable and provides insight into algorithm design.

                    Access critical reviews of Computing literature here

                    Become a reviewer for Computing Reviews.

                    Comments

                    Login options

                    Check if you have access through your login credentials or your institution to get full access on this article.

                    Sign in

                    Full Access

                    • Published in

                      cover image Communications of the ACM
                      Communications of the ACM  Volume 31, Issue 11
                      Nov. 1988
                      102 pages
                      ISSN:0001-0782
                      EISSN:1557-7317
                      DOI:10.1145/50087
                      Issue’s Table of Contents

                      Copyright © 1988 ACM

                      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                      Publisher

                      Association for Computing Machinery

                      New York, NY, United States

                      Publication History

                      • Published: 1 November 1988

                      Permissions

                      Request permissions about this article.

                      Request Permissions

                      Check for updates

                      Qualifiers

                      • article

                    PDF Format

                    View or Download as a PDF file.

                    PDF

                    eReader

                    View online with eReader.

                    eReader