- Adi Ben-Israel - RUTCOR, Rutgers (Discrete Optimization)
- Scott Decatur - DIMACS (Geometry and Protein-Folding)
- Sven Dickenson - Computer Science, Rutgers (Robotics)
- Mona Singh - DIMACS (Molecular Biology)
- Wilma Olson - Chemistry, Rutgers (Computational Chemistry/Biology)
- Charles Sims - Mathematics, Rutgers (Computational Group Theory)
- Andrew Ogielski - DIMACS and WINLAB, Rutgers (Wireless Networks Algorithms)
- Diane Souvaine - DIMACS and Computer Science, Rutgers (Computational Geometry Applied to Wireless Communications)

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.

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

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

The HP model abstracts the problem by first grouping the 20 amino acids which compose proteins into two classes: hydrophobic (or non-polar) residues and hydrophilic (or polar) residues. Three-dimensional space is commonly discretized in this model by embedding the protein in a regular lattice. The "native" fold for the protein is said to be the one which has largest number of pairwise contacts between hydrophobic residues. The biological foundation of this model is the belief that the first-order driving force of protein folding is due to a "hydrophobic collapse" in which those residues which prefer to be shielded from water (hydrophobic residues) are driven to the core of the protein, while those which interact more favorably with water (polar residues) remain on the outside of the protein.

This project will involve: (1) Approximation Algorithms (more theoretical than experimental): development of efficient algorithms which fold proteins such that the number of contacts is provably close to the protein's optimal number of contacts; AND/OR (2) Energy Surface Exploration (more experimental than theoretical): development of algorithms which examine the space of possible folds and the energy (i.e. number of contacts) of the folds in order to elucidate the pathways of protein folding.

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.

This project will approach the protein structure prediction problem using sequence-structure alignments. A sequence-structure alignment, also referred to as a threading, is sometimes used to predict the overall structure of a protein by aligning protein sequences onto 3D structures, using a pairwise energy potential. Although the general threading problem is NP-complete, in practice this approach is one of the more successful methods for 3D structure prediction. This project will be an experimental and/or theoretical study of algorithms for a simplified version of this problem.

Students should have a background in algorithms and programming experience in C.

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.

(1) A study of the structure of the largest finite group R which has exponent 5 and is generated by two elements. (R is known to have order 5^34.)

(2) A comparison of groups of exponent 5 with groups of exponent 6 in an effort to understand better why the Burnside problem with exponent 6 is easier than with exponent 5.

Due to high complexity of communications networks, studies of their behavior rely on extensive simulations. Good simulations require good approximate models of packet traffic. Many recent measurements showed that packet traffic has the characteristics of very bursty, self-similar (fractal) stochastic processes, for all kinds of data networks. This is very different from the well-studied voice traffic in the telephone networks.

This project will involve reviewing recent research literature on algorithmic techniques for generating bursty stochastic processes with long range dependence, formulating a traffic source model, and eventually implementing it in a C/C++ based description framework for parallel simulation. Basic knowledge of probability theory and stochastic processes is required. Some knowledge of data communications would be helpful, but is not required. Working knowledge of C or C++ is needed for model implementation, but the project will be successful if it delivers a well designed pseudocode instead of a running program.

At the beginning of the project we will need to research and discuss the various methods for performing fast ray-tracing, the data-structures involved, previous work in this area (like Fortune's and Rappaport's ray-tracing modeling systems for radio wave propagation prediction) and the potential for improving said methods and designs. Next we will need to design the system based upon our conclusions. Finally, the chosen algorithms will need to be coded, tested and verified.

The above paragraph only discusses the computational geometry aspect to this problem. There is the second issue which concerns how radio waves should be modeled in this domain. We will be relying upon domain experts and the literature for answers to most of these questions but the fact remains that we will have to mold the ray-tracing system to fit the needs of this radio wave propagation model. Where shortcuts can or should be taken, what information about the terrain will be necessary and what latest research can help improve this model, are all interesting questions. Some have been answered but many still remain.

Index of REU Program

DIMACS Home Page

Contacting the Center

Document last modified on October 29, 1998.