USD SOLES BUILDING REOPENED

Mother Rosalie Hill Hall is operational
Generating Functions, Algorithms, and the Frobenius Problem

Generating Functions, Algorithms, and the Frobenius Problem

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.

Location

Serra Hall, Room 104B

5998 Alcala Park San Diego, CA 92110

Cost

0

Details

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

Post Contact

Amy Prout
aprout@sandiego.edu
619-260-4706

College of Arts and Sciences

Contact Us

Phone: (619) 260-4600
Fax: (619) 260-4162
casinfo@sandiego.edu

Visit Campus

Founders Hall
5998 Alcalá Park
San Diego, CA 92110

The Journey of a Changemaker starts here.