Chapter 2

Algorithm
• Steps taken when solving a problem using a computer:
o Problem definition and specification
o Design a solution
o Testing and documentation
o Evaluation of the solution

• These steps could overlap

• Not all problems could be solved using a computer. Some difficult
problems we could build a simple model and then test it and build
on this model more and more sophisticated models.
• Design a solution id finding a suitable algorithm.

Algorithm:
Precise method used by the computer to solve a problem. The
algorithm is composed of a finite set of steps each of which
require one or more operations.

Characteristics of Algorithm
1. Definite → clear
2. Effective: It can be solved by the person using a pencil and paper
within a limit time.
When studying Algorithm, we study:
1. How to design Algorithm
2. How to analysis Algorithm
3. Prove of correctness.
4. How to express Algorithm
5. Test and documentation

Writing structure programs:

1. Local and global variables are defined
2. Should specify input, output variables for function and procedure.
3. Should use indentation
4. Should be divided into well-defined procedures
5. Flow should be forward. Unless it is necessary to do otherwise
or looping.
6. Documentation should be clear.
Min-Max application
Divide and conquer

Min-Max ( lower , upper ,minD, maxD)

If ( lower == upper )
If ( maxD < A[ Upper ] )
maxD = A[ upper ];
end if
if ( mind > A [ upper ] )
mind = A[ upper ];
end if
else
mid = ( lower + upper ) /2;
Min-Max ( lower, mid, minD, maxD);
Min-Max ( mid+1, upper, minD, maxD);
end if
end.
Time:
d n=1
T(n) =
2 T(n/2) + c n>1

T(n) = 2 T(n/2) + c
T(n/2) = T(n/4) + c

T(n) = 2 [ T(n/4) + c ] + c
T(n) = 22 T(n/22) + 2c + c
T(n/4) = 2 T(n/8) + c

T(n) = 22 [ 2 T(n/8) + c) + 2c + c
T(n) = 23 T(n/23) + 22c + 2c + c
…
T(n) = 2k T(n/2k) + 2k-1 c + 2k-2 c +… + c
= 2k T(n/2k) + c (2k-1 + 2k-2 +… + 1)

(xi-1 + xi-2 + xi-3 + .. + 1 ) * ( x-1)/(x-1)

( xi + xi-1 + xi-2 +. . . +x – xi-1 – xi-2 - . . . – x – 1) / (x -1)
( xi – 1 ) / ( x – 1 )

T(n) = 2k T(n/2k) + c ( 2k -1 ) / ( 2 – 1)
Let 2k = n
T(n) = n T(1) + c ( n – 1)
T(n) = d n + c n – c
T(n) = O(n)
 Dynamic Programming

Combines solutions to subproblems to obtain a final solution.

Approach taken:
1. Characterize the structure of optimal solution.
2. Recursively define the value of the optimal solution
3. Compute the value in the above fashion
4. Find the optimal solution

Multiplication of chain matrices

Multiply ( A, B)
if ( columns( A ) ≠ rows( B ))
error;
else
for ( i =1; i <= rows( A ); i++)
for ( j = 1; j <= columns( B ); j++)_
c [ i, j ] = 0;
for ( k = 1; k <= columns( A ); k++)
c[ i, j ] = c[ i, j ] + A[ i, k ] * B[ k, j ]
end for
end for
end for
end if
end.
Find the optimal order ( least cost = least number of multiplication) to
multiply these n matrices.

A B C

* =

pxq qxr pxr

Cost ( A x B ) = p x q x r

Example:
A = 10 x 100
B = 100 x 5
C = 5 x 50

A*B*C
• A*(B*C)=
Cost ( B * C ) = 100 * 5 * 50 = 25000
Cost ( A * [ BC ] ) = 10 * 100 * 50 = 50000
Total cost = 25000 + 50000 = 75000
• (A*B)*C=
Cost ( A * B ) = 10 * 100* 5 = 5000
Cost ( [ AB ] * C ) = 10 * 5 * 50 = 2500
Total cost = 2500 + 5000 = 7500
( A1 * A2 * A3 * … * Ak) ( Ak+1 * Ak+2 * … * An)
• Multiply A1 * A2 * A3 * … * Ak
Each solved optimally
• Multiply Ak+1 * Ak+2 * … * An
What is k ?
Optimality part m[ I, j ] = least possible cost achievable for multiplying
Ai* Ai+1 * … * Aj

Idea is
If ( i = j ) ➔ m[ I, j ] = 0
If ( i < j ) ➔ m[ i, j ] = min { m[ i, k ] + m[ k+1, j ] + pi-1 * pk * pj }
i≤k≤j

If ( i > j ) ➔x

( Ai * Ai+1 * Ai+2 * … * Ak) ( Ak+1 * Ak+2 * … * Aj)

pi-1 x pk pk x pj

pi-1 x pk x pj
A*B*C*D*E*F
A = 4x2 B = 2x3 C = 3x1 D = 1x2 E = 2x2 F = 2x3

A B C D E F
B D D D
A 0 24 14 22 26 36
D D D
B 0 6 10 14 22
D D
C 0 6 10 19
F
D 0 4 10

E 0 12

F 0

[A(BC)][(DE)F]

Idea:
A*B*C=
• ( A * B ) * C = 24 + 12 = 36
• A * ( B * C ) = 8 + 6 = 14
A*B*C*D
• ( A .. C ) * D = 14 + 0 + 8 = 22
• (AB)*(CD) = 24 + 6 + 24 = 54
• A * ( B . . . D) = 0 + 10 + 16 = 26
(B C ) * D = 6 + 0 + 4 = 10
B * ( C D ) = 0 + 6 + 12 = 18

Algorithm:
for ( i = 1; i <= n; i++ )
cost [ i ][ j ] = 0;
for ( i = 1; i <= n; i++)
for ( j = i+1; j <= n; j++)
cost [ i ][ j ] = maxInt;
for ( i = 1; i <= n-1; i++ )
for ( j = 1; j <= n-i; j++ )
for ( k = j +1; k <= i = j; k++ )
t = cost[ j ][ k-1 ] + cost[ k ][ i+j ] + r[ j ] * r[ k ] * r[ i * j + 1]
if ( t < cost[ j ] [ i + j ] )
cost[ j ] [ i + j ] = t;
best[ j ] [ i + j ] = k
end if
end for
end for
end for
A4x2 B2x3 C3x1 D1x2 E2x2 F2x3
r = 4 2 3 1 2 2 3
Example: Longest Common Subsequence Problem (LCS )
Given a string x = < x1, x2, . . ., xn >
z = < z1, z2, … zn>
z is a subsequence of x if
there is a strictly increasing sequence of k indices < i1, i2, …, in>
1≤ i1 < i2 <… < ik … ≤ n such that
Z = < xi1, xi2, …, xik >

Example:
x=<ABRACADABRA>

z = < A A D A A>
Is z a subsequence of x?
Yes 5 indices are < 1, 4, 7, 8, 11 >

• Given two string x and y, the longest common subsequence of x

and y a longest string z such that z is a subsequence of x and a
subsequence of y.

Example:
Given two sequences x=<ABC>
y=<BAC>
z1 = < A C >
z2 = < B C >
idea:
let c [ i, j ] = length of longest common subsequence of xi and yj
c [ i, 0 ] = 0
c [ 0, j ] = 0
c [ i, j ] = ?

x = < x1, x2, . . ., xi > , y = < y1, y2, . . ., yj >

0 if ( i = 0 ) OR ( j = 0 )
c [ i, j ] = c [ i-1, j-1 ] + 1 if xi = yj
max ( c [ i-1, j ], c [ i , j-1 ] ) if xi ≠ yj
Example:
x=<A B C A D C>
y=<M K B L A D>

i=1 2 3 4 5 6
if xi = yj A B C A D C

i = 4, j = 5
M K B L A D E
cost [3][4] = 1
j=1 2 3 4 5 6 7
cost [4][5] = cost[3][4] + 1= 2

if xi ≠ yj
i=1 2 3 4 5 6

A B C A D C
i = 5, j = 5
cost [5][5] =
M K B L A D E
max (cost [4][5], cost[5][4])
j=1 2 3 4 5 6 7
= max(2, 1) = 2

Cost [4][5] = 2 Cost [5][4] = 1

i=1 2 3 4 5 6
i=1 2 3 4 5 6
A B C A D C
A B C A D C

M K B L A D E
M K B L A D E
j=1 2 3 4 5 6 7
j=1 2 3 4 5 6 7
Algorithm:
m = length (x);
n = length (y);
for ( i = 1; i <= m; i++)
c [ i ] [ 0 ] = 0;
for ( j = 1; j <= n; j++)
c [ 0 ] [ j ] = 0;

for ( i = 1; i <= m; i++)

for ( j = 1; j <= n; j++)
if ( x[ i ] == y[ j ] )
c[ i ] [ j ] = c[ i-1 ][ j-1 ] +1;
b[ i ][ j ] = ‘ ’
else
if ( x[ i ][ j -1 ] > y[ i-1 ][ j ] )
c[ i ] [ j ] = c[ i ][ j-1 ] ;
b[ i ][ j ] = ‘ ’;
else
c[ i ] [ j ] = c[ i-1 ][ j ] ;
b[ i ][ j ] = ‘ ’
end if
end if
end for
end for
print_LCS ( b, x, i, j )
if ( ( i == 0 ) or ( j == 0 ) )
return
else
if ( b[ i ][ j ] = ‘ ‘)
[Link]( x[ i ] );
print_LCS ( b, x, i-1, j-1 );
else
if ( b[ I ][ j ] = ‘ ‘)
print_LCS ( b, x, i-1, j );
else
print_LCS ( b, x, i, j-1 );
end if
end if
end if
end.
Example:
x=<ABCBDAB>
y=<BDCABA>

0 B D C A B A
0 0 0 0 0 0 0 0

A 0 0 0 0 1 1 1

B 0 1 1 1 1 2 2

C 0 1 1 2 2 2 2

B 0 1 1 2 2 3 3

D 0 1 2 2 2 3 3

A 0 1 2 2 3 3 4

B 0 1 2 2 3 4 4

z=<BCAB>
z=<BCBA>
Example: The Levenshtein distance

Given two strings str1 and str2 and below operations that can
performed on str1. Find minimum number of edits (operations) required
to convert ‘str1’ into ‘str2’.

A. Insert
B. Remove
C. Replace

All of the above operations are of equal cost.

Examples:

Input: str1 = "geek", str2 = "gesek"

Output: 1
We can convert str1 into str2 by inserting a 's'.

Input: str1 = "cat", str2 = "cut"

Output: 1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input: str1 = "sunday", str2 = "saturday"

Output: 3
Last three and first characters are same. We basically need to
convert "un" to "atur". This can be done using below three
operations.
Replace 'n' with 'r', insert t, insert a
Solution:

MaxLength(str1(i),str2(j)) i=0 OR j=0

dp[i-1][j-1] str1[i] = str2[j]
dp[i][j] = dp[i][j-1] +1 // Insert
min dp[i-1][j] + 1 str1[i] ≠ str2[j] // Remove
dp[i-1][j-1] + 1 // Replace

Example 1
Str1 = < k i t t e n > str2 = < s i t t i n g >
j
s i T t i n g
0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
i t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3

Nothing Insert Replace Remove

2 ➔ Replace 1 ➔ Insert

Example 2
Str1 = < s a t u r d a y > str2 = < s u n d a y >
j

s u n d a y
0 1 2 3 4 5 6
s 1 0 1 2 3 4 5
a 2 1 1 2 3 3 4
i t 3 2 2 2 3 4 5
u 4 3 2 3 3 4 5
r 5 4 3 3 4 4 5
d 6 5 4 4 3 4 5
a 7 6 5 5 4 3 4
y 8 7 6 6 5 4 3

Nothing Insert Replace Remove

1 ➔ Replace 2 ➔ Remove
Greedy Strategy

A greedy algorithm is any algorithm that follows the problem-solving

heuristic of making the locally optimal choice at each stage. In many
problems, a greedy strategy does not usually produce an optimal
solution, but nonetheless a greedy heuristic may yield locally optimal
solutions that approximate a globally optimal solution in a reasonable
amount of time.
• Not always optimal solution
• It is a quick solution
Example:
Procedure Greedy selective activity
Job Start Finish
i si fi
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 11 14

1 4 8 11
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

j = 1;
for ( i = 2; i <= n ; i++)
if ( s[ i ] >= f[ j ] )
A = A U { i };
j = i;
end if
end for
Knapsack Problem

• 0 – 1 Knapsack: take all of them or nothing

• Fractional knapsack: We can take a part from any item

Example:
3 Items ➔ 50 kg
Item kg Price
1 10 60 NIS
2 20 100 NIS
3 30 120 NIS

0 – 1 Knapsack
Weight = item 2 + item 3 = 20 + 30 = 50 kg
Profit = 100 + 120 = 220 NIS

Fractional Knapsack
Item kg Price Price/kg
1 10 60 NIS 6 NIS
2 20 100 NIS 5 NIS
3 30 120 NIS 4 NIS

Weight = item 1 + item 2 + item 3 (10 kg) = 10 + 20 + 20 = 50 kg

Profit = 60 + 100 + 80 = 240 NIS
Example:
The knapsack problem is a problem in combinatorial optimization:
Given a set of items, each with a weight and a value, determine the
number of each item to include in a collection so that the total weight
is less than or equal to a given limit and the total value is as large as
possible. It derives its name from the problem faced by someone who
is constrained by a fixed-size knapsack and must fill it with the most
valuable items.

Weight: w1, w2, …,wn

Profit: p1, p2, … ,pn
Capacity: M
Find x1, x2, …, xn
n n
To maximizing ∑ xi . pi , ∑ xi . wi <= M
i=1 i=1

Dynamic Programming Approach

C [ i ][ j ] = Optimal rofit using only w1, w2, … , wj and knapsack capacity
is i.

= max { c [ i ][ j – 1 ] , pj + c [ i-wj, j] }
for ( i = 0; i <= m ; i++ )
c[ i ][ 1 ] = p[ 1 ] * ( i / w[ i ] );
for ( j = 2; j <= n; j++ )
for ( i = 1; i <= m; i++)
if ( i – w[ j ] >= 0 )
if ( c[ i ][ j-1 ] < p[ j ] + c[ i- w[ j ], j ] )
c[ i ][ j ] = p[ j ] + c[ i- w[ j ], j ];
else
c[ i ][ j ] = c[ i ][ j-1 ];
end if
end if
end for
end for
w: 3 4 7 8 9
p: 4 5 10 11 13
m = 17
w 3 4 7 8 9
p 4 5 10 11 13
Item 1 2 3 4 5
0 0 0 0 0 0
1 0 0 0 0 0
2 0 0 0 0 0
3 4 4 4 4 4
4 4 5 5 5 5
5 4 5 5 5 5
6 8 8 8 8 8
7 8 9 10 10 10
8 8 10 10 11 11
9 12 12 12 12 13
10 12 13 14 14 14
11 12 14 15 15 15
12 16 16 16 16 17
13 16 16 18 18 18
14 16 17 20 20 20
15 20 17 20 21 21
16 20 21 22 22 23
17 20 21 24 24 24

Item 3 + Item 3 + Item 1 Item 5 + Item 4

Weight = 7 + 7 + 3 = 17 Weight = 9 + 8 = 17
Profit = 10 + 10 + 4 = 24 Profit = 13 + 11 = 24