Proposed projects for the 1998 DIMACS REU Program

Supervisors and Suggested Problems


Faculty Supervisors

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

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.

* (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 (Adi Ben-Israel)

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

This project studies some well-known iterative methods, including the Newton and Halley methods. Topics include:

  1. 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.
  2. Chaotic phenomena associated with iterative methods (see e.g. the project webpage Iterative Methods and Complex Dynamics).
  3. The order-of-convergence of the quasi-Halley method (proved to be at least 2.41, and observed to be close to 3).
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.

* 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 problem.

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 example, David Rosenberg's project.

* (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 project.

* 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