Bax, Eric (1998) Finite-difference algorithms for counting problems. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-01182008-113319
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|
|Defense Date:||11 November 1997|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||14 Feb 2008|
|Last Modified:||26 Dec 2012 02:28|
- Final Version
Restricted to Caltech community only
See Usage Policy.
Repository Staff Only: item control page