Bookmark and Share

Department of

Mathematics and Computer Science

Title

Generating Functions, Algorithms, and the Frobenius Problem

Event Start DateMonday, February 6, 2012
Serra Hall, Room 104B
Event Start Time2:50 pm - 3:20 pm
CostCost: free
Message

Generating Functions, Algorithms, and the Frobenius ProblemPresented by Professor Kevin Woods, Oberlin College

Audience: Faculty

Abstract
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)?

ContactAmy Prout | aprout@sandiego.edu | 619-260-4706