# DIMACS 1996 REU Program

# Supervisors and Suggested Problems

## Faculty Supervisors

The following faculty have
expressed interest in participating in the program in 1996.
(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.)

- Adi Ben-Israel - RUTCOR, Rutgers (Discrete Optimization)
- Richard T. Bumby - Mathematics, Rutgers (Number Theory)
- Sven Dickinson - Computer Science, Rutgers (Robotics)
- Andras Hajnal - Mathematics, Rutgers (Combinatorics)
- Wilma Olson - Chemistry, Rutgers (Computational Chemistry/Biology)
- Charles Sims - Mathematics, Rutgers (Computational Group Theory)

## Suggested Projects

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
own interests.

### * Decision-Making under Uncertainty (Ben-Israel)

Many problems in finance, economics, and operations research
can be modeled as a multi-stage decision process. 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) and inventory (optimal
levels).
This project will focus on selected models for decision making,
introducing the student to modern optimization methods. 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.)

### * Square Roots Modulo a Prime (Bumby)

A square root of a number b modulo n is a solution x to the equation x^2 =
b (mod n). The basic problem is that of computing square roots when n is a
prime, a problem which goes back to the nineteenth century. For small
primes, one can solve the problem by exhaustive search; for example, 2 has
two square roots (mod 7), but 5 has none. Although there are several known
methods for finding such roots for large primes, the problem of finding a
process which is sure, fast, and elementary remains open. Some
algorithms that have been tried seem to have a fixed probability of
success, though there appears to be no systematic theory to explain this.
The goal of this project is to explore one or more
aspects of this problem, depending on the interest and
background of the student. One might look at the effectiveness
or complexity (number of operations) of competing methods,
the history of the problem and evolution of currently
known methods, or the application of square-root
methods to primality testing.

### * Mobile Robot Navigation (Dickinson)

A key open problem in mobile robotics is to find a way to program a
mobile robot to explore an environment and visually determine its
position (coordinates). A promising approach is to have the robot
first determine an optimal set of visual landmarks for navigation,
then use the landmarks to find its position. The problem of finding
the 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 problem (at least for simplified environments).
To test the algorithms, the student will first design and implement a
simulator to create artificial indoor environments with visual
landmarks. The student will then test various algorithms using the
simulator, and, if time allows, 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. This project has both theoretical and practical
components; background in algorithm design and some programming
experience in C would be useful. In addition, the design of the
simulator offers interesting problems in computer graphics.

### * Ramsey Theory (Hajnal)

A simple instance of Ramsey's classical theorem says that, for every
natural number k, there is a natural number n(k) such that every
graph with n or more vertices contains either a complete subgraph on
k vertices or a subgraph on k vertices with no edges. More
generally, Ramsey's theorem applies to partitions of the r-element
subsets of a given set X. A graph can be considered to be such a
partition in which X is the set of vertices and r = 2; the set of
pairs of vertices is partitioned into edges and non-edges. A subset
Y of X is called ''homogeneous'' for a partition if all
r-element subsets of Y belong to the same class of the partition.
The general theorem of Ramsey says that if X is large enough and the
number of classes in the partition is small enough then there are
large homogeneous subsets. A quantitative analysis of problems of
this kind leads to interesting results having applications in
geometry, number theory, and other branches of discrete mathematics.

### *DNA Sequences and Three-dimensional Structure (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.

### * Computational Group Theory (Sims)

Symbolic computation packages, such as Maple, Mathematica, or GAP, can
be used to gain insight into many open problems group theory. Many of
these problems are accessible to an undergraduate with a good
background in algebra. For example, a classic problem of Burnside is
to determine whether any finitely-generated group with finite exponent
n (x^n = 1 for all x in the group) is necessarily finite. This is
known to be true when n = 1, 2, 3, 4, or 6, and false for all large
odd n; the smallest open case is n = 5. In order to decide whether
the Burnside group with 2 generators and exponent 5 is finite, it is
useful to understand the structure of its largest finite quotient Q.
Although Q is extremely large (it is known to have order 5^34), some
of its proper subgroups are small enough that one can explore their
properties using tools available in GAP.

dimacs-www@dimacs.rutgers.edu
Document last modified on March 5, 1996.