# CS 5084: Introduction to Algorithms

## Required Text

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Introduction to Algorithms, Third Edition. MIT Press/McGraw-Hill Higher Education. 2009.
A very comprehensive book.
You may want to keep it for the future, as a reference.

The book covers nearly all the material taught in the course (and quite a lot that we do not get to). It is your main source for:
(i) small, but detailed, and completely worked out examples of the algorithms we discuss, and
(ii) some of the proofs we need --- both types of material are easier to grasp when read, rather than heard.

### Texts

#### Discrete Mathematics

D.L. Graham, D.E. Knuth, and O. Patashnik: Concrete Mathematics, A Foundation for Computer Science 2nd Edition, Addison-Wesley, 1995. ISBN: 0-201-55802-5.
A very good book on the mathematics needed to reason about algorithms and perform combinatorial analysis.

I have compiled a fairly elaborate collection of formulas, most of those I have used in my research. It is available at full list. There is also a small list, which may be used in closed-book tests.

#### Algorithms

Sara Baase, Allen Van Gelder: Computer Algorithms 3rd Edition, Addison-Wesley, 2000. ISBN: 0-201-61244-5.

Anany Levitin: Introduction to the Design and Analysis of Algorithms, 3rd Edition, Pearson, 2012. ISBN: 978-0-13-231681-1.

The last two are standard texts about algorithms, with somewhat different coverage and numerous exercises you should use for additional preparation.
Their choice was nearly arbitrary; I have a dozen more books which are in principle similar, and each has some topics it treats better than anybody else...

George Heineman, Gary pollice, Stanley Selkow: Algorithms in Nutshell, O'reilly, 2008. ISBN: 978-0-596-51624-6
This book was prepared by 3 faculty members of CS@WPI, it has a point of view which is very application-oriented, with much more empirical evidence than the main text. The code used in the book is available (for free) online.

Finally, the voice of the master: Donald Knuth is generally credited with having invented analysis of algorithms. He observed that the execution of an algorithm is a mathematical process that bears analysis. He has been distilling his knowledge of the field in a multivolume book; three have appeared, with a fourth coming currently out in sections, read about it in his web page: taocp. The approach of the book is in a sense similar to the course, in that the introduction of algorithms and their analysis go hand in hand, but his reach is vastly wider, and often deeper. This is not light reading, but Very Highly Recommended; if you intend to specialize in algorithmics, you could not spend too much time with these volumes. Here are the first three, and the first instalment of the fourth:

• Donald E. Knuth, The Art of Computer Programming, Vol. I: Fundamental Algorithms. 3rd Ed., Addison-Wesley, 1997.
• Donald E. Knuth, The Art of Computer Programming, Vol. II: Seminumerical Algorithms. 3rd Ed., Addison-Wesley, 1998
• Donald E. Knuth, The Art of Computer Programming, Vol. III: Sorting and Searching. 2nd Ed., Addison-Wesley, 1998.
• Donald E. Knuth, The Art of Computer Programming, Vol. IVa: Combinatorial Algorithms, Part 1. Addison-Wesley, 2011.

### Software

Most course material that I post online is rendered in portable data format (PDF) encodings.

You are presumably familiar with PDF files.

If you have a legitimate need I can also provide them as Postscript files.

The Handouts (see pointer on the left) are a variety of materials that have accumulated over several offerings of our algorithms courses, and which you may find useful. Please let me know if you find any problem using them.