DNA self-assembly is a methodology for the construction of molecular scale structures. In this method, artificially synthesized single stranded DNA self-assemble into DNA crossover molecules (tiles). These DNA tiles have sticky ends that preferentially match the sticky ends of certain other DNA tiles, facilitating the further assembly into tiling lattices. We discuss key theoretical and practical challenges of DNA self-assembly, as well as numerous potential applications. The self-assembly of large 2D lattices consisting of up to thousands of tiles have been recently demonstrated, and 3D DNA lattices may soon be feasible to construct. We describe various novel DNA tiles with properties that facilitate self-assembly and their visualization by imaging devices such as atomic force microscope. We discuss bounds on the speed and error rates of the various types of self-assembly reactions, as well as methods that may minimize errors in self-assembly. We briefly discuss the ongoing development of attachment chemistry from DNA lattices to various types of molecules, and consider application of DNA lattices (assuming the development of such appropriate attachment chemistry from DNA lattices to these objects) as a substrate for: (a) layout of molecular electronic circuit components, (b) surface chemistry, for example ultra compact annealing arrays, (c) molecular robotics; for manipulation of molecules using molecular motor devices. DNA self-assembly can, using only a small number of component tiles, provide arbitrarily complex assemblies. It can be used to execute computation, using tiles that specify individual steps of the computation. In this emerging new methodology for computation: -input is provided by sets of single stranded DNA that serve as nucleation sites for assemblies, and -output can be made by the ligation of reporter strands of DNA that run though the resulting assembly, and then released by denaturing. DNA self-assembly can be used to execute massively parallel computations at the molecular scale, with concurrent assemblies that may execute computations independently. Due to the very compact form of DNA molecules, the degree of parallelism (due to distinct tiling assemblies) may be up to 1015 to possibly 1018. We describe various DNA tiling assemblies that execute various basic computational tasks, such as sequences of arithmetic and logical computations executed in massively parallel fashion. We also consider extensions of these computational methods to 3D DNA tiling lattices and to assemblies that hold state.