4.   Algorithms and Data Structures


Overview.

In this chapter we describe and implement some of the most important algorithms and data structures in use on computers today. (For a more in-depth treatment, we recommend the companion textbook Algorithms, 4th Edition.) We begin by considering a powerful framework for measuring and analyzing the efficiency of our programs. This enables us to compare algorithms and accurately predict performance. Next, we consider several novel algorithms for the classic problem of sorting. Then, we build the most important higher level data structures, including stacks, queues, and symbol tables.


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
4.1.2 DoublingTest.java validating a doubling hypothesis
4.2.2 Gaussian.java bisection search (function inversion)
4.2.4 Insertion.java insertion sort
4.2.6 Merge.java mergesort
4.2.8 LRS.java longest repeated substring
4.3.2 LinkedStackOfStrings.java stack of strings (linked list)
4.3.4 Stack.java stack data type
4.3.6 Queue.java queue data type
4.3.8 LoadBalance.java load balancing simulation
4.4.2 Index.java indexing
4.4.4 DeDup.java dedup filter
4.5.2 IndexGraph.java using a graph to invert an index
4.5.4 PathFinder.java shortest-paths implementation


Exercises.

Include a link.