CaltechTHESIS
  A Caltech Library Service

Finite-difference algorithms for counting problems

Citation

Bax, Eric (1998) Finite-difference algorithms for counting problems. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-01182008-113319

Abstract

We present a novel method to construct counting algorithms:

1. Construct a generating function in which one type of terms corresponds to the objects to be counted.

2. Apply the proper finite-difference operators to produce a formula that counts the terms.

3. Choose finite-difference parameters to reduce the computation required to evaluate the formula.

We compare this finite-difference method to two other methods, the dynamic programming method and the inclusion and exclusion method. Using the problem of counting Hamiltonian paths as an example, we show that finite-difference algorithms require only polynomial space for problems for which dynamic programming algorithms require exponential space. Also, we show that finite-difference algorithms are a generalization of inclusion and exclusion algorithms. Finite-difference algorithms have some free parameters, and inclusion and exclusion algorithms correspond to a particular setting of those parameters. Using the 0-1 matrix permanent problem as an example, we show that the finite-difference parameters can be chosen to produce finite-difference algorithms that are faster than their inclusion and exclusion counterparts.

We use the problems of counting paths by length and counting independent path sets to illustrate how the flexibility of generating functions and extensions to finite-difference operators allow the development of finite-difference algorithms for problems beyond the realm of inclusion and exclusion. Furthermore, we use the problems of sequencing, bin packing, and deadlock avoidance to demonstrate the development of finite-difference algorithms for NP-complete and #P-complete problems.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Major Option:Computer Science
Thesis Availability:Restricted to Caltech community only
Thesis Committee:
  • Franklin, Joel N. (chair)
Defense Date:11 November 1997
Record Number:CaltechETD:etd-01182008-113319
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-01182008-113319
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:223
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:14 Feb 2008
Last Modified:26 Dec 2012 02:28

Thesis Files

[img] PDF (Bax_e_1998.pdf) - Final Version
Restricted to Caltech community only
See Usage Policy.

3811Kb

Repository Staff Only: item control page