APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

Sixth Semester B.Tech Degree Supplementary Examination May 2023 (2019 Scheme)
Course Code: CST306
Course Name: ALGORITHM ANALYSIS AND DESIGN
PART A
1. Let T(𝑛)=7𝑛+4.Prove that this is of the order of 𝛺(𝑛).
Ans:
f(n) = 7𝑛+4
7𝑛+4 ≥ 7 n for all n ≥ 1
Here c=7 n0=1 g(n)= n
7𝑛+4 = Ω(n)

2. Solve the following recurrence using Master theorem

a) T(𝑛)=8𝑇(𝑛/2)+𝑛2
b) T(𝑛)=2𝑇(𝑛/2)+𝑛
Ans:
a) T(𝑛)=8𝑇(𝑛/2)+𝑛2
a=8 b=2 n2 =Ɵ (n2 log0(n)) k=2 p=0
bk =22 = 4
Here If a>𝑏 𝑘 then T(n) = 𝜃(n (log ba)) = 𝜃(n (log 28)) = 𝜃(n3)

b) T(𝑛)=2𝑇(𝑛/2)+𝑛
a=2 b=2 n =Ɵ (n1 log0(n)) k=1 p=0
k 1
b =2 = 2
Here a= bk and p>-1
T(n) = Ɵ(n(log b a) logp+1(n))
= Ɵ(n(log 2 2) log1(n))
= Ɵ(nlog(n))

3. Define MAKE_SET(x), UNION(x,y) and FIND_SET(x) operations of disjoint set data

structure with a suitable example.
Ans:
o Make Set Operation
 Make-set(x) function will create a set that containing one element x.
 Algorithm Make-set(x)
1. Create a new linked list that contains one node n
2. ndata=x
3. nparent = NULL

o Find Operation
 Determine which subset a particular element is in.
 This will return the representative(root) of the set that the element belongs.
 This can be used for determining if two elements are in the same subset.

Find(3) will return 1, which is the root of the tree that 3 belongs
Find(6) will return 6, which is the root of the tree that 6 belongs

 Find Algorithm
Algorithm Find(n)
1. while nparent != NULL do
1.1 n = nparent
2. return n

Worst case Time Complexity = O(d), where d is the depth of the tree

o Union Operation
 Join two subsets into a single subset.
 Here first we have to check if the two subsets belong to same set. If no, then we
cannot perform union

 Union Algorithm
Algorithm Union(a, b)
1. X =Find(a)
2. Y = Find(b)
3. If X != Y then
1. Yparent = X

Worst case Time Complexity = O(d), where d is the depth of the tree
4. Find any ONE topological ordering of the following the graph
Ans:
A, B, C, D, E, F

5. Give the control abstraction of Divide and Conquer algorithm design strategy
Ans:

Algorithm DAndC(P)
{
if Small(P) then
return S(P)
else
{
Divide P into smaller instances P1, P2, . . . . Pk, k≥1;
apply DAndC to each of these sub-problems;
return Combine(DAndC(P1), DAndC(P2), . . . . , DAndC(Pk));
}
}

6. Apply greedy algorithm for fractional knapsack to find the optimal ordering for loading
the items in the knapsack. Let the knapsack capacity, M=15

Ans:
m = 15
n=3
i  { 1, 2, 3 }
P = {24, 18, 20 }
W = {8, 9, 5 }
P/W= {3, 2, 4 }

Sort p[i]/w[i] ≥ p[i+1]/w[i+1]

i  { 3, 1, 2 }
P = {20, 24, 18 }
W= {5, 8, 9 }
Item Pi Wi Xi U = U-Wi
3 20 5 1 10
1 24 8 1 2
2 18 9 2/9 0
Total Profit = Σ Pi * Xi
=24x1 + 18x2/9 + 20x1 = 48
Solution vector X ={1, 2/9 , 1}

7. Explain about the structure of an optimal paranthesization of matrix-chain multiplication

problem
Ans:
o Ai. .j denote the matrix that results from evaluating the product AiAi+1 . . . Aj where
i<= j
o If i< j, we must split the problem into two subproblems (Ai Ai+1 . . . Ak and Ak+1Ai+1 . .
. Aj ), for some integer k in the range i<= k < j.
o That is, for some value of k, we first compute the matrices Ai. .k and Ak+1. .j. Then
multiply them together to produce the final product Ai. .j .
o Total cost = Cost of computing the matrix Ai. .k+ Cost of computing Ak+1. .j+ Cost of
multiplying them together.

8. Distinguish the branch-and-bound technique from the backtracking technique

Ans:
Backtracking Branch and Bound
Backtracking is a problem-solving Branch n bound is a problem-solving
technique so it solves the decision problem. technique so it solves the optimization
problem.
Backtracking uses a Depth first search. Branch and bound uses Depth first
search/D Search/Least cost search.
In backtracking, all the possible solutions In branch and bound, based on search;
are tried. If the solution does not satisfy the bounding values are calculated. According
constraint, then we backtrack and look for to the bounding values, we either stop there
another solution. or extend.
Applications of backtracking are n-Queens Applications of branch and bound are
problem, Sum of subset. knapsack problem, travelling salesman
problem, etc.
Backtracking is more efficient than the Branch n bound is less efficient.
Branch and bound.

9. Discuss the need for approximation algorithm.

Ans:
 Approximate Solution: A feasible solution with value close to the value of optimal
solution is called an approximate solution
 Approximation Algorithms: An algorithm that returns near optimal solution is
called Approximation Algorithm.
 Approximation algorithms have two main properties:
 They run in polynomial time
 They produce solutions close to the optimal solutions
 Approximation algorithms are useful to give approximate solutions to NP complete
optimization problems.
 It is also useful to give fast approximations to problems that run in polynomial time.
10. Define graph colouring problem
Ans:
Graph coloring is the procedure of assignment of colors to each vertex of a graph G such
that no adjacent vertices get same color. The objective is to minimize the number of
colors while coloring a graph. The smallest number of colors required to color a graph is
called its chromatic number of that graph. Graph coloring problem is a NP Complete
problem.

3 Colorable graph

PART B
11.
a) Define the asymptotic notations: Big Oh, Big Omega, Theta, little oh and little omega
Ans:
 Asymptotic Notations
 It is the mathematical notations to represent frequency count. 5 types of
asymptotic notations
 Big Oh (O)
 The function f(n) = O(g(n)) iff there exists 2 positive constants c and
n0 such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0
 It is the measure of longest amount of time taken by an
algorithm(Worst case).
 It is asymptotically tight upper bound
 Omega (Ω)
 The function f(n) = Ω (g(n)) iff there exists 2 positive constant c and n0
such that f(n) ≥ c g(n) ≥ 0 for all n ≥ n0
 It is the measure of smallest amount of time taken by an
algorithm(Best case).
 It is asymptotically tight lower bound

 Theta (Ɵ)
 The function f(n) = Ɵ (g(n)) iff there exists 3 positive constants c1, c2
and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0
 It is the measure of average amount of time taken by an
algorithm(Average case).
 Little Oh (o)
 The function f(n) = o(g(n)) iff for any positive constant c>0, there
exists a constant n0>0 such that 0 ≤ f(n) < c g(n) for all n ≥ n0
 It is asymptotically loose upper bound

g(n) becomes arbitrarily large relative to f(n) as n approaches infinity

 Little Omega (ω)

 The function f(n) = ω(g(n)) iff for any positive constant c>0, there
exists a constant n0>0 such that f(n) > c g(n) ≥ 0 for all n ≥ n0
 It is asymptotically loose lower bound

f(n) becomes arbitrarily large relative to g(n) as n approaches infinity

b) Solve the following recurrence using recursion tree method:

1)T (𝑛)=𝑇(𝑛/2)+1, 𝑇(1)=1

2) T(𝑛)=2𝑇(𝑛/2)+𝑛2, 𝑇(1)=1
Ans:
1)
T(n) = 1 + T(n/2)
= 1 + [1+ T(n/22)] = 2+ T(n/22)
= 2+ [1+ T(n/23)] = 3+ T(n/23)
……………………
= k + T(n/2k) kth term
Assume n/2k= 1  2k = n  k = log2(n)
T(n) = log2(n) + T(1) = log2(n) + 1
= O(log2(n) )

2)
T(n) = n2 + 2T(n/2)
= n2 + 2[(n/2) 2+2T(n/22)] = n2+n2/2 + 22 T(n/22)
= n + n /2 + 2 [(n/2 ) +2T(n/23)]
2 2 2 2 2
= n2+n2/2 + n2/22 +23 T(n/23)
……………………
= n2[1+ (1/2) + (1/2)2 + …. + (1/2)k-12 ] + 2k T(n/2k) kth term
k k
Assume n/2 = 1  2 = n  k = log2(n)
T(n) = n2 [(1-(1/2)k) / (1-(1/2))] + n T(1)
= 2 n2 [ 1-(1/2k)] + n = 2 n2 [ 1-(1/2log n)] + n
= 2 n2 [ 1-(1/nlog 2)] + n = 2 n2 [ 1-(1/n)] + n
= 2 n2 - 2n+ n
= O(n2)

12.
a) Perform complexity analysis for the following code segments
1) For i=1 to n do

For j = 1 to n do
A=B * C
End for
End for

2) Function F(n)
{
If(n==0)
return(1)
Else
return (n*F(n-1))
}
Ans:
1)
Most frequently executing statement is A=B*C. It will execute n2 times.
So the time complexity = O(n2)

2)
Step/Executio Frequency Total Frequency
n Count Count
n==0 n>0 n≤0 n>0
Function F(n) 0 0 0 0 0
{ 0 0 0 0 0
If(n==0) 1 1 1 1 1
return(1) 1 1 0 1 0
Else 0 0 0 0 0
return (n*F(n-1)) 1 + T(n-1) 0 1 0 1 + T(n-1)
} 0 0 0 0 0
2 2 + T(n-1)
Time Complexity = T(n) = 2 if n<=0
2 + T(n-1) Otherwise
T(n) = 2 + T(n-1)
=2 + 2 + T(n-2)
=2 + 2 + 2+ T(n-3)
=2x3 + T(n-3)
. . .
=2xn +T(n-n)
=2n + 2

b) Discuss the concept of best case, worst case and average case complexity of an
algorithm with linear search algorithm.
Ans:
 In certain case we cannot find the exact value of frequency count. In this case we
have 3 types of frequency counts
 Best Case : It is the minimum number of steps that can be executed for a given
parameter
 Worst Case: It is the maximum number of steps that can be executed for a
given parameter
 Average Case: It is the average number of steps that can be executed for a
given parameter
 Example: Linear Search
 Best Case: Search data will be in the first location of the array.
 Worst Case: Search data does not exist in the array
 Average Case: Search data is in the middle of the array.
Best Case Worst Case Average Case
S/E F TFC S/E FC TFC S/E FC TFC
C
Algorithm Search(a,n,x) 0 0 0 0 0 0 0 0 0
{ 0 0 0 0 0 0 0 0 0
for i:=1 to n do 1 1 1 1 n+1 n+1 1 n/2 n/2
if a[i] ==x then 1 1 1 1 n n 1 n/2 n/2
return i; 1 1 1 1 0 0 1 1 1
return -1; 1 0 0 1 1 1 1 0 0
} 0 0 0 0 0 0 0 0 0
3 2n + n+1
2
Best Case Complexity = 3 = Ω(1)
Worst Case Complexity = 2n + 2 = O(n)
Average Case Complexity = n+1 = Ɵ(n)

13.
a) What are the operations supported by Disjoint Data Structure? Explain the working of
Disjoint Set Data Structure for computing Connected Components of an undirected
graph given in the following Figure.
Ans:
o Disjoint Set operations
 Make set
 Union
 Find

o Make Set Operation

 Make-set(x) function will create a set that containing one element x.
 Algorithm Make-set(x)
1. Create a new linked list that contains one node n
2. ndata=x
3. nparent = NULL

o Find Operation
 Determine which subset a particular element is in.
 This will return the representative(root) of the set that the element belongs.
 This can be used for determining if two elements are in the same subset.

Find(3) will return 1, which is the root of the tree that 3 belongs
Find(6) will return 6, which is the root of the tree that 6 belongs

 Find Algorithm
Algorithm Find(n)
3. while nparent != NULL do
1.1 n = nparent
4. return n

Worst case Time Complexity = O(d), where d is the depth of the tree

o Union Operation
 Join two subsets into a single subset.
 Here first we have to check if the two subsets belong to same set. If no, then
we cannot perform union
i 1 2 3 4 5 6 7
P -1 1 1 1 6 1 6
 Union Algorithm
Algorithm Union(a, b)
4. X =Find(a)
5. Y = Find(b)
6. If X != Y then
1. Yparent = X

Worst case Time Complexity = O(d), where d is the depth of the tree

 The Disjoint Set Data Structure is a way to efficiently represent a collection of

disjoint sets and perform operations on them. It's commonly used for tasks like
finding connected components in an undirected graph.
 Here's how it works:
 Initialization: Each vertex in the graph is initially placed in its own set.
 Union Operation (Merge): When an edge between two vertices is encountered,
we merge the sets containing those vertices. This is done by finding the root of
the sets each vertex belongs to and making one of the roots the parent of the
other. This effectively merges the two sets into one.
 Find Operation (Parent): This operation determines which set a particular
vertex belongs to. It's done by recursively traversing through the parent pointers
until the root of the set is reached. The root of each set serves as a unique
identifier for that set.
 Path Compression (Optimization): To improve the efficiency of the Find
operation, we apply path compression. This means that when we find the root of
a set for a vertex, we make all the vertices along the path from that vertex to the
root point directly to the root. This flattens the structure of the tree representing
the sets, reducing the time complexity of future Find operations.
 Using these operations, we can efficiently find connected components in the graph:
Initially all vertices are belong to different sets

Consider all edges one at a time. Initially consider the edge (a, b). Using FIND
operation we came to know that a and b are belongs to different sets. So perform
UNION operation. The resultant sets are

Then consider the edge (a, c). Using FIND operation we came to know that a and c
are belongs to different sets. So perform UNION operation. The resultant sets are

Then consider the edge (b, c). Using FIND operation we came to know that b and c
are belongs to the same set. So do nothing.
Then consider the edge (b, d). Using FIND operation we came to know that b and d
are belongs to different sets. So perform UNION operation. The resultant sets are

Then consider the edge (e, f). Using FIND operation we came to know that e and f
are belongs to different sets. So perform UNION operation. The resultant sets are
Then consider the edge (e, g). Using FIND operation we came to know that e and g
are belongs to different sets. So perform UNION operation. The resultant sets are

Then consider the edge (h, i). Using FIND operation we came to know that h and i
are belongs to different sets. So perform UNION operation. The resultant sets are

All edges are completed. From the above sets we can conclude that there are 4
connected components.
{a,b,c,d}
{e,f,g}
{h,i}
{j}
b) Illustrate the advantage of AVL trees with a suitable example. Discuss the various
rotations required to balance the height of AVL tree during insertion and deletion
Ans:
 AVL Tree can be defined as height balanced binary search tree in which each
node is associated with a balance factor.

 Balance Factor
 Balance Factor of a node = height of left subtree – height of right subtree
 In an AVL tree balance factor of every node is -1,0 or +1
 Otherwise the tree will be unbalanced and need to be balanced.
 Why AVL Tree?
 Most of the Binary Search Tree(BST) operations (eg: search, insertion,
deletion etc) take O(h) time where h is the height of the BST.
 The minimum height of the BST is log n
 The height of an AVL tree is always O(log n) where n is the number of nodes
in the tree.
 So the time complexity of all AVL tree operations are O(log n)
 An AVL tree becomes imbalanced due to some insertion or deletion operations
 We use rotation operation to make the tree balanced.
 There are 4 types of rotations

 Single Left Rotation(LL Rotation)

 In LL rotation every node moves one position to left from the current
position

 Single Right Rotation(RR Rotation)

 In RR rotation every node moves one position to right from the current
position
 Left-Right Rotation(LR Rotation)
 The LR rotation is the combination of single left rotation followed by
single right rotation.

 Right-Left Rotation(RL Rotation)

 The RL rotation is the combination of single right rotation followed by
single left rotation.

14.
a) Give BFS algorithm for graph traversal and perform its complexity analysis
Ans:
 Algorithm BFS(G, u)
1. Set all nodes are unvisited
2. Mark the starting vertex u as visited and put it into an empty Queue Q
3. While Q is not empty
3.1 Dequeue v from Q
3.2 While v has an unvisited neighbor w
3.2.1 Mark w as visited
3.2.2 Enqueue w into Q
4. If there is any unvisited node x
4.1 Visit x and Insert it into Q. Goto step 3
 Complexity
 If the graph is represented as an adjacency list
 Each vertex is enqueued and dequeued atmost once. Each queue
operation take O(1) time. So the time devoted to the queue operation is
O(V).
 The adjacency list of each vertex is scanned only when the vertex is
dequeued. Each adjacency list is scanned atmost once. Sum of the
lengths of all adjacency list is |E|. Total time spend in scanning
adjacency list is O(E).
 Time complexity of BFS = O(V) + O(E) = O(V+ E).
 In a dense graph:
 E=O(V2)
 Time complexity= O(V) + O(V2) = O(V2)
 If the graph is represented as an adjacency matrix
 There are V2 entries in the adjacency matrix. Each entry is checked
once.
 Time complexity of BFS = O(V2)

b) Perform the following operations in the given AVL trees.

1) Insert 54 in Tree 1 2) Delete 15 from Tree 2.
Ans:
1)
Inset 54→

X=78,Y=50,Z=54
PERFORM RIGHT LEFT ROTATION

LL(50)→
RR(78)→

2)
Delete 15→

X=51,y=10,z=60
PERFORM RIGHT LEFT ROTATION
RR(70)→
LL(60)→

15.
a) Write a divide and conquer algorithm for 2-way merge sort and perform its
complexity analysis.
Ans:
 Given a sequence of n elements a[l],…...a[n]. Split this array into two sets
a[l],,.a.[n/2] and a[(n/2)+1],…a[n]. Each set is individually sorted, and the resulting
sorted sequences are merged to produce a single sorted sequence of n element.

Algorithm MergeSort(low, high)

{
mid = (low + high )/2;
MergeSort(low, mid);
MergeSort(mid+1, high);
Merge(low, mid, high);
}
Algorithm Merge(low, mid, high)
{
i= low; x= low; y= mid + 1;
while((x ≤ mid) and (y ≤ high)) do
{
if ( a[x] ≤ a[y] ) then
{
b[i] = a[x];
x = x+1;
}
else
{
b[i] = a[y];
y = y+1;
}
i=i+1;
}
if( x ≤ mid) then
{
for k=x to mid do
{
b[i] = a[k];
i =i+1;
}
}
else
{
for k=y to high do
{
b[i] = a[k];
i =i+1;
}
}
for k= low to high do
a[k] = b[k];
}

 Complexity
T(n) = a if n=1
2 T(n/2) + cn Otherwise

a is the time to sort an array of size 1

cn is the time to merge two sub-arrays
2 T(n/2) is the complexity of two recursion calls
T(n) = 2 T(n/2) + c n
= 2(2 T(n/4)+c(n/2)) + c n
= 22T(n/22) + 2 c n
= 23T(n/23) + 3 c n
..............
= 2kT(n/2k) + k c n [Assume that 2k =n k=log n]
= n T(1) + c n log n
= a n + c n log n
= O(n log n)
Best Case, Average Case and Worst Case Complexity of Merge Sort = O(n log n)

b) Give Kruskal‟s algorithm for minimum cost spanning tree computation. Apply the
algorithm to find the minimum cost spanning tree for the following graph
Ans:
Algorithm Kruskals(E, cost, n, t)
{
Construct a heap out of edge costs using Heapify();
for i=1 to n do
parent[i] = -1;
i=0;
mincost = 0.0;
while (i < n-1) and (heap not empty) do
{
Delete a minimum cost edge (u, v) from the heap and reheapify using Adjust();
j = Find(u);
k = Find(v);
if j ≠ k then
{
i = i+1;
t[i, 1] = u; t[i, 2] = v;
mincost = mincost + cost[u, v];
Union(j, k);
}
}
if i ≠ n-1 then
Write (“No Spanning Tree”);
else
return mincost;
}
This is the minimum cost spanning tree and its cost = 60
16.
a) Write Dijkstra‟s algorithm for single source shortest path. Perform its complexity
analysis.
Ans:
 Algorithm Dijkstra(G,W, S)
1. For each vertex v in G
1.1 distance[v] = infinity
1.2 previous[v] = Null
2. distance[S] = 0
3. Q = set of vertices of graph G
4. While Q is not empty
4.1 u = vertex in Q with minimum distance
4.2 remove u from Q
4.3 for each neighbor v of u which is still in Q
4.3.1 alt = distance[u] + W(u,v)
4.3.2 if alt < distance[v]
4.3.2.1 distance[v] = alt
4.3.2.2 previous[v] = u
5. Return distance[], previous[]

 Complexity
 The complexity mainly depends on the implementation of Q
 The simplest version of Dijkstra's algorithm stores the vertex set Q as an
ordinary linked list or array, and extract-minimum is simply a linear search
through all vertices in Q. In this case, the running time is O(E + V2) = O(V2)
 Graph represented using adjacency list can be reduced to O(E log V) with the
help of binary heap.

b) Write the control abstraction for Greedy design technique. Give a greedy algorithm
for fractional knapsack problem.
Ans:

o Control Abstraction
Greedy(a, n) //a[1..n] contains n inputs
{
solution = Φ;
for i=1 to n do
{
x = Select(a);
if Feasible(solution, x) then
solution = Union(solution, x);
}
return solution;
}
 Select() selects an input from the array a[] and remove it. The selected input
value is assigned to x.
 Feasible() is a Boolean valued function that determines whether x can be
included into the solution subset.
 Union() combines x with the solution and updates the objective function.
 Fractional Knapsack Problem
o We are given with n objects and a knapsack(or bag) of capacity m. The object i
has weight Wi and profit Pi. If a fraction Xi is placed into the knapsack, then a
profit PiXi is obtained. The objective is to obtain an optimal solution of the
knapsack that maximizes the total profit earned.
o The total weight of all the chosen objects should not be more than m.
o Fractional knapsack problem can be stated as
Maximize 𝑛𝑖=1 𝑃𝑖𝑋𝑖 1
𝑛
Subject to 𝑖=1 𝑊𝑖𝑋𝑖 ≤m 2

0 ≤ Xi ≤ 1 and 1 ≤ i ≤ n 3
The profits and weights are positive numbers.
o A feasible solution is one that satisfies equation 2 and 3.
o An optimal solution is a feasible solution that satisfies equation 1.
o In greedy strategy we are arranging the objects in the descending order of
profit/weight.
o Algorithm
Algorithm GreedyKnapsack(m, n)
//p[1:n] is the profits and w[1:n] is the weights of n objects such that p[i]/w[i] ≥
p[i+1]/w[i+1].
{
for i= 1 to n do
x[i] = 0.0; // x[1:n] is the solution vector
U = m; // m is the knapsack capacity
for i=1 to n do
{ if w[i] > U then
break;
x[i] = 1.0
U = U – w[i];
}
If i ≤ n then
x[i] = U / w[i];
}
o Time Complexity
 The for loop will execute maximum n times. So the time complexity = O(n)
17.
a) Write Floyd Warshall algorithm for all pair shortest path problem and perform its
complexity analysis
Ans:
Algorithm FloydWarshall(cost[][], n)
{
for i=1 to n do
for j=1 to n do
D[i, j] = cost[i, j]
for k := 1 to n do
for i := 1 to n do
for j := 1 to n do
D[i, j] = min{D[i, j] , D[i, k] + D[k, j]
Return D
}
 Time Complexity
 Floyd Warshall Algorithm consists of three loops over all the nodes. Each
loop has constant complexities.
 Hence, the time complexity of Floyd Warshall algorithm = O(n3), where n is
the number of nodes in the given graph.

b) Define Travelling Salesman Problem. Solve the following instance of TSP using
branch and bound technique. The cost matrix is given below:

Ans:
18.
a) Consider the following four matrices and perform chain matrix multiplication using
the dynamic programming approach. Finally give the optimal cost of multiplication
and optimal parenthesization

Ans:

b) Define n-queens problem. Draw the state space tree for 4-queens problem using
backtracking method
Ans:
 n-Queens Problem
 n queens are to be placed on a n x n chessboard so that no two attack. That is, no
two queens are on the same row, column, or diagonal.
State Space Tree of 4 Queens Problem

19.
a) Explain the benefits of randomized algorithm over deterministic algorithm. Discuss
briefly the major categories of randomized algorithms. Give example for each
category.
Ans:
 Randomized Algorithm
o Deterministic Algorithm: The output as well as the running time are functions
of the input only.

o Randomized Algorithm: The output or the running time are functions of the
input and random bits chosen

 An algorithm that uses random numbers to decide what to do next

anywhere in its logic is called Randomized Algorithm
 Typically, this randomness is used to reduce time complexity or space
complexity in other standard algorithms
 It hopes to achieve good performance in the "average case" over all
possible choices of random bits.

o Type of Randomized Algorithms

 Randomized Las Vegas Algorithms

 Output is always correct and optimal.
 Running time is a random number
 Running time is not bounded
 Example: Randomized Quick Sort
 Randomized Monte Carlo Algorithms:
 May produce correct output with some probability
 A Monte Carlo algorithm runs for a fixed number of steps. That is the
running time is deterministic
o Example1: Finding an „a‟ in an array of n elements
 Input: An array of n≥2 elements, in which half are „a‟s and the other
half are „b‟s
 Output: Find an „a‟ in the array

 Las Vegas algorithm

Algorithm findingA_LV(A, n)
{
repeat
{
Randomly choose one element out of n elements
}until(‘a’ is found)
}
 The expected number of trials before success is 2.
 Therefore the time complexity = O(1)

 Monte Carlo algorithm

Algorithm findingA_MC(A, n, k )
{
i=0;
repeat
{
Randomly select one element out of n elements
i=i+1;
}until(i=k or ‘a’ is found);
}
 This algorithm does not guarantee success, but the run time is
bounded. The number of iterations is always less than or equal
to k.
 Therefore the time complexity = O(k)

b) Define bin packing problem. Discuss the first fit strategy for solving it. State the
approximation ratio of the algorithm
Ans:
 Bin packing problem: Given n items of different weights and bins each of capacity
c, assign each item to a bin such that number of total used bins is minimized. It may
be assumed that all items have weights smaller than bin capacity

 First Fit Algorithm

 Scan the previous bins in order and find the first bin that it fits.
 If such bin exists, place the item in that bin
 Otherwise use a new bin.
 Time Complexity
o Best case Time Complexity = θ(n log n)
o Average case Time Complexity = θ(n2)
o Worst case Time Complexity = θ(n2)

 Example: Apply different Bin packing approximation algorithms on the following

items with bin capacity=10. Assuming the sizes of the items be {5, 7, 5, 2, 4, 2, 5, 1,
6}.
 Minimum number of bins >= Ceil ((Total Weight) / (Bin Capacity))
= Ceil (37 / 10) = 4
 First Fit
Number of bins required = 5

20.
a) Give a randomized version of quicksort algorithm and perform its expected running
time analysis.
Ans:

Algorithm randQuickSort(A[], low, high)

1. If low >= high, then EXIT
2. While pivot 'x' is not a Central Pivot.
2.1. Choose uniformly at random a element from A[low..high]. Let the randomly
picked element be x.
2.2. Count elements in A[low..high] that are smaller than x. Let this count be sc.
2.3. Count elements in A[low..high] that are greater than x. Let this count be gc.
2.4. Let n = (high-low+1). If sc >= n/4 and gc >= n/4, then x is a central pivot.
3. Partition A[low..high] into two subarrays. The first subarray has all the elements of A
that are less than x and the second subarray has all those that are greater than x. Now
the index of x be pos.
4. randQuickSort(A, low, pos-1)
5. randQuickSort(A, pos+1, high)

Number times while loop runs before finding a central pivot?

o The probability that the randomly chosen element is central pivot is 1/n.
o Therefore, expected number of times the while loop runs is n.
o Thus, the expected time complexity of step 2 is O(n).

b) Prove that vertex cover problem is NP Complete.

Ans:
 The vertex Cover of a graph is defined as a subset of its vertices, such for every
edge in the graph, from vertex u to v, at least one of them must be a part of the
vertex cover set.
 Vertex cover problem is to find the minimum sized vertex cover of the given
graph.

 Steps to prove that Vertex Cover is a NP-Complete problem

o Step 1:Write a polynomial time verification algorithm to prove that the given problem
is NP
 Inputs: <G, k,V‟>
 Verifier Algorithm:
1. count = 0
2. for each vertex v in V‟ remove all edges adjacent to v from set E
a. increment count by 1
3. if count = k and E is empty then the given solution is correct
4. else the given solution is wrong
 This algorithm will execute in polynomial time. Therefore VERTEX
COVER problem is a NP problem.

o Step 2: Write a polynomial time reduction algorithm from CLIQUE problem to

VERTEX COVER problem
 Algorithm
Inputs: <G=(V,E), k>
1. Construct a graph G‟, which is the complement of Graph G
2. If G‟ has a vertex cover of size |V| - k, then G has a clique of size
k.

 Example:

G=(V, E) G‟=(V, E‟)

Vertex cover of G‟ is {1,2}

Size of vertex cover of G‟ is 2.
If so G has a clique of size |V| - 2 = 5
 This reduction algorithm(CLIQUE to VERTEX COVER) is a
polynomial time algorithm
 So CLIQUE problem is NP Hard.
 Conclusion
o VERTEX COVER problem is NP and NP-Hard.
o So it is NP-Complete