CS 666 Project
 
Fall 2018, Anna Lubiw, University of Waterloo
Due Date:
paper title by Monday November 12, 2013
presentation in early December
 
Your project is to read and present one paper in the area of Algorithms. It's best if you pick your own paper, but if you are stuck, a list of suggested papers is included below. Note that some of these papers are "classics" and some are quite recent and assume some sophisticated background.
 
The paper you choose must include some analysis, i.e. a paper with only heuristics and/or experimental results is not sufficient. (Such practical work can be extremely valuable, but is not appropriate for this course.) You may choose a paper that will be useful to you in your other graduate research, but you may not choose a paper that you have already studied.
 
Step 1 is to get your choice of paper approved. Send me email by Monday Nov. 12.
 
Step 2 is to present your paper to me. You may use slides or a black/white board. There will be 15 minutes for the presentation and 5 minutes for questions. You should summarize the results in the paper in your own words, and try to put the paper in context -- what came before and after. You are not responsible for following all the details of all the proofs, but should have a good overview.
 
Suggested papers:
 
data structures
V
Tarjan, Robert E., Caleb Levy, Stephen Timmel. 2018. Zip trees.
V
Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan, 2011, Rank-pairing heaps. SIAM J. Computing 40(6), 1463-1485.
V
Driscoll, J. R., Gabow, H. N., Shrairman, R., and Tarjan, R. E. 1988. Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31, 11 (Nov. 1988), 1343-1354.
V
Iacono, J. 2001. Alternatives to splay trees with O(log n) worst-case access times. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 516-522.
V
Demaine, Erik D. and Harmon, Dion and Iacono, John and Kane, Daniel and Patrascu, Mihai. 2009. The geometry of binary search trees. Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 496--505.
 
randomized algorithms
V
Cardoze, David E., and Schulman, Leonard J., 1998. Pattern matching for spatial point sets. 39th Annual Symposium on Foundations of Computer Science, 156-165.
V
Aragon, C.R.; Seidel, R.G. Randomized search trees. 30th Annual Symposium on Foundations of Computer Science, 1989. 540-545
V
Clarkson, K. L., Mehlhorn, K., and Seidel, R. 1993. Four results on randomized incremental constructions. Comput. Geom. Theory Appl. 3, 4 (Sep. 1993), 185-212.
V
Karloff, H. J. and Raghavan, P. 1993. Randomized algorithms and pseudorandom numbers. J. ACM 40, 3 (Jul. 1993), 454-476.
 
approximation algorithms
V
András Sebő, Jens Vygen. 2012. Shorter Tours by Nicer Ears. [improved approx for special case of metric TSP]
V
Blum, A., Jiang, T., Li, M., Tromp, J., and Yannakakis, M. 1994. Linear approximation of shortest superstrings. J. ACM 41, 4 (Jul. 1994), 630-647.
V
Arora, S. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5 (Sep. 1998), 753-782.
V
Richard M. Karp, Michael Luby and Neal Madras, Monte-Carlo approximation algorithms for enumeration problems, Journal of Algorithms, Volume 10, Issue 3, , September 1989, Pages 429-448.
 
others
V
Takehiro Ito, Erik D. Demaine, Nicholas J.A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno, On the complexity of reconfiguration problems. 2011. Theoretical Computer Science, 412(12–14), 1054-1065.
 
or see recent SODA papers:
 
or Tarjan's papers