A Survey of Analysis Techniques for Discrete Algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Survey of Analysis Techniques for Discrete Algorithms

Full text

Pdf (2.23 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 9 , Issue 4 (December 1977) table of contents

Pages: 291 - 313

Year of Publication: 1977

ISSN:0360-0300

Author

Bruce Weide

Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pennsylvania

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 70, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/356707.356711 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	BAUDET, G Numerical computatmns on asynchronous multiprocessors, Carnegie-Mellon Umv, Dept Computer Sci., Pittsburgh, Penn, Apml 1976
	3	BEARDWOOD, J., HALTON, J. H.; AND HAMMER- SLEY, J M. "The shortest path through many points," Proc. Cambridge Phdosoph~cal Soc. 55, 4 (Oct. 1959), 299-327.
	4	BENTLEY, J L, AND SHAMOS, M. I. Dw~de and conquer for l~near expected time, Carnegie-Mellon Univ, Dept. Computer Sci., Pittsburgh, Penn., March 1977; to appear m Inf. Process. Lett
	5	BLUM, M.; FLOYD, R. W.; PRATT, V ; RIVEST, R. L, AND TARJAN, R E. "Time bounds for selectmn," J Comput. Syst. Scz. 7, 4 (Aug. 1973), 448-461.
	6	BORODIN, A. "Computational complexity theory and practice" in Currents tn the theory of computzng, A. V. Aho, {Ed.}, Prentlce- Hall, Inc., Englewood Cliffs, N.J., 1973, pp. 35-89.
	7	BORODIN, A.; AND MUNRO, I. The computatmnal complexzty of algebraw and numeric problems, American Elsevier, N.Y., 1975
	8	K. M. Chandy , P. F. Reynolds, Scheduling partially ordered tasks with probabilistic execution times, Proceedings of the fifth ACM symposium on Operating systems principles, p.169-177, November 19-21, 1975, Austin, Texas, United States
	9	COFFMAN, E. G. {Sd.} Computer and job shop scheduling theory, John Wiley and Sons, Inc., N.Y., 1976.
	10	E. G. Coffman, Jr. , Ravi Sethi, A generalized bound on LPT sequencing, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.306-310, March 29-31, 1976, Cambridge, Massachusetts, United States [doi>10.1145/800200.806205]
	11	COHEN, J.; AND ROTH, M. "On the implementation of Strassen's fast multlphcation algorithm,"Acta Inf. 6, 4 (1976), 341-355.
	12	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	13	DAHLQUIST, G.; AND BJORCK, A. Numerwal methods, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974.
	14	DIJKSTRA, E.W. ~'A note on two problems in connexion with graphs," Numer. Math. 1, (1959), 269-271.
	15	DOBKIN, D.; AND LIPTON, R., On the complex- ~ty of computations under varying sets of pnm- ~tives, Tech. Rep no. 42, Yale Univ., Dept Computer Sci., New Haven, Conn., 1975.
	16	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	17	ERDOS, P.; AND SPENCER, J. Probabdzstw methods ~n comb~natorws, Academic Press, N Y, 1974.
	18	FISCHER, M. J.; ANY MEYER, A.R. "Boolean matrix multiphcation and transitive closure," m Conf. Record, IEEE 12th Ann Syrup Swttchzng Automata Theory, IEEE, N.Y., 1971, pp. 129-131.
	19	Robert W. Floyd, Algorithm 245: Treesort, Communications of the ACM, v.7 n.12, p.701, Dec. 1964 [doi>10.1145/355588.365103]
	20	Robert W. Floyd , Ronald L. Rivest, Expected time bounds for selection, Communications of the ACM, v.18 n.3, p.165-172, March 1975 [doi>10.1145/360680.360691]
	21	FORD, L. R.; AND JOHNSON, S.M. "A tournament problem," Am Math. Monthly 66, (1959), 387-389.
	22	FRAZER, W D. "Analysm of combinatory algorlthms-a sample of current methodology," in Proc. AFIPS 1972 Spr~ng Jr. Computer Conf., Vol. 40, AFIPS Press,Montvale, N.J., pp. 483-491.
	23	FULLER, S. H; GASCHNIG, J. G.; AND GIL- LOGLY, d. J Analysl~s of the alpha-beta pruntrig algorithm, Carnegie-Mellon Univ, Dept Computer Scl., Pittsburgh, Penn., July 1973.
	24	M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
	25	GAREY, M. R.; AND JOHNSON, D. S. "Approxlmation algorithms for combinatorial problems: an annotated bibliography," in Algorithms and complexity: New dwecttons and recent results, J. F. Traub, {Ed.}, Academic Press, N.Y., 1976, pp. 41-52
	26	GRAHAM, R L. "An efficient algorithm for determining the convex hull of a finite planar set," Inf. Process Lett. 1, (1972), 132-133.
	27	Leo J. Guibas , Endre Szemeredi, The analysis of double hashing(Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.187-191, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803647]
	28	HOARE, C. A.R. "Quicksort," Comput. J 5, (1962), 10-15.
	29	HOPCROFr, J E. "Complexity of computer computations," in Proc. 1FIP Congress 74, Vol. 3, North-Holland Publ. Co., Amsterdam, The Netherlands, 1974, pp. 620-626.
	30	John Hopcroft , Robert Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, v.16 n.6, p.372-378, June 1973 [doi>10.1145/362248.362272]
	31	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	32	HOPCROFT, J E.; AND ULLMAN, J. D. "Set merging algorithms," SIAM J. Comput. 2, 4 (Dec. 1973), 294-303.
	33	HYAFIL, L. "Bounds on selectmn," SIAM J. Comput. 5, 1 (March 1976), 109-114.
	34	L. Hyafil , H. T. Kung, The complexity of parallel evaluation of linear recurrence, Proceedings of seventh annual ACM symposium on Theory of computing, p.12-22, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803748]
	35	Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
	36	Donald B. Johnson, A Note on Dijkstra's Shortest Path Algorithm, Journal of the ACM (JACM), v.20 n.3, p.385-388, July 1973 [doi>10.1145/321765.321768]
	37	David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
	38	JOHNSON, D. S. "Fast algorithms for bm packing," J. Comput. Syst Scz. 8, 3 (June 1974), 272-314.
	39	KARP, R M. "Reducibility among combinatorial problems," in Complexity of computer computatmns, R. E. Miller, and J W. Thatcher, {Eds.}, Plenum Press, N.Y, 1972, pj). 85-103
	40	tkARP, R M "On the computational comp\|exlty of combmatorml problems," Networks 5, 1 (Jan 1975), 45-68.
	41	KARP, R. M "The probabilishc analysis of some combinatorial search algorithms," in Algorithms and complexity New dtrectmns and recent results, J F. Traub, lEd.l, Academic Press, N.Y., 1976, 1-19.
	42	Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
	43	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	44	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	45	KNUTH, D E "Mathematical analysm of alg orithms," m Proc IFIP Congress 71, Vol 1, orth-Holland Publ Co., Amsterdam, The Netherlands, 1971, pp. 135-143.
	46	K~WTH, D E The art of computer programrnzng, Vol. lII Sorlzn~ and searchtng, Addison-Wesley, Reading, lwass, 1973
	47	Donald E. Knuth, Big Omicron and big Omega and big Theta, ACM SIGACT News, v.8 n.2, p.18-24, April-June 1976 [doi>10.1145/1008328.1008329]
	48	KNUTH, D. E.; AND MOORE, R W. "An analysis of alpha-beta pruning," Artff Intell 6, (1975), 293-326.
	49	KNUTH, D. E, MORRIS, J H.; AND PRATT, V R. Fastpattern matching zn strings, Tech. Rep STAN-CS-74-440, Computer Scl Dept., Stanford Umv., Stanford, Cahf., Aug. 1974, also Knuth, D. E.; Morns, J. H.; and Pratt, V. R. "Fast pattern matching m strings," SIAM J. Comput. 60 2 (June 1977), 323-350.
	50	Richard E. Ladner, On the Structure of Polynomial Time Reducibility, Journal of the ACM (JACM), v.22 n.1, p.155-171, Jan. 1975 [doi>10.1145/321864.321877]
	51	LAWLER, E. L. "Algorithms, graphs, and complexity," Networks 5, 1 (Jan 1975), 89-92.
	52	LIU, C L. introductmn to combinatorial mathematics, McGraw-Hill, N.Y., 1968.
	53	NEWBORN, M.M. "The effioency of the alpha-beta search on trees with branch-dependent terminal node scores," abstract in Algorithms and complexity. New d~rectmns and recent results, J. F. Traub, {Ed.}, Academic Press, N.Y, 1976, p. 483.
	54	O'NEIL, P. E; AND O'NEIL, E J. "A fast expected-time algorithm for Boolean matrix multiplication and transitive closure," Inf Control 22, 2 (March 1973), 132-138.
	55	RABIN, M.O. "Probabllistlc algorithms," in Algorithms and complextty New d~recttons and recent results, J F. Traub, {Ed.}, Academm Press, N.Y., 1976, pp. 21-39.
	56	REINGOLD, E M. "Estabhshlng lower bounds on algorithms- a survey," m AFIPS 1972 ~p r~ng Jr. Computer Conf, Vol 40, AFIPS ress, Montvale, N J, 1972, pp 471-481.
	57	Edward M. Reingold, On the Optimality of Some Set Algorithms, Journal of the ACM (JACM), v.19 n.4, p.649-659, Oct. 1972 [doi>10.1145/321724.321730]
	58	Ronald L. Rivest , Jean Vuillemin, A generalization and proof of the Aanderaa-Rosenberg conjecture, Proceedings of seventh annual ACM symposium on Theory of computing, p.6-11, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803747]
	59	Arnold L. Rosenberg, On the time required to recognize properties of graphs: a problem, ACM SIGACT News, v.5 n.4, p.15-16, October 1973 [doi>10.1145/1008299.1008302]
	60	SAHNI, S. "Computatlonally related problems," SIAM J Comput. 3, 4 (Dec 1974), 262-279
	61	Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]
	62	SAHNI, S. General technzques for comb~natortal approxtmatmn, Tech. Rep. 76-6, Dept. Computer Sci., Umv Minnesota, Mmneapohs, Minn., June 1976.
	63	SCHONHAGI~, A.; PATERSON, M.; AND PIPPEN- GER, N. "Finding the median," J Comput. Syst Sc~. 13, (Oct 1976), 184-199
	64	SEDGEWICK, R. "Quicksort," PhD Thesis, Stanford Univ., Stanford, Califi, Tech. Rep. STAN-CS-75-492, May 1975; for a summary see Sedgewmk R., "The analysis of Quicksort programs," Acta Inf. 7, 4 (1977), 327-355.
	65	Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
	66	SHAMOS, M. I ; ANY HOBY, D. ~'Closest point ~roblems," m Proc 16th Ann. IEEE oundatwns Computer Sct, IEEE, S~?~t~: 1975, pp. 151-162.
	67	SHAMOS, M. I; AND Y~VAL, G. "Lower bounds from complex function theory," in Proc 17th Ann. IEEE Symp. Foundatmns Computer Sci., IEEE, N.Y., 1976, pp. 268-273.
	68	SLOANE, N. J. A. A handbook of mteger sequences, Academic Press, N.Y., 1973
	69	SOLOVAY, R.; AND STRASSEN, V. "A fast Monte-Carlo test for pnmality," SIAM J Comput 6, 1 (March 1977), 84-85
	70	SPmA, P.M. A new algorithm for finding all shortest paths in a graph of pomtlve arcs m average time O(n21og2n),'' SIAM J. Cornput. 2, 1 (March 1973), 28-32.
	71	STRASSEN, V "Gaussian elimination is not optimal," Numer Math. 13, (1969), 345-356.
	72	TAaJAN, R.E. "Depth first search and linear graph algorithms," SIAM J. Comput 1, 2 (June 1972), 146-160.
	73	Joseph F. Traub, Complexity of Sequential and Parallel Numerical Algorithms, Academic Press, Inc., Orlando, FL, 1973
	74	VALIANT, L. G "General context-free recogmtmn m less than cubic time," J. Comput Syst. Scz. 10, 2 (April 1975), 308-315.
	75	Leslie G. Valiant, On non-linear lower bounds in computational complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.45-53, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803752]
	76	WELLS, M. B. "Apphcations of a language for computing m combinatorics," m Proc IFIP Congress 65, Vol. 2, Spartan Books, Washington, D. C., 1965, pp. 497-498.
	77	WELLS, M. B Elements of combznatonal computtng, Pergamon Press, Elmsford, N.Y., 1971.
	78	WILLIAMS, J. W. J "Algomthm 232: heapsort," Commun ACM 7, 6 (June 1964), 347- 348.
	79	YUVAL, G personal communication, 1975.

CITED BY 6

	Bernard M. E. Moret, Decision Trees and Diagrams, ACM Computing Surveys (CSUR), v.14 n.4, p.593-623, Dec. 1982
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
	Dorothy E. Denning , Peter J. Denning , Mayer D. Schwartz, The tracker: a threat to statistical database security, ACM Transactions on Database Systems (TODS), v.4 n.1, p.76-96, March 1979
	Marvin V. Zelkowitz, Perspectives in Software Engineering, ACM Computing Surveys (CSUR), v.10 n.2, p.197-216, June 1978
	Subrata Dasgupta, The Organization of Microprogram Stores, ACM Computing Surveys (CSUR), v.11 n.1, p.39-65, March 1979
	Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980