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.
- 1 Aho, A., Hopcroft, J., and Ullman, J. The Design and Analysis of Computer Algorithms. Addison Wesley, Reading, Mass., 1974. Google ScholarDigital Library
- 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 ScholarDigital Library
- 3 Beckenbach, E., and Bellman, R. An Introduction to Inequalities. New Mathematical Library, Random House, 1961.Google Scholar
- 4 Bently, J.L. Multidimensional divide-and-conquer. Commun. ACM 23, 4 (April 1980), 214-229. Google ScholarDigital Library
- 5 Burge, W.H. Recursive Programming Techniques, Addison Wesley, Reading, Mass., ~975. Google ScholarDigital Library
- 6 Constable, R.L. et al. Implementing Mathematics with the Nuprl Proof Development System. Prentice Hall, Englewood Cliffs, N.J., 1986. Google ScholarDigital Library
- 7 Dijkstra, E.W. A Discipline of Programming. Prentice Hall, Englewood Cliffs, N.J., 1976. Google ScholarDigital Library
- 8 Gries, D. The Science of Programming, Springer-Verlag, New York, 1981. Google ScholarDigital Library
- 9 King, K.N., and Smith-Thomas, B. An optimal algorithm for sinkfinding, Inf. Proc. Letters 14, 3 (1982), pp. 109-111.Google ScholarCross Ref
- 10 Knuth, D.E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. 2nd ed., Addison Wesley, Reading, Mass., 1981. Google ScholarDigital Library
- 11 Lovasz, L. Combinatorial Problems and Exercises, North Holland, 1979.Google Scholar
- 12 Manber, U. Introduction to Algorithms--A Creative Approach. Addison Wesley, Reading, Mass., 1989, to appear. Google ScholarDigital Library
- 13 Paull, M.C. Algorithm Design--A Recursion Transformation Framework, John Wiley and Sons, New York, 1988. Google ScholarDigital Library
- 14 Polya, G. How to Solve It. 2nd ed., Princeton University Press, 1957.Google Scholar
- 15 Preparata, F., and Shamos, M.I. Computational Geometry, Springer- Verlag, New York, 1985. Google ScholarDigital Library
- 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 ScholarDigital Library
Index Terms
Using induction to design algorithms
Recommendations
Using Nondeterminism to Design Efficient Deterministic Algorithms
In this paper we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives a parameterized algorithm of running time O((5.7 k)k n) for the 3-D matching problem,...
Finding optimal design in nonlinear mixed effect models using multiplicative algorithms
Highlights- Multiplicative algorithm optimizes designs of longitudinal studies.
- ...
AbstractBackground and objectives: To optimize designs for longitudinal studies analyzed by nonlinear mixed effect models (NLMEMs), the Fisher information matrix (FIM) can be used. In this work, we focused on the multiplicative ...
Reusable components in decision tree induction algorithms
We propose a generic decision tree framework that supports reusable components design. The proposed generic decision tree framework consists of several sub-problems which were recognized by analyzing well-known decision tree induction algorithms, namely ...
Comments