Bahan Kuliah ke-14

Techniques for the Design of Algorithms

The first part of this course is concerned with:

Algorithmic Paradigms

That is:

General approaches to the construction of efficient solutions to

problems.

Such methods are of interest because:

They provide templates suited to solving a broad range of diverse

problems.
They can be translated into common control and data structures
provided by most high-level languages.
The temporal and spatial requirements of the algorithms which result
can be precisely analysed.

Over the next few lectures we shall examine the following paradigms:

Divide and Conquer.

Dynamic Programming
Greedy Method
Backtracking.

Although more than one technique may be applicable to a specific problem,

it is often the case that an algorithm constructed by one approach is clearly
superior to equivalent solutions built using alternative techniques.

The choice of design paradigm is an important aspect of algorithm synthesis.

Basic Algorithm Analysis

Questions

How does one calculate the running time of an algorithm?

How can we compare two different algorithms?
 How do we know if an algorithm is `optimal'?

1. Count the number of basic operations performed by the algorithm on the

worst-case input

A basic operation could be:

An assignment
A comparison between two variables
An arithmetic operation between two variables. The worst-case input
is that input assignment for which the most basic operations are
performed.

Simple Example:

n := 5;
loop
get(m);
n := n -1;
until (m=0 or n=0)
Worst-case: 5 iterations

Usually we are not concerned with the number of steps for a single fixed
case but wish to estimate the running time in terms of the `input size'.

get(n);
loop
get(m);
n := n -1;
until (m=0 or n=0)
Worst-case: n iterations

Examples of `input size':

Sorting:

n == The number of items to be sorted;

Basic operation: Comparison.

Multiplication (of x and y):

n == The number of digits in x plus the number of digits in y.

Basic operations: single digit arithmetic.

Graph `searching':

n == the number of nodes in the graph or the number of edges in the graph.

Counting the Number of Basic Operations

Sequence: P and Q are two algorithm sections:

Time( P ; Q ) = Time( P ) + Time( Q )

Iteration:

while < condition > loop

P;
end loop;
or
for i in 1..n loop
P;
end loop

Time = Time( P ) * ( Worst-case number of

iterations )

Conditional

if < condition > then

P;
else
Q;
end if;

Time = Time(P) if < condition > =true

Time( Q ) if < condition > =false

We shall consider recursive procedures later in the course.

Example:

for i in 1..n loop

for j in 1..n loop
if i < j then
swop (a(i,j), a(j,i)); -- Basic operation
end if;
end loop;
end loop;

Time < n*n*1

= n^2

Asymptotic Performance

We are usually concerned with the growth in running time as the input size
increases, e.g.

Suppose P, Q and R are 3 algorithms with the following worst-case run

times:

n P Q R
1 1 5 100
10 1024 500 1000
100 2 100 50,000 10,000
1000 2 1000 5 million 100,000

If each is run on a machine that executes one million (10^6) operations per
second

n P Q R
1 1(*ms 5(*ms 100(*ms
5 1 millisec 0.5 millisec 1 millisec
100 270years 0.05 secs 0.01 secs
1000 2970years 5 secs 0.1 secs

Thus,
The growth of run-time in terms of n (2^n; n^2; n) is more significant than
the exact constant factors (1; 5; 100)

`O'-notation

Let f:N-> R and g:N-> R. Then: f( n ) = O( g(n) ) means that

There are values, n0 and c, such that f( n ) < = c * g( n ) whenever n > = n0.

Thus we can say that an algorithm has, for example,

Run-time O( n^2 )

Examples

There is an algorithm (mergesort) to sort n items which has run-time

O( n log n ).
There is an algorithm to multiply 2 n-digit numbers which has run-
time O( n^2 ).
There is an algorithm to compute the nth Fibonacci number which has
run-time O( log n ).

OM-notation

To express the concept of an algorithm taking at least some number of steps

OM-notation

can be used.

Again let, f:N-> R and g:N-> R. Then: f( n ) = OM ( g(n) ) means that there
are values, n0 and c, such that f( n ) > = c * g( n ) whenever n > = n0.

THETA-notation

Again let, f:N-> R and g:N-> R.

If f(n)=O(g(n)) and f(n)=OM(g(n))

Then we write, f( n ) = THETA ( g(n) )

In this case, f(n) is said to be asymptotically equal to g(n).

If f( n ) = THETA( g(n) ) then algorithms with running times f(n) and g(n)
appear to perform similarly as n gets larger.

Manipulating O- and OM-notation

f(n)=O(g(n)) if and only if g(n)=OM(f(n))

If f(n) = O(g(n)) then

f(n)+g(n)=O(g(n)) ; f(n)+g(n)=OM(g(n))

f(n)*g(n)=O(g(n)^2) ; f(n)*g(n)=OM(f(n)^2)

Examples

Suppose f(n)=10n and g( n )=2n^2

f(n)=O(g(n))
10n+2n^2 = O(n^2)
10n+2n^2 = OM(n^2)
(10n)*(2n^2) = O(n^4)
(10n)*(2n^2) = OM(n^2)

Divide-and-Conquer

This is a method of designing algorithms that (informally) proceeds as

follows:

Given an instance of the problem to be solved, split this into several,

smaller, sub-instances (of the same problem) independently solve each of the
sub-instances and then combine the sub-instance solutions so as to yield a
solution for the original instance. This description raises the question:

By what methods are the sub-instances to be independently solved?

The answer to this question is central to the concept of Divide-&amp-

Conquer algorithm and is a key factor in gauging their efficiency.

Consider the following: We have an algorithm, alpha say, which is known to

solve all problem instances of size n in at most c n^2 steps (where c is some
constant). We then discover an algorithm, beta say, which solves the same
problem by:
 Dividing an instance into 3 sub-instances of size n/2.
Solves these 3 sub-instances.
Combines the three sub-solutions taking d n steps to do this.

Suppose our original algorithm, alpha, is used to carry out the `solves these
sub-instances' step 2. Let

T(alpha)( n ) = Running time of alpha

T(beta)( n ) = Running time of beta

Then,

T(alpha)( n ) = c n^2 (by definition of alpha)

But

T(beta)( n ) = 3 T(alpha)( n/2 ) + d n

= (3/4)(cn^2) + dn

So if dn < (cn^2)/4 (i.e. d < cn/4) then beta is faster than alpha

In particular for all large enough n, (n > 4d/c = Constant), beta is faster than
alpha.

This realisation of beta improves upon alpha by just a constant factor. But if
the problem size, n, is large enough then

n > 4d/c
n/2 > 4d/c
...
n/2^i > 4d/c

which suggests that using beta instead of alpha for the `solves these' stage
repeatedly until the sub-sub-sub..sub-instances are of size n0 < = (4d/c) will
yield a still faster algorithm.

So consider the following new algorithm for instances of size n

procedure gamma (n : problem size ) is
begin
if n <= n^-0 then
Solve problem using Algorithm alpha;
else
Split into 3 sub-instances of size n/2;
Use gamma to solve each sub-instance;
Combine the 3 sub-solutions;
end if;
end gamma;

Let T(gamma)(n) denote the running time of this algorithm.

cn^2 if n < = n0
T(gamma)(n) =
3T(gamma)( n/2 )+dn otherwise

We shall show how relations of this form can be estimated later in the
course. With these methods it can be shown that

T(gamma)( n ) = O( n^{log3} ) (=O(n^{1.59..})

This is an asymptotic improvement upon algorithms alpha and beta.

The improvement that results from applying algorithm gamma is due to the
fact that it maximises the savings achieved beta.

The (relatively) inefficient method alpha is applied only to "small" problem

sizes.

The precise form of a divide-and-conquer algorithm is characterised by:

The threshold input size, n0, below which the problem size is not sub-
divided.
The size of sub-instances into which an instance is split.
The number of such sub-instances.
The algorithm used to combine sub-solutions.
In (II) it is more usual to consider the ratio of initial problem size to sub-
instance size. In our example this was 2. The threshold in (I) is sometimes
called the (recursive) base value. In summary, the generic form of a divide-
and-conquer algorithm is:

procedure D-and-C (n : input size) is

begin
if n < = n0 then
Solve problem without further
sub-division;
else
Split into r sub-instances
each of size n/k;
for each of the r sub-instances do
D-and-C (n/k);
Combine the r resulting
sub-solutions to produce
the solution to the original problem;
end if;
end D-and-C;

Such algorithms are naturally and easily realised as:

Recursive Procedures

in (suitable) high-level programming languages.

Example 1:

Binary Search

Consider the following problem: one has a directory containing a set of

names and a telephone number associated with each name.

The directory is sorted by alphabetical order of names. It contains n entries

which are stored in 2 arrays:

names (1..n) ; numbers (1..n)

Given a name and the value n the problem is to find the number associated
with the name.
We assume that any given input name actually does occur in the directory,
in order to make the exposition easier.

The Divide-&amp-Conquer algorithm to solve this problem is the simplest

example of the paradigm.

It is based on the following observation

Given a name, X say,

X occurs in the middle place of the names array

Or

X occurs in the first half of the names array. (U)

Or

X occurs in the second half of the names array. (L)

U (respectively L) are true only if X comes before (respectively after) that

name stored in the middle place.

This observation leads to the following algorithm:

function search (X : name;

start, finish :
integer)
return integer is
middle : integer;
begin
middle := (start+finish)/2;
if names(middle)=x then
return numbers(middle);
elsif X&ltnames(middle) then
return search(X,start,middle-1);
else -- X&gtnames(middle)
return search(X,middle+1,finish);
end if;
end search;
Exercise: How should this algorithm be modified to cater for the possibility
that a given name does not occur in the directory? In terms of the generic
form of divide-&amp-conquer algorithms, at which stage is this
modification made?

We defer analysis of the algorithm's performance until later.

Example 2

Closest Pair

Input:

P = {p(1), p(2) ,..., p(n) }

where p(i) = ( x(i), y(i) ).

A set of n points in the plane.

Output

The distance between the two points that are closest.

Note: The distance DELTA( i, j ) between p(i) and p(j) is defined by the
expression:

Square root of { (x(i)-x(j))^2 + (y(i)-y(j))^2 }

We describe a divide-and-conquer algorithm for this problem.

We assume that:

n is an exact power of 2, n = 2^k.

For each i, x(i) < = x(i+1), i.e. the points are ordered by increasing x from
left to right.

Consider drawing a vertical line (L) through the set of points P so that half
of the points in P lie to the left of L and half lie to the right of L.

There are three possibilities:

The closest pair lie in P-LEFT.

The closest pair lie in P-RIGHT.
The closest pair contains:

One Point from P-LEFT

and

One Point from P-RIGHT

So we have a (rough) Divide-and-Conquer Method as follows:

function closest_pair (P: point set; n: in

teger )
return float is
DELTA-LEFT, DELTA-RIGHT : float;
DELTA : float;
begin
if n = 2 then
return distance from p(1) to p(2);
else
P-LEFT := ( p(1), p(2) ,..., p(n/2) );
P-RIGHT := ( p(n/2+1), p(n/2+2) ,..., p(n)
);
DELTA-LEFT := closestpair( P-LEFT, n/2 );
DELTA-RIGHT := closestpair( P-RIGHT, n/2
);
DELTA := minimum ( DELTA-LEFT, DELTA-RIGHT
);
--
*********************************************
Determine whether there are points p(l) in
P-LEFT and p(r) in P-RIGHT with
distance( p(l), p(r) ) < DELTA. If there
are such points, set DELTA to be the
smallest
distance.
--
**********************************************
return DELTA;
end if;
end closest_pair;

The section between the two comment lines is the `combine' stage of the
Divide-and-Conquer algorithm.

If there are points p(l) and p(r) whose distance apart is less than DELTA then
it must be the case that
 The x-coordinates of p(l) and p(r) differ by at most DELTA.
The y-coordinates of p(l) and p(r) differ by at most DELTA.

The combine stage can be implemented by:

Finding all points in P-LEFT whose x-coordinate is at least x(n/2)-

DELTA.
Finding all points in P-RIGHT whose x-coordinate is at most
x(n/2)+DELTA.

Call the set of points found in (1) and (2) P-strip. and sort the s points in this
in order of increasing y-coordinate. letting ( q(1),q(2) ,..., q(s) ) denote the
sorted set of points.

Then the combine stage of the algorithm consists of two nested for loops:

for i in 1..s loop

for j in i+1..s loop
exit when (| x(i) - x(j) | > DELTA or
| y(i) - y(j) | > DELTA);
if distance( q(i), q(j) ) < DELTA then
DELTA := distance ( q(i), q(j) );
 end if;
end loop;
end loop;

Example 3

Integer Multiplication

Divide-and-Conquer may also be applied to problems other than those

involving searching. The following problem should be familiar:

The (2n)-digit decimal representation of the product x * y.

Note: The algorithm below works for any number base, e.g. binary, decimal,
hexadecimal, etc. We use decimal simply for convenience.

The classical primary school algorithm for multiplication requires O( n^2 )

steps to multiply two n-digit numbers.

A step is regarded as a single operation involving two single digit numbers,

e.g. 5+6, 3*4, etc.

In 1962, A.A. Karatsuba discovered an asymptotically faster algorithm for

multiplying two numbers by using a divide-and-conquer approach.
From this we also know that the result of multiplying x and y (i.e. z) is
The terms ( a*c ), ( a*d ), ( b*c ), and ( b*d ) are each products of

2 (n/2)-digit numbers.

Thus the expression for the multiplication of x and y in terms of the numbers
a, b, c, and d tells us that:

Two single digit numbers can be multiplied immediately. (Recursive

base: 1 step)
If n > 1 then the product of 2 n-digit numbers can be expressed in
terms of 4 products of 2 (n/2)-digit numbers (Divide-and-Conquer
stage)
To calculate the result of multiplying x and y given the four products
returned involves only addition (can be done in O( n ) steps) and
multiplying by a power of 10 (also can be done in O( n ) steps, since it
only requires placing the appropriate number of 0s at the end of the
number). (Combine stage).

(1-3) therefore describe a Divide-&amp-Conquer algorithm for multiplying

two n-digit numbers represented in decimal. However,

Moderately difficult: How many steps does the resulting algorithm take to
multiply two n-digit numbers?

Karatsuba discovered how the product of 2 n-digit numbers could be

expressed in terms of three products each of 2 (n/2)-digit numbers - instead
of the four products that a naive implementation of the Divide-and-Conquer
schema above uses.

This saving is accomplished at the expense of slightly increasing the number

of steps taken in the `combine stage' (Step 3) (although, this will still only
use O( n ) operations).

Suppose we compute the following 3 products (of 2 (n/2)-digit numbers):

function Karatsuba (xunder, yunder : n-digit
integer;
n : integer)
return (2n)-digit
integer is
a, b, c, d : (n/2)-digit integer
U, V, W : n-digit integer;
begin
if n = 1 then
return x(0)*y(0);
else
a := x(n-1) ... x(n/2);
b := x(n/2-1) ... x(0);
c := y(n-1) ... y(n/2);
d := y(n/2-1) ... y(0);
U := Karatsuba ( a, c, n/2 );
V := Karatsuba ( b, d, n/2 );
W := Karatsuba ( a+b, c+d, n/2 );
return U*10^n + (W-U-V)*10^n/2 + V;
end if;
end Karatsuba;

Performance Analysis
It was observed earlier that one reason for examining algorithmic paradigms
was the fact that their running time could often be precisely determined.

This is useful in allowing comparisons between the performances of two

algorithms to be made.

For Divide-and-Conquer algorithms the running time is mainly affected by 3

criteria:

The number of sub-instances (alpha) into which a problem is split.

The ratio of initial problem size to sub-problem size. (beta)
The number of steps required to divide the initial instance and to
combine sub-solutions, expressed as a function of the input size, n.

Suppose, P, is a divide-and-conquer algorithm that instantiates alpha sub-

instances, each of size n/beta.

Let Tp( n ) denote the number of steps taken by P on instances of size n.

Then

Tp( n0 ) = Constant (Recursive-base)

Tp( n ) = alpha Tp( n/beta ) + gamma( n )

In the case when alpha and beta are both constant (as in all the examples we
have given) there is a general method that can be used to solve such
recurrence relations in order to obtain an asymptotic bound for the running
time Tp( n ).

In general:

T( n ) = alpha T( n/beta ) + O( n^gamma )

(where gamma is constant) has the solution

O(n^gamma) if alpha <

beta^gamma
T( n ) = O(n^gamma log n) if alpha =
beta^gamma}
O(n^{log^-beta(alpha)) if alpha >
beta^gamma

Dynamic Programming

This paradigm is most often applied in the construction of algorithms to

solve a certain class of

Optimisation Problem

That is: problems which require the minimisation or maximisation of some

measure.

One disadvantage of using Divide-and-Conquer is that the process of

recursively solving separate sub-instances can result in the same
computations being performed repeatedly since identical sub-instances
may arise.

The idea behind dynamic programming is to avoid this pathology by

obviating the requirement to calculate the same quantity twice.

The method usually accomplishes this by maintaining a table of sub-instance

results.

Dynamic Programming is a

Bottom-Up Technique

in which the smallest sub-instances are explicitly solved first and the results
of these used to construct solutions to progressively larger sub-instances.

In contrast, Divide-and-Conquer is a

Top-Down Technique

which logically progresses from the initial instance down to the smallest
sub-instances via intermediate sub-instances. We can illustrate these points
by considering the problem of calculating the Binomial Coefficient, "n
choose k", i.e.
Using this relationship, a rather crude Divide-and-Conquer solution to the
problem of calculating the Binomial Coefficient `n choose k' would be:

function bin_coeff (n : integer;

k : integer)
return integer is
begin
if k = 0 or k = n then
return 1;
else
return
bincoeff(n-1, k-1) + bincoeff(n-1, k);
end if;
end bin_coeff;

By contrast, the Dynamic Programming approach uses the same relationship

but constructs a table of all the (n+1)*(k+1) binomial coefficients `i
choose j' for each value of i between 0 and n, each value of j between 0 and
k.

These are calculated in a particular order:

First the table entries corresponding to the coefficients `i choose 0'

and `1 choose 1' are fixed to the value 1.
The remaining table entries corresponding to the binomial coefficient
`i choose j' are calculated in increasing order of the value of i+j.

It should be noted that since the coefficient `i choose j' requires only the
values of `i-1 choose j-1' and `i-1 choose j', computing the table entries in
the order of increasing i+j ensures that the table entries needed for ``i choose
j' have already been calculated, i.e.

(i-1)+(j-1) < (i-1)+j < i+j

The Dynamic Programming method is given by:

function bin_coeff (n : integer;

k : integer)

return integer is

type table is array (0..n, 0..k) of integer;

bc : table;

i, j, k : integer;

sum : integer;

begin

for i in 0..n loop

bc(i,0) := 1;

end loop;

bc(1,1) := 1;

sum := 3; i := 2; j := 1;

while sum <= n+k loop

bc(i,j) := bc(i-1,j-1)+bc(i,j-1);

i := i-1; j := j+1;

if i < j or j > k then

 sum := sum + 1;

if sum <= n+1 then

i := sum-1; j := 1;

else

i := n; j := sum-n;

end if;

end if;

end loop;

return bc(n,k);

end bin_coeff;

The section of the function consisting of the lines:

if i < j or j > k then

sum := sum + 1;

if sum <= n+1 then

i := sum-1; j := 1;

else

i := n; j := sum-n;

end if;

end if;
is invoked when all the table entries `i choose j', for which i+j equals the
current value of sum, have been found. The if statement increments the value
of sum and sets up the new values of i and j.

Now consider the differences between the two methods: The Divide-and-
Conquer approach recomputes values, such as "2 choose 1", a very large
number of times, particularly if n is large and k depends on n, i.e. k is not a
constant.

It can be shown that the running time of this method is

Despite the fact that the algorithm description is quite simple (it is just a
direct implementation of the relationship given) it is completely infeasible
as a practical algorithm.

The Dynamic Programming method, since it computes each value "i

choose j" exactly once is far more efficient. Its running time is O( n*k ),
which is O( n^2 ) in the worst-case, (again k = n/2).

It will be noticed that the dynamic programming solution is rather more

involved than the recursive Divide-and-Conquer method, nevertheless its
running time is practical.

The binomial coefficient example illustrates the key features of dynamic

programming algorithms.

A table of all sub-instance results is constructed.

The entries corresponding to the smallest sub-instances are initiated at
the start of the algorithm.
The remaining entries are filled in following a precise order (that
corresponds to increasing sub-instance size) using only those entries
that have already been computed.
 Each entry is calculated exactly once.
The final value computed is the solution to the initial problem
instance.
Implementation is by iteration (never by recursion, even though the
analysis of a problem may naturally suggest a recursive solution).

Example: Shortest Path

Input: A directed graph, G( V, E ), with nodes

V = {1, 2 ,..., n }

and edges E as subset of VxV. Each edge in E has associated with it a non-
negative length.

Output: An nXn matrix, D, in which D^(i,j) contains the length of the

shortest path from node i to node j in G.

Informal Overview of Method

The algorithm, conceptually, constructs a sequence of matrices:

D0, D1 ,..., Dk ,..., Dn

For each k (with 1 < = k < = n), the (i, j) entry of Dk, denoted Dk( i,j ), will
contain the Length of the shortest path from node i to node j when only
the nodes

{ 1, 2, 3 ,..., k }

can be used as intermediate nodes on the path.

Obviously Dn = D.

The matrix, D0, corresponds to the `smallest sub-instance'. D0 is initiated as:

0 if i=j
D0( i, j ) = infinite if (i,j) not in E
Length(i,j) if (i,j) is in E
Now, suppose we have constructed Dk, for some k < n.

How do we proceed to build D(k+1)?

The shortest path from i to j with only

{ 1, 2, 3 ,..., k, k+1 }

available as internal nodes

Either: Does not contain the node k+1.

Or: Does contain the node k+1.

In the former case:

D(k+1)( i, j ) = Dk( i, j )

In the latter case:

D(k+1)( i, j ) = D-k( i, k+1 ) + D-k(

k+1, j )

Therefore D(k+1)( i, j ) is given by

Dk(i,j)
minimum
Dk( i, k+1 ) + Dk( k+1, j )

Although these relationships suggest using a recursive algorithm, as with the

previous example, such a realisation would be extremely inefficient.

Instead an iterative algorithm is employed.

Only one nXn matrix, D, is needed.

This is because after the matrix D(k+1) has been constructed, the matrix Dk
is no longer needed. Therefore D(k+1) can overwrite Dk.

In the implementation below, L denotes the matrix of edge lengths for the set
of edges in the graph G( V, E ).

type matrix is array (1..n, 1..n) of integer;

L : matrix
function shortest_path_length (L : matrix;
n : integer)
return matrix is
D : matrix; -- Shortest paths matrix
begin
-- Initial sub-instance
D(1..n,1..n) := L(1..n,1..n);
for k in 1..n loop
for i in 1..n loop
for j in 1..n loop
if D(i,j) > D(i,k) + D(k,j) then
D( i,j ) := D(i,k) + D(k,j);
end if;
end loop;
end loop;
end loop;
return D(1..n,1..n);
end shortest_path_length;

This algorithm, discovered by Floyd, clearly runs in time

O( n^3 )

Thus O( n ) steps are used to compute each of the n^2 matrix entries.

Greedy Algorithms

This is another approach that is often used to design algorithms for solving

Optimisation Problems

In contrast to dynamic programming, however,

 Greedy algorithms do not always yield a genuinely optimal solution.
In such cases the greedy method is frequently the basis of a heuristic
approach.
Even for problems which can be solved exactly by a greedy algorithm,
establishing the correctness of the method may be a non-trivial
process.

In order to give a precise description of the greedy paradigm we must first

consider a more detailed definition of the environment in which typical
optimisation problems occur. Thus in an optimisation problem, one will
have, in the context of greedy algorithms, the following:

A collection (set, list, etc) of candidates, e.g. nodes, edges in a graph,

etc.
A set of candidates which have already been `used'.
A predicate (solution) to test whether a given set of candidates give a
solution (not necessarily optimal).
A predicate (feasible) to test if a set of candidates can be extended to
a (not necessarily optimal) solution.
A selection function (select) which chooses some candidate which h
as not yet been used.
An objective function which assigns a value to a solution.

In other words: An optimisation problem involves finding a subset, S, from

a collection of candidates, C; the subset, S, must satisfy some specified
criteria, i.e. be a solution and be such that the objective function is optimised
by S. `Optimised' may mean

Minimised or Maximised

depending on the precise problem being solved. Greedy methods are

distinguished by the fact that the selection function assigns a numerical
value to each candidate, x, and chooses that candidate for which:

SELECT( x ) is largest

or SELECT( x ) is smallest

All Greedy Algorithms have exactly the same general form. A Greedy
Algorithm for a particular problem is specified by describing the predicates
`solution' and `feasible'; and the selection function `select'.
Consequently, Greedy Algorithms are often very easy to design for
optimisation problems.

The General Form of a Greedy Algorithm is

function select (C : candidate_set) return

candidate;

function solution (S : candidate_set) return

boolean;

function feasible (S : candidate_set) return

boolean;

--
***************************************************

function greedy (C : candidate_set) return

candidate_set is

x : candidate;

S : candidate_set;

begin

S := {};

while (not solution(S)) and C /= {} loop

x := select( C );

C := C - {x};

if feasible( S union {x} ) then

S := S union { x };

end if;
 end loop;

if solution( S ) then

return S;

else

return es;

end if;

end greedy;

As illustrative examples of the greedy paradigm we shall describe

algorithms for the following problems:

Minimal Spanning Tree.

Integer Knapsack.

For the first of these, the algorithm always returns an optimal solution.

Minimal Spanning Tree

The inputs for this problem is an (undirected) graph, G( V, E ) in which each

edge, e in E, has an associated positive edge length, denoted Length( e ).

The output is a spanning tree, T( V, F ) of G( V,E ) such that the total edge
length, is minimal amongst all the possible spanning trees of G( V,E ).

Note: An n-node tree, T is a connected n-node graph with exactly n-1 edges.

T( V,F ) is a spanning tree of G( V,E ) if and only if T is a tree and the edges
in F are a subset of the edges in E.

In terms of general template given previously:

The candidates are the edges of G(V,E).

A subset of edges, S, is a solution if the graph T(V,S) is a spanning
tree of G(V,E).
A subset of edges, S, is feasible if there is a spanning tree T(V,H) of
G(V,E) for which S sube H.
 The objective function which is to be minimised is the sum of the
edge lengths in a solution.
The select function chooses the candidate (i.e. edge) whose length is
smallest (from the remaining candidates).

The full algorithm, discovered by Kruskal, is:

function min_spanning_tree (E : edge_set)
return edge_set is
S : edge_set;
e : edge;
begin
S := (es;
while (H(V,S) not a tree)
and E /= {} loop
e := Shortest edge in E;
E := E - {e};
if H(V, S union {e}) is acyclic then
S := S union {e};
end if;
end loop;
return S;
end min_spanning_tree;
Before proving the correctness of this algorithm, we give an example of it
running.

The algorithm may be viewed as dividing the set of nodes, V, into n parts or
components:

{1} ; {2} ; ... ; {n}

An edge is added to the set S if and only if it joins two nodes which belong
to different components; if an edge is added to S then the two components
containing its endpoints are coalesced into a single component.

In this way, the algorithm stops when there is just a single component

{ 1, 2 ,..., n }

remaining.
Iteration Edge Components
0 - {1}; {2}; {3}; {4}; {5}; {6}; {7}
1 {1,2} {1,2}; {3}; {4}; {5}; {6}; {7}
2 {2,3} {1,2,3}; {4}; {5}; {6}; {7}
3 {4,5} {1,2,3}; {4,5}; {6}; {7}
4 {6,7} {1,2,3}; {4,5}; {6,7}
5 {1,4} {1,2,3,4,5}; {6,7}
6 {2,5} Not included (adds cycle)
7 {4,7} {1,2,3,4,5,6,7}
Question: How do we know that the resulting set of edges form a Minimal
Spanning Tree?

In order to prove this we need the following result.

For G(V,E) as before, a subset, F, of the edges E is called promising if F is a

subset of the edges in a minimal spanning tree of G(V,E).

Lemma: Let G(V,E) be as before and W be a subset of V.

Let F, a subset of E be a promising set of edges such that no edges in F has

exactly one endpoint in W.

If {p,q} in E-F is a shortest edge having exactly one of p or q in W then: the

set of edges F union { {p,q} } is promising.

Proof: Let T(V,H) be a minimal spanning tree of G(V,E) such that F is a

subset of H. Note that T exists since F is a promising set of edges.

Consider the edge e = {p,q} of the Lemma statement.

If e is in H then the result follows immediately, so suppose that e is not in H.

Assume that p is in W and q is not in W and consider the graph T(V, H union
{e}).

Since T is a tree the graph T (which contains one extra edge) must contain a
cycle that includes the (new) edge {p,q}.

Now since p is in W and q is not in W there must be some edge, e' = {p',q'}
in H which is also part of this cycle and is such that p' is in W and q' is not in
W.
Now, by the choice of e, we know that

Length ( e ) < = Length ( e' )

Removing the edge e' from T gives a new spanning tree of G(V,E).

The cost of this tree is exactly

cost( T ) - Length(e') + Length(e)

and this is < = cost(T).

T is a minimal spanning tree so either e and e' have the same length or this
case cannot occur. It follows that there is a minimal spanning tree containing
F union {e} and hence this set of edges is promising as claimed.

Theorem: Kruskal's algorithm always produces a minimal spanning tree.

Proof: We show by induction on k > = 0 - the number of edges in S at each

stage - that the set of edges in S is always promising.

Base (k = 0): S = {} and obviously the empty set of edges is promising.

Step: (< = k-1 implies k): Suppose S contains k-1 edges. Let e = {p,q} be the
next edge that would be added to S. Then:

p and q lie in different components.

{p,q} is a shortest such edge.

Let C be the component in which p lies. By the inductive hypothesis the set
S is promising. The Inductive Step now follows by invoking the Lemma,
with W = Set of nodes in C and F = S.

Integer Knapsack

In various forms this is a frequently arising optimisation problem. Input: A

set of items U = {u1, u2 ,..., uN}

each item having a given size s( ui ) and value v( ui ).

A capacity K.

Output: A subset B of U such that the sum over u in B of s(u) does not
exceed K and the sum over u in B of v(u) is maximised.

No fast algorithm guaranteed to solve this problem has yet been discovered.

It is considered extremely improbable that such an algorithm exists.

Using a greedy approach, however, we can find a solution whose value is at

worst 1/2 of the optimal value.

The items, U, are the candidates.

A subset, B, is a solution if the total size of B fits within the given
capacity, but adding any other item will exceed the capacity.
The objective function which is to be maximised is the total value.

The selection function chooses that item, ui for which

v( ui )
--------
s( ui )

is maximal
These yield the following greedy algorithm which approximately solves the
integer knapsack problem.

function knapsack (U : item_set;

K : integer )
return item_set is
C, S : item_set;
x : item;
begin
C := U; S := {};
while C /= {} loop
x := Item u in C such that
v(u)/s(u) is largest;
C := C - {x};
if ( sum over {u in S} s(u) ) + s(x) < = K
then
S := S union {x};
end if;
end loop;
return S;
end knapsack;

A very simple example shows that the method can fail to deliver an optimal
solution. Let

U = { u1, u2, u3 ,..., u12 }

s(u1) = 101 ; v(u1) = 102

s(ui) = v(ui) = 10 2 < = i < = 12

K = 110

Greedy solution: S = {u1}; Value is 102.

Optimal solution: S = U - {u1}; Value is 110.

Backtracking and Searching

In a number of applications graph structures occur. The graph may be an
explicit object in the problem instance as in:

Shortest Path Problem

Minimal Spanning Tree Problem

Graphs, however, may also occur implicitly as an abstract mechanism with

which to analyse problems and construct algorithms for these. Among the
many areas where such an approach has been used are:

Game Playing Programs

Theorem Proving Systems

Semantic Nets

Hypertext

...

Whether a graph is an explicit or implicit structure in describing a problem,

it is often the case that searching the graph structure may be necessary. Thus
it is required to have methods which

Can `mark' nodes in a graph which have already been `examined'.

Determine which node should be examined next.
Ensure that every node in the graph can (but not necessarily will) be
visited.

These requirements must be realised subject to the constraint that the search
process respects the structure of the graph.

That is to say, (With the exception of the first node inspected)

Any new node examined must be adjacent to some node that has
previously been visited.

So, search methods implicitly describe an ordering of the nodes in a given

graph.
One search method that occurs frequently with implicit graphs is the
technique known as

backtracking

Suppose a problem may be expressed in terms of detecting a particular class

of subgraph in a graph.

Then the backtracking approach to solving such a problem would be:

Scan each node of the graph, following a specific order, until

A subgraph constituting a solution has been found.

or
It is discovered that the subgraph built so far cannot be extended to be
a solution.

If (2) occurs then the search process is `backed-up' until a node is reached
from which a solution might still be found.

Simple Example

Knight's Tour

Given a natural number, n, describe how a Knight should be moved on an n

times n chessboard so that it visits every square exactly once and ends on its
starting square.

The implicit graph in this problem has n^2 nodes corresponding to each
position the Knight must occupy. There is an edge between two of these
nodes if the corresponding positions are `one move apart'. The sub-graph
that defines a solution is a cycle which contains each node of the implicit
graph.
Of course it is not necessary to construct this graph explicitly, in order to to
solve the problem. The algorithm below, recursively searches the graph,
labeling each square (i.e. node) in the order in which it is visited. In this
algorithm:

board is an n times n representation of the board; initiated to 0.

(x,y) are the coordinates (row, column) of the current square.
move is the number of squares visited so far.
ok is a Boolean indicating success or failure.
type chess_board is array (1..n,1..n) of integer;

procedure knight (board : in out chess_board;

x,y,move : in out integer;

ok : in out boolean) is

w, z : integer;

begin

if move = n^2+1 then

ok := ( (x,y) = (1,1) );

elsif board(x,y) /= 0 then

ok := false;

else

board(x,y) := move;

loop

(w,z) := Next position from (x,y);

knight(board, w, z, move+1, ok );

exit when (ok or No moves remain);

end loop;

if not ok then

board ( x,y ) :=0; -- Backtracking

end if;

end if;
end knight;

Depth-First Search

The Knight's Tour algorithm organises the search of the implicit graph using
a depth-first approach.

Depth-first search is one method of constructing a search tree for explicit

graphs.

Let G(V,E) be a connected graph. A search tree of G(V,E) is a spanning

tree, T(V, F) of G(V,E) in which the nodes of T are labelled with unique
values k (1 < = k < = |V|) which satisfy:

A distinguished node called the root is labelled 1.

If (p,q) is an edge of T then the label assigned to p is less than the
label assigned to q.

The labelling of a search tree prescribes the order in which the nodes of G
are to be scanned.

Given an undirected graph G(V,E), the depth-first search method constructs

a search tree using the following recursive algorithm.

procedure depth_first_search (G(V,E) : graph;

v : node;

lambda : integer;

T : in
outsearch_tree) is

begin

label(v) := lambda;

lambda := lambda+1;

for each w such that {v,w} mem E loop

 if label(w) = 0 then

Add edge {v,w} to T;

depth_first_search(G(V,E),w,lambda,T);

end if;

end loop;

end depth_fist_search;

--*******************************

-- Main Program Section

--******************************

begin

for w mem V loop

label( w ) := 0;

end loop;

lambda := 1;

depthfirstsearch ( G(V,E), v, lambda, T);

end;
If G( V,E ) is a directed graph then it is possible that not all of the nodes of
the graph are reachable from a single root node. To deal with this the
algorithm is modified by changing the `Main Program Section' to

begin
for each w in V loop
label( w ) := 0;
end loop;
lambda := 1;
for each v mem V loop
if label( v ) = 0 then
depthfirstsearch ( G(V,E),v,lambda,T );
end if;
end loop;
end;

The running time of both algorithms, input G( V,E ) is O( |E| ) since each
edge of the graph is examined only once.
It may be noted that the recursive form given, is a rather inefficient method
of implementing depth first search for explicit graphs.

Iterative versions exist, e.g. the method of Hopcroft and Tarjan which is
based on a 19th century algorithm discovered by Tremaux. Depth-first
search has a large number of applications in solving other graph based
problems, for example:

Topological Sorting

Connectivity Testing

Planarity Testing

One disadvantage of depth first search as a mechanism for searching implicit

graph structures, is that expanding some paths may result in the search
process never terminating because no solution can be reached from these.
For example this is a possible difficulty that arises when scanning proof
trees in Prolog implementations.

Breadth-first Search is another search method that is less likely to exhibit

such behaviour.

lambda := 1; -- First label

CurrentLevel := {v}; -- Root node

while CurrentLevel /= (es loop

for each v mem CurrentLevel loop

NextLevel := Nextlevel union

Unmarked neighbours of v;

if label( v ) = 0 then

label( v ) := lambda;

lambda := lambda + 1;

end if;

end loop;

CurrentLevel := NextLevel;

NextLevel := (es;

end loop;