Data-Structures-And-Algorithms-Alfred-V-Aho

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

other characters unchanged. The output of translate consists of a file f2 that has the words of f1, uncapitalized, one to a line. Next comes a command sort that sorts the lines of its input file into lexicographic (alphabetical) order. The output of sort is a file f3 that has all the words of f2 in alphabetical order, with repetitions. Then a command unique removes duplicate lines from its input file, producing an output file f4 that has the words of the original file, without capitalization or duplicates, in alphabetical order. Finally, a command diff, with a parameter indicating a second file f5 that holds the alphabetized list of words in the dictionary, one to a line, is applied to f4. The result is all words in f4 (and hence f1) but not in f5, i.e., all words in the original input that are not in the dictionary. The complete program spell is just the following sequence of commands.

spell : translate [A-Z] → [a-z], blank → newline sort

unique

diff dictionary

Command level programming requires discipline from a community of programmers; they must write programs as filters wherever possible, and they must write tools instead of special purpose programs wherever possible. Yet the reward, in terms of the overall ratio of work to results, is substantial.

1.7 Super Pascal

Most of the programs written in this book are in Pascal. To make programs more readable, however, we occasionally use three constructs not found in standard Pascal, each of which can be mechanically translated into pure Pascal. One such construct is the nonnumeric label. The few times we need labels, we shall use nonnumeric labels since they make programs easier to understand. For example, "goto output" is invariably more meaningful than "goto 561." To convert a program containing nonnumeric labels into pure Pascal, we must replace each nonnumeric label by a distinct numeric label and we must then declare those labels with a label declaration at the beginning of the program. This process can be clone mechanically.

The second nonstandard construct is the return statement, which we use because it allows us to write more understandable programs without using goto statements to interrupt the flow of control. The return statement we use has the form

return (expression)

where the (expression) is optional. We can convert a procedure containing return statements into a standard Pascal program quite simply. First, we declare a new label, say 999, and let it label the last end statement of the procedure. If the statement return (x) appears in a function zap, say, we replace this statement with the block

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (27 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

begin

zap := x; goto 999

end

In a procedure, the statement return, which can have no argument, is simply replaced by goto 999.

Example 1.12. Figure 1.15 shows the factorial program written using return statements. Figure 1.16 shows the resulting Pascal program if we apply this transformation systematically to Fig. 1.15.

function fact ( n: integer ): integer; begin

if n <= l then return (1)

else

return ( n * fact(n- 1)) end; { fact }

Fig. 1.15. Factorial program with return statements.

The third extension is that we use expressions as names of types

function fact ( n: integer ) :integer; label

999; begin

if n <= 1 then begin

fact := 1; goto 999

end else

begin

fact := n * fact(n - 1); goto 999

end

999:

end; { fact }

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (28 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

Fig. 1.16. Resulting Pascal program.

uniformly throughout a program. For example, an expression like − celltype, while permissible everywhere else, is not permitted as the type of a parameter of a procedure or the type of the value returned by a function. Technically, Pascal requires that we invent a name for the type expression, say ptrtocell. In this book, we shall allow such expressions, expecting that the reader could invent such a type name and mechanically replace type expressions by the type name. Thus, we shall write statements like

function zap ( A: array[1..10] of integer ) : − celltype

to stand for

function zap (A: arrayoftenints ) : ptrtocell

Finally, a note on our typesetting conventions for programs. Pascal reserved words are in boldface, types are in roman, and procedure, function, and variable names are in italic. We distinguish between upper and lower case letters.

Exercises

There are six teams in the football league: the Vultures, the Lions, the Eagles, the Beavers, the Tigers, and the Skunks. The Vultures have already played the Lions and the Eagles; the Lions have also played the Beavers and Skunks. The Tigers have played the Eagles and Skunks. Each team plays one game per

1.1week. Find a schedule so that all teams will have played each other in the fewest number of weeks. Hint. Create a graph whose vertices are the pairs of teams that have not yet played each other. What should the edges be so that in a legal coloring of the graph, each color can represent the games played in one week?

Consider a robot arm that is fixed at one end. The arm contains two elbows at

each of which it is possible to rotate the arm 90 degrees up and down in a *1.2 vertical plane. How would you mathematically model the possible movements

of the end of the arm? Describe an algorithm to move the end of the robot arm from one permissible position to another.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (29 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

Suppose we wish to multiply four matrices of real numbers M1 × M 2 × M 3 × M 4 where M1 is 10 by 20, M2 is 20 by 50, M3 is 50 by 1, and M4 is 1 by 100. Assume that the multiplication of a p × q matrix by a q × r matrix requires pqr

*1.3 scalar operations, as it does in the usual matrix multiplication algorithm. Find the optimal order in which to multiply the matrices so as to minimize the total number of scalar operations. How would you find this optimal ordering if there are an arbitrary number of matrices?

Suppose we wish to partition the square roots of the integers from 1 to 100 into two piles of fifty numbers each, such that the sum of the numbers in the first

**1.4 pile is as close as possible to the sum of the numbers in the second pile. If we could use two minutes of computer time to help answer this question, what computations would you perform in those two minutes?

1.5

Describe a greedy algorithm for playing chess. Would you expect it to perform very well?

In Section 1.2 we considered an ADT SET, with operations MAKE-NULL, UNION, and SIZE. Suppose for convenience that we assume all sets are subsets

1.6of {0, 1, . . . , 31} and let the ADT SET be interpreted as the Pascal data type set of 0..31. Write Pascal procedures for these operations using this implementation of SET.

The greatest common divisor of two integers p and q is the largest integer d that divides both p and q evenly. We wish to develop a program for computing the greatest common divisor of two integers p and q using the following algorithm. Let r be the remainder of p divided by q. If r is O, then q is the greatest common divisor. Otherwise, set p equal to q, then q equal to r, and repeat the process.

1.7 a. Show that this process does find the correct greatest common divisor.

b. Refine this algorithm into a pseudo-language program.

c. Convert your pseudo-language program into a Pascal program.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (30 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

We want to develop a program for a text formatter that will place words on lines that are both left and right justified. The program will have a word buffer and a line buffer. Initially both are empty. A word is read into the word buffer. If there is sufficient room in the line buffer, the word is transferred to the line buffer. Otherwise, additional spaces are inserted between words in the line

buffer to fill out the line, and then the line buffer is emptied by printing the line.

1.8

a.Refine this algorithm into a pseudo-language program.

b.Convert your pseudo-language program to a Pascal program.

Consider a set of n cities and a table of distances between pairs of cities. Write a pseudo-language program for finding a short path that goes through each city

1.9

exactly once and returns to the city from which it started. There is no known method for obtaining the shortest such tour except by exhaustive searching. Thus try to find an efficient algorithm for this problem using some reasonable heuristic.

Consider the following functions of n:

1.10

Indicate for each distinct pair i and j whether fi(n) is O(fj(n)) and whether fi(n) is Ω(fj(n)).

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (31 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

Consider the following functions of n:

1.11

Indicate for each distinct pair i and j whether gi(n) is O(gj(n)) and whether gi(n) is Ω(gj(n)).

Give, using "big oh" notation, the worst case running times of the following procedures as a function of n.

a.procedure matmpy ( n: integer);

var

i, j, k: integer; begin

for i := 1 to n do

for j := 1 to n do begin

C[i, j] := O;

for k := 1 to n do

C[i, j] := C[i, j,] + A[i, k] * B[k, j]

end end

b.procedure mystery ( n: integer);

var

i, j, k: integer; begin

for i:= 1 to n-1 do for j:= i + 1 to n do for k := 1 to j do

{ some statement requiring O(1) time }

end

1.12

c.procedure veryodd ( n: integer );

var

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (32 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

i, j, x, y: integer; begin

for i := 1 to n do

if odd(i) then begin for j := i to n do

x := x + 1;

for j := 1 to i do y := y + l

end end

d.function recursive (n: integer ) : integer;

begin

if n <= 1 then return (l)

else

return (recursive(n-1) + recursive(n-1))

end

Show that the following statements are true.

a.17 is O(1).

b.n(n-1)/2 is O(n2).

c.max(n3, 10n2) is O(n3).

1.13

e) If p(x) is any kth degree polynomial with a positive leading coefficient, then p(n) is O(nk) and Ω(nk).

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (33 of 37) [1.7.2001 18:58:23]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

end; writeln(count)

end

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (34 of 37) [1.7.2001 18:58:23]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

Here is a function max(i, n) that returns the largest element in positions i through i+n-1 of an integer array A. You may assume for convenience that n is a power of 2.

function max ( i, n: integer ): integer;

var

m1, m2: integer;

begin

if n = 1 then

return (A[i])

else begin

m1 := max(i, n div 2);

m2 := max(i+n div 2,

n div 2);

return (m2)

else

return (m1)

end

end

a.Let T(n) be the worst-case time taken by max with second argument n. That is, n is the number of elements of which the largest is found. Write an equation expressing T(n) in terms of T(j) for one or more values of j less than n and a constant or constants that represent the times taken by individual statements of the max program.

b.Give a tight big oh upper bound on T(n). Your answer should be equal to the big omega lower bound, and be as simple as possible.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (35 of 37) [1.7.2001 18:58:23]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

Bibliographic Notes

The concept of an abstract data type can be traced to the class type in the language SIMULA 67 (Birtwistle et al. [1973]). Since that time, a variety of other languages that support abstract data types have been developed including Alphard (Shaw, Wulf, and London [1977]), C with classes (Stroustrup [1982]), CLU (Liskov, et al. [1977]), MESA (Geschke, Morris, and Satterthwaite [1977]), and Russell (Demers and Donahue [1979]). The ADT concept is further discussed in works such as Gotlieb and Gotlieb [1978] and Wulf et al. [1981].

Knuth [1968] was the first major work to advocate the systematic study of the running time of programs. Aho, Hopcroft, and Ullman [1974] relate the time and space complexity of algorithms to various models of computation, such as Turing machines and randomaccess machines. See also the bibliographic notes to Chapter 9 for more references to the subject of analysis of algorithms and programs.

For additional material on structured programming see Hoare, Dahl, and Dijkstra [1972], Wirth [1973], Kernighan and Plauger [1974], and Yourdon and Constantine [1975]. Organizational and psychological problems arising in the development of large software projects are discussed in Brooks [1974] and Weinberg [1971]. Kernighan and Plauger [1981] show how to build useful software tools for a programming environment.

† The symbol Ø stands for the empty set.

‡ We distinguish the abstract data type SET from the built-in set type of Pascal.

†The record has no known name because it was created by a call new(header), which made header point to this newly-created record. Internal to the machine, however, there is a memory address that can be used to locate the cell.

†Note the asymmetry between big-oh and big-omega notation. The reason such asymmetry is often useful is that there are many times when an algorithm is fast on many but not all inputs. For example, there are algorithms to test whether their input is of prime length that run very fast whenever that length is even, so we could not get a good lower bound on

running time that held for all n ³ n0.

†Unless otherwise specified all logarithms are to the base 2. Note that O(logn) does not depend on the base of the logarithm since logan = clogbn, where c = logab.

†UNIX is a Trademark of Bell Laboratories.

‡ We could use an unabridged dictionary, but many misspellings are real words one has never heard of.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (36 of 37) [1.7.2001 18:58:23]