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**: 30,582

**Type**: Book

**Publisher**:
n/a

**License**:
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

**Post time**: 08 Sep 2005 03:39:38

Combinatorial Algorithms

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

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.

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

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?

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?

Tweet

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.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors