Adleman recently described how to solve a 7-node instance of the Hamiltonian Path Problem using tools from molecular biology (Science, November 1994). A major goal of subsequent research in this area is to understand how DNA computing can be used to solve NP-hard problems. Simple algorithms of Adleman and Lipton showed that 3Sat and 3-Coloring can be solved in principle, but since their algorithms are essentially exhaustive search, they can only be run on small instances and hence can never be practical. In this talk, we describe the pioneering work of Adleman and, subsequently, Lipton, on DNA computing. We then show how improved algorithms can be developed for the 3-Coloring and Independent Set problems. Our algorithms use only the DNA operations proposed by Adleman and Lipton, but combine them in more powerful ways, and use polynomial preprocessing on a standard computer to tailor them to the specific instance to be solved. Our results demonstrate that DNA computing can do much more than just exhaustive search. Further research in this direction will help determine whether or not DNA computing can be viable for NP-hard problems. We also present a probabilistic analysis of errors that arise in generating the solution space for DNA computation.