Generating Functions, Algorithms, and the Two Stamp Problem

Start: 12/02/2009 - 4:15pm
End  : 12/02/2009 - 5:15pm


Kevin Woods, Oberlin College


We'll start with the following question: \Given two denominations of stamps, a cents and b cents, what is the largest postal rate that we cannot pay exactly?" This is called the Frobenius problem with two generators. Using generating functions, we'll get a nice formula for the answer. Then we'll take a look at a wide variety of questions that we can answer using this same sort of generating function. In general, generating functions can often encode a seemingly complicated set (such as the set of postal rates that can be paid with a cent and b cent stamps) in a nice, compact form. Then we can use the generating functions to answer questions like \Is this set nonempty?" \What is its cardinality?" \What is its maximal element?" We'll build up a theory of what can be done with generating functions, and we will approach these problems from an algorithmic perspective: what can we do quickly (that is, in polynomial time)?

Millikan 134, Pomona College

Misc. Information

Refreshments will be served at 3:45 p.m. in the Harry Mullikin Room, Millikan 209

The dinner will be hosted by Prof. Francis Su. If interested in attending, please call
Ext. 73616