1. Fundamentals
Overview.
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.
REF PROGRAM DESCRIPTION / JAVADOC - BinarySearch.java binary search - RandomSeq.java random numbers in a given range - Average.java average of a sequence of numbers - Cat.java concatenate files - Knuth.java Knuth shuffle - Counter.java counter - StaticSETofInts.java set of integers - Allowlist.java allowlist client - Vector.java Euclidean vector - Date.java date - Transaction.java transaction - Point2D.java point - RectHV.java axis-aligned rectangle - Interval1D.java 1d interval - Interval2D.java 2d interval - Accumulator.java running average and stddev 1.1 ResizingArrayStack.java LIFO stack (resizing array) 1.2 LinkedStack.java LIFO stack (linked list) - Stack.java LIFO stack - ResizingArrayQueue.java FIFO queue (resizing array) 1.3 LinkedQueue.java FIFO queue (linked list) - Queue.java FIFO queue - ResizingArrayBag.java multiset (resizing array) 1.4 LinkedBag.java multiset (linked list) - Bag.java multiset - Stopwatch.java timer (wall time) - StopwatchCPU.java timer (CPU time) - LinearRegression.java simple linear regression - ThreeSum.java brute-force three sum - ThreeSumFast.java faster three sum - DoublingTest.java doubling test - DoublingRatio.java doubling ratio - QuickFindUF.java quick find - QuickUnionUF.java quick union 1.5 WeightedQuickUnionUF.java weighted quick union - UF.java union-by-rank with path halving