Events & News
Computer Science Colloquium
| Category | Lecture |
| Date | Thursday, February 7, 2008 |
| Time | 11:00 am |
| Location | GS 906 |
| Details | Light refreshments served in the 9th floor atrium at 10:45 AM. |
| Speaker | Jeffrey Shallit |
| Affiliation | University of Waterloo |
The Frobenius Problem and Its Generalizations
The classical but oddly little-known Frobenius problem from number theory is the following: Given a set of positive integers with greatest common divisor equal to 1, find the largest integer not representable as a non-negative integer linear combination of the set elements. This largest integer is called the Frobenius number. For example, the Frobenius number of 6, 9, and 20 is 43. In this talk I will survey some of the known results on this problem and its applications to computer science, and a new generalization of this problem to words (strings of symbols).