This research involves foundational research on algorithms for NP- hard problems. The primary research area is DNA computing. A careful study of models and algorithms for DNA computation provides a basis for assessing whether DNA computing is viable. This research will provide new, massively parallel algorithms for NP- hard problems that may be useful on other computing models. Another contribution will be analysis of error-prone computation. Research will also be carried out in the area of approximation algorithms. The goal is to extend the range of applicability of the semidefinite programming relaxation method of Goemans and Williamson to an NP-hard timetabling problem that typically arises in high schools. The interactive activities to be undertaken include: teaching a senior-level undergraduate course in theoretical computer science, giving several research presentations in departmental seminars, doing collaborative research with faculty in Computer Science and Engineering and Molecular Biotechnology, and serving as an advisor for an NSF-funded project on development of mentor training packages.
