College of Computer & Information Science Fall 2006 Northeastern University Handout 2 CSU690: Algorithms and Data 15 September 2006

Books for Reference

The following is a list of books related to algorithms that may be useful for reference. This list, which was largely compiled by Prof. John Casey, contains both introductory texts as well as advanced books. Some of these books may be available on the reserve section at Snell.

Introductory books on algorithms

1. T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press/McGraw-Hill 1990.

Perhaps the most comprehensive textbook on algorithms. The style of coverage is formal. All of the topics covered in our course are also covered in this text. So it is a very useful reference for the course.

2. Steven Skiena. The Algorithm Design Manual. Springer-Verlag, 1998.

This text is an implementation-oriented study of algorithms. The book also lists a number of sources for good implementations of various algorithms. Also, the book has a CD-ROM full of code, plus practical advice on choosing algorithms for large-scale problems.

3. Gregory J. E. Rawlins. Compared to what?: An Introduction to the Analysis of Algorithms. Computer Science Press/W. H. Freeman, 1998.

This text is a friendly, undergraduate-oriented book. If the treatment of a topic in the course text doesn’t satisfy you, look here.

4. Sara Baase. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, 1988.

“General reference, although the exposition is sometimes terse or sketchy.” – Leonidas Guibas

5. Gilles Brassard and Paul Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.

“Good examples and problems. Focus on methods rather than specific problems.” – Leonidas Guibas

6. Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.

This is a good undergraduate-level textbook on algorithms.

7. Robert Sedgewick. Algorithms in C++. Volumes 1 and 2. Addison-Wesley, 1998.

This book is an in-depth coverage of algorithms from the point of view of a programmer. Volume 1 covers fundamentals, data structures, sorting, and searching. Volume 2 covers string algorithms, computational geometry, graph algorithms, and some advanced topics.

8. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

This book is somewhat outdated; it is still a useful book from a technical standpoint.

9. Donald E. Knuth. The Art of Computer Programming. Addison-Wesley, 1968-1974.

Encyclopaedic work in three volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, (3) Sorting and Searching. A fourth volume is in progress. Knuth had originally planned for seven volumes.

This set of books is one of the greatest collections in computer science.

10. Donald E. Knuth. The Stanford GraphBase. Addison Wesley, 1993.

This is a collection of data and actual C programs implementing a variety of graph and related algorithms. It is a useful companion to the portion of the course text devoted to graph algorithms.

11. Richard Neapolitan and Kumarss Naimipour. Foundations of Algorithms. Heath, 1996.

This book has an interesting approach, which minimizes the mathematical machinery used. If your math skills are rusty, Section 1.4 on “Order” is a good review.

12. Paul Purdom and Cynthia Brown. Analysis of Algorithms. CBS College Publishing.

This develops the mathematics needed for analysis.

13. Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran. Computer Algorithms in C++. Computer Science Press, 1997.

It covers data structures, dynamic programming, as well as branch-and-bound, randomized, and parallel algorithms.

14. Gaston Gonnet. Handbook of Algorithms and Data Structures, 1991.

This handbook has a large number of algorithms, with complete code in C and Pascal. It also has formulas for calculating performance, expectation, variance, and other probabilistic measures.

Basic Mathematics

1. Kenneth Rosen. Discrete Mathematics and its Applications. McGraw-Hill, 1998.

A standard textbook for discrete mathematics.

2. Judith Gersting. Mathematical Structures for Computer Science. W. H. Freeman & Co., 1998.

Chapter 2 of this text (Proofs, Recurrences, and Analysis of Algorithms) is a useful chapter to look at.

3. Ralph Grimaldi. Combinatorial and Discrete Mathematics: An Applied Introduction. Longman Publishing Group, 1994.

Another introductory book on discrete mathematics.

4. Donald E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, 1968.

This book covers a lot of the basic discrete mathematics that is useful throughout the course.

5. C. L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill, 1968.

This an old yet quite useful book on elementary descrete mathematics.

6. Tom Apostol. Calculus, Volume 1. Blaisdell, 1967.

This book provides a more thorough treatment than you probably had in your calculus textbooks.

7. Jim Pitman. Probability. Springer-Verlag, 1993.

This book is an excellent elementary introduction to probability theory.

8. Kai Lai Chung. Elementary Probability Theory with Stochastic Processes. Springer-Verlag, 1974. This is a readable and intuitive introduction to probability theory.

A few advanced books

1. Bernard M. E. Moret and Henry D. Shapiro. Algorithms from P to NP. Benjamin-Cummings, 1991. This book contains algorithms for the computationally hard problems, with practical advice on what happens on real machines.

2. Robert Sedgewick and Philippe Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, 1996. This book describes introductory as well as advanced techniques for analyzing algorithms.

3. Robert Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1983. This is an advanced book with succinct descriptions of lots of good ideas.

Other fun books

1. Ronald Graham, D. E. Knuth, and Mark Patashnik. Concrete Mathematics. Addison-Wesley, 1994. This is a fun book to read. It provides a number of techniques for summations and solving combinatorial problems. All of the text is flanked by funny (and often distracting) graffiti.

2. David Harel. Algorithmics: the Spirit of Computing. Addison-Wesley, 1992.

It’s just what the title claims. The book originated as a popular TV series.

3. Jon Bentley. Writing efficient programs (1982), Programming Pearls(1986), and More Programming Pearls (1988). Addison-Wesley. Jon Bentley, one of the leading authorities on programming, provides suggestions for improving the code you write.