Textbook and references
We use the following text:
Algorithm Design , by Jon Kleinberg and Eva Tardos,
Addison-Wesley, 2005 [text's website].
Apart from the above text, chapters 3 & 4 from CLRS (see below) and the notes posted in the handouts no other text
or set of notes is required for this course. Please note that using any other source apart from the
recommended texts (see below) requires you to contact the instructor in advance.
Related textbooks
Other WWW resources
Related textbooks
The above-mentioned texts + lecture notes are sufficient to master the
material of 3101. Below, I have compiled a list
of supplementary,
optional sources that students often find useful.
A somehow closely related to this course texts are the following:
How to think about algorithms , by Jeff Edmonds (being sold at York's bookstore).
Introduction to Algorithms (2nd edition) (aka CLRS), by Cormen, Leiserson, Rivest and
Stein, MIT Press.
If you want to focus more on the ideas (rather on the technical analysis part - essential to this course) then I would also
recommend the following (much more elementary) texts:
Algorithmics: The Spirit of Computing (3rd Edition), by D. Harel, Pearson Education.
Excellent introductory book. Not focused on analysis but without loosing (much of) mathematical clarity.
This book is very readable.
Algorithms, by R. Sedgewick, Addison-Wesley, 1988. This is an elementary book which
doesn't go into rigorous analysis. It has lots of examples and covers many topics. Sedgewick has also
published revisited versions of this book, coming under the titles "Algorithms in C", "Algorithms in
C++", "Algorithms in Java". Despite the titles the books focus on algorithms and not on the primitives
of the programming languages. The book also covers topics from data-structures (not covered in this
course).
We review the basic material needed from discrete math. You may also wish to check the following
(excellent) texts. I would strongly recommend especially Liu's book:
Introduction to Combinatorial Mathematics, by C.L. Liu, Mcgraw-Hill.
Concrete Mathematics: A Foundation for Computer Science (2nd Edition), by R.L. Graham, D.E. Knuth,
O. Patashnik, Addison-Wesley.
A more advanced (regarding mathematical analysis) text is the following. This book is more restricted
than our syllabus.
The Design and Analysis of Computer Algorithms, by A.V. Aho, J. E. Hopcroft, J.D. Ullman, Addison Wesley.
Here are two more classics. Though, the style and approach seems not to be that contemporary.
The Art of Computer Programming (3 volumes), by D.E. Knuth, Addison-Wesley.
Data Structures and Algorithms (3 volumes), by K. Melhorn, Springer-Verlag.
The following text is a very well-written introduction and in-depth (rigorous) treatment of
shortest-paths and network flows problems.
Network Flows: Theory, Algorithms, and Applications, by R.K. Ahuja, T.L. Magnanti, J.B.
Orlin, Prentice Hall.
An introductory text to combinatorial optimization with emphasis on Linear Programming (not considered in
this course). Despite this it contains a very accessible introduction to connections of Matroids and
greedy algorithm (chapter 12).
Combinatorial Optimization : Algorithms and Complexity, by C.H. Papadimitriou and K. Steiglitz, Dover
Publications.
We skim over intractable problems. To improve your understanding you may wish to check the following.
Introduction to the theory of computation, by M. Sipser, PWS Publishing. Introductory
and very readable text in complexity and computability. Relevant chapters: 3 & 7.
Computers and Intractability: A Guide to the Theory of NP-Completeness, by M.R. Garey and
D.D. Johnson, W.H. Freeman & Co.. This is a classical text in NP-completeness. It follows a very nice
systematic approach in proving NP-hardness results and also contains a list of NP-complete problems.
WWW resources
Jeff Edmonds's lecture slides.
Andranik Mirzaian's AAW - Algorithmics Animation
Workshop.
The following links mainly concern implementations of algorithms for quite interesting problems.
Valladolid problem set archive. This is an excellent
site with hund reds of problems. Implement your solution in C, C++, Java or Pascal and submit the source
code to be tested for efficiency. I strongly recommend this site.
ACM
Collegiate Programming
Contest official web-site.