1.2 Java as an Algorithm Language 3 techniques,tools and principles for analyzing algorithms and problems,and methods of proving correctness.We will present,study,and analyze algorithms to solve a variety of problems for which computer programs are frequently used.We will analyze the amount of time the algorithms take to execute,and we will also often analyze the amount of space used by the algorithms.In the course of describing algorithms for a variety of problems, we will see that several algorithm design techniques often prove uscful.Thus we will pause now and then to talk about some general techniques.such as divide-and-conquer,greedy algorithms,depth-first search,and dynamic programming.We will also study the com- putational complexity of the problems themselves.that is,the time and space inherently required to solve the problem no matter what algorithm is used.We will study the class of NP-complete problems-problems for which no efficient algorithms are known-and consider some heuristics for getting useful results.We will also describe an approach for solving these problems using DNA instead of electronic computers.Finally,we will intro- duce the subject of algorithms for parallel computers. In the following sections we outline the algorithm language,review some hackground and tools that will be used throughout the book,and illustrate the main concepts involved in analyzing an algorithm. 1.2 Java as an Algorithm Language We chose Java as the algorithm language for this book by balancing several criteria.The algorithms should be easy to read.We want to focus on the strategy and techniques of an al- gorithm,not declarations and syntax details of concern to a compiler.The language should support data ahstraction and prohlem decomposition,to make it easy to express algorithmic ideas clearly.The language should provide a practical pathway to implementation.It should be widely available and provide support for program development.Actually implementing and running algorithms can enhance the student's understanding greatly,and should not turn into a frustrating battle with the compiler and debugger.Finally,because this book is teaching algorithms,not a programming language,it should be reasonably easy to trans- late an algorithm to a varicty of languages that readers might wish to use,and specialized language features should be minimized. Java showed up well by several of our criteria,although we would not claim it is ideal.It supports data abstraction naturally.It is type-safe,meaning that objects of one type cannot be used in operations intended for a different type;arbitrary type conversions(called "casts")are not permitted,either.There is an explicit boolean type,so if one types (the assignment operator)when"=="(the equality operator)was intended,the compiler catches it. Java does not permit pointer manipulations,which are a frequent source of obscure errors;in fact,pointers are hidden from the programmer and handled automatically behind the scenes.At run time,Java checks for out-of-range array subscripts,and other incon- sistencies that might be other sources of obscure errors.It performs "garbage collection," which means that it recycles the storage space of ohjects that are no longer referenced;this takes a hig burden of space management off the programmer