DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

UNIT III
Dynamic Programming: The general method, multistage graphs, All pairs-shortest
paths, single-source shortest paths: general weights, optimal Binary search trees, 0/1
knapsack, reliability Design, The traveling salesperson problem, matrix chain
multiplication.

Dynamic Programming
Dynamic programming is a name, coined by Richard Bellman in 1955. Dynamic
programming, as greedy method, is a powerful algorithm design technique that can
be used when the solution to the problem may be viewed as the result of a sequence
of decisions. In the greedy method we make irrevocable decisions one at a time,
using a greedy criterion. However, in dynamic programming we examine the decision
sequence to see whether an optimal decision sequence contains optimal decision
subsequence.

When optimal decision sequences contain optimal decision subsequences, we can

establish recurrence equations, called dynamic-programming recurrence equations,
that enable us to solve the problem in an efficient way.

Dynamic programming is based on the principle of optimality (also coined by

Bellman). The principle of optimality states that no matter whatever the initial state
and initial decision are, the remaining decision sequence must constitute an optimal
decision sequence with regard to the state resulting from the first decision. The
principle implies that an optimal decision sequence is comprised of optimal decision
subsequences. Since the principle of optimality may not hold for some formulations
of some problems, it is necessary to verify that it does hold for the problem being
solved. Dynamic programming cannot be applied when this principle does not hold.

The steps in a dynamic programming solution are:

 Verify that the principle of optimality holds

 Set up the dynamic-programming recurrence equations

 Solve the dynamic-programming recurrence equations for the value of the

optimal solution.

 Perform a trace back step in which the solution itself is constructed.

Dynamic programming differs from the greedy method since the greedy method
produces only one feasible solution, which may or may not be optimal, while dynamic
programming produces all possible sub-problems at most once, one of which
guaranteed to be optimal. Optimal solutions to sub-problems are retained in a table,
thereby avoiding the work of recomputing the answer every time a sub-problem is
encountered

The divide and conquer principle solve a large problem, by breaking it up into smaller
problems which can be solved independently. In dynamic programming this principle
is carried to an extreme: when we don't know exactly which smaller problems to
solve, we simply solve them all, then store the answers away in a table to be used
later in solving larger problems. Care is to be taken to avoid recomputing previously
computed values, otherwise the recursive program will have prohibitive complexity.

CSE Page 3
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

In some cases, the solution can be improved and in other cases, the dynamic
programming technique is the best approach.

CSE Page 3
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

Two difficulties may arise in any application of dynamic programming:

1. It may not always be possible to combine the solutions of smaller problems to

form the solution of a larger one.

2. The number of small problems to solve may be un-acceptably large.

There is no characterized precisely which problems can be effectively solved with

dynamic programming; there are many hard problems for which it does not seen to
be applicable, as well as many easy problems for which it is less efficient than
standard algorithms.

5.1 MULTI STAGE GRAPHS

A multistage graph G = (V, E) is a directed graph in which the vertices are

partitioned into k > 2 disjoint sets Vi, 1 < i < k. In addition, if <u, v> is an edge in E,
then u  Vi and v  Vi+1 for some i, 1 < i < k.

Let the vertex „s‟ is the source, and „t‟ the sink. Let c (i, j) be the cost of edge <i, j>.
The cost of a path from „s‟ to „t‟ is the sum of the costs of the edges on the path. The
multistage graph problem is to find a minimum cost path from „s‟ to „t‟. Each set Vi
defines a stage in the graph. Because of the constraints on E, every path from „s‟ to
„t‟ starts in stage 1, goes to stage 2, then to stage 3, then to stage 4, and so on, and
eventually terminates in stage k.

A dynamic programming formulation for a k-stage graph problem is obtained by first

noticing that every s to t path is the result of a sequence of k – 2 decisions. The ith
decision involves determining which vertex in v i+1, 1 < i < k - 2, is to be on the
path. Let c (i, j) be the cost of the path from source to destination. Then using the
forward approach, we obtain:

cost (i, j) = min {c (j, l) + cost (i + 1, l)}

l  Vi + 1
<j, l>  E

ALGORITHM:

Algorithm Fgraph (G, k, n, p)

// The input is a k-stage graph G = (V, E) with n vertices
// indexed in order or stages. E is a set of edges and c [i, j]
// is the cost of (i, j). p [1 : k] is a minimum cost path.
{
cost [n] := 0.0;
for j:= n - 1 to 1 step – 1 do
{ // compute cost [j]
let r be a vertex such that (j, r) is an edge
of G and c [j, r] + cost [r] is minimum;
cost [j] := c [j, r] + cost [r];
d [j] := r:
}
p [1] := 1; p [k] := n; // Find a minimum cost path.
for j := 2 to k - 1 do p [j] := d [p [j - 1]];
}

CSE Page 3
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

The multistage graph problem can also be solved using the backward approach.
Let bp(i, j) be a minimum cost path from vertex s to j vertex in V i. Let Bcost(i, j) be
the cost of bp(i, j). From the backward approach we obtain:

Bcost (i, j) = min { Bcost (i –1, l) + c (l, j)}

l  Vi - 1
<l, j>  E

Algorithm Bgraph (G, k, n, p)

// Same function as Fgraph
{
Bcost [1] := 0.0;
for j := 2 to n do
{ // Compute Bcost [j].
Let r be such that (r, j) is an edge of
G and Bcost [r] + c [r, j] is minimum;
Bcost [j] := Bcost [r] + c [r, j];
D [j] := r;
} //find a minimum cost path
p [1] := 1; p [k] := n;
for j:= k - 1 to 2 do p [j] := d [p [j + 1]];
}

Complexity Analysis:

The complexity analysis of the algorithm is fairly straightforward. Here, if G has E
edges, then the time for the first for loop is  (V +E).

EXAMPLE 1:

Find the minimum cost path from s to t in the multistage graph of five stages shown
below. Do this first using forward approach and then using backward approach.

2 4 6
2 6 9
9 2 5 4
1

3 4
7 7 2
7 10 12 t
s 1 3 3

4 11
2 5
5
8 11
11 6
5 8

FORWARD APPROACH:

We use the following equation to find the minimum cost path from s to t:

cost (i, j) = min {c (j, l) + cost (i + 1, l)}

l  Vi + 1
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

<j, l>  E
cost (1, 1) = min {c (1, 2) + cost (2, 2), c (1, 3) + cost (2, 3), c (1, 4) + cost (2, 4),
c (1, 5) + cost (2, 5)}
= min {9 + cost (2, 2), 7 + cost (2, 3), 3 + cost (2, 4), 2 + cost (2, 5)}

Now first starting with,

cost (2, 2) = min{c (2, 6) + cost (3, 6), c (2, 7) + cost (3, 7), c (2, 8) + cost (3, 8)}
= min {4 + cost (3, 6), 2 + cost (3, 7), 1 + cost (3, 8)}

cost (3, 6) = min {c (6, 9) + cost (4, 9), c (6, 10) + cost (4, 10)}
= min {6 + cost (4, 9), 5 + cost (4, 10)}

cost (4, 9) = min {c (9, 12) + cost (5, 12)} = min {4 + 0) = 4

cost (4, 10) = min {c (10, 12) + cost (5, 12)} = 2

Therefore, cost (3, 6) = min {6 + 4, 5 + 2} = 7

cost (3, 7) = min {c (7, 9) + cost (4, 9) , c (7, 10) + cost (4, 10)}
= min {4 + cost (4, 9), 3 + cost (4, 10)}

cost (4, 9) = min {c (9, 12) + cost (5, 12)} = min {4 + 0} = 4

Cost (4, 10) = min {c (10, 2) + cost (5, 12)} = min {2 + 0} = 2

Therefore, cost (3, 7) = min {4 + 4, 3 + 2} = min {8, 5} = 5

cost (3, 8) = min {c (8, 10) + cost (4, 10), c (8, 11) + cost (4, 11)}
= min {5 + cost (4, 10), 6 + cost (4 + 11)}

cost (4, 11) = min {c (11, 12) + cost (5, 12)} = 5

Therefore, cost (3, 8) = min {5 + 2, 6 + 5} = min {7, 11} = 7

Therefore, cost (2, 2) = min {4 + 7, 2 + 5, 1 + 7} = min {11, 7, 8} = 7

Therefore, cost (2, 3) = min {c (3, 6) + cost (3, 6), c (3, 7) + cost (3, 7)}
= min {2 + cost (3, 6), 7 + cost (3, 7)}
= min {2 + 7, 7 + 5} = min {9, 12} = 9

cost (2, 4) = min {c (4, 8) + cost (3, 8)} = min {11 + 7} = 18

cost (2, 5) = min {c (5, 7) + cost (3, 7), c (5, 8) + cost (3, 8)}
= min {11 + 5, 8 + 7} = min {16, 15} = 15

Therefore, cost (1, 1) = min {9 + 7, 7 + 9, 3 + 18, 2 + 15}

= min {16, 16, 21, 17} = 16

The minimum cost path is 16.

102
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

The path is 1 2 7 10 12

or
1 3 6 10 12

BACKWARD APPROACH:

We use the following equation to find the minimum cost path from t to s:

Bcost (i, J) = min {Bcost (i – 1, l) + c (l, J)}

l  vi – 1
<l, j>  E

Bcost (5, 12) = min {Bcost (4, 9) + c (9, 12), Bcost (4, 10) + c (10, 12),
Bcost (4, 11) + c (11, 12)}
= min {Bcost (4, 9) + 4, Bcost (4, 10) + 2, Bcost (4, 11) + 5}

Bcost (4, 9) = min {Bcost (3, 6) + c (6, 9), Bcost (3, 7) + c (7, 9)}
= min {Bcost (3, 6) + 6, Bcost (3, 7) + 4}

Bcost (3, 6) = min {Bcost (2, 2) + c (2, 6), Bcost (2, 3) + c (3, 6)}
= min {Bcost (2, 2) + 4, Bcost (2, 3) + 2}

Bcost (2, 2) = min {Bcost (1, 1) + c (1, 2)} = min {0 + 9} = 9

Bcost (2, 3) = min {Bcost (1, 1) + c (1, 3)} = min {0 + 7} = 7

Bcost (3, 6) = min {9 + 4, 7 + 2} = min {13, 9} = 9

Bcost (3, 7) = min {Bcost (2, 2) + c (2, 7), Bcost (2, 3) + c (3, 7),
Bcost (2, 5) + c (5, 7)}

Bcost (2, 5) = min {Bcost (1, 1) + c (1, 5)} = 2

Bcost (3, 7) = min {9 + 2, 7 + 7, 2 + 11} = min {11, 14, 13} = 11

Bcost (4, 9) = min {9 + 6, 11 + 4} = min {15, 15} = 15

Bcost (4, 10) = min {Bcost (3, 6) + c (6, 10), Bcost (3, 7) + c (7, 10),
Bcost (3, 8) + c (8, 10)}

Bcost (3, 8) = min {Bcost (2, 2) + c (2, 8), Bcost (2, 4) + c (4, 8),
Bcost (2, 5) + c (5, 8)}
Bcost (2, 4) = min {Bcost (1, 1) + c (1, 4)} = 3

Bcost (3, 8) = min {9 + 1, 3 + 11, 2 + 8} = min {10, 14, 10} = 10

Bcost (4, 10) = min {9 + 5, 11 + 3, 10 + 5} = min {14, 14, 15) = 14

Bcost (4, 11) = min {Bcost (3, 8) + c (8, 11)} = min {Bcost (3, 8) + 6}
= min {10 + 6} = 16

103
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

Bcost (5, 12) = min {15 + 4, 14 + 2, 16 + 5} = min {19, 16, 21} = 16.

EXAMPLE 2:

Find the minimum cost path from s to t in the multistage graph of five stages shown
below. Do this first using forward approach and then using backward approach.

4 1
3
2 4 7
6 7
5
3 6
s 1 5 2 9 t

2 5
3
3 8
6
8 2
6

SOLUTION:

FORWARD APPROACH:

cost (i, J) = min {c (j, l) + cost (i + 1, l)}

l  Vi + 1
<J, l> E

cost (1, 1) = min {c (1, 2) + cost (2, 2), c (1, 3) + cost (2, 3)}
= min {5 + cost (2, 2), 2 + cost (2, 3)}

cost (2, 2) = min {c (2, 4) + cost (3, 4), c (2, 6) + cost (3, 6)}
= min {3+ cost (3, 4), 3 + cost (3, 6)}

cost (3, 4) = min {c (4, 7) + cost (4, 7), c (4, 8) + cost (4, 8)}
= min {(1 + cost (4, 7), 4 + cost (4, 8)}

cost (4, 7) = min {c (7, 9) + cost (5, 9)} = min {7 + 0) = 7

cost (4, 8) = min {c (8, 9) + cost (5, 9)} = 3

Therefore, cost (3, 4) = min {8, 7} = 7

cost (3, 6) = min {c (6, 7) + cost (4, 7), c (6, 8) + cost (4, 8)}
= min {6 + cost (4, 7), 2 + cost (4, 8)} = min {6 + 7, 2 + 3} = 5

Therefore, cost (2, 2) = min {10, 8} = 8

cost (2, 3) = min {c (3, 4) + cost (3, 4), c (3, 5) + cost (3, 5), c (3, 6) + cost
(3,6)}

cost (3, 5) = min {c (5, 7) + cost (4, 7), c (5, 8) + cost (4, 8)}= min {6 + 7, 2 + 3}
=5

Therefore, cost (2, 3) = min {13, 10, 13} = 10

cost (1, 1) = min {5 + 8, 2 + 10} = min {13, 12} = 12

104
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

BACKWARD APPROACH:

Bcost (i, J) = min {Bcost (i – 1, l) = c (l, J)}

l  vi – 1
<l ,j> E

Bcost (5, 9) = min {Bcost (4, 7) + c (7, 9), Bcost (4, 8) + c (8, 9)}
= min {Bcost (4, 7) + 7, Bcost (4, 8) + 3}

Bcost (4, 7) = min {Bcost (3, 4) + c (4, 7), Bcost (3, 5) + c (5, 7),
Bcost (3, 6) + c (6, 7)}
= min {Bcost (3, 4) + 1, Bcost (3, 5) + 6, Bcost (3, 6) + 6}

Bcost (3, 4) = min {Bcost (2, 2) + c (2, 4), Bcost (2, 3) + c (3, 4)}
= min {Bcost (2, 2) + 3, Bcost (2, 3) + 6}

Bcost (2, 2) = min {Bcost (1, 1) + c (1, 2)} = min {0 + 5} = 5

Bcost (2, 3) = min (Bcost (1, 1) + c (1, 3)} = min {0 + 2} = 2

Therefore, Bcost (3, 4) = min {5 + 3, 2 + 6} = min {8, 8} = 8

Bcost (3, 5) = min {Bcost (2, 3) + c (3, 5)} = min {2 + 5} = 7

Bcost (3, 6) = min {Bcost (2, 2) + c (2, 6), Bcost (2, 3) + c (3, 6)}
= min {5 + 5, 2 + 8} = 10

Therefore, Bcost (4, 7) = min {8 + 1, 7 + 6, 10 + 6} = 9

Bcost (4, 8) = min {Bcost (3, 4) + c (4, 8), Bcost (3, 5) + c (5, 8),
Bcost (3, 6) + c (6, 8)}
= min {8 + 4, 7 + 2, 10 + 2} = 9

Therefore, Bcost (5, 9) = min {9 + 7, 9 + 3} = 12

All pairs shortest paths

In the all pairs shortest path problem, we are to find a shortest path between every
pair of vertices in a directed graph G. That is, for every pair of vertices (i, j), we are
to find a shortest path from i to j as well as one from j to i. These two paths are the
same when G is undirected.

When no edge has a negative length, the all-pairs shortest path problem may be
solved by using Dijkstra‟s greedy single source algorithm n times, once with each of
the n vertices as the source vertex.

The all pairs shortest path problem is to determine a matrix A such that A (i, j) is the
length of a shortest path from i to j. The matrix A can be obtained by solving n
single-source problems using the algorithm shortest Paths. Since each application of
this procedure requires O (n2) time, the matrix A can be obtained in O (n 3) time.

105
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

The dynamic programming solution, called Floyd‟s algorithm, runs in O (n 3) time.

Floyd‟s algorithm works even when the graph has negative length edges (provided
there are no negative length cycles).

The shortest i to j path in G, i ≠ j originates at vertex i and goes through some

intermediate vertices (possibly none) and terminates at vertex j. If k is an
intermediate vertex on this shortest path, then the subpaths from i to k and from k
to j must be shortest paths from i to k and k to j, respectively. Otherwise, the i to j
path is not of minimum length. So, the principle of optimality holds. Let A k (i, j)
represent the length of a shortest path from i to j going through no vertex of index
greater than k, we obtain:

Ak (i, j) = {min {min {Ak-1 (i, k) + Ak-1 (k, j)}, c (i, j)}
1<k<n

Algorithm All Paths (Cost, A, n)

// cost [1:n, 1:n] is the cost adjacency matrix of a graph which
// n vertices; A [I, j] is the cost of a shortest path from vertex
// i to vertex j. cost [i, i] = 0.0, for 1 < i < n.
{
for i := 1 to n do
for j:= 1 to n do
A [i, j] := cost [i, j]; // copy cost into A.
for k := 1 to n do
for i := 1 to n do
for j := 1 to n do
A [i, j] := min (A [i, j], A [i, k] + A [k, j]);
}

Complexity Analysis: A Dynamic programming algorithm based on this recurrence

involves in calculating n+1 matrices, each of size n x n. Therefore, the algorithm has
a complexity of O (n3).

Example 1:

Given a weighted digraph G = (V, E) with weight. Determine the length of the
shortest path between all pairs of vertices in G. Here we assume that there are no
cycles with zero or negative cost.

6
1 2 0 4 11
4
0 
Cost adjacency matrix (A ) = 6 0 2 
 
3 1 1 2
3  0 

3


General formula: min {Ak-1 (i, k) + Ak-1 (k, j)}, c (i, j)}
1<k<n

Solve the problem for different values of k = 1, 2 and 3

Step 1: Solving the equation for, k = 1;

106
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

A1 (1, 1) = min {(Ao (1, 1) + Ao (1, 1)), c (1, 1)} = min {0 + 0, 0} = 0

A1 (1, 2) = min {(Ao (1, 1) + Ao (1, 2)), c (1, 2)} = min {(0 + 4), 4} = 4
A1 (1, 3) = min {(Ao (1, 1) + Ao (1, 3)), c (1, 3)} = min {(0 + 11), 11} = 11
A1 (2, 1) = min {(Ao (2, 1) + Ao (1, 1)), c (2, 1)} = min {(6 + 0), 6} = 6
A1 (2, 2) = min {(Ao (2, 1) + Ao (1, 2)), c (2, 2)} = min {(6 + 4), 0)} = 0
A1 (2, 3) = min {(Ao (2, 1) + Ao (1, 3)), c (2, 3)} = min {(6 + 11), 2} = 2
A1 (3, 1) = min {(Ao (3, 1) + Ao (1, 1)), c (3, 1)} = min {(3 + 0), 3} = 3
A1 (3, 2) = min {(Ao (3, 1) + Ao (1, 2)), c (3, 2)} = min {(3 + 4), } = 7
A1 (3, 3) = min {(Ao (3, 1) + Ao (1, 3)), c (3, 3)} = min {(3 + 11), 0} = 0

0 4 11
 
A (1)
= 2 
6 0
3 7 0 

Step 2: Solving the equation for, K = 2;

A2 (1, 1) = min {(A1 (1, 2) + A1 (2, 1), c (1, 1)} = min {(4 + 6), 0} = 0
A2 (1, 2) = min {(A1 (1, 2) + A1 (2, 2), c (1, 2)} = min {(4 + 0), 4} = 4
A2 (1, 3) = min {(A1 (1, 2) + A1 (2, 3), c (1, 3)} = min {(4 + 2), 11} = 6
A2 (2, 1) = min {(A (2, 2) + A (2, 1), c (2, 1)} = min {(0 + 6), 6} = 6
A2 (2, 2) = min {(A (2, 2) + A (2, 2), c (2, 2)} = min {(0 + 0), 0} = 0
A2 (2, 3) = min {(A (2, 2) + A (2, 3), c (2, 3)} = min {(0 + 2), 2} = 2
A2 (3, 1) = min {(A (3, 2) + A (2, 1), c (3, 1)} = min {(7 + 6), 3} = 3
A2 (3, 2) = min {(A (3, 2) + A (2, 2), c (3, 2)} = min {(7 + 0), 7} = 7
A2 (3, 3) = min {(A (3, 2) + A (2, 3), c (3, 3)} = min {(7 + 2), 0} = 0

0 4 6 
 
A (2)
= 6 0 2 

3 7 0 

Step 3: Solving the equation for, k = 3;

A3 (1, 1) = min {A2 (1, 3) + A2 (3, 1), c (1, 1)} = min {(6 + 3), 0} = 0
A3 (1, 2) = min {A2 (1, 3) + A2 (3, 2), c (1, 2)} = min {(6 + 7), 4} = 4
A3 (1, 3) = min {A2 (1, 3) + A2 (3, 3), c (1, 3)} = min {(6 + 0), 6} = 6
A3 (2, 1) = min {A2 (2, 3) + A2 (3, 1), c (2, 1)} = min {(2 + 3), 6} = 5
A3 (2, 2) = min {A2 (2, 3) + A2 (3, 2), c (2, 2)} = min {(2 + 7), 0} = 0
A3 (2, 3) = min {A2 (2, 3) + A2 (3, 3), c (2, 3)} = min {(2 + 0), 2} = 2
A3 (3, 1) = min {A2 (3, 3) + A2 (3, 1), c (3, 1)} = min {(0 + 3), 3} = 3
A3 (3, 2) = min {A2 (3, 3) + A2 (3, 2), c (3, 2)} = min {(0 + 7), 7} = 7

107
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

A3 (3, 3) = min {A2 (3, 3) + A2 (3, 3), c (3, 3)} = min {(0 + 0), 0} = 0

0 4 6 
 
A(3) = 5
 0 2 
3 7 0 


TRAVELLING SALESPERSON PROBLEM

Let G = (V, E) be a directed graph with edge costs Cij. The variable cij is defined such
that cij > 0 for all I and j and cij =  if < i, j>  E. Let |V| = n and assume n > 1. A
tour of G is a directed simple cycle that includes every vertex in V. The cost of a tour
is the sum of the cost of the edges on the tour. The traveling sales person problem is
to find a tour of minimum cost. The tour is to be a simple path that starts and ends
at vertex 1.

Let g (i, S) be the length of shortest path starting at vertex i, going through all
vertices in S, and terminating at vertex 1. The function g (1, V – {1}) is the length of
an optimal salesperson tour. From the principal of optimality it follows that:

g1, V -  1  min c1k  g  k, V   1, k  -- 1

2kn

Generalizing equation 1, we obtain (for i  S)

g i, S   minci j  g i, S   j   -- 2

j S

The Equation can be solved for g (1, V – 1}) if we know g (k, V – {1, k}) for all
choices of k.

Complexity Analysis:

For each value of |S| there are n – 1 choices for i. The number of distinct sets S of
n  2
size k not including 1 and i is .
 k 
 
Hence, the total number of g (i, S)‟s to be computed before computing g (1, V – {1})
is:
n 1  n  2 
 n1 k 
k  0  

To calculate this sum, we use the binominal theorem:
(n  2 (n  2 (n  2 (n  2)
(n – 1)                
 0   1   2  (n  2)

According to the binominal theorem:

(n  2 (n  2 (n  2 (n  2)
                 = 2n - 2
 0   1   2  (n  2)

Therefore,

108
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

n 1  n  2 
 n1 k   (n  1) 2n  2
k  0  


This is Φ (n 2n-2), so there are exponential number of calculate. Calculating one g (i,
S) require finding the minimum of at most n quantities. Therefore, the entire
algorithm is Φ (n2 2n-2). This is better than enumerating all n! different tours to find
the best one. So, we have traded on exponential growth for a much smaller
exponential growth. The most serious drawback of this dynamic programming
solution is the space needed, which is O (n 2 n). This is too large even for modest
values of n.

Example 1:

For the following graph find minimum cost tour for the traveling salesperson
problem:

1 2
0 10 15 20
The cost adjacency matrix = 
5
0 9 10 

6 13 0 12 
 
8 9 0 
3 4 8


Let us start the tour from vertex 1:

g (1, V – {1}) = min {c1k + g (k, V – {1, K})} - (1)

2<k<n

More generally writing:

g (i, s) = min {cij + g (J, s – {J})} - (2)

Clearly, g (i, ) = ci1 , 1 ≤ i ≤ n. So,

g (2, ) = C21 = 5

g (3, ) = C31 = 6

g (4, ) = C41 = 8

Using equation – (2) we obtain:

g (1, {2, 3, 4}) = min {c12 + g (2, {3, 4}, c13 + g (3, {2, 4}), c14 + g (4, {2, 3})}

g (2, {3, 4}) = min {c23 + g (3, {4}), c24 + g (4, {3})}
= min {9 + g (3, {4}), 10 + g (4, {3})}

g (3, {4}) = min {c34 + g (4, )} = 12 + 8 = 20

g (4, {3}) = min {c43 + g (3, )} = 9 + 6 = 15

109
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

Therefore, g (2, {3, 4}) = min {9 + 20, 10 + 15} = min {29, 25} = 25

g (3, {2, 4}) = min {(c32 + g (2, {4}), (c34 + g (4, {2})}

g (2, {4}) = min {c24 + g (4, )} = 10 + 8 = 18

g (4, {2}) = min {c42 + g (2, )} = 8 + 5 = 13

Therefore, g (3, {2, 4}) = min {13 + 18, 12 + 13} = min {41, 25} = 25

g (4, {2, 3}) = min {c42 + g (2, {3}), c43 + g (3, {2})}

g (2, {3}) = min {c23 + g (3, } = 9 + 6 = 15

g (3, {2}) = min {c32 + g (2, } = 13 + 5 = 18

Therefore, g (4, {2, 3}) = min {8 + 15, 9 + 18} = min {23, 27} = 23

g (1, {2, 3, 4}) = min {c12 + g (2, {3, 4}), c13 + g (3, {2, 4}), c14 + g (4, {2, 3})}
= min {10 + 25, 15 + 25, 20 + 23} = min {35, 40, 43} = 35

The optimal tour for the graph has length = 35

The optimal tour is: 1, 2, 4, 3, 1.

OPTIMAL BINARY SEARCH TREE

Let us assume that the given set of identifiers is {a1, . . . , an} with a1 < a2 < <
an. Let p (i) be the probability with which we search for ai. Let q (i) be the probability
that the identifier x being searched for is such that ai < x < ai+1, 0 < i < n (assume
a0 = -  and an+1 = +). We have to arrange the identifiers in a binary search tree in
a way that minimizes the expected total access time.
In a binary search tree, the number of comparisons needed to access an element at
depth 'd' is d + 1, so if 'ai' is placed at depth 'di', then we want to minimize:
n

 Pi (1  di ) .
i 1

Let P (i) be the probability with which we shall be searching for 'ai'. Let Q (i) be the
probability of an un-successful search. Every internal node represents a point where
a successful search may terminate. Every external node represents a point where an
unsuccessful search may terminate.

The expected cost contribution for the internal node for 'ai' is:

P (i) * level (ai ) .

Unsuccessful search terminate with I = 0 (i.e at an external node). Hence the cost
contribution for this node is:

Q (i) * level ((Ei) - 1)

The expected cost of binary search tree is:

110
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

n n

 P(i) * level (a )   Q (i) * level ((E )  1)

i i
i 1 i 0

Given a fixed set of identifiers, we wish to create a binary search tree organization.
We may expect different binary search trees for the same identifier set to have
different performance characteristics.

The computation of each of these c(i, j)‟s requires us to find the minimum of m
quantities. Hence, each such c(i, j) can be computed in time O(m). The total time for
all c(i, j)‟s with j – i = m is therefore O(nm – m2).

The total time to evaluate all the c(i, j)‟s and r(i, j)‟s is therefore:

 nm  m   O n 
1m n
2 3

Example 1: The possible binary search trees for the identifier set (a1, a2, a3) = (do,
if, stop) are as follows. Given the equal probabilities p (i) = Q (i) = 1/7 for all i, we
have:
st o p if

if do st o p

do

Tree 2
Tree 1

do do

if st o p

st o p if

Tree 3 T ree 4

1 1 1  1 1 1 1 
Cost (tree # 1) = x1 x2 x3   x1 x2 x3 x3 
   
 

 7 7 7   7 7 7 7 
1  2  3 1  2  3  3 6  9 15
=   
7 7 7 7 1
1 1 1  1 1 1 
Cost (tree # 2) = x 1  x 2  x2   x 2  x 2  x 2  x2 


  

7 7
 

 7 7 7  7 7 

1  2 2 2  2  2  2 5  8 13
=   
7 7 7 7

111
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

1 1 1  1 1 1 1 
Cost (tree # 3) = x1 x2 x3   x1 x2 x3 
  


7 7 7   7 7 x 3 

 7 7
1 23 1 2 33 6 9 15
=   
7 7 7 7 1
1 1 1  1 1 1 
Cost (tree # 4) = x1 x2 x3  x1 x2 x3 x3 
  


 7 7 7   7 7 7 7 


1 23 1 2 33 6 9 15
=   
7 7 7 7

Huffman coding tree solved by a greedy algorithm has a limitation of having the data
only at the leaves and it must not preserve the property that all nodes to the left of
the root have keys, which are less etc. Construction of an optimal binary search tree
is harder, because the data is not constrained to appear only at the leaves, and also
because the tree must satisfy the binary search tree property and it must preserve
the property that all nodes to the left of the root have keys, which are less.
A dynamic programming solution to the problem of obtaining an optimal binary
search tree can be viewed by constructing a tree as a result of sequence of decisions
by holding the principle of optimality. A possible approach to this is to make a
decision as which of the ai's be arraigned to the root node at 'T'. If we choose 'ak'
then is clear that the internal nodes for a1, a2, . . . . . ak-1 as well as the external
nodes for the classes Eo, E1, . . . . . . . Ek-1 will lie in the left sub tree, L, of the root.
The remaining nodes will be in the right subtree, R. The structure of an optimal
binary search tree is:

ak

L R

K K
Cost (L) =  P(i)* level (a )   Q(i)* level (E )  1
i i


i 1 i 0

n n
Cost (R) =  P(i)* level (a )   Q(i)* level (E )  1
i i
i K i K

The C (i, J) can be computed as:

C (i, J) = min {C (i, k-1) + C (k, J) + P (K) + w (i, K-1) + w (K, J)}
i<k<J

= min {C (i, K-1) + C (K, J)} + w (i, J) -- (1)

i<k<J

Where W (i, J) = P (J) + Q (J) + w (i, J-1) -- (2)

Initially C (i, i) = 0 and w (i, i) = Q (i) for 0 < i < n.

Equation (1) may be solved for C (0, n) by first computing all C (i, J) such that J - i =
1
Next, we can compute all C (i, J) such that J - i = 2, Then all C (i, J) with J - i = 3
and so on.
112
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

C (i, J) is the cost of the optimal binary search tree 'T ij' during computation we record
the root R (i, J) of each tree 'Tij'. Then an optimal binary search tree may be
constructed from these R (i, J). R (i, J) is the value of 'K' that minimizes equation (1).

We solve the problem by knowing W (i, i+1), C (i, i+1) and R (i, i+1), 0 ≤ i < 4;
Knowing W (i, i+2), C (i, i+2) and R (i, i+2), 0 ≤ i < 3 and repeating until W (0, n),
C (0, n) and R (0, n) are obtained.

The results are tabulated to recover the actual tree.

Example 1:

Let n = 4, and (a1, a2, a3, a4) = (do, if, need, while) Let P (1: 4) = (3, 3, 1, 1) and Q
(0: 4) = (2, 3, 1, 1, 1)

Solution:

Table for recording W (i, j), C (i, j) and R (i, j):

Column
0 1 2 3 4
Row
0 2, 0, 0 3, 0, 0 1, 0, 0 1, 0, 0, 1, 0, 0

1 8, 8, 1 7, 7, 2 3, 3, 3 3, 3, 4

2 12, 19, 1 9, 12, 2 5, 8, 3

3 14, 25, 2 11, 19, 2

4 16, 32, 2

This computation is carried out row-wise from row 0 to row 4. Initially, W (i, i) = Q
(i) and C (i, i) = 0 and R (i, i) = 0, 0 < i < 4.

Solving for C (0, n):

First, computing all C (i, j) such that j - i = 1; j = i + 1 and as 0 < i < 4; i = 0, 1, 2

and 3; i < k ≤ J. Start with i = 0; so j = 1; as i < k ≤ j, so the possible value for
k=1

W (0, 1) = P (1) + Q (1) + W (0, 0) = 3 + 3 + 2 = 8

C (0, 1) = W (0, 1) + min {C (0, 0) + C (1, 1)} = 8
R (0, 1) = 1 (value of 'K' that is minimum in the above equation).

Next with i = 1; so j = 2; as i < k ≤ j, so the possible value for k = 2

W (1, 2) = P (2) + Q (2) + W (1, 1) = 3 + 1 + 3 = 7

C (1, 2) = W (1, 2) + min {C (1, 1) + C (2, 2)} = 7
R (1, 2) = 2

Next with i = 2; so j = 3; as i < k ≤ j, so the possible value for k = 3

113
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

W (2, 3) = P (3) + Q (3) + W (2, 2) = 1 + 1 + 1 = 3

C (2, 3) = W (2, 3) + min {C (2, 2) + C (3, 3)} = 3 + [(0 + 0)] = 3
R (2, 3) = 3

Next with i = 3; so j = 4; as i < k ≤ j, so the possible value for k = 4

W (3, 4) = P (4) + Q (4) + W (3, 3) = 1 + 1 + 1 = 3

C (3, 4) = W (3, 4) + min {[C (3, 3) + C (4, 4)]} = 3 + [(0 + 0)] = 3
R (3, 4) = 4

Second, Computing all C (i, j) such that j - i = 2; j = i + 2 and as 0 < i < 3; i = 0,

1, 2; i < k ≤ J. Start with i = 0; so j = 2; as i < k ≤ J, so the possible values for k =
1 and 2.

W (0, 2) = P (2) + Q (2) + W (0, 1) = 3 + 1 + 8 = 12

C (0, 2) = W (0, 2) + min {(C (0, 0) + C (1, 2)), (C (0, 1) + C (2, 2))}
= 12 + min {(0 + 7, 8 + 0)} = 19
R (0, 2) = 1
Next, with i = 1; so j = 3; as i < k ≤ j, so the possible value for k = 2 and 3.

W (1, 3) = P (3) + Q (3) + W (1, 2) = 1 + 1+ 7 = 9

C (1, 3) = W (1, 3) + min {[C (1, 1) + C (2, 3)], [C (1, 2) + C (3, 3)]}
= W (1, 3) + min {(0 + 3), (7 + 0)} = 9 + 3 = 12
R (1, 3) = 2

Next, with i = 2; so j = 4; as i < k ≤ j, so the possible value for k = 3 and 4.

W (2, 4) = P (4) + Q (4) + W (2, 3) = 1 + 1 + 3 = 5

C (2, 4) = W (2, 4) + min {[C (2, 2) + C (3, 4)], [C (2, 3) + C (4, 4)]
= 5 + min {(0 + 3), (3 + 0)} = 5 + 3 = 8
R (2, 4) = 3

Third, Computing all C (i, j) such that J - i = 3; j = i + 3 and as 0 < i < 2; i = 0, 1;

i < k ≤ J. Start with i = 0; so j = 3; as i < k ≤ j, so the possible values for k = 1, 2
and 3.

W (0, 3) = P (3) + Q (3) + W (0, 2) = 1 + 1 + 12 = 14

C (0, 3) = W (0, 3) + min {[C (0, 0) + C (1, 3)], [C (0, 1) + C (2, 3)],
[C (0, 2) + C (3, 3)]}
= 14 + min {(0 + 12), (8 + 3), (19 + 0)} = 14 + 11 = 25
R (0, 3) = 2

Start with i = 1; so j = 4; as i < k ≤ j, so the possible values for k = 2, 3 and 4.

W (1, 4) = P (4) + Q (4) + W (1, 3) = 1 + 1 + 9 = 11

C (1, 4) = W (1, 4) + min {[C (1, 1) + C (2, 4)], [C (1, 2) + C (3, 4)],
[C (1, 3) + C (4, 4)]}
= 11 + min {(0 + 8), (7 + 3), (12 + 0)} = 11 + 8 = 19
R (1, 4) = 2

Fourth, Computing all C (i, j) such that j - i = 4; j = i + 4 and as 0 < i < 1; i = 0;

i < k ≤ J.

Start with i = 0; so j = 4; as i < k ≤ j, so the possible values for k = 1, 2, 3 and 4.

114
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

W (0, 4) = P (4) + Q (4) + W (0, 3) = 1 + 1 + 14 = 16

C (0, 4) = W (0, 4) + min {[C (0, 0) + C (1, 4)], [C (0, 1) + C (2, 4)],
[C (0, 2) + C (3, 4)], [C (0, 3) + C (4, 4)]}
= 16 + min [0 + 19, 8 + 8, 19+3, 25+0] = 16 + 16 = 32
R (0, 4) = 2

From the table we see that C (0, 4) = 32 is the minimum cost of a binary search tree
for (a1, a2, a3, a4). The root of the tree 'T04' is 'a2'.

Hence the left sub tree is 'T01' and right sub tree is T24. The root of 'T01' is 'a1' and the
root of 'T24' is a3.

The left and right sub trees for 'T01' are 'T00' and 'T11' respectively. The root of T01 is
'a1'

The left and right sub trees for T24 are T22 and T34 respectively.

The root of T24 is 'a3'.

The root of T22 is null

The root of T34 is a4.

a2
T04 if

a1 a3
T 01 T24 do read

a4
T00 T11 T22 T34 while

Example 2:

Consider four elements a1, a2, a3 and a4 with Q0 = 1/8, Q1 = 3/16, Q2 = Q3 = Q4 =

1/16 and p1 = 1/4, p2 = 1/8, p3 = p4 =1/16. Construct an optimal binary search tree.
Solving for C (0, n):

First, computing all C (i, j) such that j - i = 1; j = i + 1 and as 0 < i < 4; i = 0, 1, 2

and 3; i < k ≤ J. Start with i = 0; so j = 1; as i < k ≤ j, so the possible value for
k=1

W (0, 1) = P (1) + Q (1) + W (0, 0) = 4 + 3 + 2 = 9

C (0, 1) = W (0, 1) + min {C (0, 0) + C (1, 1)} = 9 + [(0 + 0)] = 9
R (0, 1) = 1 (value of 'K' that is minimum in the above equation).

Next with i = 1; so j = 2; as i < k ≤ j, so the possible value for k = 2

W (1, 2) = P (2) + Q (2) + W (1, 1) = 2 + 1 + 3 = 6

C (1, 2) = W (1, 2) + min {C (1, 1) + C (2, 2)} = 6 + [(0 + 0)] = 6
R (1, 2) = 2

Next with i = 2; so j = 3; as i < k ≤ j, so the possible value for k = 3

W (2, 3) = P (3) + Q (3) + W (2, 2) = 1 + 1 + 1 = 3

C (2, 3) = W (2, 3) + min {C (2, 2) + C (3, 3)} = 3 + [(0 + 0)] = 3

115
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

R (2, 3) = 3

Next with i = 3; so j = 4; as i < k ≤ j, so the possible value for k = 4

W (3, 4) = P (4) + Q (4) + W (3, 3) = 1 + 1 + 1 = 3

C (3, 4) = W (3, 4) + min {[C (3, 3) + C (4, 4)]} = 3 + [(0 + 0)] = 3
R (3, 4) = 4

Second, Computing all C (i, j) such that j - i = 2; j = i + 2 and as 0 < i < 3; i = 0,

1, 2; i < k ≤ J

Start with i = 0; so j = 2; as i < k ≤ j, so the possible values for k = 1 and 2.

W (0, 2) = P (2) + Q (2) + W (0, 1) = 2 + 1 + 9 = 12

C (0, 2) = W (0, 2) + min {(C (0, 0) + C (1, 2)), (C (0, 1) + C (2, 2))}
= 12 + min {(0 + 6, 9 + 0)} = 12 + 6 = 18
R (0, 2) = 1
Next, with i = 1; so j = 3; as i < k ≤ j, so the possible value for k = 2 and 3.

W (1, 3) = P (3) + Q (3) + W (1, 2) = 1 + 1+ 6 = 8

C (1, 3) = W (1, 3) + min {[C (1, 1) + C (2, 3)], [C (1, 2) + C (3, 3)]}
= W (1, 3) + min {(0 + 3), (6 + 0)} = 8 + 3 = 11
R (1, 3) = 2

Next, with i = 2; so j = 4; as i < k ≤ j, so the possible value for k = 3 and 4.

W (2, 4) = P (4) + Q (4) + W (2, 3) = 1 + 1 + 3 = 5

C (2, 4) = W (2, 4) + min {[C (2, 2) + C (3, 4)], [C (2, 3) + C (4, 4)]
= 5 + min {(0 + 3), (3 + 0)} = 5 + 3 = 8
R (2, 4) = 3

Third, Computing all C (i, j) such that J - i = 3; j = i + 3 and as 0 < i < 2; i = 0, 1;

i < k ≤ J. Start with i = 0; so j = 3; as i < k ≤ j, so the possible values for k = 1, 2
and 3.

W (0, 3) = P (3) + Q (3) + W (0, 2) = 1 + 1 + 12 = 14

C (0, 3) = W (0, 3) + min {[C (0, 0) + C (1, 3)], [C (0, 1) + C (2, 3)],
[C (0, 2) + C (3, 3)]}
= 14 + min {(0 + 11), (9 + 3), (18 + 0)} = 14 + 11 = 25
R (0, 3) = 1

Start with i = 1; so j = 4; as i < k ≤ j, so the possible values for k = 2, 3 and 4.

W (1, 4) = P (4) + Q (4) + W (1, 3) = 1 + 1 + 8 = 10

C (1, 4) = W (1, 4) + min {[C (1, 1) + C (2, 4)], [C (1, 2) + C (3, 4)],
[C (1, 3) + C (4, 4)]}
= 10 + min {(0 + 8), (6 + 3), (11 + 0)} = 10 + 8 = 18
R (1, 4) = 2

Fourth, Computing all C (i, j) such that J - i = 4; j = i + 4 and as 0 < i < 1; i = 0;

i < k ≤ J. Start with i = 0; so j = 4; as i < k ≤ j, so the possible values for k = 1, 2,
3 and 4.

W (0, 4) = P (4) + Q (4) + W (0, 3) = 1 + 1 + 14 = 16

C (0, 4) = W (0, 4) + min {[C (0, 0) + C (1, 4)], [C (0, 1) + C (2, 4)],
[C (0, 2) + C (3, 4)], [C (0, 3) + C (4, 4)]}

116
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

= 16 + min [0 + 18, 9 + 8, 18 + 3, 25 + 0] = 16 + 17 = 33
R (0, 4) = 2

Table for recording W (i, j), C (i, j) and R (i, j)

Column
0 1 2 3 4
Row
0 2, 0, 0 1, 0, 0 1, 0, 0 1, 0, 0, 1, 0, 0

1 9, 9, 1 6, 6, 2 3, 3, 3 3, 3, 4

2 12, 18, 1 8, 11, 2 5, 8, 3

3 14, 25, 2 11, 18, 2

4 16, 33, 2

From the table we see that C (0, 4) = 33 is the minimum cost of a binary search tree
for (a1, a2, a3, a4)

The root of the tree 'T04' is 'a2'.

Hence the left sub tree is 'T01' and right sub tree is T24. The root of 'T01' is 'a1' and the
root of 'T24' is a3.

The left and right sub trees for 'T01' are 'T00' and 'T11' respectively. The root of T01 is
'a1'

The left and right sub trees for T24 are T22 and T34 respectively.

The root of T24 is 'a3'.

The root of T22 is null.

The root of T34 is a4.

a2
T 04 a2

a1 a3
T 01 T 24 a1 a3

a4
T 00 T 11 T 22 T 34 a4

Example 3:

WORD PROBABILITY
A 4
B 2
C 1
D 3
E 5
F 2
G 1

117
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

and all other elements have zero probability.

Solving c(0,n):

First computing all c(i, j) such that j- i = 1;j = i +1 and as 0 ≤ i < 7; i = 0, 1, 2, 3,

4, 5 and 6; i < k ≤ j. Start with i = 0 ; so j = 1; as i < k ≤ j, so the possible value
for k = 1

W(0, 1) = P(1) + Q(1)+W(0, 0) = 4+0+0 = 4

C(0, 1) = W(0, 1)+ min {C (0, 0) + C(1, 1) }=4 + [ (0 + 0 ) ] = 4
R(0, 1) = 1

next with i = 1 ; so j = 2; as i < k ≤ j, so the possible value for k = 2

W(1, 2) = P(2) + Q(2)+W(1, 1) = 2+0+0 = 2

C(1, 2) = W(1, 2)+ min {C (1, 1) + C(2, 2) }=2 + [ (0 + 0 ) ] = 2
R(1, 2) = 2
next with i = 2 ; so j = 3; as i < k ≤ j, so the possible value for k = 3

W(2, 3) = P(3) + Q(3)+W(2, 2) = 1+0+0 = 1

C(2, 3) = W(2, 3)+ min {C (2, 2) + C(3, 3) }=1 + [ (0 + 0 ) ] = 1
R(2, 3) = 3

next with i = 3 ; so j = 4; as i < k ≤ j, so the possible value for k = 4

W(3, 4) = P(4) + Q(4)+W(3, 3) = 3+0+0 = 3

C(3, 4) = W(3, 4)+ min {C (3, 4) + C(4, 4) }=3 + [ (0 + 0 ) ] = 3
R(3, 4) = 4

next with i = 4 ; so j = 5; as i < k ≤ j, so the possible value for k = 5

W(4, 5) = P(5) + Q(5)+W(4, 4) = 5+0+0 = 5

C(4, 5) = W(4, 5)+ min {C (4, 4) + C(5, 5) }=5 + [ (0 + 0 ) ] = 5
R(4, 5) = 5

next with i = 5; so j = 6; as i < k ≤ j, so the possible value for k = 6

W(5, 6) = P(6) + Q(6)+W(5, 5) = 2+0+0 = 2

C(5, 6) = W(5, 6)+ min {C (5, 5) + C(6, 6) }=2 + [ (0 + 0 ) ] = 2
R(5, 6) = 6

next with i = 6; so j = 7; as i < k ≤ j, so the possible value for k = 7

W(6, 7) = P(7) + Q(7)+W(6, 6) = 1+0+0 = 1

C(6, 7) = W(6, 7)+ min {C (6, 6) + C(7, 7) }=1 + [ (0 + 0 ) ] = 1
R(6, 7) = 7

Second, computing all c(i, j) such that j - i = 2 ;j = i + 2 and as 0 ≤ i < 6; i = 0,

1, 2, 3, 4 and 5; i < k ≤ j; Start with i = 0 ; so j = 2; as i < k ≤ j, so the possible
values for k = 1 and 2.

W(0, 2) = P(2) + Q(2)+W(0, 1) = 2 + 0 + 4 = 6

C(0, 2) = W(0, 2)+ min {C (0, 0) + C(1, 2) ,C(0, 1) + C(2, 2)}
= 6 +min{ 0 + 2, 4 + 0} = 8
R(0, 2) = 1

118
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

next with i = 1 ; so j = 3; as i < k ≤ j, so the possible values for k = 2 and 3.

W(1, 3) = P(3) + Q(3) +W(1, 2) = 1+ 0 + 2 = 3

C(1, 3) = W(1, 3)+ min {C (1, 1) + C(2,3) ,C(1, 2) + C(3, 3)}
= 3 +min{ 0 + 1, 2 + 0} = 4
R(1, 3) = 2

next with i = 2 ; so j = 4; as i < k ≤ j, so the possible values for k = 3 and 4.

W(2, 4) = P(4) + Q(4) +W(2, 3) = 3+ 0 + 1 = 4

C(2, 4) = W(2, 4)+ min {C (2, 2) + C(3,4) ,C(2, 3) + C(4, 4)}
= 4 +min{ 0 + 3, 1 + 0} = 5
R(2, 4) = 4
next with i = 3 ; so j = 5; as i < k ≤ j, so the possible values for k = 4 and 5.

W(3, 5) = P(5) + Q(5)+W(3, 4) = 5+ 0 + 3 =8

C(3, 5) = W(3, 5)+ min {C (3, 3) + C(4,5) ,C(3,4) + C(5, 5)}
= 8 +min{ 0 + 5, 3 + 0} = 11
R(3, 5) = 5
next with i = 4 ; so j = 6; as i < k ≤ j, so the possible values for k = 5 and 6.

W(4, 6) = P(6) + Q(6)+W(4, 5) = 2+ 0 + 5 = 7

C(4, 6) = W(4, 6)+ min {C (4, 4) + C(5,6) ,C(4, 5) + C(6, 6)}
= 7 +min{ 0 + 2, 5 + 0} = 9
R(4, 6) = 5

next with i = 5 ; so j = 7; as i < k ≤ j, so the possible values for k = 6 and 7.

W(5, 7) = P(7) + Q(7)+W(5, 6) = 1+ 0 + 2 = 3

C(5, 7) = W(5, 7)+ min {C (5, 5) + C(6,7) ,C(5, 6) + C(7, 7)}
= 3 +min{ 0 + 1, 2 + 0} = 4
R(5, 7) = 6

Third, computing all c(i, j) such that j – i = 3 ;j = i + 3 and as 0 ≤ i < 5 ; i = 0, 1,

2, 3, 4 and I < k ≤ j.

Start with i = 0 ; so j = 3; as i < k ≤ j, so the possible values for k = 1,2 and 3.

W(0, 3) = P(3) + Q(3)+W(0, 2) = 1+ 0 + 6 = 7

C(0, 3) = W(0, 3)+ min {C (0, 0) + C(1,3) ,C(0, 1) + C(2, 3),C(0, 2) + C(3, 3)}
= 7 +min{ 0 + 4, 4 + 1, 8 + 0} = 7
R(0, 3) = 1

next with i = 1 ; so j = 4; as i < k ≤ j, so the possible values for k = 2,3 and 4.

W(1, 4) = P(4) + Q(4)+W(1, 3) = 3+ 0 + 3 = 6

C(1, 4) = W(1, 4)+ min {C (1, 1) + C(2, 4) ,C(1, 2) + C(3, 4),C(1, 3) + C(4, 4)}
= 6 +min{ 0 + 5, 2 + 3, 4 + 0} = 10
R(1, 4) = 4

next with i = 2 ; so j = 5; as i < k ≤ j, so the possible values for k = 3, 4 and 5.

W(2, 5) = P(5) + Q(5)+W(2, 4) = 5+ 0 + 4 = 9

C(2, 5) = W(2, 5)+ min {C (2, 2) + C(3, 5) ,C(2, 3) + C(4, 5),C(2, 4) + C(5, 5)}
= 9 +min{ 0 + 11, 1 + 5 ,5 + 0} = 14
R(2, 5) = 5

119
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

next with i = 3 ; so j = 6; as i < k ≤ j, so the possible values for k = 4, 5 and 6.

W(3, 6) = P(6) + Q(6)+W(3, 5) = 2+ 0 + 8 = 10

C(3, 6) = W(3, 6)+ min {C (3, 3) + C(4, 6) ,C(3 ,4) + C(5, 6),C(3, 5) + C(6, 6)}
= 10 +min{ 0 + 9 , 3 + 2 ,11 + 0} = 15
R( 3, 6) = 5

next with i = 4 ; so j = 7; as i < k ≤ j, so the possible values for k = 5, 6 and 7.

W(4, 7) = P(7) + Q(7)+W(4, 6) = 1+ 0 + 7 = 8

C(4, 7) = W(4, 7)+ min {C (4, 4) + C(5, 7) ,C(4 ,5) + C(6, 7),C(4, 6) + C(7, 7)}
= 8 +min{ 0 + 4 , 5 + 1 ,9 + 0} = 12
R(4, 7) = 5

Fourth, computing all c(i, j) such that j – i = 4 ;j = i + 4 and as 0 ≤ i < 4 ; i = 0, 1,

2, 3 for i < k ≤ j. Start with i = 0 ; so j = 4; as i < k ≤ j, so the possible values for
k = 1,2 ,3 and 4.

W(0, 4) = P(4) + Q(4)+W(0, 3) = 3+ 0 + 7 = 10

C(0, 4) = W(0, 4)+ min {C (0, 0) + C(1,4) ,C(0, 1) + C(2, 4),C(0, 2) + C(3, 4),
C(0, 3) + C(4, 4)}
= 10 +min{ 0 + 10, 4 + 5,8 + 3,11 + 0} = 19
R(0, 4) = 2

next with i = 1 ; so j = 5; as i < k ≤ j, so the possible values for k = 2,3 ,4 and 5.

W(1, 5) = P(5) + Q(5)+W(1, 4) = 5+ 0 + 6 = 11

C(1, 5) = W(1, 5)+ min {C (1, 1) + C(2, 5) ,C(1, 2) + C(3, 5),C(1, 3) + C(4, 5)
C(1, 4) + C(5, 5)}
= 11 +min{ 0 + 14, 2 + 11,4 + 5,10 +0} = 20
R(1, 5) = 4

next with i = 2 ; so j = 6; as i < k ≤ j, so the possible values for k = 3,4,5 and 6.

W(2, 6) = P(6) + Q(6)+W(2, 5) = 2+ 0 + 9 = 11

C(2, 6) = W(2, 6)+ min {C (2, 2) + C(3, 6) ,C(2, 3) + C(4, 6),C(2, 4) + C(5, 6)
C(2, 5) + C (6, 6)} = 11 +min{ 0 + 15, 1 + 9 ,5 + 2,14 + 0} = 18
R(2, 6) = 5

next with i = 3 ; so j = 7; as i < k ≤ j, so the possible values for k = 4,5,6 and 7.

W(3, 7) = P(7) + Q(7)+W(3, 6) = 1+ 0 +11 = 12

C(3, 7) = W(3, 7)+ min {C (3, 3) + C(4, 7) ,C(3, 4) + C(5, 7),C(3, 5) + C(6, 7)
C(3, 6) + C (7, 7)} = 12 +min{ 0 + 12, 3 +4 ,11 +1,15 + 0} = 19
R(3, 7) = 5

Fifth, computing all c(i, j) such that j – i = 5; j = i + 5 and as 0 ≤ i < 3;

i = 0, 1, 2, i < k ≤ j. Start with i = 0 ; so j = 4; as i < k ≤ j, so the possible
values for k = 1,2 ,3,4 and 5.

W(0, 5) = P(5) + Q(5)+W(0, 4) = 5+ 0 + 10 = 15

C(0, 5) = W(0, 5)+ min {C (0, 0) + C(1,5) ,C(0, 1) + C(2, 5),C(0, 2) + C(3, 5),
C(0, 3) + C(4, 5),C(0, 4) + C(5, 5)}
= 10 +min{ 0 + 20, 4 + 14, 8 + 11 ,19 + 0} = 28

120
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

R(0, 5) = 2

next with i = 1 ; so j = 6; as i < k ≤ j, so the possible values for k = 2, 3 ,4, 5 & 6.

W(1, 6) = P(6) + Q(6)+W(1, 5) = 2+ 0 + 11 = 13

C(1, 6) = W(1, 6)+ min {C (1, 1) + C(2, 6) ,C(1, 2) + C(3, 6),C(1, 3) + C(4, 6)
C(1, 4) + C(5, 6),C(1, 5)+C(6, 6)}
= 13 +min{ 0 + 18, 2 + 15, 4 + 9, 10 +2, 20 + 0} = 25
R(1, 6) = 5

next with i = 2 ; so j = 7; as i < k ≤ j, so the possible values for k = 3,4,5,6 and 7.

W(2, 7) = P(7) + Q(7)+W(2, 6) = 1+ 0 + 11 = 12

C(2, 7) = W(2, 7)+ min {C (2, 2) + C(3, 7) ,C(2, 3) + C(4, 7),C(2, 4) + C(5, 7)
C(2, 5) + C (6, 7),C(2, 6) + C(7,7)}
= 12 +min{ 0 + 18, 1 + 12 , 5 + 4, 14 + 1, 18 + 0} = 21
R(2, 7) = 5

Sixth, computing all c(i, j) such that j – i = 6 ;j = i + 6 and as 0 ≤ i < 2 ; i = 0, 1

i < k ≤ j. Start with i = 0; so j = 6; as i < k ≤ j, so the possible values for k = 1,
2, 3, 4 5 & 6.
W(0, 6) = P(6) + Q(6)+W(0, 5) = 2+ 0 + 15 = 17
C(0, 6) = W(0,6 )+ min {C (0, 0) + C(1,6) ,C(0, 1) + C(2, 6),C(0, 2) + C(3, 6),
C(0, 3) + C(4, 6),C(0, 4) + C(5, 6),C(0, 5) + C(6, 6)}
= 17 +min{ 0 + 25, 4 + 18, 8 + 15,19 + 2, 31 + 0} = 37
R(0, 6) = 4

next with i = 1 ; so j = 7; as i < k ≤ j, so the possible values for k = 2, 3, 4, 5, 6

and 7.

W(1, 7) = P(7) + Q(7)+W(1, 6) = 1+ 0 + 13 = 14

C(1, 7) = W(1, 7)+ min {C (1, 1) + C(2, 7) ,C(1, 2) + C(3, 7),C(1, 3) + C(4, 7)
C(1, 4) + C(5, 7),C(1, 5)+C(6, 7),C(1, 6) +C(7, 7)}
= 14 +min{ 0 + 21, 2 + 18, 4 + 12, 10 + 4, 20 + 1, 21 + 0} = 28
R(1, 7) = 5

Seventh, computing all c(i, j) such that j – i = 7 ;j = i + 7 and as 0 ≤ i < 1 ; i = 0

i < k ≤ j. Start with i = 0 ; so j = 7; as i < k ≤ j, so the possible values for k = 1, 2,
3, 4, 5, 6 and 7.

W(0, 7) = P(7) + Q(7)+W(0, 6) = 1+ 0 + 17 = 18

C(0, 7) = W(0, 7 )+ min {C (0, 0) + C(1, 7) ,C(0, 1) + C(2, 7),C(0, 2) + C(3, 7),
C(0, 3) + C(4, 7),C(0, 4) + C(5, 6),C(0, 5) + C (6, 7 ),C(0, 6) + C(7, 7)}
= 18 +min{ 0 + 28, 4 + 21, 8 + 18,19 +4, 31 + 1, 37 + 0} = 41
R(0, 7) = 4

0/1 – KNAPSACK

We are given n objects and a knapsack. Each object i has a positive weight w i and a
positive value Vi. The knapsack can carry a weight not exceeding W. Fill the knapsack
so that the value of objects in the knapsack is optimized.

A solution to the knapsack problem can be obtained by making a sequence of

decisions on the variables x1, x2, . . . . , xn. A decision on variable xi involves
determining which of the values 0 or 1 is to be assigned to it. Let us assume that

121
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

decisions on the xi are made in the order xn, xn-1, . . . .x1. Following a decision on xn,
we may be in one of two possible states: the capacity remaining in m – wn and a
profit of pn has accrued. It is clear that the remaining decisions x n-1, . . . , x1 must be
optimal with respect to the problem state resulting from the decision on x n.
Otherwise, xn,. , x1 will not be optimal. Hence, the principal of optimality holds.

Fn (m) = max {fn-1 (m), fn-1 (m - wn) + pn} -- 1

For arbitrary fi (y), i > 0, this equation generalizes to:

Fi (y) = max {fi-1 (y), fi-1 (y - wi) + pi} -- 2

Equation-2 can be solved for fn (m) by beginning with the knowledge fo (y) = 0 for all
y and fi (y) = - , y < 0. Then f1, f2, . . . fn can be successively computed using
equation–2.

When the wi‟s are integer, we need to compute fi (y) for integer y, 0 < y < m. Since fi
(y) = -  for y < 0, these function values need not be computed explicitly. Since
each fi can be computed from fi - 1 in Θ (m) time, it takes Θ (m n) time to compute fn.
When the wi‟s are real numbers, fi (y) is needed for real numbers y such that 0 < y
< m. So, fi cannot be explicitly computed for all y in this range. Even when the w i‟s
are integer, the explicit Θ (m n) computation of fn may not be the most efficient
computation. So, we explore an alternative method for both cases.

The fi (y) is an ascending step function; i.e., there are a finite number of y‟s, 0 = y1
< y2 < . . . . < yk, such that fi (y1) < fi (y2) < . . . . . < fi (yk); fi (y) = -  , y < y1; fi
(y) = f (yk), y > yk; and fi (y) = fi (yj), yj < y < yj+1. So, we need to compute only fi
(yj), 1 < j < k. We use the ordered set Si = {(f (yj), yj) | 1 < j < k} to represent fi
(y). Each number of Si is a pair (P, W), where P = fi (yj) and W = yj. Notice that S0 =
{(0, 0)}. We can compute Si+1 from Si by first computing:

Si1 = {(P, W) | (P – pi, W – wi)  Si}

Now, Si+1 can be computed by merging the pairs in S i and Si1 together. Note that if
Si+1 contains two pairs (Pj, Wj) and (Pk, Wk) with the property that Pj < Pk and Wj >
Wk, then the pair (Pj, Wj) can be discarded because of equation-2. Discarding or
purging rules such as this one are also known as dominance rules. Dominated tuples
get purged. In the above, (Pk, Wk) dominates (Pj, Wj).

Example 1:

Consider the knapsack instance n = 3, (w1, w2, w3) = (2, 3, 4), (P1, P2, P3) = (1, 2,
5) and M = 6.

Solution:

Initially, fo (x) = 0, for all x and fi (x) = -  if x < 0.

Fn (M) = max {fn-1 (M), fn-1 (M - wn) + pn}

F3 (6) = max (f2 (6), f2 (6 – 4) + 5} = max {f2 (6), f2 (2) + 5}

F2 (6) = max (f1 (6), f1 (6 – 3) + 2} = max {f1 (6), f1 (3) + 2}

122
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

F1 (6) = max (f0 (6), f0 (6 – 2) + 1} = max {0, 0 + 1} = 1

F1 (3) = max (f0 (3), f0 (3 – 2) + 1} = max {0, 0 + 1} = 1

Therefore, F2 (6) = max (1, 1 + 2} = 3

F2 (2) = max (f1 (2), f1 (2 – 3) + 2} = max {f1 (2), -  + 2}

F1 (2) = max (f0 (2), f0 (2 – 2) + 1} = max {0, 0 + 1} = 1

F2 (2) = max {1, -  + 2} = 1

Finally, f3 (6) = max {3, 1 + 5} = 6

Other Solution:

For the given data we have:

S0 = {(0, 0)}; S01= {(1, 2)}

S1 = (S0 U S01 ) = {(0, 0), (1, 2)}

X - 2 = 0 => x = 2. y – 3 = 0 => y = 3
X - 2 = 1 => x = 3. y – 3 = 2 => y = 5

S11 = {(2, 3), (3, 5)}

S2 = (S1 U S1 1) = {(0, 0), (1, 2), (2, 3), (3, 5)}

X – 5 = 0 => x = 5. y–4=0 => y = 4

X – 5 = 1 => x = 6. y–4=2 => y = 6
X – 5 = 2 => x = 7. y–4=3 => y = 7
X – 5 = 3 => x = 8. y–4=5 => y = 9

S21 = {(5, 4), (6, 6), (7, 7), (8, 9)}

S3 = (S2 U S21 ) = {(0, 0), (1, 2), (2, 3), (3, 5), (5, 4), (6, 6), (7, 7), (8, 9)}

By applying Dominance rule,

S3 = (S2 U S21 ) = {(0, 0), (1, 2), (2, 3), (5, 4), (6, 6)}

From (6, 6) we can infer that the maximum Profit  pi xi = 6 and weight  xi wi = 6

Reliability Design

The problem is to design a system that is composed of several devices connected in

series. Let ri be the reliability of device Di (that is ri is the probability that device i
will function properly) then the reliability of the entire system is  ri. Even if the
individual devices are very reliable (the r i‟s are very close to one), the reliability of
the system may not be very good. For example, if n = 10 and ri = 0.99, i < i < 10,
then  ri = .904. Hence, it is desirable to duplicate devices. Multiply copies of the
same device type are connected in parallel.

123
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

If stage i contains mi copies of device Di. Then the probability that all mi have a
mi mi
malfunction is (1 - ri) . Hence the reliability of stage i becomes 1 – (1 - r)i .

The reliability of stage „i‟ is given by a function i (mi).

Our problem is to use device duplication. This maximization is to be carried out under
a cost constraint. Let ci be the cost of each unit of device i and let c be the maximum
allowable cost of the system being designed.

We wish to solve:

Maximize 
1 i n
i mi

Subject to  C m C
1 i n
i i

mi > 1 and interger, 1 < i < n

Assume each Ci > 0, each mi must be in the range 1 < mi < ui, where
  n  
ui   C  Ci 
 CJ 

Ci 
  1  

The upper bound ui follows from the observation that mj > 1

An optimal solution m1, m2............... mn is the result of a sequence of decisions, one

decision for each mi.

Let fi (x) represent the maximum value of   mJ

1  j i
Subject to the constrains:

C
1 j i
J mJ  x and 1 < mj < uJ, 1 < j < i

The last decision made requires one to choose m n from {1, 2, 3, .......... un}

Once a value of mn has been chosen, the remaining decisions must be such as to use
the remaining funds C – Cn mn in an optimal way.

The principle of optimality holds on

fn C   max n mn  fn  1 C  Cn mn  

1  mn  un


for any fi (xi), i > 1, this equation generalizes to

124
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

fn x  max i mi  fi  1 x  Ci mi 

1  mi  ui

clearly, f0 (x) = 1 for all x, 0 < x < C and f (x) = - for all x < 0.

Let Si consist of tuples of the form (f, x), where f = f i (x).

There is atmost one tuple for each different „x‟, that result from a sequence of
decisions on m1, m2, . . . . mn. The dominance rule (f1, x1) dominate (f2, x2) if f1 ≥ f2
and x1 ≤ x2. Hence, dominated tuples can be discarded from S i.

Example 1:

Design a three stage system with device types D1, D2 and D3. The costs are $30, $15
and $20 respectively. The Cost of the system is to be no more than $105. The
reliability of each device is 0.9, 0.8 and 0.5 respectively.

Solution:

We assume that if if stage I has mi devices of type i in parallel, then  i (mi) =1 – (1-
ri)mi

Since, we can assume each ci > 0, each mi must be in the range 1 ≤ mi ≤ ui. Where:
  n  
ui   C  Ci
 
 
1
CJ 


Ci 


Using the above equation compute u 1, u2 and u3.

105 30 3015  20
u1   70  2
30 30
10515 3015  20 55
u2   3
15 15
105 20 3015  20 60
u3   3
20 20

We useSji  i:stage number and J: no. of devices in stage i  mi

S o  fo (x), x initially fo x  1 and x  0, so, So  1, 0


Compute S1, S2 and S3 as follows:

S1 = depends on u1 value, as u1 = 2, so

S1  S , S 
1 1

1 2

S2 = depends on u2 value, as u2 = 3, so

125
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

S2  S , S 2 2
, S2 
1 2 3

S3 = depends on u3 value, as u3 = 3, so

S3  S , S 3 3
, S3 
1 2 3

Now find,S11  f (x), x 

1

f1 x   1 (1) fo  , 1 (2) f 0 ()} With devices m1 = 1 and m2 = 2

Compute 1 (1) and 1 (2) using the formula: i mi)  1 (1  ri )mi

1 1  1 1  r1m 1 = 1 – (1 – 0.9)1 = 0.9

1 2  1 1 0.92  0.99

S1   f1 x, x     0.9, 30

1

S21   0.99 , 30  30    0.99, 60

Therefore, S1 = {(0.9, 30), (0.99, 60)}

Next findS12  f 2 (x), x 

f2 (x)  {2 1 * f1  , 2 2 * f1  , 2 3 * f1  }
2 1  1  1  rImi = 1 – (1 – 0.8) 1
= 1 – 0.2 = 0.8

2 2  1  1  0.8 2  0.96

2 3  1  1  0.8 3  0.992

S12  {(0.8(0.9),30  15), (0.8(0.99),60  15)} = {(0.72, 45), (0.792, 75)}

S22  {(0.96(0.9),30  15 15) , (0.96(0.99),60  15  15)}

= {(0.864, 60), (0.9504, 90)}

S32  {(0.992(0.9),30  15 1515) , (0.992(0.99),60  15  1515)}

= {(0.8928, 75), (0.98208, 105)}
2
S  S 2
, S 2 , S2 
1 2 3

By applying Dominance rule to S2:

Therefore, S2 = {(0.72, 45), (0.864, 60), (0.8928, 75)}

Dominance Rule:

126
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

If Si contains two pairs (f1, x1) and (f2, x2) with the property that f1 ≥ f2 and x1 ≤ x2,
then (f1, x1) dominates (f2, x2), hence by dominance rule (f2, x2) can be discarded.
Discarding or pruning rules such as the one above is known as dominance rule.
Dominating tuples will be present in Si and Dominated tuples has to be discarded
from Si.

Case 1: if f1 ≤ f2 and x1 > x2 then discard (f1, x1)

Case 2: if f1 > f2 and x1 < x2 the discard (f2, x2)

Case 3: otherwise simply write (f1, x1)

S2 = {(0.72, 45), (0.864, 60), (0.8928, 75)}

 3 1  1  1  rI  mi = 1 – (1 – 0.5)1 = 1 – 0.5 = 0.5

 3 2  1  1  0.5 2  0.75

 3 3  1  1  0.5 3  0.875

S13  0.5 (0.72), 45  20, 0.5 (0.864), 60  20, 0.5 (0.8928), 75  20

S13  0.36, 65, 0.437, 80, 0.4464, 95

S23 {0.75 (0.72), 45  20  20, 0.75 (0.864), 60  20  20,

0.75 (0.8928), 75  20  20}
= {(0.54, 85), (0.648, 100), (0.6696, 115)}

S33   0.875 (0.72), 45  20  20  20, 0.875 (0.864), 60  20  20  20,

0.875 (0.8928), 75  20  20  20 

S33   (0.63, 105), 1.756, 120, 0.7812, 135

If cost exceeds 105, remove that tuples

S3 = {(0.36, 65), (0.437, 80), (0.54, 85), (0.648, 100)}

The best design has a reliability of 0.648 and a cost of 100. Tracing back for the
solution through Si „s we can determine that m3 = 2, m2 = 2 and m1 = 1.

Other Solution:

According to the principle of optimality:

fn(C) = max {n (mn). fn-1 (C - Cn mn) with fo (x) = 1 and 0 ≤ x ≤ C;

1  mn  un

Since, we can assume each ci > 0, each mi must be in the range 1 ≤ mi ≤ ui.
Where:

127
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

  n  

ui   C  Ci  C J
 / Ci 
  i
 

Using the above equation compute u 1, u2 and u3.

105 30 3015  20
u1   70  2
30 30
10515 3015  20 55
u2   3
15 15
105 20 3015  20 60
u3   3
20 20

f3 (105) = max {3 (m3). f2 (105 – 20m3)}

1  m3  u3

= max {3(1) f2(105 - 20), 3(2) f2(105 - 20x2), 3(3) f2(105 -20x3)}

= max {0.5 f2(85), 0.75 f2(65), 0.875 f2(45)}

= max {0.5 x 0.8928, 0.75 x 0.864, 0.875 x 0.72} = 0.648.

f2 (85) = max {2 (m2). f1 (85 -15m2)}

1  m2  u2

= max {2(1).f1(85 - 15), 2(2).f1(85 - 15x2), 2(3).f1(85 - 15x3)}

= max {0.8 f1(70), 0.96 f1(55), 0.992 f1(40)}

= max {0.8 x 0.99, 0.96 x 0.9, 0.99 x 0.9} = 0.8928

f1 (70) = max {1(m1). f0(70 - 30m1)}

1 m1  u1

= max {1(1) f0(70 - 30), 1(2) f0 (70 - 30x2)}

= max {1(1) x 1, 1(2) x 1} = max {0.9, 0.99} = 0.99

f1 (55) = max {1(m1). f0(55 - 30m1)}

1 m1  u1

= max {1(1) f0(50 - 30), 1(2) f0(50 - 30x2)}

= max {1(1) x 1, 1(2) x -} = max {0.9, -} = 0.9

f1 (40) = max {1(m1). f0 (40 - 30m1)}

1 m1  u1

= max {1(1) f0(40 - 30), 1(2) f0(40 - 30x2)}

= max {1(1) x 1, 1(2) x -} = max{0.9, -} = 0.9

128
 DESIGN AND ANALYSIS OF ALGORITHMS (III - CSE) – II SEM

f2 (65) = max {2(m2). f1(65 -15m2)}

1 m2u2

= max {2(1) f1(65 - 15), 2(2) f1(65 - 15x2), 2(3) f1(65 - 15x3)}

= max {0.8 f1(50), 0.96 f1(35), 0.992 f1(20)}

= max {0.8 x 0.9, 0.96 x 0.9, -} = 0.864

f1 (50) = max {1(m1). f0(50 - 30m1)}

1 m1  u1

= max {1(1) f0(50 - 30), 1(2) f0(50 - 30x2)}

= max {1(1) x 1, 1(2) x -} = max{0.9, -} = 0.9

f1 (35) = max 1(m1). f0(35 - 30m1)}

1 m1  u1

= max {1(1).f0(35-30), 1(2).f0(35-30x2)}

= max {1(1) x 1, 1(2) x -} = max{0.9, -} = 0.9

f1 (20) = max {1(m1). f0(20 - 30m1)}

1 m1  u1

= max {1(1) f0(20 - 30), 1(2) f0(20 - 30x2)}

= max {1(1) x -, 1(2) x -} = max{-, -} = -

f2 (45) = max {2(m2). f1(45 -15m2)}

1 m2 u2

= max {2(1) f1(45 - 15), 2(2) f1(45 - 15x2), 2(3) f1(45 - 15x3)}

= max {0.8 f1(30), 0.96 f1(15), 0.992 f1(0)}

= max {0.8 x 0.9, 0.96 x -, 0.99 x -} = 0.72

f1 (30) = max {1(m1). f0(30 - 30m1)}

1  m1 u1

= max {1(1) f0(30 - 30), 1(2) f0(30 - 30x2)}

= max {1(1) x 1, 1(2) x -} = max{0.9, -} = 0.9

Similarly, f1 (15) = -, f1 (0) = -.

The best design has a reliability = 0.648 and

Cost = 30 x 1 + 15 x 2 + 20 x 2 = 100.

Tracing back for the solution through Si „s we can determine that:

m3 = 2, m2 = 2 and m1 = 1.

129