DIMACS DCI '01
Topic: Tournaments
July 19, 2001

REU Abstracts


Students

Zdenek Dvorak, Charles University, Czech Republic

zdvorak@dimacs.rutgers.edu

Jan Kara, Charles University, Czech Republic

jkara@dimacs.rutgers.edu

Daniel Kral, Charles University, Czech Republic

dkral@dimacs.rutgers.edu

Mentors

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.



Students

Ricardo Collado, University of Puerto Rico

rcollado@dimacs.rutgers.edu

Daniel Krasner, University of California, Berkeley, CA

dkrasner@dimacs.rutgers.edu

Mentors

Endre Boros, RUTCOR

Vladimir Gurvich, RUTCOR

Alexander Kelmans, University of Puerto Rico


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




Students

Dorea Claassen, University of Nebraska, Lincoln, NE

dclaassen@dimacs.rutgers.edu

Mentors

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.



Students

Matthew Adereth, Carnegie Melon University, Pittsburgh, PA

madareth@dimacs.rutgers.edu

Mentors

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