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

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

Often, we can eliminate mechanically the last call a procedure makes to itself. If a procedure P(x) has, as its last step, a call to P(y), then we can replace the call to P(y) by an assignment x := y, followed by a jump to the beginning of the code for P. Here, y could be an expression, but x must be a parameter passed by value, so its value is stored in a location private to this call to P ‡ P could have more than one parameter, of course, and if so, they are each treated exactly as x and y above.

This change works because rerunning P with the new value of x has exactly the same effect as calling P(y) and then returning from that call.

function knapsack ( target: integer; candidate: integer ): boolean; begin

(1)if target = 0 then

(2)return (true)

(3)else if (target < 0) or (candidate > n) then

(4)return (false)

Fig. 2.25. Recursive knapsack solution.

Notice that the fact that some of P's local variables have values the second time around is of no consequence. P could not use any of those values, or had we called P(y) as originally intended, the value used would not have been defined.

Another variant of tail recursion is illustrated by Fig. 2.25, where the last step of the function knapsack just returns the result of calling itself with other parameters. In such a situation, again provided the parameters are passed by value (or by reference if the same parameter is passed to the call), we can replace the call by assignments to the parameters and a jump to the beginning of the function. In the case of Fig. 2.25, we can replace line (8) by

candidate:= candidate + 1;

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (30 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

goto beginning

where beginning stands for a label to be assigned to statement (1). Note no change to target is needed, since it is passed intact as the first parameter. In fact, we could observe that since target has not changed, the tests of statements (1) and (3) involving target are destined to fail, and we could instead skip statements (1) and (2), test only for candidate > n at line (3), and proceed directly to line (5).

Complete Recursion Elimination

The tail recursion elimination procedure removes recursion completely only when the recursive call is at the end of the procedure, and the call has the correct form. There is a more general approach that converts any recursive procedure (or function) into a nonrecursive one, but this approach introduces a user-defined stack. In general, a cell of this stack will hold:

1.The current values of the parameters of the procedure;

2.The current values of any local variables of the procedure; and

3.An indication of the return address, that is, the place to which control returns when the current invocation of the procedure is done.

In the case of the function knapsack, we can do something simpler. First, observe that whenever we make a call (push a record onto the stack), candidate increases by 1. Thus, we can keep candidate as a global variable, incrementing it by one every time we push the stack and decreasing it by one when we pop.

A second simplification we can make is to keep a modified "return address" on the stack. Strictly speaking, the return address for this function is either a place in some other procedure that calls knapsack, or the call at line (5), or the call at line (8). We can represent these three conditions by a "status," which has one of three values:

1.none, indicating that the call is from outside the function knapsack,

2.included, indicating the call at line (5), which includes weights[candidate] in the solution, or

3.excluded, indicating the call at line (8), which excludes weights[candidate].

If we store this status symbol as the return address, then we can treat target as a global variable. When changing from status none to included, we subtract weights[candidate] from target, and we add it back in when changing from status included to excluded. To help represent the effect of the knapsack's return indicating whether a solution has been found, we use a global winflag. Once set to true, winflag

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (31 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

remains true and causes the stack to be popped and those weights with status included to be printed. With these modifications, we can declare our stack to be a list of statuses, by

type

statuses = (none, included, excluded);

STACK = { suitable declaration for stack of statuses }

Figure 2.26 shows the resulting nonrecursive procedure knapsack operating on an array weights as before. Although this procedure may be faster than the original function knapsack, it is clearly longer and more difficult to understand. For this reason, recursion elimination should be used only when speed is very important.

procedure knapsack ( target: integer ); var

candidate: integer; winflag: boolean; S: STACK;

begin

candidate := 1; winflag := false; MAKENULL(S);

PUSH(none, S); { initialize stack to consider weights[1] } repeat

if winflag then begin

{ pop stack, printing weights included in solution } if TOP(S) = included then

writeln(weights[candidate]); candidate := candidate - 1; POP(S)

end

else if target = 0 then begin { solution found } winflag := true;

candidate := candidate - 1; POP(S)

end

else if (((target < 0) and (TOP(S) = none)) or (candidate > n)) then begin

{ no solution possible with choices made } candidate := candidate - 1;

POP(S) end

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (32 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

else { no resolution yet; consider status of current candidate } if TOP(S) = none then begin { first try including candidate }

target := target - weights[candidate]; candidate := candidate + 1;

POP(S); PUSH(included, S); PUSH(none, S) end

else if TOP(S) = included then begin { try excluding candidate } target := target + weights[candidate];

candidate := candidate + 1;

POP(S); PUSH(excluded, S); PUSH(none, S) end

else begin { TOP(S) = excluded; give up on current choice } POP(S);

candidate := candidate - 1 end

until EMPTY(S) end; { knapsack }

Fig. 2.26. Nonrecursive knapsack procedure.

Exercises

2.1

Write a program to print the elements on a list. Throughout these exercises use list operations to implement your programs.

Write programs to insert, delete, and locate an element on a sorted list using

a. array,

2.2

b.pointer, and

c.cursor implementations of lists.

What is the running time of each of your programs?

Write a program to merge

2.3a. two sorted lists, b. n sorted lists.

2.4Write a program to concatenate a list of lists.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (33 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

Suppose we wish to manipulate polynomials of the form p(x) = c1xe1 + c2xe2 + . . . + cnxen, where e1 > e2 > . . . > en ³ 0. Such a polynomial can

2.5be represented by a linked list in which each cell has three fields: one for the coefficient ci, one for the exponent ei, and one for the pointer to the next cell. Write a program to differentiate polynomials represented in this

manner.

Write programs to add and multiply polynomials of the form in Exercise

2.62.5. What is the running time of your programs as a function of the number of terms?

Suppose we declare cells by

type

celltype = record bit: 0..1;

next: - celltype

end;

*2.7

A binary number b1b2 . . . bn, where each bi is 0 or 1, has numerical value

. This number can be represented by the list b1, b2 , . . . , bn. That list, in turn, can be represented as a linked list of cells of type celltype. Write a procedure increment(bnumber) that adds one to the binary number pointed to by bnumber. Hint: Make increment recursive.

2.8

Write a procedure to interchange the elements at positions p and

NEXT(p) in a singly linked list.

The following procedure was intended to remove all occurrences of element x from list L. Explain why it doesn't always work and suggest a way to repair the procedure so it performs its intended task.

procedure delete ( x: elementtype; var L: LIST ); var

p: position;

*2.9

begin

p := FIRST(L);

while p <> END(L) do begin if RETRIEVE(p, L) = x then

DELETE(p, L);

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (34 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

p := NEXT(p, L) end

end; { delete }

We wish to store a list in an array A whose cells consist of two fields, data to store an element and position to give the (integer) position of the element. An integer last indicates that A[1] through A[last] are used to hold the list. The type LIST can be defined by

type

LIST = record

2.10

last: integer;

elements: array[1..maxlength] of record data: elementtype;

position: integer

end end;

Write a procedure DELETE(p, L) to remove the element at position p. Include all necessary error checks.

Suppose L is a LIST and p, q, and r are positions. As a function of n, the length of list L, determine how many times the functions FIRST, END, and NEXT are executed by the following program.

p := FIRST(L);

while p <> END(L) do begin q := p;

while q <> END(L) do begin

2.11

q := NEXT(q, L); r := FIRST(L); while r <> q do

r := NEXT(r, L)

end;

p := NEXT(p, L) end;

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (35 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

Rewrite the code for the LIST operations assuming a linked list

2.12representation, but without a header cell. Assume true pointers are used and position 1 is represented by nil.

2.13Add the necessary error checks in the procedure of Fig. 2.12.

Another array representation of lists is to insert as in Section 2.2, but when deleting, simply replace the deleted element by a special value

2.14

"deleted," which we assume does not appear on lists otherwise. Rewrite the list operations to implement this strategy. What are the advantages and disadvantages of the approach compared with our original array representation of lists?

Suppose we wish to use an extra bit in queue records to indicate whether

2.15

a queue is empty. Modify the declarations and operations for a circular queue to accommodate this feature. Would you expect the change to be worthwhile?

A dequeue (double-ended queue) is a list from which elements can be

2.16inserted or deleted at either end. Develop array, pointer, and cursor implementations for a dequeue.

Define an ADT to support the operations ENQUEUE, DEQUEUE, and

2.17ONQUEUE. ONQUEUE(x) is a function returning true or false depending on whether x is or is not on the queue.

How would one implement a queue if the elements that are to be placed

2.18on the queue are arbitrary length strings? How long does it take to enqueue a string?

Another possible linked-list implementation of queues is to use no header cell, and let front point directly to the first cell. If the queue is empty, let

2.19

front = rear = nil. Implement the queue operations for this representation. How does this implementation compare with the list implementation given for queues in Section 2.4 in terms of speed, space utilization, and conciseness of the code?

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (36 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

A variant of the circular queue records the position of the front element and the length of the queue.

b. Write the five queue operations for this implementation. c. Compare this implementation with the circular queue

implementation of Section 2.4.

It is possible to keep two stacks in a single array, if one grows from position 1 of the array, and the other grows from the last position. Write a

2.21procedure PUSH(x, S) that pushes element x onto stack S, where S is one or the other of these two stacks. Include all necessary error checks in your procedure.

We can store k stacks in a single array if we use the data structure suggested in Fig. 2.27, for the case k = 3. We push and pop from each stack as suggested in connection with Fig. 2.17 in Section 2.3. However, if pushing onto stack i causes TOP(i) to equal BOTTOM(i-1), we first move all the stacks so that there is an appropriate size gap between each adjacent pair of stacks. For example, we might make the gaps above all stacks equal, or we might make the gap above stack i proportional to the current size of stack i (on the theory that larger stacks are likely to grow sooner, and we want to postpone as long as possible the next reorganization).

a.On the assumption that there is a procedure reorganize to call when stacks collide, write code for the five stack operations.

b.On the assumption that there is a procedure makenewtops that computes newtop[i], the "appropriate" position for the top of stack

on considering stack i, we can move it safely, do so, and then reconsider the stack whose number is on top of the goal stack. If we cannot safely move stack i, push i onto the goal stack.

c. What is an appropriate implementation for the goal stack in (b)? Do we really need to keep it as a list of integers, or will a more succinct representation do?

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (37 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

d.Implement makenewtops in such a way that space above each stack is proportional to the current size of that stack.

e.What modifications of Fig. 2.27 are needed to make the implementation work for queues? For general lists?

Modify the implementations of POP and ENQUEUE in Sections 2.3 and

2.23

2.4 to return the element removed from the stack or queue. What modifications must be made if the element type is not a type that can be returned by a function?

Use a stack to eliminate recursion from the following procedures.

a.function comb ( n, m: integer ): integer;

{computes (

) assuming 0 £ m £ n and n ³ 1 }

begin

if (n = 1) or (m = 0) or (m = n)

then

return (1) else

return (comb(n-1, m) + comb(n-1, m-1)) end; { comb }

2.24

Fig. 2.27. Many stacks in one array.

b.procedure reverse ( var L: LIST );

{reverse list L }

var

x: elementtype; begin

if not EMPTY(L) then begin

x := RETRIEVE(FIRST(L), L); DELETE(FIRST(L), L);

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (38 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

reverse(L);

INSERT(x, END(L), L) end

end; { reverse }

*2.25

Can we eliminate the tail recursion from the programs in Exercise 2.24? If so, do it.

Bibliographic Notes

Knuth [1968] contains additional information on the implementation of lists, stacks, and queues. A number of programming languages, such as LISP and SNOBOL, support lists and strings in a convenient manner. See Sammet [1969], Nicholls [1975], Pratt [1975], or Wexelblat [1981] for a history and description of many of these languages.

†Strictly speaking, the type is "LIST of elementtype." However, the implementations of lists we propose do not depend on what elementtype is; indeed, it is that independence that justifies the importance we place on the list concept. We shall use "LIST" rather than "LIST of elementtype," and similarly treat other ADT's that depend on the types of elements.

†In this case, if we eliminate records that are "the same" we might wish to check that the names and addresses are also equal; if the account numbers are equal but the other fields are not, two people may have inadvertently gotten the same account number. More likely, however, is that the same subscriber appears on the list more than once with distinct account numbers and slightly different names and/or addresses. In such cases, it is difficult to eliminate all duplicates.

†Even though L is not modified, we pass L by reference because frequently it will be a big structure and we don't want to waste time copying it.

†Making the header a complete cell simplifies the implementation of list operation in Pascal. We can use pointers for headers if we are willing to implement our operations so they do insertions and deletions at the beginning of a list in a special way. See the discussion under cursor-based implementation of lists in this section.

†Of course, there are many situations where we would like p to continue to

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (39 of 40) [1.7.2001 18:59:00]