CSCI 3104
Algorithms
Fall 1995

References

Textbook

Cormen, T.H., Leiserson, C. E., and Rivest, R. L. (1990). Introduction to Algorithms. The MIT Press. Cambridge, Massachusetts. London, England. QA76.6 .C662

Other books

Brassard, G. and Bratley, P. (1996). Fundamentals of Algorithmics. Prentice Hall, Englewood Cliffs, New Jersey. QA 9.58 .B73

Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison-Wesley. QA 76.9 .D35M36

Papadimitriou, C. H., and Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, Englewood Cliffs, New Jersey. QA 402.5 P37

Preparata, F. P., and Shamos, M. I. (1985). Computational Geometry: An Introduction. Springer Verlag.

Rawlins, G. J. E. (1992). Compared to What? An Introduction to the Analysis of Algorithms. Computer Science Press. QA 76.9 .A43R39 [Has a short section, about 10 pages, on cryptography.]

Russell, S. and Norvik, P. (1995). Artificial Intelligence: A Modern Approach. Prentice Hall, Englewood Cliffs, New Jersey. Q335 .R86

Tarjan, R. E. (1983). Data Structures and Network Algorithms. SIAM, Philadelphia, Pennsylvania.

Weiss, M. A. (1993). Data Structures and Algorithm Analysis in C++. Benjamin/Cummings. QA 76.73.C153W46

Other references

These are references that are either not mentioned in the textbook or else references that play a special role in the course. This is not meant to be a complete list in any sense nor will we necessarily cover all the topics represented here.

Cryptography

Bennett, C. H., Brassard, G. and Ekert, A. K. (1995). Quantum Cryptography. In: Scientific American Special Issue: The Computer in the 21st Century. 164-171. Originally published in the October 1992 issue.

Brassard, G. (1988). Modern Cryptology. A Tutorial. Lecture Notes in Computer Science, vol. 325. Springer Verlag. QA76.9 A25 B73 1988.

Brassard, G. (1994). Cryptology Column - Quantum computing: The end of classical cryptography? SIGACT News. December 1994. 15-21. [Quick introduction, nice brief example, and plenty of references.]

NP-completeness

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco. QA 76.6 .G35 [This is the "bible" on NP-completeness results. Subsequent results have been collected in a regular column by M. R. Garey in the Journal of Algorithms.]

Physics and Computation

Deutsch, D. Quantum-theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society, London. A400, 97-117.

Feynman, R. P. (1982). Simulating Physics with Computers. International Journal of Theoretical Physics, 21(6/7):467-488.

Feynman, R. P. (1985). QED: The strange theory of light and matter. Princeton University Press. [Notes from a series of four lectures to a lay audience about the quantum nature of light, "quantum electrodynamics (QED)." A very accessible introduction to the counterintuitive "quantum" nature of photons and electrons.]

Lemonick, M. D. (1991). How to go back in time. TIME, May 13, 1991. Page 74.

Linden, E. (1990). Can we really understand matter? TIME, April 16, 1990. Page 57.

Simon, D. R. (1994) On the power of quantum computation. 35th Annual IEEE Conference on Foundations of Computer Science. Santa Fe, New Mexico. November 1994.

Shor, P. (1994) Algorithms for quantum computation: discrete log and factoring. 35th Annual IEEE Conference on Foundations of Computer Science. Sanat Fe, New Mexico. November 1994.

Genetic algorithms and simulated annealing

Crutchfield, J. P., and Mitchell, M. (1994). The evolution of emergent computation. Santa Fe Institute Technical Report 94-03-012.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, Mass. QA402.5 .G635 1989.

Grefenstette, J. J. (1987). Incorporating problem-specific knowledge into genetic algorithms. In: Lawrence, D. (ed.). Genetic Algorithms and Simulated Annealing. Pitman Publishing, London. QA4025 .L393.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, Massachusetts. QA 402.5 .G635.

van Laarhoven, P. J. M. (1988). Theoretical and computational aspect of simulated annealing. Centrum voor Wiskunde en Informatica CWI Tracts, Amsterdam. QA 402.5 L322.