Proposed projects for the 1998 DIMACS REU Program
Supervisors and Suggested Problems
The following faculty have
expressed interest in participating in the program in 1998-99.
(Other faculty and project areas may be added later.)
The suggested area of research appears in parentheses.
(Note: RUTCOR is the Rutgers Center for Operations Research.)
The following topics have been suggested by REU
research supervisors, and offer a range of both applied and
theoretical problems. The topics are of current interest to Computer
Scientists and Mathematicians, but can be understood in a short period
of time by a well-trained undergraduate. Supervisors may also be
willing to work on other topics, depending on the student's and their
* (Project 1) Decision-Making Under Uncertainty (Adi Ben-Israel)
In business, or in personal life, we are often required to make decisions
without having all the relevant information. Such information (e.g. the
local weather a week hence, or next-quarter earnings of IBM) may become
known only after the decision.
This project is a study of situations which can be modeled as multi-stage
decision processes, with uncertainty represented by random variables with
known distributions. At each stage a decision is made, then a random variable
is sampled, and the return (to the decision maker) depends on the decisions
and observed values at all stages. Examples are in finance (portfolio
selection), insurance (optimal coverage), production under price
uncertainty (e.g. agriculture), inventory control (optimal levels)
and artificial intelligence.
A good background for this project includes knowledge of probability and
linear algebra, and computational experience. Some exposure to optimization
methods such as linear or dynamic programming, as well as experience using
a language such as LISP or PROLOG would also be useful.
* (Project 2) Iterative Methods for Solving Nonlinear Equations
Nonlinear equations in one variable, f(x)=0, or systems of such
equations in several variables, are solved numerically by iterative
methods. Each iteration typically begins with an approximate solution,
produces a "better" approximation, or decides to stop (because the
current approximation is good enough, or it cannot be improved by the
This project studies some well-known iterative methods, including the Newton
and Halley methods. Topics include:
Knowledge of advanced calculus, complex variables, numerical analysis and
programming is desireable. The project involves numerical experiments, using
MATLAB or symbolic software (MATHEMATICA, MAPLE, etc) which the student should
be ready to learn in short order.
- Iterative methods obtained by applying Newton & Halley to modified
functions g(x):=h(x)f(x), or transformed variables g(u):=f(h(u)),
for suitable functions h designed to improve convergence.
- Chaotic phenomena associated with iterative methods (see e.g. the
project webpage Iterative
Methods and Complex Dynamics).
- The order-of-convergence of the quasi-Halley method (proved to be
at least 2.41, and observed to be close to 3).
* Algorithms for Network Visualization (Sandeep Bhatt)
Visual representations can give a quick and intuitive picture of the
dynamics of a large, complex system. Communication networks, for
example, are too large to visualize within a single screen. A better
method is to represent the network hierarchically and allow the user
to traverse the representation to view different parts of the system
at different levels of detail. During the course of a traversal the
user may change the representation. If the visualization system is
connected to a operational network, or a simulation of one, attributes
of the network traffic are also displayed on the screen.
This project will review research on algorithms for hierarchical
network representation, graph drawing and algorithm animation. The
student will work with a team implementing the hierarchical
visualization system. Knowledge of C/C++ is required.
* (Project 1) Mobile Robot Navigation (Sven Dickenson)
A key problem in mobile robotics is to find a way to program a mobile
robot (equipped with a camera) to visually navigate its environment,
i.e., visually determine its position (coordinates). A promising
approach is to have the robot first determine the optimal set of
visual landmarks for navigation, and then use these landmarks to
compute its position. The problem of finding the optimal set of
landmarks can be formulated as a graph coloring problem with special
constraints introduced by the nature of the problem. The goal of this
project is to design, implement, and/or test algorithms to solve this
In order to test both landmark acquisition and navigation algorithms,
an environment simulator is needed in which indoor environments with
different shapes, obstacles, and landmarks can be created. The
student's role in this project will be to design and implement (in
software) such an indoor environment simulator. This will not only
include exposure to computational geometry algorithms, but to computer
graphics techniques as well. Once the simulator is complete, the
student will test various landmark acquisition algorithms using the
simulator, and, if time permits, promising approaches will be tested
on a mobile robot operating in a mock-up nuclear reactor in Canada.
Students with an interest in graph theory and graph algorithms are
encouraged to apply. A background in algorithm design and programming
experience in C would be be very useful. In addition, the design of
the simulator offers interesting problems in computer graphics.
Note: This project will build upon previous projects. See, for
* (Project 2) To be announced soon! (Sven Dickenson)
* DNA Sequences and Three-dimensional Structure (Wilma Olson)
The DNA base sequence, once thought to be interesting only as a carrier
of the genetic blueprint, is now recognized as playing a structural role
in modulating the biological activity of genes. Through subtle
variations of bending and twisting at the level of neighboring base
pairs, the chemical sequence not only generates a higher-order folding
of the double helix itself but also produces structural motifs that
facilitate the specific binding of proteins and other ligands. The
consequent looping and twisting of the DNA assumes an important role in
various biological processes.
To understand how the genetic code is translated into three-dimensional
structures used in biological processes, our group is analyzing the
known geometry of DNA bases in chemical structures and developing
mathematical models to incorporate the sequence-dependent bending,
twisting, and translation of known fragments in DNA molecules of varying
lengths and chemical composition.
Note that this year's project will build on the successes of previous
students who worked with Prof. Olson on this project. See, for
example, Lynette Hock's
* Evolutionary Tree Reconstruction (Shibu Yooseph)
Evolutionary tree reconstruction is an integral part of
several scientific disciplines such as biology and historical
linguistics. It is an extremely difficult task for a variety of
computational, statistical, and scientific reasons.
Currently used methods have been shown to have problems in the
reconstruction of very large trees (especially those containing
significant amounts of divergence).
However, recent analytical and experimental studies have resulted
in new techniques like "Hybrid Methods", "Optimal Tree Refinement",
and "Divide-and-Conquer Techniques" to produce better estimates of
the true evolutionary tree. In this project, the
student will look for ways to improve these methods,
either making them more efficient, or by extending them to
be successful on a wider class of problems. The student will
also be invited to devise brand-new approaches for solving large
data sets with significant amounts of divergence.
This page last modified on April 3, 1998