Algorithm Design Paradigms

Techniques for the Design of Algorithms

The first part of this course is concerned with:

Algorithmic Paradigms

That is: Such methods are of interest because: Over the next few lectures we shall examine the following paradigms: 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


1. Count the number of basic operations performed by the algorithm on the worst-case input

A basic operation could be:

Simple Example:

n := 5;
    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'.

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

Examples of `input size':


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 )


while < condition > loop
end loop;

for i in 1..n loop
end loop

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


if < condition > then
end if;

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

We shall consider recursive procedures later in the course.


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:

1002 10050,00010,000
10002 10005 million100,000

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

51 millisec0.5 millisec1 millisec
100270years0.05 secs0.01 secs
10002970years5 secs0.1 secs


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)


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 )



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


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.


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)


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


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-&-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:

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


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


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
       if n <= n^-0 then
           Solve problem using Algorithm alpha;
           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:

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
      if n < = n0 then
         Solve problem without further
          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-&-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


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


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;
      middle := (start+finish)/2;
      if names(middle)=x then
          return numbers(middle);
      elsif X<names(middle) then
          return search(X,start,middle-1);
      else -- X>names(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-&-conquer algorithms, at which stage is this modification made?

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

Example 2

Closest Pair


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

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

A set of n points in the plane.


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:

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

function closest_pair (P: point set; n: in
teger )
                               return float is
   DELTA : float;
      if n = 2 then
         return distance from p(1) to p(2);
         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
         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 combine stage can be implemented by:

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:

(1-3) therefore describe a Divide-&-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;
   if n = 1 then
      return x(0)*y(0);
      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:

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
      if k = 0 or k = n then
         return 1;
         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:

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.

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, 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
  -- 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, 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: 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:

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 full algorithm, discovered by Kruskal, is:

function min_spanning_tree (E : edge_set)
                           return edge_set is
S : edge_set;
e : edge;
  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 }


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)

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:

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 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;
   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



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

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


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

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:

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:

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

  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;

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;

Thus each vertex labelled on the k'th iteration of the outer loop is `expanded' before any vertex found later.

PED Home Page