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.


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