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.
- Required:
-
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.
- Rob
Weir. Doing the Microsoft shuffle: Algorithm fail in browser ballot. http://www.robweir.com/,
February 2010.
- Recommended:
-
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.