DivideandConquer

DivideandConquerforfinding Counterfeitcoin(exactlyonecoin):

AlgorithmCounterfeitCoin(Bunch,numberofcoins)
{
if(numberofcoins=2){ weigh
the two coins;
ifoneofthemweighslessthat iscounterfeit coin; else,
no counterfeit coin in the Bunch
}
else{
DivideBunchintotwohalvesBunch1andBunch2;
ifBunch1weighslessthanBunch2,callCounterfeitCoin(Bunch1,numberofcoins/2); else, call
CounterfeitCoin(Bunch2, numberofcoins / 2);
}
}

FindingLargest withDivideand Conquer:

AlgorithmDandCLargest(a,k,j)
{
if(k=j)Returna[n];
else
{
mid:=(k+j) /2;
x1= DandCLargest (a,k,mid);
x2=DandCLargest(a,mid+1,j); if
(x1 > x2) Return x1;
elseReturnx2;
}
}

First CallforRecursion:
DandCLargest(a,1,n);

Divide and Conquer algorithm design works on the principle of dividing the given problem into
smaller sub problems which are similar to the original problem. The sub problems are ideallyof
the same size.
The Divide and Conquer strategy can be viewed as one which has three steps. The first step is
called Divide which is nothing but dividing the givenproblems into smaller subproblems which
are identical to the original problem and also these sub problems are of the samesize. The
[Link]
is called Combine where inwe combine the solutions ofthe subproblems to get the solution for the
original problem.

ControlAbstractionforDivideandConquerAlgorithms– GeneralMethod

AlgorithmDandC(P){
ifSmall(P)thenreturn S(P);
else {
DividePintosmallerinstancesP1,P2,…….,Pk,k≥1; Apply
DandC to each of these sub-problems;
ReturnCombine(DandC(P1),DandC(P2)...,DandC(Pk)),
}
}

BinarySearch

• BinarySearchtakesasorted arrayastheinput
• It works by comparing the target (search key) with the middle element of the array and
terminatesifit equals,else it dividesthearrayintotwosubarraysandcontinuesthesearchinleft (right)
sub array if the target is less (greater) than the middle element of the array.
Reducing the problem size by half is part of the Divide step in Binary Search and searching in
this reduced problem space is part of the Conquer step in Binary Search. There is no Combine
step in Binary Search.
WithDivideandConquer(recursion)

AlgorithmBinSrch(a,i,l,x){
// Givenanarraya[I:l]ofelementsinnondecreasing order,1≤i≤l,
//determinewhetherxis//presentandifso,returnjsuchthatx=a[j];elsereturn 0.
if(l=i)then{//ifSmall(P)
if(x=a(i))thenreturni;elsereturn0;
}
else {
//ReducePintoasmallersubproblem.
mid :=[(i + l)/2 ];
if(x=a[mid])thenreturnmid; else
if (x<a[mid] then
returnBinSrch(a,i,mid -1,x);
elsereturnBinSrch(a,mid+1,l,x);
}
}
IterativeBinarySearch(non-recursive)

AlgorithmBinSearch(a,n,x)
{ low :=1;high :=n;
while (low ≤ high) do
{ mid:=(low+high)/2;
 if( x<a[mid]) thenhigh:=mid–1;
elseif(x>a[mid])thenlow:=mid+1;
elsereturn mid;
}
return0;
}

TheoremAlgorithmBinSearch(a,n,x)workscorrectly. Proof:
Weassumethatallstatementsworkasexpectedandthatcomparisonssuchasx>a[mid]are appropriately
carried out.
Initiallylow=1,high= n,n≥0,anda[1]≤a[2]≤..≤a[n]. If n = 0,
the while loop is not entered and 0 is returned.
Otherwiseweobservethat eachtimethroughthe loopthepossibleelementsto bechecked for equality with x
are a [low], a[low + 1]…, ..., a[mid],..., a[high).
Ifx= a[mid],thenthe algorithmterminatessuccessfully.
Otherwise the range is narrowed by either increasing low to mid + 1 or decreasing high to mid— 1.
Clearly this narrowing of the range does not affect the outcome of the search.
Iflowbecomesgreaterthanhigh,thenxis notpresentandhencetheloopisexited.

PerformanceofBinarySearch

k_1 k
Theorem:-Ifnisin therange[2 , 2 ), thenBinSearch makesat most kelement comparisons for a
successful search and either k —1 or k comparisons for an unsuccessful search. (In other words
the time fora successful search is 0 (log n) and foran unsuccessful search is(log n).

Proof: Consider the binary decision tree describing the action of BinSearch on n elements. All
successfulsearches end at a circular node whereas allunsuccessful searches end at a square node.
k-1 k
If2 ≤n<2 ,thenallcircular nodesareatlevels1, 2,..., kwhereasallsquarenodesareat levelsk and k + 1
(note that the root is at level 1). The number of comparisons needed to terminate at acircular node on
level i is i whereas the number of element comparisons needed to terminate at a square node at level i
is only i — 1. The theorem follows.

MergeSort

MergesortisyetanothersortingalgorithmwhichworksontheDivideandConquerdesign principle.
• Mergesortworksbydividingthe givenarrayintotwosubarraysofequal size
• Thesubarraysaresortedindependentlyusingrecursion
• Thesortedsubarraysarethenmergedtoget thesolutionfortheoriginalarray.
Thebreaking ofthegiven input arrayinto two subarraysofequalsize ispart ofthe Divide step. The
recursive calls to sort the sub arrays are part of the Conquer step. The merging of the sub arrays
to get the solution for the original array is part of the Combine step.

The basic operation in Merge sort is comparison and swapping. Merge SortAlgorithm calls it self
recursively. Merge Sort divides the array into sub arrays based on the position of the elements
whereas Quick Sort divides the array into sub arrays based on the value of theelements. Merge
Sort requires an auxiliary array to do the merging (Combine step). Themerging oftwo sub
arrays, which are already sorted, into an auxiliaryarraycan be done in O(n) where n is the total
number of elements in boththe sub arrays. This is possible because both the sub arrays are sorted.

AlgorithmMergeSort(low,high){
//Small(P) istrueifthereisonlyoneelement tosort .
//Inthiscasethe list isalreadysorted. if
(low < high) then {
//Ifthere aremorethanone element
//DividePintosubproblems.
mid := [(low + high)/2] ;
// Solve the subproblems.
MergeSort(low, mid);
MergeSort(mid+1,high);
//Combinethesolutions.
Merge(low, mid, high);
}
}

MerginginMergeSort
AlgorithmMerge(low,mid,high){
//a[low:high]isaglobalarraycontainingtwosortedsubsetsin
//a[low:mid] andina[mid+1:high].Thegoalistomerge these
//twosetsintoasinglesetresidingina[low:high]. B[]isan
// auxiliary global array.
h:=low; i:=low ;j : =mid
+1;while((h≤mid)and(j≤high))do {
if(a[h]≤a[j]then{
b[i]:=a[h];h:=h+1;
}
else {
b[i]:=a[j];j:=j+1;
}
i:= i+1;
}
if(h>mid)then
 fork:=jtohighdo
{b[i]: =a[k];i:=i+1;}
elsefork :=hto mid do
{b[i]:=a[k];i:=i+1;}
fork: =lowto highdoa[k] :=b[k];
}

Complexity of Merge Sort is O(n log n) and binary search is O(log n).
Thiscanbeprovedbyrepeatedsubstitutionintherecurrencerelations.

Suppose(forsimplicity)thatn=[Link]=2kk =log2n
MergeSort:
LetT(n)thetimeusedto [Link] merging inlineartime, it takes cn
time to perform these two steps, for some constant c. So,recurrence relation is :T(n) = 2T(n/2) + cn.
In the same way:T(n/2) = 2T(n/4) + cn/2, so T(n)=4T(n/4)+2cn.
Going in this way ...
T(n)=2mT(n/2m) +mcn, and

T(n)=2kT(n/2k)+kcn= nT(1)+cnlog2n= O(n log n).

BinarySearch:
LetT(n)thetimeusedto [Link] needto searchonlyoneofthehalves, the Recurrence
relation is :T(n) = T(n/2) + c
In the same way:T(n/2) = T(n/4) + c, so T(n)=T(n/4)+2c.
Going in this way ...
T(n)=T(n/2m) +mc, and

T(n)=T(n/2k)+ kc=T(1)+kc= kc+1=O(log n).

QuickSort:

Quick sort is one of the most powerful sorting algorithms. It works on the Divide and Conquer
design principle. Quick sort works by finding an element, called the pivot, in the given input
array and partitions the array into three sub arrays such that the left sub array contains all
elementswhicharelessthanorequalto [Link]
right sub array contains all elements which are greater than the [Link], the two sub arrays,
namely the left sub array and the right sub array are sorted recursively.
The partitioning of the given inputarray is partof the Divide step. The recursive calls tosort the
sub arrays are part of the Conquer step. Since the sorted sub arrays are already in the right place
there is no Combine step for the Quick sort.

1. AlgorithmQuickSort(p,q)
2. //Sortstheelementsa[p],…,a[q]whichresideintheglobal
3. //arraya[1;n]intoascendingorder;a[n+1]isconsideredto
4. //bedefinedandmustbe≥alltheelementsina[1:n]
5. {
6. if(p < q)then//iftherearemorethanoneelement
7. {
8. //dividePintotwosub problems.
9. j:=Partition(a,p,q+1);
10. //jisthepositionofthepartitioningelement.
11. //Solvethesubproblems.
12. QuickSort(p,j-1),
13. QuickSort (j +1,q)
14. //thereisnoneedforcombining solutions.
15. }
16. }

Algorithm forSortingby partitioning.

1. AlgorithmPartition(a,m,p)
2. //Within a[m],a[m+1],….a[p-1]theelements are
3. //rearrangedinsuchamannerthatifinitiallyt=a[m],
4. //thenaftercompletion a[q]=tforsomeqbetweenm
5. //andp-1, a[k]≤tfor m≤k<q, anda[k]≥t
6. //for q<k<[Link][p]=∞.
7. {
8. v:=a[m], I:=m;j :=p;
9. repeat
10. {
11. repeat
12. i:=i+1;
13. until(a[i]≥v);

14. repeat
15. j :=j–1;
16. until(a[j]≤v);

17. if(I<i)theninterchange(a,I,j);
 18. }until(I≥j);

19. a[m]:= a[j]; a[j]:=v; returnj;

20. }

1. AlgorithmInterchange(a,i,j)
2. //Exchangea[i]witha[j]
3. {
4. p:=a[i];
5. a[i]: =a[j];a[j]: p;
6. }

AlgorithmPartitionthearray a[m :p-1]abouta[m]

(3) (4) (8) (9) i

50

55 50 70 + 8

55 75 70 + 7

80 75 70 + 6

80 75 70 + 5

80 75 70 +
GreedyAlgorithms

Greedyalgorithms– overview

GreedydesigntechniqueisprimarilyusedinOptimizationproblems.
Optimization problems are problems where in we would like to find the best of all possible
solutions. In other words, we need to find the solution which has the optimal (maximum or
minimum) value satisfying the given constraints.

The Greedy approach helps in constructing a solution for a problem through a sequence of steps
where each step is considered to be a partial solution. This partial solution is extended
progressively to get the complete solution.

Inthe greedyapproacheachstep chosenhas to satisfythe constraints given inthe problem. Each

stepischosensuchthat it isthebest alternativeamongallfeasiblechoicesthat areavailable. The choice
of a step once made cannot be changed in subsequent steps.

Changemakingexample:

Suppose, wewantto makechange foranamount‘A’using fewest [Link] the

available denominations are Rs 1, 2, 5, 10, 20, 50, 100, 500, 1000.
Tomake a changeforA=Rs 28,with theminimum numberof notes, one wouldfirstchoose a note of
denomination Rs 20, 5, 2 and 1.

Denominationtable
forRs28 forRs783 forRs3799
1000X0 0 1000X 1000X
500X0 0 500X 500X
100X0 0 100X 100X
50X0 0 50X 50X
20X1 20 20X 20X
10X0 0 10X 10X
5X1 5 5X 5X
2X1 2 2X 2X
1X1 1 1X 1X
 Total 28 Total Total

Algorithmchangemaking(denom_value[],TargetAmount)
{
//denom={1000,500,100,50,20,10,5,2,1}

selectedamount(SA):=0;
i :=1;
while(SA<TargetAmount){
if(SA+denom_value[i]<=TargetAmount){ //Select &Feasible

denom_select[i]++;// Union
 SA:=SA+denom_value[i];
} i++;
else{

}
}
Printdenom_select
}

GreedyAlgorithm-Generalmethod

In Greedy method the problems have 'n'inputs called as candidate set, from which a subset is
selected to forma solution for the given problem. Any subset that satisfies the given constraints is
called a feasible solution. We need to find a feasible solution that maximizes or minimizes an
objective function and such solution is called an optimal solution.

In the above excurrency notes denomination set { 1000 ….1000 ,500….500, 100….100, 50…
50, 20…20,10…10,5…5,2..2,1…1}is candidate set.

In the above ex constraint is our solution make the exact target amount of cash. Hence, any
feasible solution i.e. sum of selected notes should be equal to target amount.

In the above ex objective function is our solution should consist of the fewest number of
currency notes. Hence, anyoptimalsolutionwhich isoneofthe feasible solutionsthat optimizes the
objective function. There can be more than one optimal solution.

ControlAbstractionforGreedyGeneralMethod

AlgorithmGreedy(a,n)
// a[1..n]containstheninputs
{
solution:=ø;
fori:=1tondo
{
x:=Select(a);
ifFeasible(solution, x)thensolution:=Union(solution, x);
}
returnsolution;
}
Greedymethodconsistsof3functions (steps).

1) Select:itselectsaninputfromarraya[] (candidateset)andputsinthevariablex.

2) Feasible:it is a Boolean function which checks whether the selected input meets the
constraints or not.

3) Union:iftheselected input i.e. 'x'makesthesolutionfeasible, thenxis included inthe

solution and objective function get updated.
 CharacteristicsofGreedy:

1) Thesealgorithmsaresimpleandstraightforwardandeasytoimplement.

2) Theytake decisions onthe basis ofinformationathand without worrying aboutthe effect

these decisions may have in the future.

3) Theywork instagesand neverreconsideranydecision.

GreedyAlgorithmsApplications

Knapsackproblem:

A thief robbing a store finds n items, the items each worth virupees and weights wigrams, where
viand wiare positive numbers. He wants to take as valuable load as possible but he can
carry at most w grams in his knapsack(bag). Which item should he take?

Theyare twotypesofknapsackproblem.

1) 0-1 knapsack problem: Here the items may not be broken into smaller pieces, so thief may
decide either to take an item or to leave to it(binary choice). It cannot be efficiently solved by
greedy algorithm

2) Fractional(General) Knapsack problem: Here thiefcantake the fractionof items, meaning

thatthe items can be broken into smaller pieces so thatthief may be able to carrya fractionx iof
item i. This can be solved easily by greedy.

Ifa fractionxi, 0 ≤xi ≤ 1, ofobjects iis placed intothe knapsack, thena profit ofpi xiis earned. The
objective is to obtain a filling of the knapsack that maximizes the total profit earned. Since the
knapsack capacity is m, we require the totalweight ofall chosen objects to be at most m.

Formallythe problemcanbe statedas

Maximize∑Pixi...................................... (1)

Subjectto∑ Wi xi ≤m.............................................(2)

And 0 ≤xi≤1,1≤i≤n................................................(3)

Theprofitandweights..............are positive numbers. A feasible solution is any set

 (x1,x2,........................xn)satisfying(2)and(3). Anoptimalsolutionisfeasiblesolutionforwhich
(1)is maximized.

Eg; consider the following instance of the knapsack problem. n=3,

m=20,(P1,P2,P3)=(25,24,15)&(w1,w2,w3)=(18,15,10)
Notethatknapsackproblemcallsfor selectasubsetoftheobjectshencefitsthesubsetparadigm.
1) We can try to fill the knapsack by including the object with largest profit(greedy approach to
the profit) .Ifan object under consideration does not fit, then a fraction ofit is included to fit the
[Link] 1hasthelargest profit value.P1=[Link] [Link] x1=1
and a profit of 25 is earned. Only 2 units of knapsack capacity are left. Objects 2 has the next
largest profit P2=24. But W2 =15 & it doesnot fit into the knapsack. Using x2 =2/15 fillsthe
knapsack exactly with the part of the object 2.

Themethodusedtoobtainthissolutionistermedagreedymethodateachstep,wechoseto introduce that object

which would increase the objective function value the most.
(x1,x2 ,x3) ∑wixi ∑pixi
(1,2/15,0) 20 28.2
Thisisnotanoptimalsolution.
2) Weapplygreedyapproachbychoosingvalueper unitweightisashighas possible
Item(n) Value(p1,p2,p3) Weight(w1,w2,w3) Val/weight
1 25 18 1.388
2 24 15 1.6
3 15 10 1.5

Here p2/w2> p3/w3> p1/w1. Now the items are arranged into non increasing order of pi/wi.
Second item is the most valuable item. We chose item 2 first. Item 3 is second most valuable
item. But we cannot choose the entire item3 as the weight of item 3 exceeds the capacity of
knapsack. We can take ½ of the third item. Therefore the solution is x1= 0, x2= 1, x3= ½ and
maximum profit is ∑ pixi= 0*25 + 1*24 + ½ * 15 = 31.5

(x1,x2,x3) ∑wixi ∑pixi

(1,2/15,0) 20 28.2
(0,2/3,1) 20 31
(0, 1, 1/2) 20 31.5

Iftheitemsarealreadyarrangedinnonincreasingorderofpi/wi,thenthefunction greedy knapsack

obtains solution corresponding to this strategy.

AlgorithmGreedyKnapsack(a,n)
//Objectsare sorted inthenon-increasing orderofp[i]/w[i]
{
for i := 1 to n do x[i]:=0.0;
U := m;
fori:=1tondo
{
if(w[i]> U) thenbreak;
x[i] :=1;U:=U-w[i];
}
 if(i<= n)thenx[i]:= U /w[i];
}

AnalysisofGreedyKnapsack

 Iftheitemsarealreadysortedintodecreasingorderofvi/wi,thentimecomplexityis
O(n)
 ThereforeTimecomplexityincludingsortisO(nlogn)
Minimum Spanning Tree
Atreeisdefinedtobeanundirected,acyclicandconnectedgraph(ormoresimply,a
graphinwhichthereisonlyonepathconnecting eachpairofvertices).

Assume there is an undirected, connected graph G.A spanning tree is a sub-graph of G, is

a tree, and contains allthe vertices of G.A minimumspanning tree is a spanning tree, but
has weights or lengths associated with the edges, and the total weight of the tree (the sum
of the weights of its edges) is at a minimum

Applicationof MST

1) practical application of a MST would be in the design of a network. For instance, a group
ofindividuals, who are separated by varying distances, wish to be connected together in a
telephone [Link] can be used to determine the least costly pathswith no cyclesinthis
network, thereby connecting everyone at a minimum cost.

2) Another usefulapplicationofMST would be finding airline routes MST canbe applied to

optimize airline routes by finding the least costly paths with no cycles
 28
1 1
2 10 2
10 14 16
16
14
6 3 6 7 3

24 7
25 18 25 5 12
12
22 4
5
22 4

(a) (b)

Prim’sAlgorithm(DJPalgorithm,theJarníkalgorithm,orthe Prim-Jarníkalgorithm).

Prim's algorithm finds a minimumspanning treeforaconnected weighted graph. This means it

finds a subset of the edges that forms a tree that includes every vertex, where the total weight
of all the edges in the tree is minimized.
Steps

 Buildsthe treeedge byedge

 Next edge to be selected is one that result in a minimum increase in the sumof costs
of the edges so far included
 Always verifythatresultantisatree

Ex:

Considertheconnectedgraphgivenbelow
 MinimumspanningtreeusingPrim’salgorithmcanbeformedasfollows.

AlgorithmPrim(E,cost,n,t)

//Eistheset [Link][1:n,1:n]isthecost
//adjacencymatrixofannvertexgraphsuchthatcost[i,j]is
//eitherapositiverealnumberor∞ifnoedges(i,j)exists,
//Aminimumspanningtreeiscomputedandstoredasset of
//edgesinthearrayt[1:n -1,1:2],(t[i,1],t[i,2])isanedge in
//theminimum–[Link].
{
Let (k,l)beanedgeofminimumcost inE;
mincost :=cost[k,l];
t[1,1]:=k;t[1,2] :=l;
fori:=1tondo//Initializenear.
 if(cost[i,l]<cost[i,k ])then
near[i] :=l;
else
near[i]:=k;
near[k]:=near[l]:=0; for
i := 2 ton-1 do
{// Findn-2 additionaledgesfort.
Let jbeanindexsuchthat near[j]≠0and cost
[j,near[j]] is minimum;
t[i,1]:=j;t[i,2]:=near[j];
 mincost:=mincost+cost[j,near[j]]; near[j]:=0;
fork:=1to ndo// Updatenear[]
if((near[k]≠0)and(cost[k,near[k]]>cost[k,j]))then
near[k]:=j;
}
returnmincost;
}

Timecomplexityofthe above algorithmisO(n2).

Kruskal’sAlgorithm

Kruskal's algorithm is another algorithmthat finds a minimum spanning tree for a connected
weighted graph. If the graph is not connected, then it finds a minimum spanning forest (a
minimum spanning tree for each connected component).

Kruskal's Algorithm builds the MST in forest. Initially, each vertex is in its own tree inforest.
Then, algorithm considers eachedge in turn,order byincreasing weight. Ifanedge(u, v)
connects two different trees, then (u, v) is added to the set of edges of the MST, and two trees
connected by an edge (u, v) are merged into a single tree on the other hand,if an edge (u, v)
connects two vertices in the same tree, then edge (u, v) is discarded. The resultant may not be
a tree in all stages. But can be completed into a tree at the end.

t =EMPTY;
while((t hasfewer thann-1 edges) &&(E!=EMPTY))
{
chooseanedge(v,w)fromEoflowest cost;
delete (v, w) from E;
if(v,w)doesnotcreateacycleint add (v,
w) to t;
else
discard(v, w);
}

Tocheckwhetherthereexistacycle,placeallverticesinthesameconnectedcomponentoft
[Link] intthentheyareinthesameset.
Example:

Considertheconnectedgraphgivenbelow:

MinimumspanningtreeusingKruskal’salgorithmcanbeformedasgivenbelow.

Kruskal’sAlgorithm
Float kruskal(intE[][], floatcost[][],intn, intt[][2])
{
intparent[w];
considerheapoutofedgecost; for
(i=1; i<=n; i++)
parent[i]=-1; //Eachvertexindifferentset
i=0;
mincost= 0;
while((i<n-1) &&(heapnot empty))
 {
Deletea minimumcost edge(u,v)fromtheheapandre heapify; j =
Find(u); k = Find(v); // Find the set
if(j !=k)
{
i++;t[i]
[1]=u;
t[i][2]=v;
mincost+=cost[u][v];
Union(j, k);
}
if(i!=n-1)
printf(“Nospanningtree\n”);
else
return(mincost);
}
}

Timecomplexityoftheabovealgorithmis O(nlogn)

GreedyAlgorithmforSingle-sourceshortest pathsto allothervertices

45

1 2 3
15
35 30
10 20 20

4 5 6
153

Path Length
1)1.4 10
2)1.4.5 25
3)[Link] 45
4)1.3 45

(b)Shortest pathfrom1
 Greedyalgorithmtogenerateshortestpaths

AlgorithmShortest paths(v,cost ,dist,n)

//dist[j].1≤j≤n,issettothelengthofthe shortest
//pathfromvertexvtovertexjina digraphG withn
//vertices,dist[v][Link]
//cost adjacency matrixcost[1:n,1;n]
{
fori:=1tondo
{ //Initialize S.
S[i]:=false;dist[i]:=cost[v,i];
}
S[v]:=true;dist[v]:=0.0;//putvinS. for
num := 2 to n do
{
//Determinen-1 pathsfromv.
Chooseufromamongthoseverticesnot in S
such that dist[u] is minimum;
S[n]:=true;//putuinS.
for(eachwadjacent tou withS[w] =false)do
//Update distances.
if(dist[w]>dist[u]+cost[u,w]))then
dist[w] :=dist[u] + cost[u, w];
}
}

Boston

SanFrancisco Chicago 1500 5

250
4
1000 NewYork
2 800
3 6
 300 1400 900
Denver
100
1 0 1700

LosAngeles 8
1000 7

Neworleans Miami

(a)Digraph
 1 2 3 4 5 6 7 8

1. 0
2. 300 0
3. 100 8000
4. 1200 0
5. 1500 0 250
6. 1000 0 900 1400
7. 0 1000
8. 1700 0
(a)Length–adjacencymatrix