Combinatorial Algorithms

Combinatorial Algorithms

These lecture notes cover algorithms, especially combinatorial algorithms, with the main goal of creating correct and always-efficient ones.

Publication date: 31 Jan 2015

ISBN-10: n/a

ISBN-13: n/a

Paperback: 1250 pages

Views: 29,790

Type: Book

Publisher: n/a

License: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

Post time: 08 Sep 2005 03:39:38

Combinatorial Algorithms

Combinatorial Algorithms These lecture notes cover algorithms, especially combinatorial algorithms, with the main goal of creating correct and always-efficient ones.
Tag(s): Theory of Computation
Publication date: 31 Jan 2015
ISBN-10: n/a
ISBN-13: n/a
Paperback: 1250 pages
Views: 29,790
Document Type: Book
Publisher: n/a
License: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International
Post time: 08 Sep 2005 03:39:38
Summary/Excerpts of (and not a substitute for) the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International:
You are free to:

Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click here to read the full license.
Terms and Conditions:
Jeff Erickson wrote:Anything on this page may be freely downloaded, printed, copied, or distributed, either electronically or on paper. However, nothing on this page may be sold in any form for more than the actual cost of printing and/or reproduction.

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?
 




About The Author(s)


Jeff Erickson is a Professor and Associate Department Head in the Department of Computer Science at University of Illinois at Urbana-Champaign. His research focuses on computational topology, with an emphasis on algorithmic questions involving graphs embedded on surfaces.

Jeff Erickson

Jeff Erickson is a Professor and Associate Department Head in the Department of Computer Science at University of Illinois at Urbana-Champaign. His research focuses on computational topology, with an emphasis on algorithmic questions involving graphs embedded on surfaces.


Book Categories
Sponsors
Icons8, a free icon pack