Analysis of Algorithms

-Submitted by

Abhilash Bhandari ‘2’

Ghanshyam.S.Malu ‘18’
December 16, 2009
 Abstract

Algorithms play an important role in developing programs. Algorithms also

help us to solve a wide range of problems including combinatorial problems,
graphical problems, arithmetic problems, etc. This document discusses about
a few of the algorithms.
Contents

1 Floyd’s Algorithm 2
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Pseudo Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Dijkstra’s Algorithm 4
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Pseudo Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Kruskal’s Algorithm 6
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Pseudo Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Horspool Algorithm 8
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Pseudo Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5 Binomial Co-efficient using Dynamic Programming 10

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2 Pseudo Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6 Prim’s Algorithm 12
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.2 Pseudo Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

7 Warshall’s Algorithm 14
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7.2 Pseudo Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

8 N-queens problem using Backtracking method 16

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8.2 Pseudo Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1
Chapter 1

Floyd’s Algorithm

1.1 Introduction
In all pairs shortest path problem, we find the shortest distance from all
the nodes to all other nodes. The solution for this problem can be obtained
easily Floyd’s algorithm. The Floyd’s algorithm is the modified version of
Warshal’s algorithm. Formally, the problem can be stated as follows:
Let G=(V,E) be a directed graph where V is set of vertices with n number
of vertices and E is the set of edges. Let ”cost” be the cost adjacency matrix
for the graph G such that

1. cost(i,j)=0 , for 0 ≤ i<n

2. cost(i,j) is the cost associated with the edge (i,j)if there is an edge from
i to j

3. cost(i,j)=infinity if there is no edge from i to j

The all-pairs-shortest-path-problem is to determine a matrix D such that

D(i,j) contains the shortest distance from i to j.

1.2 Pseudo Code

Floyd(W[1...n][1...n])
D←W
for k ← to n do
for i ← to n do
for j ← to n do
D[ i ][ j ] ← min( D[ i ][ j ], D[ i ][ k ] + D[ k ][ j ] )

2
 end for
end for
end for
return D

Time complexity of the Floyd’s Algorithm=θ(n3 ) where n is number of vertices

3
Chapter 2

Dijkstra’s Algorithm

2.1 Introduction
Given a graph G = (V,E) and a source vertex Vs (that belongs to) V, find
the shortest path and shortest distance from Vs to every other vertex Vd
in V (Vd is the destination node). Clearly, when we search for the shortest
path, we must consider all the vertices in V. If a vertex say Vi is ignored,
then we will not consider any of the paths from Vs to Vd through Vi. This
problem is not defined for negative numbers.
In short, in single source shortest path problem, we find the shortest
distance (may be path also) from a given node to any other node. We can
easily find the shortest distance and the path from one node to any node in
the graph using Dijkstra’s algorithm.

2.2 Pseudo Code

Dijkstra (n,w,source,destination,d,p)
// Purpose To compute the shortest distance and shortest path from
given source to destination
// Inputs
n- Number of vertices in the graph
w- Cost adjcacency matrix with values ≥ 0
source- Source vertex
destination- destination vertex
//Output
count ← 0
k←0
sum ← 0

4
for i = 0 to n do
parent[i] ← i
end for
while count! = n − 1 and E! = Φ do
select an edge (u,v) with least cost
i ← f ind(u, parent)
j ← f ind(v, parent)
if i! = j then
t[k][0] ← u
t[k][1] ← v
k++
count + +
sum ← sum + cost(u,v)
union(i, j, parent)
end if
end while
if count! = n − 1 then
write(“Spanning tree does not exist”)
return
end if
write(“The spanning tree is shown below”)
for i = 0 to n-2 do
write(t[i][0],t[i][1])
end for
write(“Cost of spanning tree is”,sum)

Time complexity of the Dijkstra’s Algorithm=θ(V 2 )

5
Chapter 3

Kruskal’s Algorithm

3.1 Introduction
Every spanning tree of n vertices will have n-1 edges. The problem here is
to select n-1 edges such that the cost of the spanning tree is minimum. Like
Prim’s algorithm, using Kruskal’s algorithm also we can find the minimum
spanning tree ( MST ).
Let G=(V,E) be a directed graph. This algorithm selects n-1 edges one
at a time. The algorithm selects the least cost edge(u,v) from E and deletee
the edge(u,v) from E. Then, it checks whether the selected edge(u,v) results
in a cycle when cycles are formed, the selected edge is added to the list of
edges selected to form a minimal spanning tree(MST). The selected edge
which results in a cycle is neglected. The procedure is repeated till all the
n-1 edges are selected and there are no more edges to consider. If n-1 edges
are selected, the selected edges results in a minimal spanning tree; otherwise,
the spanning tree does not exist.

3.2 Pseudo Code

Kruskal (n,m,E)
// Purpose To compute the minimum spanning tree using Kruskal’s al-
gorithm
// Inputs
n- Number of vertices in the graph
m- Number of edges in the graph
E- edge list consisting of set of edges along with equivalent
weights
//Output- The minimum spanning tree along

6
 count- shortest distance from the source to all other nodes
p- shortest path from source to destination
s- gives the nodes that are so far visited and the nodes that are
not visited

s[source] ← 1
for i = 0 to n-1 do
find u and d[u] such that d[u] is minimum and u ∈ V − S
add u to S
if u = destination then
break;
end if
for every v ∈ V − S do
if d[u] + w[u, v]<d[v] then
d[v] ← d[u] + w[u, v]
p[v] ← u
end if
end for
end for
E is the number of edges in the graph and V is the number of vertices,
Kruskal’s algorithm can be shown to run in O(E log E) time, or equivalently,
O(E log V) time. These running times are equivalent because:

• E is at most V 2 and log(V 2 ) = 2 log V is O(log V )

• If we ignore isolated vertices, which will each be their own component

of the minimum spanning forest, V ≤ E + 1, so log V is O(log E).

Time complexity of the Kruskal Algorithm=O(E log E)

7
Chapter 4

Horspool Algorithm

4.1 Introduction
The horspool’s algorithm is very simple and efficient pattern matching al-
gorithm. The technique used here is to first align the pattern string to the
beginning of the text string. But, instead of comparing from left to right, we
start comparing from right to left.

4.2 Pseudo Code

• Shift table (p,s)
// Purpose To fill the shift table, based on the pattern string
// Inputs
p- pattern string to be searched
//Output
t- shift table is returned through parameter

m ← length(p)
for i = 0 to 127 do
s[i] ← m
end for
for i = 0 to m-2 do
s[p[i]] ← m − 1 − i
end for
return

• Horspool Pattern Matching (p,t)

8
// Purpose To check whether the pattern string is present in the
text string
// Inputs
p- pattern string to be searched
t- text string where searching takes place
//Output- Position of pattern string p in the text string t if search
successful −1 otherwise
shift table(p,s)
n ← length(t)
m ← length(p)
i←m−1
while i ≤ n − 1 do
k←0
while k ≤ m − 1 and t[i-k]=p[m-1-k] do
k ←k+1
end while
end while
return -1

Time complexity of the Horspool Algorithm=θ(mn)

9
Chapter 5

Binomial Co-efficient using

Dynamic Programming

5.1 Introduction
We know that a binomial formula is given by

(a + b)n = (n C0 an b0 ) + (n C1 an−1 b1 ) + ...................... + (n Cn an−n bn )

Here, n C0 , n C1 , ........... ,n Cn are called the binomial coefficients. the two

useful properties of binomial coefficients are
n
Ck = n−1 Ck−1 + n−1 Ck for n>k >0
n
Ck = 1 for k=0 or n=k

The above recurrence relation can also be written as

C(n,k) = 1 if k=0 or n=k
C(n,k) = C(n-1,k-1) + C(n-1,k) for n>k>0

It is clear from the above recurrence relation that c(n,k) can be computed
by two overlapping problems c(n-1,k-1) and c(n-1,k) and hence this problem
can be solved using dynamic programming.

5.2 Pseudo Code

• Binomial( coefficients [0...level][0...level] )
for i ← 0 to level do
for j ← i do

10
 if j=0 or j=i then
coefficients[i][j] ← 1
else
coefficients[i][j] ← coefficients[i-1][j-1] + coefficients[i-1][j]
end if
end for
end for

Time complexity of the Binomial Coefficient Algorithm=θ(nk)

11
Chapter 6

Prim’s Algorithm

6.1 Introduction
Prim’s algorithm is used to find the minimal spanning tree. The mimimal
spanning tree can be used in many of the applications. Prim’s algorithm is
almost similar to Dijkstra’s algorithm. The only change to be done is, in
Dijkstra The statements
if d[u] + w[u, v]<d[v] then
d[v] ← d[u] + w[u, v]
p[v] ← u
end if
are to be replaced in Prim as follows
if w[u, v]<d[v] then
d[v] ← w[u, v]
p[v] ← u
end if
Another statement to be modified is “After adding u to S” add the fol-
lowing statements:

• Store the edge (n,p[u])

• Find the cost of the spanning tree by adding u + p[u] to sum.

6.2 Pseudo Code

• Prim (n,w)
// Purpose To compute the minimum spanning tree

12
 // Inputs
n- number of vertices in the graph
w- cost adjacency matrix with values ≥ 0
//Output
d- shortest distance from source to all other nodes
p- shortest path from source to destination
s- gives the nodes that are so far visited and the nodes
that are not visited
for i = 0 to n-1 do
s[i] ← 0
d[i] ← w[source, i]
p[i] ← source
end for
s[source] ← 1
sum ← 0
k←0
for i = 1 to n-1 do
find u and d[u] such that d[u] is minimum and u ∈ V − S
add u to S
select an edge with least cost
add cost associated with edge to get total cost of mimimal spanning
tree
for every v ∈ V − S do do
if w[u, v]<d[v] then
d[v] ← w[u, v]
p[v] ← u
end if
end for
end for
if sum ≥ 9999 then
spanning tree does not exist
end if

Time complexity of the Prim’s Algorithm using adjacency matrix =θ(n2 )

where n is number of vertices.

13
Chapter 7

Warshall’s Algorithm

7.1 Introduction
Let G=(V,E) be a simple graph where V is set of vertices and E is the set
of edges. Let N be the number of vertices in graph G. The matrix P(N*N)
whose elements are
P[i,j]= 1 if there is a path from vertex i to vertex j or P[i,j]=0 otherwise
is called path matrix (transitive closure).
Given a graph G=(V,E) , adjacency matrix can be obtained. Using the
adjacency matrix, transitive closure can be obtained. This process of trans-
forming adjacency matrix to transitive closure is done by Warshall’s algo-
rithm.

7.2 Pseudo Code

The algorithm is based on dynamic programming strategy. The steps fol-
lowed are :

1. Copy the Adjacency matrix into another matrix called the Path matrix.

2. Find in the Path matrix for every element in the Graph, the incoming
and outgoing edges

3. For every such pair of incoming and outgoing edges put a 1 in the Path
matrix.

Warshall(A[1...n][1...n])
R(0) ← A
for k ← to n do

14
 for i ← to n do
for j ← to n do
R(k) [i][j] ← R(k−1) [i][j] or R(k−1) [i][j] and R(k−1) [k][j]
end for
end for
end for
return R(n)

Time complexity of the Warshall Algorithm=θ(n3 ) where n is number of vertices

15
Chapter 8

N-queens problem using

Backtracking method

8.1 Introduction
Backtracking is the process of solving the problem by returning to the previ-
ous state in a computation on order to try an alternative strategy. In back-
tracking, multiple solutions can be eliminated without being explicitly exam-
ined. In this method, the solution can be expressed as n-tuple(x1,x2,....,xn).
Problems such as n-queens, sum of subsets etc can be solved using backtrack-
ing.
Given N*N chess board and N-queens, it is required to place all N-queens
on the chess board such that no two queens attach. It can implemented
using backtracking strategy. The function to check whether kth queen can
be placed successfully or not, is shown below:

8.2 Pseudo Code

• place (x[ ],k)
for i = 0 to k do
if x[i] = x[k] or i-x[i]= k- x[k] or i+ x[i]=k+x[k] then
return FALSE
end if
end for
return TRUE
The algorithm to place all N-Queens on the chess board is shown below:
• nqueens(n)

16
 k←1
x[k] ← 0
while k! = 0 do
x[k]+ = 1
while (x[k] ≤ n) and (!place(x,k)) do
x[k]+ = 1
end while
if x[k] ≤ n then
if k = n then
print (x1,x2,x3,....xn)
else
k + +;
x[k] = 0
end if
else
k−−
end if
end while
return

Time complexity of the n-Queens Algorithm=O(n)

where n is the number of coloums.

17