DESIGN AND ANALYSIS OF

ALGORITHM
UNIT-III

IT-3 1/11/2024 1
 CONTENTS
 Divide and Conquer.
 Matrix Multiplication.
 Convex Hull.
 Searching.

 Greedy Mehtod.
 Activity selection problem.
 Knapsack problem.
 Minimum Spinning tree.
 Single Source Shortest path.

IT-3 1/11/2024 2
 Divide and Conquer:

 In divide and conquer method, a given problem is,

i. Divided into smaller sub problems.
ii. These sub problems are solved independently.
iii. Combining all the solutions of sub problems into a solution of the whole.

 If the sub problems are large enough the divide and conquer is reapplied.
 The generated sub problems are usually of same type as the original problem.
Hence recursive algorithms are used in divide and conquer strategy.

IT-3 1/11/2024 3
IT-3 1/11/2024 4
 Application Of Divide and Conquer with their Time Complexity:

Worst-case Best-case running Average-case

Algorithm
running time time running time

Selection sort Θ(n^2) Θ(n^2) Θ(n^2)

Insertion sort Θ(n^2) Θ(n) Θ(n^2)

Merge sort Θ(nlogn) Θ(nlogn) Θ(nlogn)

Quicksort Θ(n^2) Θ(nlogn) Θ(nlogn)

IT-3 1/11/2024 5
 Matrix Multiplication :

STRASSEN MATRIX:

Strassen showed that 2x2 matrix multiplication can be

accomplished in 7 multiplication and 18 additions or
subtractions.

The divide and conquer approach can be used for

implementing Stressen’s matrix multiplication.

IT-3 1/11/2024 6
P1 = (A11+ A22)(B11+B22)
P2 = (A21 + A22) * B11
P3 = A11 * (B12 - B22) C11 = P1 + P4 - P5 +P7
P4 = A22 * (B21 - B11) C12 = P3 + P5
P5 = (A11 + A12) * B22 C21 = P2 + P4
P6 = (A21 - A11) * (B11 + B12) C22 = P1 + P3 - P2 + P6
P7 = (A12 - A22) * (B21 + B22)

IT-3 1/11/2024 7
 Time Analysis

IT-3 1/11/2024 8
 Convex Hull:

There exist a set of points on a plane which is said to be convex if for any two
points A and B in the set, the entire line segment with the end points at A and
B belongs to the set

Algorithm

Step 1: Sort the points(p1,p2,p3,…..pn) by their x coordinates.

Step 2: Repeatedly find the convex hull through p1 to p n/2.
Step 3: Repeatedly find the convex hull through p n/2+1 to pn.
Step 4: Merge the two convex hulls.

The merge procedure requires finding a bridge between two hulls that are
adjacent to each other. Left part of the left hull and right part of right hull.

IT-3 1/11/2024 9
 Example :

IT-3 1/11/2024 10
IT-3 1/11/2024 11
 Binary Searching:

Binary search is the most popular Search algorithm.It is efficient and also
one of the most commonly used techniques that is used to solve problems.

RULES FOR BINARY SEARCHING :

1. Find the middle element of array( A[MID] ).
2.Compare the middle element with the data to be searched , then there are
three cases:-
( a ). If middle element is a desired element then search is successful.
( b ). If middle element is less than desired element then search only the first
half of the array.
( c ). If middle element is greater than desired element then search only the
second half of the array.

IT-3 1/11/2024 12
 ALGORITHM OF BINARY SEARCHING

• A=Sorted Array.
• LOC=Location.
• Beg= Beginning LOC.
• Mid= Middle LOC.
• End= End LOC.
Step 1: Input an array A of n elements and data to be stored.
Step 2: Beg=0, End=n; Mid=int((Beg+End )/2).
Step 3: Repeat step 4 and 5 while(Beg<=End)and (A[Mid]!=data).
Step 4: if(data<A[Mid])
( a) Beg=Mid-1.
Step 5: Else
( a ) Beg=Mid+1.
Step 6: Mid= int((Beg+End)/2).
Step 7: If (A[Mid]==data)
( a ) Display the data found.
Step 8: Exit.
IT-3 1/11/2024 13
 Search element 40 in the following array elements:-
Beg End
9 10 25 30 40

Step 1: A[0] A[1] A[2] A[3] A[4]

Beg=0; End=4
Mid =int((0+4)/2)= 2
A[Mid]=A[2]=25
Step 2:
A[2]!=40, 40<25 i. e. Reinitialize the variable
Beg=2+1=3, End=4
Mid=int((3+4)/2)=3 Step 5:
A[Mid]=A[3]=30 Since (A[4]==data),
Step 3: 40==40
A[3]!=40, 40<30, i.e. Reinitialize the variable A[4]=40, 40=40.
Beg=3+1=4, End=4
Mid=int((4+4)/2)=4

Searching is successful . Element present on 5th position

IT-3 1/11/2024 14
 The worst case time complexity of binary search is O(log2n)

Advantage :-
• The binary search is fast as compared to linear search.
• Most suitable for sorted array.
Disadvantage :-
• The list must be sorted.
• Direct access to the middle element in any sub list.
• Time complexity is high in both average and worst case.

IT-3 1/11/2024 15
 Greedy Algorithm:

A greedy algorithm, as the name suggests, always makes the choice that seems to be
the best at that moment. This means that it makes a locally-optimal choice in the
hope that this choice will lead to a globally-optimal solution.

 General design technique

 Used for optimization problems
 Simply choose best option at each step
Solve remaining sub problems after making greedy step

IT-3 1/11/2024 16
 Pseudo code for Greedy Algorithm:

Algorithm Greedy ( a, n )
//a[1:n]contains the n inputs.
{
solution:=0;//initialize the solution.
for i:=1 to n do
{
x:=Select(a);
if Feasible( solution, x)
then

solution:=Union(solution x);
}
return solution;
}

IT-3 1/11/2024 17
 Continued…

 Select() selects an input from a[] and removes 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 vector(no constraints are violated).

 Union() combines x with the solution and updates the objective function.

IT-3 1/11/2024 18
 Application of Greedy Method :

• Travelling Salesman Problem

• Prim's Minimal Spanning Tree Algorithm

• Kruskal's Minimal Spanning Tree Algorithm

• Dijkstra's Minimal Spanning Tree Algorithm

• Graph - Map Coloring

•Graph - Vertex Cover

• Knapsack Problem

• Job Scheduling Problem

IT-3 1/11/2024 19
 Activity selection problem:

The activity selection problem is a mathematical optimization problem. That concerning

the selection of non-conflicting activities. Each activity assigned by a start time (si) and
finish time (fi). The activity selection problem is to select the maximum number of
activities that can be performed by a single machine, assuming that a machine can only
work on a single activity at a time.
Greedy Algorithm for Selection Problem
I. Sort the input activities by increasing finishing time.
f1 ≤ f 2 ≤ . . . ≤ f n
II. Call GREEDY-ACTIVITY-SELECTOR (Sif)
n = length [s]
A={i}
j=1
FOR i = 2 to n
do if si ≥ fj
then A= AU{i}
j=i
Return A

IT-3 1/11/2024 20
 EXAMPLE:

QUESTION : Given 10 activities along their start and finish time as

S ={ A1 A2 A3 A4 A5 A6 A7 A8 A9 A10}
Si ={1, 2, 3 , 4, 7, 8, 9, 9, 11, 12}
Fi={3, 5, 4, 7, 10, 9, 11, 13, 12, 14}

ANS : We will arrange the activities into non-decreasing order of finish time.

Ai A1 A3 A2 A4 A6 A5 A7 A9 A8 A10
Si 1 3 2 4 8 7 9 11 9 12
Fi 3 4 5 7 9 10 11 12 13 14
The F1=3 i.e. select A1 search for activity where Si>=Fi. We obtain A3 where Si=3.Hence
select A3. As F4=4 we select A4 whose S4=4.Hence select A4. The F4=7and S6=8.As
S6>=F4 we select A6.The F6=9 and we get A7=9.The F7=11and S9=11.Therefore select
A9.The F9=12 and S10=12.Hence select A10.
The complete selection of activities will be:
{A1, A3 ,A4, A6, A7, A9, A10}
IT-3 1/11/2024 21
 Knapsack problem:
There are n items in a store. For i =1,2, . . . , n, item i has weight wi > 0 and worth vi > 0.
Thief can carry a maximum weight of W pounds in a knapsack. In this version of a
problem the items can be broken into smaller piece, so the thief may decide to carry
only a fraction xi of object i, where 0 ≤ xi ≤ 1. Item i contributes xiwi to the total weight
in the knapsack, and xivi to the value of the load.
ALGORITHM :
Greedy-fractional-knapsack (w, v, W)
FOR i =1 to n
do x[i] =0
weight = 0
while weight < W
do i = best remaining item
IF weight + w[i] ≤ W
then x[i] = 1
weight = weight + w[i]
else
x[i] = (w - weight) / w[i]
weight = W
return x
IT-3 1/11/2024 22
 Analysis

If the items are already sorted into decreasing order of vi / wi, then
the while-loop takes a time in O(n);
Therefore, the total time including the sort is in O(n log n).

If we keep the items in heap with largest vi/wi at the root. Then
•creating the heap takes O(n) time
•while-loop now takes O(log n) time (since heap property must be restored after the
removal of root)

Although this data structure does not alter the worst-case, it may be faster if only a
small number of items are need to fill the knapsack.

IT-3 1/11/2024 23
 PROBLEM
Assume that we have a knapsack with max weight capacity, W = 16.
our objective is to fill the knapsack with items such that the benefit (value or profit) is
maximum.
Consider the following items and their associated weight and value
ITEM i1 i2 I3 i4 i5 i6
WEIGHT 6 10 3 5 1 3
VALUE 6 2 1 8 3 5

Steps:

Calculate value per weight for each item (we can call this value density)
Sort the items as per the value density in descending order
Take as much item as possible not already taken in the knapsack.

Compute density = (value/weight)

IT-3 1/11/2024 24
 ITEM i1 i2 i3 i4 i5 i6
WEIGHT 6 10 3 5 1 3
VALUE 6 2 1 8 3 5
DENSITY 1.000 0.200 0.333 1.600 3.000 1.667

Sort the items as per density in descending order

ITEM i5 i6 i4 i1 i3 i2
WEIGHT 1 3 5 6 3 10
VALUE 3 5 8 6 1 2
DENSITY 3.000 1.667 1.600 1.000 0.333 0.200

Now we will pick items such that our benefit is maximum and total weight of the
selected items is at most W.

Our objective is to fill the knapsack with items to get maximum benefit without
crossing the weight limit W = 16.
IT-3 1/11/2024 25
 How to fill the knapsack table?

is WEIGHT(i) + TOTAL WEIGHT<= W if its YES then we

take the whole item

How to calculate benefit?

benefit = (weight taken) x (total value of the item / total weight of the item)

ITEM i5 i6 i4 i1 i3
WEIGHT 1 3 5 6 1
VALUE 3 5 8 6 0.333
TOTAL 1.000 4.000 9.000 15.000 16.000
WEIGHT
TOTAL 3.000 8.000 16.000 22.000 22.333
BENIFIT

So, total weight in the knapsack = 16 and total value inside it = 22.333336

IT-3 1/11/2024 26
 Spanning Tree
Given an undirected and connected graph G=(V,E)G=(V,E), a spanning tree of the
graph GG is a tree that spans GG (that is, it includes every vertex of GG) and is a
subgraph of GG (every edge in the tree belongs to GG)

Minimum Spanning Tree

The cost of the spanning tree is the sum of the weights of all the edges in
the tree. There can be many spanning trees. Minimum spanning tree is the
spanning tree where the cost is minimum among all the spanning trees.
There also can be many minimum spanning trees.

IT-3 1/11/2024 27
 Kruskal’s Algorithm :
Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing
spanning tree. Kruskal's algorithm follows greedy approach as in each iteration it finds an
edge which has least weight and add it to the growing spanning tree.
Algorithm Steps:

• Sort the graph edges with respect to their weights.

• Start adding edges to the MST from the edge with the smallest weight until the edge
of the largest weight.
• Only add edges which doesn't form a cycle , edges which connect only disconnected
components.
So now the question is how to check if 22 vertices are connected or not ?

This could be done using DFS which starts from the first vertex, then check if the second
vertex is visited or not. But DFS will make time complexity large as it has an order
of O(V+E)O(V+E) where VV is the number of vertices, EE is the number of edges. So the
best solution is "Disjoint Sets":
Disjoint sets are sets whose intersection is the empty set so it means that they don't
have any element in common.
IT-3 1/11/2024 28
 Total cost=11

IT-3 1/11/2024 29
 Prim’s Algorithm
Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s
Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal's,
we add vertex to the growing spanning tree in Prim's.

Algorithm Steps:

• Maintain two disjoint sets of vertices. One containing vertices that are in the
growing spanning tree and other that are not in the growing spanning tree.
• Select the cheapest vertex that is connected to the growing spanning tree and is not
in the growing spanning tree and add it into the growing spanning tree. This can be
done using Priority Queues. Insert the vertices, that are connected to growing
spanning tree, into the Priority Queue.
• Check for cycles. To do that, mark the nodes which have been already selected and
insert only those nodes in the Priority Queue that are not marked.

IT-3 1/11/2024 30
 Total cost = 7
IT-3 1/11/2024 31
 Single Source Shortest path

Dijkstra's algorithm - is a solution to the single-source shortest path problem in graph

theory.

Works on both directed and undirected graphs. However, all edges must have nonnegative
weights.

Approach: Greedy

Input: Weighted graph G={E,V} and source vertex v∈V, such that all edge weights are
nonnegative

Output: Lengths of shortest paths (or the shortest paths themselves) from a given source
vertex v∈V to all other vertices

IT-3 1/11/2024 32
 Example:

IT-3 1/11/2024 33
IT-3 1/11/2024 34
IT-3 1/11/2024 35
IT-3 1/11/2024 36
IT-3 1/11/2024 37
IT-3 1/11/2024 38
IT-3 1/11/2024 39