Generating Functions, Algorithms, and the Frobenius Problem
This event occurred in the past
Date and Time
Monday, February 6, 2012 from 2:50 p.m. to 3:20 p.m.
Serra Hall, Room 104B
Generating Functions, Algorithms, and the Frobenius ProblemPresented by Professor 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 discuss at a variety of related questions and future research directions. 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 will approach these problems from an algorithmic perspective: what can we do "quickly" (that is, in polynomial time)?