AHO, A.V., J. E. HOPCROFT, J. D. ULLMAN: Data Structures and Algorithms. Addison‐Wesley Amsterdam S. W. Issel · Search for more papers by this. Data Structures and Algorithms. 6. Recommended readings. Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft, Data Structures and. Algorithms, Addison Wesley. The authors' treatment of data structures in "Data Structures and Algorithms" is unified by an informal notion of "abstract data types," allowing readers to compare.
|Language:||English, Spanish, Dutch|
|ePub File Size:||27.40 MB|
|PDF File Size:||13.39 MB|
|Distribution:||Free* [*Regsitration Required]|
Alfred V. Aho, Bell Laboratories, Murray Hill, New. Jersey This book presents the data structures and algorithms that underpin much of today's computer. Design and Analysis of Computer Algorithms;. Addison-Wesley, Aho A.V.; Hopcroft J.E.; Ullman J.D.; Data. Structures and Algorithms. Computer Science homeworks / projects / backups. Contribute to sunnypatel/ Classwork development by creating an account on GitHub.
For example, we described the greedy graph coloring algorithm in terms such as "select some uncolored vertex. Share Give access Share full text access. We can use the theory of algorithms again to evaluate the goodness of the solution produced. Note that the assignment at line 1 uses an informal expression on the right. We are now confronted with the possibility that finding an optimal solution for the problem at hand is computationally very expensive.
Learn more. Volume 26 , Issue 4. Please check your email for instructions on resetting your password.
If you do not receive an email within 10 minutes, your email address may not be registered, and you may need to create a new Wiley Online Library account. If the address matches an existing account you will receive an email with instructions to retrieve your username. Biometrical Journal Volume 26, Issue 4. Issel Search for more papers by this author. First published: Tools Request permission Export citation Add to favorites Track citation.
Share Give access Share full text access. Share full text access. Please review our Terms and Conditions of Use and check box below to share full-text version of article. No abstract is available for this article.
Citing Literature Number of times cited according to CrossRef: The steps go from problem formulation and specification, to design of the solution, to implementation, testing and documentation, and finally to evaluation of the solution. This chapter outlines our approach to these steps. Subsequent chapters discuss the algorithms and data structures that are the building blocks of most computer programs.
Half the battle is knowing what problem to solve. When initially approached, most problems have no simple, precise specification. In fact, certain problems, such as creating a "gourmet" recipe or preserving world peace, may be impossible to formulate in terms that admit of a computer solution.
Even if we suspect our problem can be solved on a computer, there is usually considerable latitude in several problem parameters. Often it is only by experimentation that reasonable values for these parameters can be found. If certain aspects of a problem can be expressed in terms of a formal model, it is usually beneficial to do so, for once a problem is formalized, we can look for solutions in terms of a precise model and determine whether a program already exists to solve that problem.
Even if there is no existing program, at least we can discover what is known about this model and use the properties of the model to help construct a good solution. Almost any branch of mathematics or science can be called into service to help model some problem domain. Problems essentially numerical in nature can be modeled by such common mathematical concepts as simultaneous linear equations e. Symbol and text processing problems can be modeled by character strings and formal grammars.
Problems of this nature include compilation the translation of programs written in a programming language into machine language and information retrieval tasks such as recognizing particular words in lists of titles owned by a library.
Once we have a suitable mathematical model for our problem, we can attempt to find a solution in terms of that model. Our initial goal is to find a solution in the form of an algorithm, which is a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time.
An integer assignment statement such as x: In an algorithm instructions can be executed any number of times, provided the instructions themselves indicate the repetition. However, we require that, no matter what the input values may be, an algorithm terminate after executing a finite number of instructions. Thus, a program is an algorithm as long as it never enters an infinite loop on any input. There is one aspect of this definition of an algorithm that needs some clarification.
We said each instruction of an algorithm must have a "clear meaning" and must be executable with a "finite amount of effort. It is often difficult as well to prove that on any input, a sequence of instructions terminates, even if we understand clearly what each instruction means. By argument and counterargument, however, agreement can usually be reached as to whether a sequence of instructions constitutes an algorithm.
The burden of proof lies with the person claiming to have an algorithm. In Section 1. In addition to using Pascal programs as algorithms, we shall often present algorithms using a pseudo-language that is a combination of the constructs of a programming language together with informal English statements.
We shall use Pascal as the programming language, but almost any common programming language could be used in place of Pascal for the algorithms we shall discuss. The following example illustrates many of the steps in our approach to writing a computer program. Example 1. A mathematical model can be used to help design a traffic light for a complicated intersection of roads.
To construct the pattern of lights, we shall create a program that takes as input a set of permitted turns at an intersection continuing straight on a road is a "turn" and partitions this set into as few groups as possible such that all turns in a group are simultaneously permissible without collisions.
We shall then associate a phase of the traffic light with each group in the partition. By finding a partition with the smallest number of groups, we can construct a traffic light with the smallest number of phases.
For example, the intersection shown in Fig.
Roads C and E are oneway, the others two way. There are 13 turns one might make at this intersection. Some pairs of turns, like AB from A to B and EC , can be carried out simultaneously, while others, like AD and EB , cause lines of traffic to cross and therefore cannot be carried out simultaneously.
The light at the intersection must permit turns in such an order that AD and EB are never permitted at the same time, while the light might permit AB and EC to be made simultaneously. We can model this problem with a mathematical structure known as a graph. A graph consists of a set of points called vertices , and lines connecting the points, called edges.
For the traffic intersection problem we can draw a graph whose vertices represent turns and whose edges connect pairs of vertices whose turns cannot be performed simultaneously. For the intersection of Fig.
The graph can aid us in solving the traffic light design problem. A coloring of a graph is an assignment of a color to each vertex of the graph so that no two vertices connected by an edge have the same color.
It is not hard to see that our problem is one of coloring the graph of incompatible turns using as few colors as possible. The problem of coloring graphs has been studied for many decades, and the theory of algorithms tells us a lot about this problem.
Unfortunately, coloring an arbitrary graph with as few colors as possible is one of a large class of problems called "NP-complete problems," for which all known solutions are essentially of the type "try all possibilities.
With care, we can be a little speedier than this, but it is generally believed that no algorithm to solve this problem can be substantially more efficient than this most obvious approach. We are now confronted with the possibility that finding an optimal solution for the problem at hand is computationally very expensive.
We can adopt. If the graph is small, we might attempt to find an optimal solution exhaustively, trying all possibilities. This approach, however, becomes prohibitively expensive for large graphs, no matter how efficient we try to make the program. A second approach would be to look for additional information about the problem at hand. It may turn out that the graph has some special properties, which make it unnecessary to try all possibilities in finding an optimal solution.
The third approach is to change the problem a little and look for a good but not necessarily optimal solution. We might be happy with a solution that gets close to the minimum number of colors on small graphs, and works quickly, since most intersections are not even as complex as Fig. An algorithm that quickly produces good but not necessarily optimal solutions is called a heuristic.
One reasonable heuristic for graph coloring is the following "greedy" algorithm. Initially we try to color as many vertices as possible with the first color, then as many as possible of the uncolored vertices with the second color, and so on.
To color vertices with a new color, we perform the following steps. Select some uncolored vertex and color it with the new color.
Scan the list of uncolored vertices. For each uncolored vertex, determine whether it has an edge to any vertex already colored with the new color. If there is no such edge, color the present vertex with the new color. This approach is called "greedy" because it colors a vertex whenever it can, without considering the potential drawbacks inherent in making such a move.
There are situations where we could color more vertices with one color if we were less "greedy" and skipped some vertex we could legally color. For example, consider the graph of Fig. The greedy algorithm would tell us to color 1 and 2 red, assuming we considered vertices in numerical order.
As an example of the greedy approach applied to Fig. Similarly, we cannot color BD , DA , or DB blue because each of these vertices is connected by an edge to one or more vertices already colored blue.
However, we can color DC blue. Now we start a second color, say by coloring BC red. Each other uncolored vertex has an edge to a red vertex, so no other vertex can be colored red. These two may be colored with a fourth color, say yellow.
The colors are summarized in Fig.
The "extra" turns are determined by the greedy approach to be compatible with the turns already given that color, as well as with each other.
When the traffic light allows turns of one color, it can also allow the extra turns safely. The greedy approach does not always use the minimum possible number of colors. We can use the theory of algorithms again to evaluate the goodness of the solution produced.
In graph theory, a k-clique is a set of k vertices, every pair of which is connected by an edge. Obviously, k colors are needed to color a k -clique, since no two vertices in a clique may be given the same color. In the graph of Fig. Therefore, no coloring with three or fewer colors exists, and the solution of Fig. In terms of our original problem, no traffic light for the intersection of Fig. Therefore, consider a traffic light controller based on Fig.