91.503 Algorithms

Project Requirements

Purpose of the project:
1. become familiar with research literature in algorithms
2. develop ability to prepare technical presentations

By Nov 23/24 obtain a copy of the assigned paper, provide a copy to the instructor, and identify any issues that will effect the completion of the project.
By Dec 14/15 read the assigned paper and create a powerpoint presentation that explains the main results of the paper, in a style that is similar to lecture presentations in 91.503 this semester. Put the PPT online and email the URL to buford at cs dot uml dot edu. Use the PPT template linked below.

Where to obtain papers: MIT Barker Engineering library or MIT LCS reading room should have every publication listed.

PPT Template

Name email Paper

shkrishn Comer, D., The Ubiquitous B-Tree. Computing Suveys (11,2). June 1979. pp. 121-137

bjenkins Loui, R. P., Optimal Paths in Graphs with Stochastic or Multidimensional Weights. CACM. Sept 1983 (28,9) pp 670-676

rui.wu@ummed.edu Hopcroft, J. and Tarjan R. Efficient Planarity Testing. JACM (Oct 1974) 21,4 pp. 549-568

lwang Litke, J. D. An Improved Solution to the TSP with Thousands of Nodes. CACM (Dec 1984) 27,12. pp. 1227-1236.

kparikh Golden, B. A Statistical Approach to TSP. Networks, 7, pp. 209-225.

rkothapa Goodman, S.E., S.T. Hedetniemi. On Hamilitonian Walks in Graphs. SIAM J. of Computing. (Sept 1974), 3,3, pp. 214-221

dwan Balas, E. and Gang, S. Y. Finding a Maximum Clique in an Arbitrary Graph. SIAM J. of Computing (Nov 1986), 15, 4, pp. 1054-1068.

lliu Kubale, M., Boguslaw, J. A Generalized Implicit Enumeration Algorithm for Graph Coloring. CACM (April 1985), 28, 4,

drey Schaback, R., On the Expected Subliniearity of the Boyer-Moore Algorithm. SIAM J. of Computing 18(1989). pp 648-658

sgangula Apostolico, A., and Giancarlo, R. The Boyer Moore String Searching Strategies Revisited. SIAM J. of Computing (15,1), Feb 1986, pp. 98-105.

crossano Berglund, G.D., A Guided Tour of the Fast Fourier Transform. IEEE Spectrum (6) July 1969, pp. 41-52.

agakis Diaconis, P. Average Running Time of the Fast Fourier Transform. Algorithms. 1(1980), pp. 187-208.

smohamme Adelman, L, Pomerance, C., and Rumely, R. On distinguishing prime numbers from composite numbers. Annals of Mathematics. 117: 173-206, 1983

avenkata Beauchemin, P., Brassard, G., Crepeau, C, et al. The Generation of random numbers that are probably prime. J. of Cryptology, 1:53-64, 1988.

feinbejm@tiac.com Boyer, R.S., and Moore, J.S., A fast string-searching algorithm. CACM.20(10): 762-772, 1977.

szaman Diffie, W., and Hellman, M. New directions in cryptograph. IEEE Trans. on Information Theory. IT-22(6):644-654, 1976.

sye Dixon, J. Factorization and primality tests. American Mathematical Monthly. 91(6): 333-352, 1984

wtang Gabow, H., and Tarjan, R. A linear-time algorithm for a special case of disjoint set union. J. of computer and System Sciences, 30(2): 209-221, 1985.

akoudsi Graham, R.L., and Hell, P. On the History of the minimum spanning tree problem. Annals of the History of Computing, 7(1):43-57, 1985.

byohgargnto Huffman, D. A method for the construction of minimum-redundancy codes. Proc. of the IRE, 40(9):1098-1101, 1952

upatel Karmarkar, N. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-395, 1984

rhegde Rosengrantz, D.J., Stearns, R.E., Lewis, P.M., An analysis of several heuristics for the traveling salesman problem. SIAM J. of Computing, 6:563-581, 1977

roger@primeon.com Witten, I, and Cleary, J. Arithmetic coding for data compression. CACM (30,6): 520-541.

tnadeau@cisco.com Hanan Samet: Hierarchical Representations of Collections of Small Rectangles. Computing Surveys 20(4): 271-309(1988)

himanshu.patel2@gte.net Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573

xy.yang@aspect.com David Plainfossé, Marc Shapiro: A Survey of Distributed Garbage Collection Techniques. IWMM 1995: 211-249

ylin Chazelle, B, and Edelsbrunner, H. An optimal algorithm for intersecting line segments in the plane. Proc 29th Annual IEEE Symposium Foundations Computer Science. FOCS-88, pp. 590-600, 1988.

hlee Kirkpatrick, S. and Seidel, R. The ultimate planar convex hull algorithm? SIAM J. Computing 15, pp. 287-299, 1986.

ntansala Shamos, M, Hoey, D., Geometric intersection problems, Proc. 17th Ann. IEEE Symp. Foundations Comput. Sci. FOCS-76, pp. 208-215.

kiran@comversens.com Rytter, W. On the parallel computation of dynamic programming problems. Theoretical Computer Science. 59, pp. 297-307

byoo Cook, S. The complexity of theorem proving procedures. Proc of the third annual ACM Symposium on Theory of Computing. pp 151-158, 1971

atatinen Garey, M.R., Graham, R.L., and Ullman, J.D. Worst-case analysis of memory allocation algorithms. Proc Fourth Annual ACM Symposium on Theory of Computing, pp. 143-150, 1972.

qyang Hall, P., and Downling, G. Approximate String Matching. ACM Computing Surveys (12,4) pp 381-402, Dec 1980.

hgarg Quinn, M., and Deo, N. Parallel graph algorithms. ACM Computing Surveys, (16,3) pp 319-348. Sept 1984.

van Leeuwen, J., and Tarjan, R. Worst-case analysis of set union algorithms. J. ACM (31,2) ppp 245-281, April 1984

akorke Jacques Cohen: Garbage Collection of Linked Data Structures. Computing Surveys 13(3): 341-367 (1981)

Eddy, W. A new convex hull algorithm for planar sets. ACM Trans. Math. Softw. 3, pp 398-403, 1977.

R*

quadtrees

http://sunsite.ust.hk/dblp-cgi/title

Name	email	Paper
	shkrishn	Comer, D., The Ubiquitous B-Tree. Computing Suveys (11,2). June 1979. pp. 121-137
	bjenkins	Loui, R. P., Optimal Paths in Graphs with Stochastic or Multidimensional Weights. CACM. Sept 1983 (28,9) pp 670-676
	rui.wu@ummed.edu	Hopcroft, J. and Tarjan R. Efficient Planarity Testing. JACM (Oct 1974) 21,4 pp. 549-568
	lwang	Litke, J. D. An Improved Solution to the TSP with Thousands of Nodes. CACM (Dec 1984) 27,12. pp. 1227-1236.
	kparikh	Golden, B. A Statistical Approach to TSP. Networks, 7, pp. 209-225.
	rkothapa	Goodman, S.E., S.T. Hedetniemi. On Hamilitonian Walks in Graphs. SIAM J. of Computing. (Sept 1974), 3,3, pp. 214-221
	dwan	Balas, E. and Gang, S. Y. Finding a Maximum Clique in an Arbitrary Graph. SIAM J. of Computing (Nov 1986), 15, 4, pp. 1054-1068.
	lliu	Kubale, M., Boguslaw, J. A Generalized Implicit Enumeration Algorithm for Graph Coloring. CACM (April 1985), 28, 4,
	drey	Schaback, R., On the Expected Subliniearity of the Boyer-Moore Algorithm. SIAM J. of Computing 18(1989). pp 648-658
	sgangula	Apostolico, A., and Giancarlo, R. The Boyer Moore String Searching Strategies Revisited. SIAM J. of Computing (15,1), Feb 1986, pp. 98-105.
	crossano	Berglund, G.D., A Guided Tour of the Fast Fourier Transform. IEEE Spectrum (6) July 1969, pp. 41-52.
	agakis	Diaconis, P. Average Running Time of the Fast Fourier Transform. Algorithms. 1(1980), pp. 187-208.
	smohamme	Adelman, L, Pomerance, C., and Rumely, R. On distinguishing prime numbers from composite numbers. Annals of Mathematics. 117: 173-206, 1983
	avenkata	Beauchemin, P., Brassard, G., Crepeau, C, et al. The Generation of random numbers that are probably prime. J. of Cryptology, 1:53-64, 1988.
	feinbejm@tiac.com	Boyer, R.S., and Moore, J.S., A fast string-searching algorithm. CACM.20(10): 762-772, 1977.
	szaman	Diffie, W., and Hellman, M. New directions in cryptograph. IEEE Trans. on Information Theory. IT-22(6):644-654, 1976.
	sye	Dixon, J. Factorization and primality tests. American Mathematical Monthly. 91(6): 333-352, 1984
	wtang	Gabow, H., and Tarjan, R. A linear-time algorithm for a special case of disjoint set union. J. of computer and System Sciences, 30(2): 209-221, 1985.
	akoudsi	Graham, R.L., and Hell, P. On the History of the minimum spanning tree problem. Annals of the History of Computing, 7(1):43-57, 1985.

	byohgargnto	Huffman, D. A method for the construction of minimum-redundancy codes. Proc. of the IRE, 40(9):1098-1101, 1952
	upatel	Karmarkar, N. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-395, 1984
	rhegde	Rosengrantz, D.J., Stearns, R.E., Lewis, P.M., An analysis of several heuristics for the traveling salesman problem. SIAM J. of Computing, 6:563-581, 1977
	roger@primeon.com	Witten, I, and Cleary, J. Arithmetic coding for data compression. CACM (30,6): 520-541.
	tnadeau@cisco.com	Hanan Samet: Hierarchical Representations of Collections of Small Rectangles. Computing Surveys 20(4): 271-309(1988)
	himanshu.patel2@gte.net	Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573
	xy.yang@aspect.com	David Plainfossé, Marc Shapiro: A Survey of Distributed Garbage Collection Techniques. IWMM 1995: 211-249
	ylin	Chazelle, B, and Edelsbrunner, H. An optimal algorithm for intersecting line segments in the plane. Proc 29th Annual IEEE Symposium Foundations Computer Science. FOCS-88, pp. 590-600, 1988.
	hlee	Kirkpatrick, S. and Seidel, R. The ultimate planar convex hull algorithm? SIAM J. Computing 15, pp. 287-299, 1986.
	ntansala	Shamos, M, Hoey, D., Geometric intersection problems, Proc. 17th Ann. IEEE Symp. Foundations Comput. Sci. FOCS-76, pp. 208-215.
	kiran@comversens.com	Rytter, W. On the parallel computation of dynamic programming problems. Theoretical Computer Science. 59, pp. 297-307
	byoo	Cook, S. The complexity of theorem proving procedures. Proc of the third annual ACM Symposium on Theory of Computing. pp 151-158, 1971
	atatinen	Garey, M.R., Graham, R.L., and Ullman, J.D. Worst-case analysis of memory allocation algorithms. Proc Fourth Annual ACM Symposium on Theory of Computing, pp. 143-150, 1972.
	qyang	Hall, P., and Downling, G. Approximate String Matching. ACM Computing Surveys (12,4) pp 381-402, Dec 1980.
	hgarg	Quinn, M., and Deo, N. Parallel graph algorithms. ACM Computing Surveys, (16,3) pp 319-348. Sept 1984.
		van Leeuwen, J., and Tarjan, R. Worst-case analysis of set union algorithms. J. ACM (31,2) ppp 245-281, April 1984
	akorke	Jacques Cohen: Garbage Collection of Linked Data Structures. Computing Surveys 13(3): 341-367 (1981)
		Eddy, W. A new convex hull algorithm for planar sets. ACM Trans. Math. Softw. 3, pp 398-403, 1977.
		R*
		quadtrees
		http://sunsite.ust.hk/dblp-cgi/title