Citation
Bax, Eric (1998) Finitedifference algorithms for counting problems. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd01182008113319
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 finitedifference operators to produce a formula that counts the terms.
3. Choose finitedifference parameters to reduce the computation required to evaluate the formula.
We compare this finitedifference 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 finitedifference algorithms require only polynomial space for problems for which dynamic programming algorithms require exponential space. Also, we show that finitedifference algorithms are a generalization of inclusion and exclusion algorithms. Finitedifference algorithms have some free parameters, and inclusion and exclusion algorithms correspond to a particular setting of those parameters. Using the 01 matrix permanent problem as an example, we show that the finitedifference parameters can be chosen to produce finitedifference 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 finitedifference operators allow the development of finitedifference 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 finitedifference algorithms for NPcomplete and #Pcomplete 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: 

Defense Date:  11 November 1997 
Record Number:  CaltechETD:etd01182008113319 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd01182008113319 
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 ETDdb 
Deposited On:  14 Feb 2008 
Last Modified:  26 Dec 2012 02:28 
Thesis Files
PDF (Bax_e_1998.pdf)
 Final Version
Restricted to Caltech community only See Usage Policy. 3811Kb 
Repository Staff Only: item control page