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. doi:10.7907/fdc3-5s46. https://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.)) California Institute of Technology Computer Science Public (worldwide access) Franklin, Joel N. (chair) 11 November 1997 CaltechETD:etd-01182008-113319 https://resolver.caltech.edu/CaltechETD:etd-01182008-113319 10.7907/fdc3-5s46 No commercial reproduction, distribution, display or performance rights in this work are provided. 223 CaltechTHESIS Imported from ETD-db 14 Feb 2008 19 Apr 2021 22:29

## Thesis Files

 Preview
PDF (Bax_e_1998.pdf) - Final Version
See Usage Policy.

3MB

Repository Staff Only: item control page