The objective of this tutorial is to study a broad variety of important and useful algorithms—methods for solving problems that are suited for computer implementation. We shall deal with many different areas of app, always concentrating on fundamental algorithms that are important to know and interesting to study. We shall spend enough time on each algorithm to understand its essential characteristics and to respect its subtleties. Our goal is to learn well enough to be able to use and appreciate a large number of the most important algorithms used on computers today.
The strategy that we use for understanding the programs presented in this tutorial is to implement and test them, to experiment with their variants, to discuss their operation on small examples, and to try them out on larger examples similar to what we might encounter in practice. We shall use the Java coding language to describe the algorithms, thus providing useful implementations at the same time. Our programs have a uniform style that is amenable to translation into other modern coding languages as well.
We also pay careful attention to performance characteristics of our algorithms in order to help us develop improved versions, compare different algorithms for the same task, and predict or guarantee performance for large problems. Understanding how the algorithms perform might require experimentation or mathematical analysis or both. We consider detailed information for many of the most important algorithms, developing analytic results directly when feasible, or calling on results from the research literature when necessary.
To illustrate our general approach to developing algorithmic solutions, we consider in this chapter a detailed example comprising a number of algorithms that solve a particular problem. The problem that we consider is not a toy problem; it is a fundamental computational task, and the solution that we develop is of use in a variety of apps. We start with a simple solution, then seek to understand that solution's performance characteristics, which help us to see how to improve the algorithm. After a few iterations of this process, we come to an efficient and useful algorithm for solving the problem. This prototypical example sets the stage for our use of the same general methodology throughout the tutorial.
We conclude the chapter with a short discussion of the contents of the tutorial, including brief descriptions of what the major parts of the tutorial are and how they relate to one another.