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. 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.- 4.1 Performance outlines a scientific method and powerful theory for understanding the performance and resource consumption of the program that we write.
- 4.2 Sorting and Searching describes two classical algorithms - mergesort and binary search - along with several applications where their efficiency plays a critical role.
- 4.3 Stacks and Queues introduces two closely related data structures for manipulating arbitrary large collections of data.
- 4.4 Symbol Tables considers a quintessential data structure known as the symbol table for storing information, and an efficient implementation known as the binary search tree.
- 4.5 Small World Phenomenon presents a case study to investigate the small world phenomenon - the principle that we are all linked by short chains of acquaintances.
Java programs in this chapter.
REF PROGRAM DESCRIPTION 4.1.1 ThreeSum.java count the number of triples whose sum is zero 4.1.2 DoublingTest.java analyze effect of doubling the problem size 4.2.1 TwentyQuestions.java apply binary search to play the game of twenty questions 4.2.2 Gaussian.java use bisection search to invert a function 4.2.3 BinarySearch.java search a sorted list using binary search 4.2.4 InsertionSort.java sort an array using insertion sort 4.2.5 MergeSort.java sort an array using mergesort 4.2.7 FrequencyCount.java tabulate word frequencies in a text corpus 4.2.8 LRS.java find the longest repeated substring 4.3.1 ArrayStackOfStrings.java stack of strings (using an array) 4.3.2 LinkedStackOfStrings.java stack of strings (using a linked list) 4.3.3 ArrayDoublingStackOfStrings.java stack of strings (using a doubling array) 4.3.4 Stack.java generic stack (using a linked list) 4.3.5 Evaluate.java evaluate arithmetic expressions 4.3.6 Queue.java generic queue (using a linked list) 4.3.7 MD1Queue.java simulate an M/D/1 queue 4.3.8 LoadBalance.java simulance process of assigning items to servers 4.4.1 Lookup.java lookup values in a database using a symbol table 4.4.2 Index.java create an index of a text corpus 4.4.3 BST.java symbol table (using a binary search tree) 4.5.1 Graph.java graph (using a symbol table of sets) 4.5.2 IndexGraph.java use a graph to invert an index 4.5.3 AllShortestPaths.java find the shortest path between all-pairs of vertices 4.5.4 PathFinder.java solve the single source shortest path problem 4.5.5 SmallWorldTest.java small-world phenomenon tester
Click on the program name to access the Java code; click on the reference number for a more detailed description.