The objective of this book is to study a broad variety of important and useful algorithms—methods for solving problems that are suited for computer implementations. Algorithms go hand in hand with data structures—schemes for organizing data. This chapter introduces the basic tools that we need to study algorithms and data structures.
- 1.1 Programming Model introduces our basic programming model. All of our programs are implemented using a small subset of the Java programming language plus a few of our own libraries for input and output.
- 1.2 Data Abstraction emphasizes data abstraction, where we define abstract data types (ADTs). We specify an applications programming interface (API) and then use the Java class mechanism to develop an implementation for use in client code.
- 1.3 Bags, Queues, and Stacks considers three fundamental ADTs: the bag, the queue, and the stack. We describe APIs and implementations using resizing arrays and linked lists.
- 1.4 Analysis of Algorithms describes our approach to analyzing algorithm performance. The basis of our approach is the scientific method: we develop hypotheses about performance, create mathematical models, and run experiments to test them.
- 1.5 Case Study: Union-Find is a case study where we consider solutions to a connectivity problem that uses algorithms and data structures that implement the classic union-find ADT.
Java programs in this chapter.Below is a list of Java programs in this chapter. Click on the program name to access the Java code; click on the reference number for a brief description; read the textbook for a full discussion.