Topic: Tournaments
July 19, 2001

REU Abstracts


Zdenek Dvorak, Charles University, Czech Republic


Jan Kara, Charles University, Czech Republic


Daniel Kral, Charles University, Czech Republic



Jeffry Kahn, Math (Faculty)

Ondvrej Pangrac, Charles University (Graduate/Postdoc)

Pattern Coloring of Cycle Systems

A t-cycle system is a system of cyclically ordered t-tuples of a finite set. A pattern is a sequence of letters. A coloring of a t-cycle system with respect to a set of patterns of length t is proper iff each cycle is colored consistently with one of the patterns, i.e. the same/distinct letters correspond to (the) same/distinct color(s).

For all combinations of P and k, we either find a polynomial algorithm or prove NP-completeness of the problem whether a given cycle system with a set of patterns P can be colored by at most k colors.


Ricardo Collado, University of Puerto Rico


Daniel Krasner, University of California, Berkeley, CA



Endre Boros, RUTCOR

Vladimir Gurvich, RUTCOR

Alexander Kelmans, University of Puerto Rico

On Convex Polytopes in the Plane "Containing" and "Avoiding" Zero


Dorea Claassen, University of Nebraska, Lincoln, NE



Dr. Wilma Olson, Chemistry

Dr. Ilya Muchnik, DIMACS

Convex Hull Analysis of Protein/DNA Complexes

With complete three-dimensional structural data it is possible to understand which amino acids in a protein lie along that protein's surface and how the surface of the protein is shaped. This, in turn, provides information about protein function as proteins usually interact with other molecules along their surfaces. Analysis of the surface can provide information about where the protein is most likely to form bonds with ligands and what sort of bonds it might form. However, If only the sequence of amino acids for a protein is known, it is difficult to say which amino acids will likely be on the surface of the protein, how that particular protein might interact, or functions that protein might perform in the cell. Our research seeks to develop models about protein/DNA interaction capable of predicting some of these characteristics based only on the protein's primary structure. We are developing our model using protein/DNA complexes for which complete structural data is already known. We will examine features of the protein structures as well as attributes of the DNA itself at the binding sites in terms of the primary structure of the protein in an attempt to develop predictive power about proteins for which structural data is not available.


Matthew Adereth, Carnegie Melon University, Pittsburgh, PA



Mahesh Viswanathan, DIMACS

Space-Efficient Algorithms for Streaming Data

When analyzing a large stream of data it is often impractical to store all of the input for later processing. To solve this problem, algorithms that process the data stream as it is received, called Streaming Algorithms, are used. I will be discussing techniques for analyzing lower bounds on the memory usage of these algorithms.

Page last updated July 18, 2001