Readings

This list will be revised and annotated as the semester progresses to reflect, in particular, the topics and papers selected based on class discussions.

Assigned
1.
Sudarshan S. Chawathe. Capstone project proposals—suggestions for deeper explorations. Department of Computer Science, University of Maine. http://cs.umaine.edu/, February 2008.
2.
Bruce Barnett. Sed—an introduction and tutorial. http://www.grymoire.com/Unix/Sed.html, July 2008.
3.
Michael E. Lesk and Eric Schmidt. Lex—a lexical analyzer generator. In Andrew G. Hulme and M. Douglas McIlroy, editors, UNIX Vol. II: research system, pages 375–387. W. B. Saunders Company, Philadelphia, Pennsylvania, 10th edition, 1990.
4.
Stephen C. Johnson and Ravi Sethi. In Andrew G. Hulme and M. Douglas McIlroy, editors, UNIX Vol. II: research system, chapter Yacc: a parser generator, pages 347–374. W. B. Saunders Company, Philadelphia, Pennsylvania, 10th edition, 1990.
5.
Ken Thompson. Reflections on trusting trust. Communications of the ACM, 27(8):761–763, August 1984.
6.
Derrick Coetzee. An efficient implementation of Blum, Floyd, Pratt, Rivest, and Tarjan’s worst-case linear selection algorithm. http://moonflare.com/, January 2004.
7.
Jon Bentley. Little languages. Communications of the ACM, 29(8):711–721, August 1986.
8.
Rob Weir. Doing the Microsoft shuffle: Algorithm fail in browser ballot. http://www.robweir.com/, February 2010.
Others
1.
Jon L. Bentley and M. Douglas McIlroy. Engineering a sort function. Software–Practice and Experience, 23(11):1249–1265, November 1993.
2.
Timothy Furtak, José Nelson Amaral, and Robert Niewiadomski. Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms. In Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 348–357, San Diego, California, 2007.
3.
Derrick Coetzee. An efficient implementation of Blum, Floyd, Pratt, Rivest, and Tarjan’s worst-case linear selection algorithm. http://moonflare.com/, January 2004.
4.
Bingsheng He, Ke Yang, Rui Fang, Mian Lu, Naga K. Govindaraju, Qiong Luo, and Pedro V. Sander. Relational joins on graphics processors. In Proceedings of the 28th ACM International Conference on Management of Data (SIGMOD), Vancouver, Canada, June 2008.
5.
Naga K. Govindaraju, Jim Gray, Ritesh Kumar, and Dinesh Manocha. GPUTeraSort: High performance graphics coprocessor sorting for large database management. In Proceedings of the 26th ACM International Conference on Management of Data (SIGMOD), Chicago, Illinois, July 2006.
6.
Daniel Cederman and Philippas Tsigas. A practical quicksort algorithm for graphics processors. Technical Report 2008-01, Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, Göteborg, Sweden, 2008.
7.
Sang-Won Lee and Bongki Moon. Design of flash-based DBMS: an in-page logging approach. In Proceedings of the 27th ACM International Conference on Management of Data (SIGMOD), pages 55–66, Beijing, China, June 2007.
8.
Gilad Bracha. Generics in the Java programming language. Tutorial. http://java.sun.com/, July 2004.
9.
Mark C. Hamburg. Two tagless variations on the Deutsch-Schorr-Waite algorithm. Information Processing Letters, 22:179–183, 1986.
10.
Martin E. Hellman. An overview of public-key cryptography. IEEE Communications Magazine, 50(5):42–49, May 2002. Originally published in 16(6), November 1978.
11.
Jon Bentley and Don Knuth. Programming pearls: Literate programming. Communications of the ACM, 29(5):364–369, May 1986.
12.
Jon Bentley, Don Knuth, and Doug McIlroy. A literate program. Communications of the ACM, 29(6):471–483, June 1986.
13.
Paul E. Black. Dictionary of algorithms and data structures. http://www.nist.gov/dads/, September 1998.
14.
Nadathur Satish, Mark Harris, and Michael Garland. Designing efficient sorting algorithms for manycore GPUs. In Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1–10, Rome, Italy, May 2009.
15.
Lloyd Allison. Suffix trees. http://www.allisons.org/ll/AlgDS/Tree/Suffix/, 2008.