Spring
2013
Bachelor
of Science in Information Technology (BSc IT) – Semester 4
BT0080
– Fundamentals of Algorithms – 4 Credits
(Book ID: B1092)
Assignment Set
(60 Marks)
1.
Write the
different characteristics of an algorithm.
Ans.- There are three important
characteristics of an algorithm.
A.
Finiteness:- An algorithm
must terminate after a finite number of steps and further each step must be
executable in finite amount of time. In order to establish a sequence of steps
as an algorithm, it should be established that it terminates on all allowed
inputs.
B.
Definiteness:- Each step of an
algorithm must be precisely defined, the action to be carried out must be
rigorously and unambiguously specified for each case. However, the method is
not definite, as two different executions may yield different outputs.
C.
Effectiveness:- An algorithm should be effective. This
means that each of the operations to be performed in an algorithm must be
sufficiently basic that it can, in principle, be done exactly and in a finite
length of time, by a person using pencil and paper. It may be noted that the
‘FINITENESS’ condition is a special case of ‘EFFECTIVENESS’. If a sequence of
steps is not finite, then it can’t be effective also. A method may be designed
which is a definite sequence of actions but is not finite.
2.
Explain in the
asymptotic notations.
Ans.- We often want to know a quantity only
approximately and not necessarily exactly, just to compare with another
quantity. And, in many situations, correct comparison may be possible even with
approximate values of the quantities. The advantage of the possibility of
correct comparisons through even approximate value may be much less than the
time required to find exact values. We will introduce five approximation
functions and their notations.
The
purpose of these asymptotic growth rate functions to be introduced, is to
facilitate the recognition of essential character of a complexity function
through some simpler functions delivered by these notations. For example a
complexity function f(n) = 5004n2+83n2+19n+408, has
essentially same behavior as that of g(n)=n3 as the problem size n
becomes larger and larger. But g(n)=n3 is much more understandable
and its value easier to compute than the function f(n).
A.
O-notation:- for function
g(n), we define O(g(n)), big-O of n, as the set:
Intuitively: Set of all functions whose
rate of growth is the same as or lower than that of g(n).
g(n) is an
asymptotic upper bound for f(n).
B.
Ω-notation:- for function g(n), we define Ω(g(n)), big
omega of n, as the set:
Intuitively: set of all functions whose
rate of growth is the same as or higher than that of g(n).
g(n) is an asymptotic lower bound for
f(n).
C.
Ө-notation:- for function
g(n), we define Ө(g(n)), big-theta of n, as the set:
Intutively:
set
of all functions that have the same rate of growth as g(n).
g(n) is an asymptotically tight bound
for f(n).
3.
Write an
algorithm of insertion sort and explain with an example.
Ans.- It is a sorting
algorithm that used for sort or arrange the final sorted array in any
particular sequential order like ascending or descending.
Lets
look the picture of insertion sort algorithm as follows:
Lines Time Cost
For jß2
to length[Array] n C1
Do key ßArray[j] n-1 C2
/**Comments*/ 0 ---
ißj-1 n-1 C3
while i>0 and Array[i]>key nΣj=2
tj C4
do Array[i+1]ßArray[i] nΣj=2 (tj-1) C5
ißi-1 nΣj=2
(tj-1) C6
Array[i+1] ß
Key n-1 C7
1.
You all will notice in this algorithm 1st line is
taking running time n and costing C1.
2.
Line number 2nd, 3rd, and 7th
is taking running time n-1 and costing C2, C3, C7 respectively.
3.
Line number 4th is taking running time nΣj=2 tj-1. We
have taken summation to make our calculation more easier.
4.
There is no sense of the /**Comments*/ it is ignored by the
compiler so don’t be confuse.
Now why we have taken nΣj=2
tj and nΣj=2 tj-1 respectively as follows:
Lets take simple example of while loop:
while{ :t2+t3+t4+t5+t6+……….+tn
statement; :t2-1+t3-1+t4-1+t5-1+t6-1+………+tn-1
}
Now here you will notice
the particular timing of the while and the statement so therefore you can write
nΣj=2 tj i.e. j=2,3,4,5,……,n and tj=t2,t3,t4,t5,…….tn similarly for nΣj=2
(tj-1).
We will go through how
above algorithm works using an simple example as follows”
=> [8][3][1][6][2][4] <--------------
this is our given unsorted array.
↑ ↑
i j now
here key is set to [3] because j is at position Array[2]
=>
[3][8][1][6][2][4]
↑ ↑
i j now here key is ser to [1]
because j is at position Array[3]
=>
[3][1][8][6][2][4] Algo will check till
the beginning of array.
=> [1][3][8][6][2][4]
↑ ↑
i
j now here key is set to [6] because j is at position
Array[4]
=> [1][3][6][8][2][4]
↑ ↑
i j now
here key is set to [2] because j is at position Array[5]
=> [1][3][6][2][8][4]
=> [1][3][2][6][8][4]
=> [1][2][3][6][8][4]
↑ ↑
i j now here key is set to [4] because j is at position array[6]
=> [1][2][3][6][4][8]
=>
[1][2][3][4][6][8] <---------- this
is our shorted array
1.
In the above procedure you will see j is set to position 2 and i
is set to j-1 that is position 1.
2.
Position where j is set is the key element in Array which is used
to compare with other element in the array according to algorithm.
3.
As you will notice here j is set to position 2 and i is set to
position 1, element of Array[1]>Array[2] i.e. [8]>[3] validating
condition “while i>0 and
Array[i]>Key”
4.
Putting value of Array[i] into Array[i+1] i.e. putting element
of Array[1] into Array[2] i.e. [8] into place of [3] according to algo line “Array[i+1] <----Array[i]” and then
i=i-1 till beginning of array to get higher element in array if present. And
key is put into position of Array[1] because here key is Array[2]. Last process
done according to “Array[i+1]<----Key”.
5.
These all above four repeated till the given is not sorted. One
more thing kept in your mind that when Array[i]>Key is true then while loop
is executed in algorithm. We can’t say that how much time while loop will take
to execute i.e. we have to assume that for j time taken is t2,t3,……..,tn.
4. Write short notes on (i) Path Matrix
and (ii) Circuit Matrix
Ans.- (i) Path Matrix:-
This matrix is used in communications and transport networks. This is also a
(0,1) matrix, which is defined for a specific pair of vertices in a graph,
(x,y) and its denoted by P(x,y). the rows in P(x,y) correspond to defferent
paths between vertices x and y and the columns correspond to the edges in G.
Definition:- P(x,y)=(Pij)p,q
where p=number of paths between x and y and
Q= total number of edges.
1, if jth edge lies
in ith path, and
Pij=
0, otherwise
Observations:-
I.
A column of all 0’s corresponds to an edge that does not lie in
any path between x and y.
II.
A column of all 1’s corresponds to an edge that lies in every
path between x and y.
III.
There is no row with all 0’s
Theorem:- if the edges of a connected grapgh
are arranged in the same order for the columns of the incidence matrix / and
the path matrix P(x,y), then the product (mod 2)
/.PT(x,y)
= M
Where, the matrix M has
1’s is two rows x and y, and the rest of the n-2 rows are all 0’s.
(ii) Circuit Matrix:- Let the mumber of edges
in G be e and the number of circuits in g be q. Then, a circuit matrix:
B = bij qxe,
(0,1)-matrix defined as follows;
Bij = 1 if the
ith circuit includes the jth edge;
= 0 oterwise.
The circuit B of G may be
denoted by B(G).
Example:- consider the
graph given in figure
For this graph, n = number
of vertices = 6
e =
number of edges = 8
here, the graph has 4
different circuits;
{a,b}, {c,d,f,e}, {d,f,g}
and {c,e,g}
Therefore,
the circuit matrix B(G) is a 4x8, (0,1)-matrix as given below
a b c d e f g h
1 1 1 0 0 0 0 0 0
B(G) = 2
0 0 1 0 1 0 1 0
3 0 0 0 1 0 1 1 0
4 0 0 1 1 1 1 0 0
4x8
Observations:
i.
If a column of B(G) contains all zeros, then the related edge
doesn’t belong to any circuit. An edge that doesn’t lie in any circuit is said
to be a non-circuit edge.
ii.
Each row of B(G) corresponds to a circuit. So each row may be
called as a circuit vector.
iii.
If a row contains only one “1”, then the related edge is a
self-loop.
iv.
The number of 1’s in the ith-row is equal to the
number of the edges is the ith circuit.
v.
If
a graph G is separable (or disconnected) and consists of two blocks (or
components) g1 and g2 then the circuit matrix B(G) can be written in a clock-
diagonal
form as B(G) = where, B(g1) and B(g2)
are the circuit
matrices
of g1 and g2 respectively.
5.
Explain
Greedy method strategy and also write algorithm for it.
Ans.- It is used to
solve problems that have ‘n’ inputs and require us to obtain a subset that
satisfies some constraints. Any subset that satisfied the constraints is called
as a feasible solution that optimizes the given objective functions.
The greedy method suggests that one can divide the
algorithm that works in stages. Considering one input at a time. At each stage
a decision is made regarding weather or particular input is in the optimum
solution. For this purpose all the inputs must be arranged in a particular
order by using a selection process. If the inclusion of next input in to the
partially constructed solution will result in an infeasible solution then the
input will not be considered and will not be added to partially constructed set
otherwise it is added.
Algorithm for Greedy method strategy
1. Algorithm
Greedy (a,n)
2. //a[1:n]
contains the n inputs
3. {
4. Solution:
= Φ;//initialize the solution
5. for
i:=1 to n do
6. {
7. x:=select
(a);
8. if
feasible (solution, x) then
9. solution:=Union(solution,x);
10. }
11. Return
solution
12. }
6. Explain O/I Knapsack Problem with
algorithm.
Ans.- To use the
branch-and-bound technique to solve any problem, it is first necessary to
conceive of a state space tree for the problem.
The
objective function Σpixi is replaced by the function –Σpixi.
Clearly, Σpixi is maximized iff - Σpixi is
minimized. This modified knapsack problem is stated as given below
Minimize-
Subject to
xi = 0 or 1,
1≤i≤n
We continue the discussion
assuming a fixed tuple size formulation for the solution space. The discussion
is easily extended to the variable tuple size formulation. Every leaf node in
the state space tree represents an assignment for which 
is an answer node. All other leaf nodes are
infeasible. For a minimum-cost answer node to correspond to any optional
solution, we need to define 
for every answer node x. The cost c(x) = ∞ for infeasible leaf nodes. For
non-leaf nodes, c(x) is recursively defined to be min{c(lchild)x)),
c(rchild(x))}
is an answer node. All other leaf nodes are
infeasible. For a minimum-cost answer node to correspond to any optional
solution, we need to define for every answer node x. The cost c(x) = ∞ for infeasible leaf nodes. For
non-leaf nodes, c(x) is recursively defined to be min{c(lchild)x)),
c(rchild(x))}
Algorithm for O/I Knapsack Problem
1. Algorithm
U Bound(cp, cq, k, m)
2. //
cp is the current profit total, cw is the current
3. //
weight total; k is the index of the last removed
4. //
item; and m is the knapsack size
5. //
w[i] and p[i] are respectively the weight and profit
6. //
of the ith object
8. B:=cp;
c:=cw;
9. for
l:=k+1 to n do
10. {
11. if (c+w[i]≤m) then
12. {
13. c:c+w[i]; b:=b-[i];
14. }
15. }
16. return
b;
No comments:
Post a Comment