DIMACS ,
the Center for Discrete Mathematics and Theoretical
Computer Science, conducts research, education and outreach
programs in discrete mathematics and theoretical computer science.
These areas are
the underlying models of much recent progress in digital computing,
optimization, communications, and increasingly in areas
such as molecular biology.
The advent of digital computing and communication has both enabled
scientific progress in many disciplines and become a grand challenge
for science in its own right.
This page introduces just 3 of DIMACS accomplishments.
The home page for DIMACS
gives a broad overview.
Molecular Biology Special Year
A special year program in
Mathematical Support for Molecular Biology
(1994-1996) is currently looking
at problems in molecular biology that can be addressed through discrete
models and computation. These problems include genome sequencing,
database methods, and phylogeny reconstruction, as well as applications to
protein folding, HIV analysis, and drug discovery. Sponsors include
AT&T Bell Laboratories,
Bellcore,
CDC,
DOE,
National Center for Human Genome Research,
National Institute of Allergy and Infectious Diseases,
NIH,
NSF,
NSA,
New Jersey Commission on Science and Technology,
Princeton University,
Roche Molecular Systems,
Rutgers University,
Sandia Labs.
Smith-Kline Beecham,
DIMACS is training 4
postdoctoral fellows
concentrating
on mathematical and computational problems arising from molecular biology;
conducted a 3 week program of tutorials to introduce fellows, graduate students
and researchers to this emerging research area;
is sponsoring 13
workshops
on topics ranging from determining family trees via genetic analysis (phylogeny)
to HIV sequence analysis;
and is sponsoring a series of 10
distinguished lecturers .
K-12 Education Programs
The Leadership Program in Discrete Mathematics has
directly trained over 330 teachers in the Northeast US in learning discrete
mathematics and adapting it to their classrooms.
Sponsors include DIMACS, Rutgers Center for Math, Science and Computer Education,
and NSF-EHR.
This program began with high school teachers in 1989, extended to middle school teachers in 1992 and will
initiate programs for elementary teachers in 1995.
Program goals include enabling the teachers to become mathematicians in their
own careers as well as introducing teachers and students to discrete mathematics
to prepare them for careers that apply this mathematics in computing,
communications and other new technologies.
Leadership program alumni have
incorporated discrete mathematics in their classrooms, have hosted
Workshops in Your District programs to reach an additional 300 teachers per year,
have led workshops for their teaching peers to reach over
10,000 teachers in the US.
Other impacts include a group of alumni who have developed a curriculum for
a discrete mathematics course that has been adopted for the New York City
curriculum; Greatest Hits in Discrete Mathematics, a book in preparation
of tested classroom
activities that were developed and written by alumni, a regular newsletter
reaching over 3000 teachers, and incorporating discrete mathematics in the
New Jersey Curriculum Framework,
a curriculum being developed by the NJ Math Coalition
and the NJ Dept. of Education, in cooperation with the NJ-SSI.
DIMACS Implementation Challenges: The Traveling Salesman Problem
In response to the need to bridge fundamental theoretical work in
algorithms and combinatorial optimization to implementations for practical use,
DIMACS has sponsored annual Implementation Challenges
on problems related to the Grand Challenges. Challenge topics have
been Network Flows and Matching (1990-91),
Clique, Coloring and Satisfiability (1992-93),
Parallel Algorithms for Tree Searching and for
Manipulating Sparse and Dynamic Graphs (1993-94), and currently
Two Problems in Computational Biology:
Fragment Assembly and Genome Rearrangements (1994-95).
In work that grew out of the 1992-93 challenge, Vasek Chvatal, William Cook
and Robert Bixby have made enormous strides on solving the
Traveling Salesman Problem, the best known NP-Complete problem
which seeks the shortest path to visit all the cities on a map.
They have set several international records for largest maps solved,
including: 3038 cities in 1992; 4461 cities in 1993; and 7397 cities in 1994.
Their work illustrates the doubled impact of combining basic mathematical research
on the combinatorial models of the problem with steady improvements in
implementations and access to faster computers.
