Meeting Agenda
Meeting Agenda 
"PROBLEMS THAT CONFOUND EVEN THE FASTEST COMPUTERS"
A talk by: DR. SYLVIA BOYD (BMath, C&O; MMath, C&O) Department of Computer Science University of Ottawa
THURSDAY, FEBRUARY 27, 1997 3:30 P.M. DC 1304
** Of special interest to students **Abstract:
Many practically important combinatorial optimization problems are known to belong to a class of problems called "NP-hard" which indicates that these problems are extremely difficult to solve, and that it is unlikely that efficient techniques for finding the optimal (i.e. the best) solution will ever be found. A classical example is the Travelling Salesperson Problem (TSP), which has applications in areas such as vehicle routing, printed circuit board production and robotics. Fortunately, the "NP-hardness" of these problems does not preclude the possibility of finding practical methods for dealing with particular large-scale instances of these problems when they are encountered in real world applications. Using the TSP as an example, we will give a "guided tour" of some of the different strategies and methods which have been used successfully to tackle such problems. tour" of some of the different strategies and methods which have been used successfully to tackle such problems.
Presented by the Women in Mathematics Committee
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF WATERLOO SEMINAR ACTIVITIES
SYMBOLIC COMPUTATION SEMINAR *Note Type of Seminar* - Thursday, February 20, 1997
Frederic Chyzak, INRIA (France), will speak on `` Non- commutative Groebner bases prove combinatorial identities''. TIME: 3:30-4:30 p.m. ROOM: DC 1304
ABSTRACT:
The algorithmic of definite hypergeometric summation has been a field of intensive research since it was initiated by Zeilberger at the beginning of the 1990's. In particular, several extensions of Gosper's algorithm for indefinite hypergeometric summation and Zeilberger's algorithm for the definite case are of large applicability for various models in combinatorics and in the theory of special functions. Theoretical algorithms to deal with the larger class of holonomic functions and sequences were known, including algorithms for summation and integration. However, this larger class had not received much attention since then. We build on the theory of holonomy and an extension of the theory of Groebner bases to give improved algorithms for the general case. Applications are the proof of identities and the calculation of closed forms, which we illustrate by nice combinatorial examples. This presentation is based on a joint work with Bruno Salvy.
Mathematics Faculty Lecture Series Winter 1997 Term Lecture
(This is the first of an ongoing series of special Faculty lectures, one to be held in the Fall term and one in the Winter term of each year)
TUESDAY, FEBRUARY 25, 1997 3:00 P.M. DC 1302 Title: Network Flows, Tree Decompositions, and Fast Parallel Computation Speaker: Prabhakar Ragde, Department of Computer Science, UW
Abstract: This talk, intended to be accessible to the non-specialist, will touch on aspects of algorithm design and analysis, combinatorial optimization, and graph theory. Network flows have a rich history within the fields of computer science, mathematics, engineering, and management sciences. I will introduce fast parallel algorithms and discuss why we are unlikely to find them for network flow problems. A natural question about flow "patterns" in a multiterminal network will lead us to a good characterization of such patterns. This characterization can be used to develop a fast parallel algorithm for network flow on restricted networks (those which have a "bounded-width tree decomposition"). This is joint work with Torben Hagerup, Jyrki Katajainen, and Naomi Nishimura. Reception to follow in DC 1301