Combinatorial Algorithms

Author(s) : Jeff Erickson, University of Illinois, Urbana-Champaign
Publication Date : 2002
Free Licenses : Creative Commons License

Terms and Conditions:


Book excerpts:

These lecture notes is about algorithms, especially combinatorial algorithms. Put in its basic form, an algorithm is a set of simple, unambiguous, step-by-step instructions for accomplishing a specific task. Note that the word 'computer' doesn't appear anywhere in this definition; algorithms don't necessarily have anything to do with computers. True though, these notes focus (almost) exclusively on algorithms that can be reasonably implemented on a computer. In other words, each step in the algorithm must be something that either is directly supported by a programming language (arithmetic, assignments, loops, recursion, etc.) or is something that the reader already learned how to do in an earlier subjects (sorting, binary search, depth first search, etc.).

So what's a combinatorial algorithm? The distinction is fairly articial, but basically, this means something distinct from a numerical algorithm. Numerical algorithms are used to approximate computation with ideal real numbers on finite precision computers. The output of a numerical algorithm is necessarily an approximation to some ideal mathematical object. Any number that's close enough to the ideal answer is a correct answer. Combinatorial algorithms, on the other hand, manipulate discrete objects like arrays, lists, trees, and graphs that can be represented exactly on a digital computer.

These notes also shows how to prove an algorithm is correct on all possible inputs. Sometimes this is fairly obvious, especially for algorithms in earlier subjects. But many of the algorithms discussed in these notes will require some extra work to prove. This is where formal mathematical descriptions will come in handy. Inevitably, one must also takes into account how fast different algorithms run for the same problem. And in these notes, one will learn how to create algorithms that always run efficiently, even in the worst case. The goal is to help the reader in developing algorithmic intuition. How do various algorithms really work? When we see a problem for the first time, how should we attack it? How do we tell which techniques will work at all, and which ones will work best? How do we judge whether one algorithm is better than another? How do we tell if we have the best possible solution?

View/Download Combinatorial Algorithms