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.)

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.

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