# anany levitin design and analysis of algorithms free ebook download

Write down a recipe for cooking your favorite dish with the precision required by an algorithm. Design an algorithm for computing L ftJ for any positive integer n. Besides assignment and comparison, your algorithm may only use the four basic arithmetical operations. Find gcd , by applying Euclid's algorithm. What does Euclid's algorithm do for a pair of numbers in which the first number is smaller than the second one?

What is the largest number of times this can happen during the algorithm's execution on such an input? Euclid's algorithm, as presented in Euclid's treatise, uses subtractions rather than integer divisions. Write a pseudocode for this version of Eu- clid's algorithm. Euclid's game see [Bog] starts with two unequal positive numbers on the board.

Two players move in turn. On each move, a player has to write on the board a positive number equal to the difference oftwo numbers already on the board; this number must be new, i.

The player who cannot move loses the game. Should you choose to move first or second in this game? Look up a description of the extended Euclid's algorithm see, e. Locker doors There are n lockers in a hallway, numbered sequentially from 1 to n. Initially all the locker doors are closed. You make 11 passes by the lockers, each time starting with locker 1. For example, after the first pass every door is open; on the second pass you only toggle the even-numbered lockers 2, 4, After the last pass, which locker doors are open and which are closed?

How many of them are open? These solutions are not answers but specific instructions for getting answers. It is this emphasis on precisely defmed constructive procedures that makes computer science distinct from other disciplines. In particular, this distinguishes it from the- oretical mathematics whose practitioners are typically satisfied with just proving the existence of a solution to a problem and, possibly, investigating the solution's properties.

We now list and briefly discuss a sequence of steps one typically goes through in designing and analyzing an algorithm Figure 1. Understanding the Problem From a practical perspective, the frrst thing you need to do before designing an algorithm is to understand completely the problem given. Read the problem's description carefully and ask questions if you have any doubts about the problem, do a few small examples by hand, think about special cases, and ask questions again if needed.

There are a few types of problems that arise in computing applications quite often. We review them in the next section. If the problem in question is one of them, you might be able to use a known algorithm for solving it. Of course, it helps to understand how such an algorithm works and to know its strengths and r 10 Introduction Understand the problem Decide on: computational means, exact vs.

But often, you will not find a readily available algorithm and will have to design your own. The sequence of steps outlined in this section should help you in this exciting but not always easy task. An input to an algorithm specifies an of the problem the algorithm solves. It is very important to specify exactly the range of instances the algorithm needs to handle. As an example, recall the variations in the range of instances for the three greatest common divisor algorithms discussed in the previous section.

If you fail to do this, your algorithm may work correctly for a majority of inputs but crash on some "boundary" value. Do not skimp on this first step of the algorithmic problem-solving process; if you do, you will run the risk of unnecessary rework.

The vast majority of algorithms in use today are still destined to be programmed for a computer closely resembling the von Neumann machine-a computer architecture outlined by the prominent Hungarian-American mathematician John von Neumann , in collaboration with A. Burks and H. Goldstine, in The essence of this architecture is captured by the so-called random-access machine RAM.

Its central assumption is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called sequential algorithms. The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i. Algorithms that take advantage of this capability are called parallel algorithms. Still, studying the classic techniques for design and analysis of algorithms under the RAM model remains the cornerstone of algorithmics for the foreseeable future.

Should you worry about the speed and amount of memory of a computer at your disposal? If you are designing an algorithm as a scientific exercise, the answer is a qualified no. As you will see in Section 2. If you are designing an algorithm as a practical tool, the answer may depend on a problem you need to solve. Even "slow" computers of today are almost unimaginably fast. Consequently, in many situations, you need not worry about a computer being too slow for the task.

There are important problems, however, that are very complex by their nature, have to process huge volumes of data, or deal with applications where time is critical. In such situations, it is imperative to be aware of the speed and memory available on a particular computer system. Choosing between Exact and Approximate Problem Solving The next principal decision is to choose between solving the problem exactly or solving it approximately. In the former case, an algorithm is called an exact algo- rithm; in the latter case, an algorithm is called an approximation algorithm.

Why would one opt for an approximation algorithm? First, there are important prob- lems that simply cannot be solved exactly for most of their instances; examples include extracting square roots, solving nonlinear equations, and evaluating def- inite integrals. Second, available algorithms for solving a problem exactly can be unacceptably slow because of the problem's intrinsic complexity. Tbis happens, in particular, for many problems involving a very large number of choices; you will see examples of such difficult problems in Chapters 3, 11, and Third, an ap- proximation algorithm can be a part of a more sophisticated algorithm that solves a problem exactly.

But others are, in fact, predicated on ingenious data structures. In addition, some of the algorithm design techniques we shall discuss in Chapters 6 and 7 depend intimately on structuring or restructuring data specifying a problem's instance. In the new world of object- oriented programming, data structures remain crucially important for both design and analysis of algorithms.

We review basic data structures in Section 1. Algorithm Design Techniques Now, with all the components of the algorithmic problem solving in place, how do you design an algorithm to solve a given problem? This is the main question this book seeks to answer by teaching you several general design techniques.

What is an algorithm design technique? An algorithm design technique or "strategy" or "paradigm" is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing. Check this book's table of contents and you will see that a majority of its chapters are devoted to individual design techniques.

They distill a few key ideas that have proven to be useful in designing algorithms. Learning these techniques is of utmost importance for the following reasons. First, they provide guidance for designing algorithms for new problems, i.

Therefore-to use the language of a famous proverb-learning such techniques is akin to learning to fish as opposed to being given a fish caught by somebody else. It is not true, of course, that each of these general techniques will be necessarily applicable to every problem you may encounter.

But taken together, they do constitute a powerful collection of tools that you will find quite handy in your studies and work. Second, algorithms are the cornerstone of computer science. Every science is interested in classifying its principal subject, and computer science is no exception. Algorithm design techniques make it possible to classify algorithms according to an underlying design idea; therefore, they can serve as a natural way to both categorize and study algorithms.

Methods of Specifying an Algorithm Once you have designed an algorithm, you need to specify it in some fashion. In Section 1. These are the two options that are most widely used nowadays for specifying algorithms. Nevertheless, being able to do this is an important skill that you should strive to develop in the process of learning algorithms.

A pseudocode is a mixture of a natural language and programming language- like constructs. A pseudocode is usually more precise than a natural language, and its usage often yields more succinct algorithm descriptions. Surprisingly, computer scientists have never agreed on a single form of pseudocode, leaving textbook authors to design their own "dialects. This book's dialect was selected to cause minimal difficulty for a reader.

For the sake of simplicity, we omit declarations of variables and use indentation to show the scope of such statements as for, if, and while. In the earlier days of computing, the dominant vehicle for specifying algo- rithms was a flowchart, a method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm's steps. This representation technique has proved to be inconvenient for all but very simple algorithms; nowadays, it can be found only in old algorithm books.

The state of the art of computing has not yet reached a point where an algorithm's description-whether in a natural language or a pseudocode-can be fed into an electronic computer directly. Instead, it needs to be converted into a computer program written in a particular computer language. We can look at such a program as yet another way of specifying the algorithm, although it is preferable to consider it as the algorithm's implementation.

Proving an Algorithm's Correctness Once an algorithm has been specified, you have to prove its correctness. That is, you have to prove that the algorithm yields a required result for every legitimate input in a finite amount of time.

For some algorithms, a proof of correctness is quite easy; for others, it can be quite complex. A common technique for proving correctness is to use mathe- matical induction because an algorithm's iterations provide a natural sequence of steps needed for such proofs.

It might be worth mentioning that although tracing the algorithm's performance for a few specific inputs can be a very worthwhile activity, it cannot prove the algorithm's correctness conclusively. But in order to 14 Introduction show that an algorithm is incorrect, you need just one instance of its input for which the algorithm fails.

If the algorithm is found to be incorrect, you need to ei- ther redesign it under the same decisions regarding the data structures, the design technique, and so on, or, in a more dramatic reversal, to reconsider one or more of those decisions see Figure 1.

The notion of correctness for approximation algorithms is less straightforward than it is for exact algorithms. For an approximation algorithm, we usually would like to be able to show that the error produced by the algorithm does not exceed a predefined limit.

You can find examples of such investigations in Chapter Analyzing an Algorithm We usually want our algorithms to possess several qualities. After correctness, by far the most important is efficiency. In fact, there are two kinds of algorithm effi- ciency: time efficiency and space efficiency. A general framework and specific techniques for analyzing an algorithm's efficiency appear in Chapter 2. Another desirable characteristic of an algorithm is simplicity.

Unlike effi- ciency, which can be precisely defined and investigated with mathematical rigor, simplicity, like beauty, is to a considerable degree in the eye of the beholder. For example, most people would agree that Euclid's algorithm is simpler than the middle-school procedure for computing gcd m, n , but it is not clear whether Eu- clid's algorithm is simpler than the consecutive integer checking algorithm. Still, simplicity is an important algorithm characteristic to strive for.

Because sim- pler algorithms are easier to understand and easier to program; consequently, the resulting programs usually contain fewer bugs. There is also the undeniable aes- thetic appeal of simplicity. Sometimes simpler algorithms are also more efficient than more complicated alternatives. Unfortunately, it is not always true, in which case a judicious compromise needs to be made.

Yet another desirable characteristic of an algorithm is generality. There are, in fact, two issues here: generality of the problem the algorithm solves and the range of inputs it accepts. On the first issue, note that it is sometimes easier to design an algorithm for a problem posed in more general terms. Consider, for example, the problem of determining whether two integers are relatively prime, i.

It is easier to design an algorithm for a more general problem of computing the greatest common divisor of two integers and, to solve the former problem, check whether the gcd is 1 or not. There are situations, however, where designing a more general algorithm is unnecessary or difficult or even impossible. To give another example, the standard formula for roots of a quadratic equation cannot be generalized to handle polynomials of arbitrary degrees.

For exam- ple, excluding integers equal to 1 as possible inputs for a greatest common divisor algorithm would be quite unnatural. On the other hand, although the standard formula for the roots of a quadratic equation holds for complex coefficients, we would normally not implement it on this level of generality unless this capability is explicitly required. If you are not satisfied with the algorithm's efficiency, simplicity, or general- ity, you must return to the drawing board aud redesign the algorithm.

In fact, even if your evaluation is positive, it is still worth searching for other algorithmic solutions. Recall the three different algorithms in the previous section for com- puting the greatest common divisor; generally, you should not expect to get the best algorithm on the first try. At the very least, you should try to fine-tunc the algorithm you already have. For example, we made several improvements in our implementation of the sieve of Eratosthenes compared with its initial outline in Section 1.

Can you identify them? You will do well if you keep in mind the following observation of Antoine de Saint-Exupery, the French writer, pilot, and aircraft designer: "A designer knows he has arrived at perfection not when there is no longer anything to add, but when there is no longer anything to take away. Programming an algorithm presents both a peril and an opportunity. The peril lies in the possibility of making the transition from an algorithm to a pro- gram either incorrectly or very inefficiently.

Some influential computer scientists strongly believe that unless the correctness of a computer program is proven with full mathematical rigor, the program cannot be considered correct. They have de- veloped special techniques for doing such proofs see [Gri81] , but the power of these techniques of formal verification is limited so far to very small programs. As a practical matter, the validity of programs is still established by testing. Test- ing of computer programs is an art rather than a science, but that does not mean that there is nothing in it to learn.

Look up books devoted to testing and debug- ging; even more important, test and debug your program thoroughly whenever you implement an algorithm. Also note that throughout the book, we assume that inputs to algorithms fall within their specified ranges and hence require no verification. When implement- ing algorithms as programs to be used in actual applications, you should provide such verifications.

I found this call for design simplicity in an essay collection by Jon Bentley [BenOO]; the essays deal with a variety of issues in algorithm design and implementation, and arc justifiably titled Programming Pearls.

I I 1: i il 16 Introduction Of course, implementing an algorithm correctly is necessary but not sufficient: you would not like to diminish your algorithm's power by an inefficient implemen- tation. Modern compilers do provide a certain safety net in this regard, especially when they are used in their code optimization mode. Still, you need to be aware of such standard tricks as computing a loop's invariant an expression that does not change its value outside the loop, collecting common subexpressions, replac- ing expensive operations by cheap ones, and so on.

See [Ker99] and [BenOO] for a good discussion of code tuning and other issues related to algorithm program- ming. Typically, such improvements can speed up a program only by a constant factor, whereas a better algorithm can make a difference in running time by orders of magnitude. A working program provides an additional opportunity in allowing an em- pirical analysis of the underlying algorithm.

The analysis is based on timing the program on several inputs and then analyzing the results obtained. We discuss the advantages and disadvantages of this approach to analyzing algorithms in Sec- tion 2. In conclusion, let us emphasize again the main lesson of the process depicted in Figure 1. Even if you have been fortunate enough to get an algorithmic idea that seems perfect, you should still try to see whether it can he improved.

Actually, this is good news since it makes the ultimate result so much more enjoyable. Yes, I did think of naming this hook The Joy of Algorithms. On the other hand, how does one know when to stop? In the real world, more often than not the project's schedule or the patience of your boss will stop you. And so it should be: perfection is expensive and in fact not always called for.

Designing an algorithm is an engineering-like activity that calls for compromises among competing goals under the constraints of available resources, with the designer's time being one of the resources. In the academic world, the question leads to an interesting but usually difficult investigation of an algorithm's optimality. Actually, this question is not about the efficiency of an algorithm but about the complexity of the problem it solves: what is the minimum amount of effort any algorithm will need to exert to solve the problem in question?

For some problems, the answer to this question is known. For example, any algorithm that sorts an array by comparing values of its elements needs about n log 2 n comparisons for some arrays of size n see Section But for many seemingly easy problems, such as matrix multiplication, computer scientists do not yet have a final answer. Another important issue of algorithmic problem solving is the question of whether or not every problem can be solved by an algorithm. We are not talking here about problems that do not have a solution, such as finding real roots of E i l 1- j!

For such cases, an output indicating that the problem does not have a solution is all we can and should expect from an algorithm. Nor are we talking about ambiguously stated problems. Even some unambiguous problems that must have a simple yes or no answer are "undecidable," i.

An important example of such a problem appears in Section Fortunately, a vast majority of problems in practical computing can be solved by an algorithm. Before leaving this section, let us be sure that you do not have the mis- conception-possibly caused by the somewhat mechanical nature of the diagram of Figure 1. There is nothing further from the truth: inventing or discovering? This book is designed to convince you that this is the case. Old World puzzle A peasant finds himself on a riverbank with a wolf, a goat, and a head of cabbage.

He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item either the wolf, the goat, or the cabbage. In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Solve this problem for the peasant or prove it has no solution. Note: The peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage to help him solve the problem. And it goes without saying that the wolf is a protected species.

New World puzzle There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side.

It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them.

The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person's pace. For example, if person 1 and person 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge.

If person 4 returns the flashlight, a total of 20 minutes have passed and you have failed the mission. Note: According to a rumor on the Internet, interviewers at a well-known software company located near Seattle have given this problem to interviewees. Which of the following formulas can be considered an algorithm for comput- ing the area of a triangle whose side lengths are given positive numbers a, b, and c? You may assume the availability of the square root function sqrt x.

Describe the standard algorithm for finding the binary representation of a positive decimal integer a. Describe the algorithm used by your favorite ATM machine in dispensing cash. You may give your description in either English or a pseudocode, whichever you find more convenient.

Can the problem of computing the number n be solved exactly? How many instances does this problem have? Look up an algorithm for this problem on the World Wide Web. Give an example of a problem other than computing the greatest common divisor for which you know more than one algorithm. Which of them is simpler? Which is more efficient? Consider the following algorithm for finding the distance between the two closest elements in an array of numbers. If you need to, you may change the algorithm altogether; if not, improve the implementation given.

One of the most influential books on problem solving, titled How to Solve It [Pol57], was written by the Hungarian-American mathematician George Polya Polya summarized his ideas in a four-point summary. Find 1. What do they have in common? How are they different? By and large, interest has been driven either by the problem's practical importance or by some specific characteristics making the problem an interesting research subject; fortunately, these two motivating forces reinforce each other in most cases.

In this section, we take up the most important problem types: ill Sorting "' Searching " String processing " Graph problems " Combinatorial problems " Geometric problems "' Numerical problems These problems are used in subsequent chapters of the book to illustrate different algorithm design techniques and methods of algorithm analysis. Sorting The sorting problem asks us to rearrange the items of a given list in ascending order.

Of course, for this problem to be meaningful, the nature of the list items must allow such an ordering. Mathematicians would say that there must exist a relation of total ordering. As a practical matter, we usually need to sort lists of numbers, characters from an alphabet, character strings, and, most important, records similar to those maintained by schools about their students, libraries about their holdings, and companies about their employees.

In the case of records, we need to choose a piece of information to guide sorting. For example, we can choose to sort student records in alphabetical order of names or by student number or by student grade point average. Such a specially chosen piece of information is called a key. Computer scientists often talk about sorting a list of keys even when the list's items are not records but, say, just integers.

Why would we want a sorted list? Well, sorting makes many questions about the list easier to answer. The most important of them is searching: it is why dictionaries, telephone books, class lists, and so on are sorted. You will see other r. In a similar vein, sorting is used as an auxiliary step in several important algorithms in other areas, e. By now, computer scientists have discovered dozens of different sorting algo- rithms.

In fact, inventing a new sorting algorithm has been likened to designing the proverbial mousetrap. And I am happy to report that the hunt for a better sorting mousetrap continues. This perseverance is admirable in view of the fol- lowing facts. On the one hand, there are a few good sorting algorithms that sort an arbitrary array of size n using about n log 2 n comparisons.

On the other hand, no algorithm that sorts by key comparisons as opposed to, say, comparing small pieces of keys can do substantially better than that. There is a reason for this embarrassment of algorithmic riches in the land of sorting.

Although some algorithms are indeed better than others, there is no algorithm that would be the best solution in all situations. Some of the algorithms are simple but relatively slow while others are faster but more complex; some work better on randomly ordered inputs while others do better on almost sorted lists; some are suitable only for lists residing in the fast memory while others can be adapted for sorting large files stored on a disk; and so on.

Two properties of sorting algorithms deserve special mention. A sorting algo- rithm is called stable if it preserves the relative order of any two equal elements in its input. This property can be desirable if, for example, we have a list of students sorted alphabetically and we want to sort it according to student GPA: a stable algorithm will yield a list in which students with the same GPA will still be sorted alphabetically.

Generally speaking, algorithms that can exchange keys located far apart are not stable but they usually work faster; you will see how this general comment applies to important sorting algorithms later in the book. The second notable feature of a sorting algorithm is the amount of extra memory the algorithm requires. An algorithm is said to be in place if it does not require extra memory, except, possibly, for a few memory units.

There are important sorting algorithms that are in place and those that are not. Searching The searching problem deals with finding a given value, called a search key, in a given set or a multiset, which permits several elements to have the same value. There are plenty of searching algorithms to choose from.

They range from the straightforward sequential search to a spectacularly efficient but limited binary search and algorithms based on representing the underlying set in a different form more conducive to searching.

The latter algorithms are of particular importance for real-life applications because they are indispensable for storing and retrieving information from large databases.

Some algorithms work faster than others but require more memory; some are very fast but applicable only to sorted arrays; and so on. Unlike with sorting algorithms, there is no stability problem, but different issues arise. Specifically, in applica- tions where the underlying data may change frequently relative to the uumber of searches, searching has to be considered in conjunction with two other oper- ations: addition to and deletion from the data set of an item. In such situations, data structures and algorithms should be chosen to strike a balance among the requirements of each operation.

Also, organizing very large data sets for efficient searching poses special challenges with important implications for real-life appli- cations. String Processing In recent years, the rapid proliferation of applications dealing with nonnumerical data has intensified the interest of researchers and computing practitioners in string-handling algorithms.

A string is a sequence of characters from an alphabet. It should be pointed out, however, that string-processing algorithms have been important for computer science for a long time in conjunction with computer languages and compiling issues. One particular problem-that of searching for a given word in a text-has attracted special attention from researchers.

They call it string matching. Several algorithms that exploit the special nature of this type of searching have been invented. We introduce one very simple algorithm in Chapter 3, and discuss two algorithms based on a remarkable idea by R. Boyer and J. Moore in Chapter 7. Graph Problems One of the oldest and most interesting areas in algorithmics is graph algorithms.

Informally, a graph can be thought of as a collection of points called vertices, some of which are connected by line segments called edges. A more formal definition is given in the next section. Graphs are an interesting subject to study for both theoretical and practical reasons. Graphs can be used for modeling a wide variety of real-life applications, including transportation and communication networks, project scheduling, and games.

One interesting recent application is an estimation of the Web's diameter, which is the maximum number of links one needs to follow to reach one Web page from another by the most direct route between them 2 2.

This number, according to an estimate by a group of researchers at the University of Notre Dame [Alb99], is just Fortunately, these algorithms can be considered illustrations of general design techniques; accordingly, you will find them in corresponding chapters of the book. Some graph problems are computationally very hard; the most well-known examples are the traveling salesman problem and the graph-coloring problem. The traveling salesman problem TSP is the problem of finding the shortest tour through n cities that visits every city exactly once.

In addition to obvious applications involving route planning, it arises in such modern applications as circuit board and VLSI chip fabrication, X-ray chrystallography, and genetic engineering. The gmph-coloring problem asks us to assign the smallest number of colors to vertices of a graph so that no two adjacent vertices are the same color. This problem arises in several applications, such as event scheduling: if the events are represented by vertices that are connected by an edge if and only if the corresponding events cannot be scheduled in the same time, a solution to the graph-coloring problem yields an optimal schedule.

Combinatorial Problems From a more abstract perspective, the traveling salesman problem and the graph- coloring problem are examples of combinatorial problems.

Tbese are problems that ask explicitly or implicitly to find a combinatorial object-such as a permu- tation, a combination, or a subset-that satisfies certain constraints and has some desired property e.

Generally speaking, combinatorial problems are the most difficult problems in computing, from both the theoretical and practical standpoints. Their difficulty sterns from the following facts. First, the number of combinatorial objects typically grows extremely fast with a problem's size, reaching unimaginable magnitudes even for moderate-sized instances. Second, there are no known algorithms for solving most such problems exactly in an acceptable amount of time. Moreover, most computer scientists believe that such algorithms do not exist.

This conjecture has been neither proved nor disapproved, and it remains the most important unresolved issue in theoretical computer science. We discuss this topic in more detail in Section Some combinatorial problems can be solved by efficient algorithms, but they should be considered fortunate exceptions to the rule.

The shortest -path problem mentioned earlier is among such exceptions. Geometric Problems Geometric algorithms deal with geometric objects such as points, lines, and poly- gons. Ancient Greeks were very much interested in developing procedures they did not call them algorithms, of course for solving a variety of geometric problems, 1. Then, for about years, intense interest in geometric algorithms disappeared, to be resurrected in the age o computers-no more rulers and compasses, just bits, bytes, and good old hu- man ingenuity.

We will discuss algorithms for only two classic problems of computational geometry: the closest-pair problem and the convex-hull problem. The closest-pair problem is self-explanatory: given n points in the plane, find the closest pair among them. The convex-hull problem asks to find the smallest convex polygon that would include all the points of a given set.

If you are interested in other geometric algorithms, you will find a wealth of material in specialized monographs e. Numerical Problems Numerical problems, another large special area of applications, are problems that involve mathematical objects of continuous nature: solving equations and systems of equations, computing definite integrals, evaluating functions, and so on.

The majority of such mathematical problems can be solved only approximately. Another principal difficulty stems from the fact that such problems typically require manipulating real numbers, which can be represented in a computer only approximately.

Moreover, a large number of arithmetic operations performed on approximately represented numbers can lead to an accumulation of the round-off error to a point where it can drastically distort an output produced by a seemingly sound algorithm. Many sophisticated algoritluns have been developed over the years in this area, and they continue to play a critical role in many scientific and engineering applications. But in the last 25 years or so, the computing industry has shifted its focus to business applications.

These new applications require primarily algo- rithms for information storage, retrieval, transportation through networks, and presentation to users. As a result of this revolutionary change numerical analysis has lost its formerly dominating position in both industry and computer science programs.

Still, it is important for any computer-literate person to have at least a rudimentary idea about numerical algorithms. We discuss several classical numer- ical algorithms in Sections 6. Consider the algorithm for the sorting problem that sorts an array by counting, for each of its elements, the number of smaller elements and then uses this information to put the element in its appropriate position in the sorted array: 24 Introduction ALGORITHM ComparisonCountingSort A[O..

Apply this algorithm to sorting the list 60, 35, 81, 98, 14, Is this algorithm stable? Is it in place? Name the algorithms for the searching problem that you already know. Give a good succinct description of each algorithm in English.

If you know no such algorithms, use this opportunity to design one. Design a simple algorithm for the string-matching problem. Konigsberg bridges The Konigsberg bridge puzzle is universally accepted as the problem that gave birth to graph theory. It was solved by tbe great Swiss-born mathematician Leonhard Euler The problem asked whether one could, in a single stroll, cross all seven bridges of the city of Konigsberg exactly once and return to a starting point.

Following is a sketch of the river with its two islands and seven bridges: a. State the problem as a graph problem. Does this problem have a solution? If you believe it does, draw such a stroll; if you believe it does not, explain why and indicate the smallest number of new bridges that would be required to make such a stroll possible. II li! Icosian Game A century after Euler's discovery see Problem 4 , another famous puzzle-this one invented by the renown Irish mathematician Sir William Hamilton -was presented to the world under the name of the Icosian Game.

The game was played on a circular wooden board on which the following graph was carved: Find a Hamiltonian circuit-a path that visits all the graph's vertices exactly once before returning to the starting vertex-for this graph.

Consider the following problem: Design an algorithm to determine the best route for a subway passenger to take from one designated station to another in a well-developed subway system similar to those in such cities as Washington, D.

The problem's statement is somewhat vague, which is typical of real-life problems. In particular, what reasonable criterion can be used for defining the "best" route? How would you model this problem by a graph? Rephrase the traveling salesman problem in combinatorial object terms.

Rephrase the graph-coloring problem in combinatorial object terms. Consider the following map: i' , I 26 Introduction a. Explain how we can use the graph-coloring problem to color the map so that no two neighboring regions are colored the same. Use your answer to part a to color the map with the smallest number of colors. Design an algorithm for the following problem: Given a set of n points in the Cartesian plane, determine whether all of them lie on the same circumference.

Write a program that reads as its inputs the x, y coordinates of the endpoints of two line segments P 1 Q 1 and P 2 Q 2 and determines whether the segments have a common point. A data structure can be defined as a particular scheme of organizing related data items. The nature of the data items is dictated by a problem at hand; they can range from elementary data types e. There are a few data structures that have proved to be particularly important for computer algorithms.

Since you are undoubtedly familiar with most if not all of them, just a quick review is provided here. Linear Data Structures The two most important elementary data structures are the array and the linked list. A one-dimensional array is a sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of the array's index Figure 1.

In the majority of cases, the index is an integer either between 0 and n - 1 as shown in Figure 1. Some computer languages allow an array index to range between any two integer bounds low and high, and some even permit nonnumerical indices to specify, for example, data items corresponding to the 12 months of the year by the month names. This feature positively distinguishes arrays from linked lists see below.

It is also assumed that every element of an array occupies the same amount of computer storage. Arrays are used for implementing a variety of other data structures. Promi- nent among them is the string, a sequence of characters from an alphabet termi- nated by a special character indicating the string's end.

Strings composed of zeros and ones are called binary strings or bit strings. Strings are indispensable for pro- cessing textual data, defining computer languages and compiling programs written in them, and studying abstract computational models. Operations we usually per- form on strings differ from those we typically perform on other arrays say, arrays of numbers. They include computing the string length, comparing two strings to determine which one precedes the other according to the so-called lexicographic order, i.

A linked list is a sequence of zero or more elements called nodes each containing two kinds of information: some data and one or more links called pointers to other nodes of the linked list.

A special pointer called "null" is used to indicate the absence of a node's successor. In a singly linked list, each node except the last one contains a single pointer to the next element Figure 1. To access a particular node of a linked list, we start with the list's first node and traverse the pointer chain until the particular node is reached. Thus, the time needed to access an element of a singly linked list, unlike that of an array, depends on where in the list the element is located.

On the positive side, linked lists do not require any preliminary reservation of the computer memory, and insertions and deletions can be made quite efficiently in a linked list by reconnecting a few appropriate pointers.

We can exploit flexibility of the linked list structure in a variety of ways. For example, it is often convenient to start a linked list with a special node called the header.

This node often contains information about the linked list such as its current length; it may also contain, in addition to a pointer to the first element, a pointer to the linked list's last element. Another extension is the structure called the doubly linked list, in which every node, except the first and the last, contains pointers to both its successor and its predecessor Figure 1.

The array and linked list are two principal choices in representing a more abstract data structure called a linear list or simply a list. The basic operations performed on this data structure are searching for, inserting, and deleting an element. Two special types of lists, stacks and queues, are particularly important.

A stack is a list in which insertions and deletions can be done only at the end. This end is called the top because a stack is usually visualized not horizontally but vertically akin to a stack of plates whose "operations" it mimics very closely. As a result, when elements are added to pushed onto a stack and deleted from popped off it, the structure operates in the "last-in-first-out" LIFO fashion, exactly as the stack of plates does if we can remove only the top plate or add another plate to top of the stack.

Stacks have a multitude of applications; in particular, they are indispensable for implementing recursive algorithms. A queue, on the other hand, is a list from which elements are deleted from one end of the structure, called the front this operation is called dequeue , and new elements are added to the other end, called the rear this operation is called enqueue. Consequently, a queue operates in the "first -in-first-out" FIFO fashion akin, say, to a queue of customers served by a single teller in a bank.

Queues also have many important applications, including several algorithms for graph problems. Many important applications require selection of an item of the highest prior- ity among a dynamically changing set of candidates. A data structure that seeks to satisfy the needs of such applications is called a priority queue. A priority queue is a collection of data items from a totally ordered universe most often, inte- ger or real numbers.

The principal operations on a priority queue are finding its largest element, deleting its largest element, and adding a new element. Of course, a priority queue must be implemented so that the last two operations yield an- other priority queue. Straightforward implementations of this data structure can be based on either an array or a sorted array, but neither of these options yields the most efficient solution possible.

A better implementation of a priority queue is based on an ingenious data structure called the heap. We discuss heaps and an important sorting algorithm based on them in Section 6.

Graphs As mentioned in the previous section, a graph is informally thought of as a collec- tion of points in the plane called "vertices" or "nodes," some of them connected by line segments called "edges" or "arcs. We call the vertices u and v endpoints of the edge u, v and say that u and v are incident to this edge; we also say that the edge u, v is incedent to its endpoints u and v. A graph G is called undirected if every edge in it is undirected. If a pair of vertices u, v is not the same as the pair v, u , we say that the edge u, v is directed from the vertex u, called the edge's tail, to the vertex v, called the edge's head.

We also say that the edge u, v leaves u and enters v. A graph whose every edge is directed is called directed. Directed graphs are also called digraphs. It is normally convenient to label vertices of a graph or a digraph with letters, integer numbers, or, if an application calls for it, character strings Figure 1. The graph in Figure 1. The digraph in Figure 1.

Our definition of a graph does not forbid loops, or edges connecting vertices to themselves. Unless explicitly stated otherwise, we will consider graphs without loops. We get the largest number of edges in a graph if there is an edge connecting each of its 1 V 1 vertices with all IV I - 1 other vertices. A graph with every pair of its vertices connected by an edge is called complete.

Whether we are dealing with a dense or sparse graph may influence how we choose to represent the graph and, consequently, the running time of an algorithm being designed or used. Graph representations Graphs for computer algorithms can be represented in two principal ways: the adjacency matrix and adjacency lists.

The adjacency matrix of a graph with n vertices is an n-by-n boolean matrix with one row and one column for each of the graph's vertices, in which the element in the ith row and the jth column is equal to 1 if there is an edge from the ith vertex to the jth vertex, and equal to 0 if there is no such edge. For example, the adjacency matrix for the graph in Figure 1. Note that the adjacency matrix of an undirected graph is always symmetric, i.

In general, which of the two representations is more convenient depends on the nature of the problem, on the algorithm used for solving it, and, possibly, on the type of input graph sparse or dense. Weighted graphs A weighted graph or weighted digraph is a graph or digraph with numbers assigned to its edges. These numbers are called weights or costs. An interest in such graphs is motivated by numerous real-life applications, such as finding the shortest path between two points in a transportation or communication network or the traveling salesman problem mentioned earlier.

Both principal representations of a graph can be easily adopted to accommo- date weighted graphs. If a weighted graph is represented by its adjacency matrix, then its element A[i, j] will simply contain the weight of the edge from the ith to the jth vertex if there is such an edge and a special symbol, e. Such a matrix is called the weight matrix or cost matrix. This approach is illustrated in Figure l. For some applications, it is more convenient to put O's on the main diagonal of the adjacency matrix.

Adjacency lists for a weighted graph have to include in their nodes not only the name of an adjacent vertex but also the weight of the corresponding edge Figure 1. Paths and cycles Among many interesting properties of graphs, two are impor- tant for a great number of applications: connectivity and acyclicity. Both are based on the notion of a path.

A path from vertex u to vertex v of a graph G can be de- tined as a sequence of adjacent connected by an edge vertices that starts with u and ends with v. If all vertices of a path are distinct, the path is said to be simple. The length of a path is the total number of vertices in a vertex sequence defining the path minus one, which is the same as the number of edges in the path.

For ex- ample, a, c, b, f is a simple path oflength 3 from a to fin the graph of Figure 1. In the case of a directed graph, we are usually interested in directed paths. A directed path is a sequence of vertices in which every consecutive pair of the vertices is connected by an edge directed from the vertex listed first to the vertex listed next. For example, a, c, e, f is a directed path from a to fin the graph of Figure 1. A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v.

Informally, this property means that if we make a model of a connected graph by connecting some balls representing the graph's vertices with strings representing the edges, it will be a single piece.

If a graph is not connected, such a model will consist of several connected pieces that are called connected components of the graph. For example, the graphs of Figures 1. Sa are connected, while the graph in Figure 1.

Graphs with several connected components do happen in real-life applica- tions. A graph representing the Interstate highway system of the United States would be an example why? It is important to know for many applications whether or not a graph under consideration has cycles. A cycle is a path of a positive length that starts and ends at the same vertex and does not traverse the same edge more than once. For example, j, h, i, g,. A graph with no cycles is said to be acyclic.

We discuss acyclic graphs in the next subsection. Trees A tree more accurately, afree tree is a connected acyclic graph Figure l. A graph that has no cycles but is not necessarily connected is called a forest: each of its connected components is a tree Figure l.

Trees have several important properties other graphs do not have. As the graph of Figure 1. However, for connected graphs it is sufficient and hence provides a convenient way of checking whether a connected graph has a cycle. Rooted trees Another very important property of trees is the fact that for every two vertices in a tree, there always exists exactly one simple path from one of these vertices to the other.

You must be logged in to post a comment. Review Ratings. More Info! User Reviews. Marvins Underground Academic Resources. View More.