Algorithms & Java library
Explore the course algorithms, then go deeper with the supplied algs4 library. Original implementations and author comments are preserved; expanded guides are identified separately.
Binary search
Locate a key in a sorted array by halving the candidate interval.
Θ(log n) · Expanded guideBinary search timing experiment
Study logarithmic queries while separating preprocessing and I/O from the measured run.
Θ(log n) per query · Expanded guideDoubling-ratio experiment
Compare successive timings while repeatedly doubling the 3-SUM input size.
Θ(n³) per ThreeSum trial · Expanded guideDoubling test
Observe how the brute-force 3-SUM running time changes with input size.
Θ(n³) per ThreeSum trial · Expanded guideEuclidean algorithm
Find the greatest common divisor by repeatedly taking a remainder.
O(log min(p, q)) · Expanded guideFixed-capacity string stack
Use an array and an item count to implement the stack discipline.
Θ(1) valid push/pop · Expanded guideLinear search timing experiment
Scan for a key and inspect what the supplied timing wrapper actually measures.
Θ(n) per query · Expanded guideLinked queue
Enqueue at the tail and dequeue at the head for FIFO order.
Θ(1) enqueue/dequeue · Expanded guideLinked stack
Implement LIFO operations at the beginning of a linked list.
Θ(1) push/pop · Expanded guidePercolation · depth-first search
Mark open grid sites reachable from the top using the actual supplied recursive implementation.
Θ(n²) for an n × n grid · Expanded guideQuick-find
Maintain an eager component label for every object.
Union Θ(n) · Expanded guideQuick-union
Represent components as trees of parent pointers.
Θ(n) per find or union · Expanded guideResizing array queue
Store FIFO items in a circular buffer that grows as needed.
Θ(n) when resizing · Expanded guideResizing array stack
Combine a compact array representation with geometric capacity changes.
Θ(n) when resizing · Expanded guideStopwatch utility
Measure elapsed wall-clock time around an algorithm experiment.
Θ(1) per timing call in the unit-cost model · Expanded guide3-SUM · brute force
Count triples of indices whose integer values sum to zero.
Θ(n³) · Expanded guide3-SUM · binary-search approach
Combine sorting, pair enumeration and binary search to avoid the third linear loop.
O(n² log n) · Expanded guideWeighted union with path compression
Flatten visited paths while retaining size-based linking.
O(log n) for one operation · Expanded guideWeighted quick-union
Attach the smaller component beneath the larger one to limit tree height.
O(log n) per operation · Expanded guideInsertion sort
Grow a sorted prefix by inserting each next element into its position.
Θ(n²) · Expanded guideMerge sort
Recursively sort two halves and merge their ordered elements.
Θ(n log n) · Expanded guideQuicksort
Partition around a pivot, then recursively sort the two sides.
Θ(n²) · Expanded guideSelection sort
Repeatedly select the smallest item remaining in the unsorted suffix.
Θ(n²) · Expanded guideAverage
*************************************************************************** Compilation: javac Average.java Execution: java Average < data.txt Dependencies: StdIn.java StdOut.java Reads in a sequence of real nu
Course example · 57 lines