CS 573: Graduate Algorithms

This manuscript is a collection of class notes for the (no longer required graduate) course “473G/573 Graduate Algo- rithms” taught in the University of Illinois, Urbana-Champaign, in (1) Spring 2006, (2) Fall 07, (3) Fall 09, (4) Fall 10, (5) Fall 13, and (6) Fall 14.

Class notes for algorithms class are as common as mushrooms after a rain. I have no plan of publishing these class notes in any form except on the web. In particular, Jeff Erickson has class notes for 374/473 which are better written and cover some of the topics in this manuscript (but naturally, I prefer my exposition over his). 

My reasons in writing the class notes are to (i) avoid the use of a (prohibitly expensive) book in this class, (ii) cover some topics in a way that deviates from the standard exposition, and (iii) have a clear description of the material covered. In particular, as far as I know, no book covers all the topics discussed here. Also, this manuscript is available (on the web) in more convenient lecture notes form, where every lecture has its own chapter. 

Most of the topics covered are core topics that I believe every graduate student in computer science should know about. This includes NP-Completeness, dynamic programming, approximation algorithms, randomized algorithms and linear programming. Other topics on the other hand are more optional and are nice to know about. This includes topics like network flow, minimum-cost network flow, and union-find. Nevertheless, I strongly believe that knowing all these topics is useful for carrying out any worthwhile research in any subfield of computer science.