CMSI 282 References

CMSI 282 - References

Aho, Hopcroft, and Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Formal, early text on algorithm design and complexity, but still relevant (and still in print).

Bell. Board and Table Games from Many Civilizations. Dover Publications, 1979. Classic work on race games, war games, games of position, mancala games, dice games, dominoes.

Brams and Taylor. Fair Division- from Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996. Comprehensive treatment of cake-cutting, fair division, and dispute resolution, including their own discrete, envy-free procedure for arbitrary numbers of players, and interesting sections on auctions and elections.

Cohen. "Bioinformatics- An Introduction for Computer Scientists." Computing Surveys 36, 2, pp. 122-158. Typically excellent survey article with a comprehensive, annotated bibliography.

Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms (2nd edition). McGraw-Hill, 2001; first edition, 1990. Broad coverage includes mathematical techniques, sorting and order statistics, search trees, advanced data structures, dynamic vs. greedy programming, graphs, and computational geometry (among the topics that we will cover); plus linear programming, FFT's, and number-theoretic algorithms (among the topics that we will not cover). Every computer scientist should own this book.

Dasgupta, Papadimitriou, Vazirani. Algorithms. McGraw-Hill, 2008. Similar to Kleinberg and Tardos in its coverage, plus a fairly comprehensible final chapter on quantum algorithms.

de Berg, van Kreveld, Overmars, and Schwarzkopf. Computational Geometry- Algorithms and Applications (2nd edition). Springer-Verlag, 1998. Broad treatment of the subject, with algorithms chosen for clarity rather than optimality.

Flake. The Mathematical Beauty of Nature- Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation. MIT Press, 1998. Unusual blend of topics with good treatments of genetic algorithms, cellular automata, and decidability.

Gardner. aha! Insight. Scientific American, 1978; the sequel is aha! Gotcha. W. H. Freeman, 1982. Two books about puzzles and paradoxes of logic, combinatorics, procedures, etc., by the long-time editor of Scientific American's "Mathematical Games" section.

Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

Gonick and Wheelis. The Cartoon Guide to Genetics. HarperPerennial, 1991. Fine introduction to the subject, sprinkled throughout with Gonick's (un)usual brand of humor.

Graham, Knuth, and Patashnik. Concrete Mathematics- A Foundation for Computer Science. Addison-Wesley, 1989. More often used in courses on discrete mathematics, with chapters on sums, number theory, binomial coefficients, generating functions, discrete probability.

Gupta, Smolka, and Bhaskar. "On Randomization in Sequential and Distributed Algorithms." Computing Surveys 28, 1, pp. 7-86. Also available on the web- try Googling Gupta + randomization.

Gusfield. Algorithms on Strings, Trees, and Sequences- Computer Science and Computational Biology. Cambridge, 1997. Authoritative text on string processing, with extensive coverage of suffix trees.

Holland. "Genetic Algorithms." Scientific American, July, 1992.

Jones and Pevzner. An Introduction to Bioinformatics Algorithms. MIT Press, 2004.

Kemeny, Snell, and Thompson. Introduction to Finite Mathematics. Prentice-Hall, 1956. One of the first books on the application of finite mathematics to problems in the social sciences. It has reappeared in numerous revised editions. Similar, but harder to find, is Kemeny and Snell, Mathematical Models in the Social Sciences, Blaisdell, 1962, which cuts directly to the applications.

Kleinberg and Tardos. Algorithm Design. Addison-Wesley, 2006. Good general text, organized around paradigms, with stronger-than-usual emphases on graph and network problems, and intractability.

Knuth. The Art of Computer Programming- Volume Two: Seminumerical Algorithms. Addison-Wesley, 1969. Extensive coverage of random number generation and algorithms for arithmetic; included in this list primarily for its comprehensive discussion of computing x to the nth.

Knuth. The Art of Computer Programming- Volume Three: Sorting and Searching. Addison-Wesley, 1973.

Knuth. "Estimating the Efficiency of Backtrack Programs." In Selected Papers on Analysis of Algorithms. CSLI Publications, 2000.

Knuth. "Mathematical Analysis of Algorithms." In Selected Papers on Analysis of Algorithms. CSLI Publications, 2000.

Levitin. Introduction to the Design and Analysis of Algorithms (2nd edition). Addison-Wesley, 2007. The first edition was the required text for the 2004 version of the course.

Michalewicz and Fogel. How to Solve It: Modern Heuristics. Springer-Verlag, 2000. Interesting text emphasizing non-traditional paradigms, including evolutionary algorithms, neural networks, fuzzy systems, simulated annealing, etc.

Moret and Shapiro. Algorithms from P to NP- Volume One: Design and Efficiency. Benjamin/Cummings, 1991. Excellent text covering much of the material in this course. The implementation language is Pascal, which makes it very readable, if somewhat dated.

Nahin. Duelling Idiots and other Probability Puzzlers. Princeton, 2000. A fun book that poses several cute probability problems and then solves them both analytically and experimentally using randomized computer programs.

Nahin. Digital Dice: Computational Solutions to Practical Probability Problems. Princeton, 2008.

Parlett. The Oxford History of Board Games. Oxford University Press, 1999. An updated version of Bell (see above) with an interesting section on varieties of dice.

Reingold, Nievergelt, and Deo. Combinatorial Algorithms- Theory and Practice. Prentice-Hall, 1977. Outstanding text emphasizing combinatorial objects (representation, generation, counting); exhaustive search (backtracking, sieves); sorting; and graphs.

Resnick. Turtles, Termites and Traffic Jams- Explorations in Massively Parallel Microworlds. MIT Press, 1994.

Roberts. Applied Combinatorics. Prentice-Hall, 1984. Basically an expanded version of his own 1976 book, Discrete Mathematical Models- with Applications to Social, Biological, and Environmental Problems, . Four chapters on graph theory and applications, several more on combinatorial mathematics (generating functions, recurrence relations, theory of counting), etc.

Robertson and Webb. Cake-Cutting Algorithms- Be Fair If You Can. A K Peters, 1998. A very nice introduction to the subject of cake-cutting and fair division, striking just the right balance of rigor and readability.

Sedgewick. Algorithms in C- Part Five: Graph Algorithms. Addison-Wesley, 2001. The first edition (1983) was a single volume, and a fraction of that book was devoted to graphs. The present edition comprises three volumes, with the entire middle volume devoted to graphs. Also available in a Java edition.

Shasha. Puzzles for Programmers and Pros. Wiley, 2007.

Skiena. The Algorithm Design Manual. Telos/Springer-Verlag, 1998. This book includes a comprehensive catalog of combinatorial problems and algorithms, including where to find implementations (but use them at your own risk). This was the required text for the spring, 2005, version of the course.

Skiena. Calculated Bets- Computers, Gambling, and Mathematical Modeling to Win. Cambridge, 2001. The author of the preceding book uses Monte Carlo simulation to discover winning strategies for wagering at jai alai.

Steinhaus. Mathematical Snapshots. Dover republication of a book that appeared, in its original form, in 1964. It contains an early discussion of cake-cutting and fair division, by the originator of the problem.

Tucker. Applied Combinatorics (4th edition). Wiley, 2002. Topics are similar to Graham et al. This is the required text for MATH 366.

Vazirani. Approximation Algorithms. Springer-Verlag, 2003.

Return to: CMSI 282 home page
Revised: December 20, 2008