Algorithm BinSearch (a,n,x) { Algorithm BubbleSort (a,n)

Algorithm BinSrch(a,i,l,x) { low :=1;high :=n; {

// Given an array a[I:l] of elements in non decreasing while (low ≤ high) do { for i := 1 to n do
order, 1≤ i ≤ l, mid :=(low +high)/2; {
// determine whether x is //present and if so, return j if ( x<a[mid]) then high :=mid – 1; for j :=1 to n-i do
such that x =a[j]; else return 0. else if (x>a[mid]) then low :=mid + 1; {
if (l=i) then else return mid; if ( a[j] > a[j+1] )
{ // if Small(P) } {
if (x=a(i)) then return i; return 0; // swap a[j] and a[j+1]
else return 0; } temp := a[j]; a[j] := a[j+1];a[j + 1] := temp;
} }
else { }
// Reduce P into a smaller subproblem. }
mid :=[(i + l)/2 ]; }
if (x=a[mid]) then return mid;
else if (x<a[mid] then
return BinSrch (a,i, mid -1,x);
else return BinSrch (a, mid +1,l,x);
}
}

Algorithm DandCLargest (a,k,j) Algorithm Greedy Knapsack(a,n) Algorithm IBacktrack(n)

{ // Objects are sorted in the non-increasing order of p[i]/w[i] // This schema describes the backtracking process.
if (k = j) Return a[n]; { // All solutions are generated in x{1: n} and printed
else for i := 1 to n do x[i] := 0.0; // as soon as they are determined.
{ U := m; {
mid := (k + j) /2; for i := 1 to n do k := 1;
x1= DandCLargest (a,k,mid); { while (k ≠ 0) do
x2= DandCLargest (a,mid+1,j); if (w[i] > U ) then break; {
if (x1 > x2) Return x1; x[i] := 1; U:=U - w[i]; if (there remains an untried x[k] €T (x[1],x[2],…..,
else Return x2; } x[k-1] and Bk(x[1],….,x[k])is true)then
} } {
} if (i <= n) then x[i] := U / w[i]; if(x[1],….,x[k] is a path to an answer node)
then write(x[1:k]);
First Call for Recursion: k :=k+1; // Consider the next set.
DandCLargest (a,1,n); }
else k:= k-1;// Backtrack to the previous set.
}
}
}
Algorithm insertionSort(a,n) Algorithm Merge_Sort(low, high) { Algorithm N Queen(k,n)
{ // Small(P) is true if there is only one element to sort . // Using backtracking, this procedure prints all
for i := 2 to n do // In this case the list is already sorted. //possible placement of n queens on an n x n
{ if (low < high) then { //chessboard so that they are nonattacking.
value := a[i]; j := i - 1; //If there are more than one element {
done := false; //Divide P into subproblems. for i:=1 to n do
repeat mid := [(low + high)/2] ; {
if a[j] > value // Solve the subproblems. }
{ MergeSort(low, mid); }
a[j + 1] := a[j]; j := j - 1; MergeSort (mid + 1, high); if place(k, i) then
if (j < 1) done := true; // Combine the solutions. {
} Merge(low, mid, high); }
else } x[k] := i;
done := true; } if (k = n] then write (x[1 ; n]);
until done; else NQueens (k+1,n);
a[j + 1] := value; }
} }
} }

Algorithm place(k,i) Greedy algorithm to generate shortest paths Kruskal’s Algorithm

// Returns true if a queen can be placed in kth row and Algorithm Shortest paths (v, cost ,dist, n) Float kruskal (int E[ ][ ], float cost[ ][ ], int n, int t[ ][2])
//ith column. Otherwise it returns false. x[]is a // dist[j]. 1≤ j≤ n, is set to the length of the shortest {
//global array whose first (k-1) values have been set. // path from vertex v to vertex j in a digraph G with n int parent[w];
//Abs(r) returns the absolute value of r. // vertices, dist[v]is set to zero. G is represented by its consider heap out of edge cost;
{ // cost adjacency matrix cost[1:n ,1;n] for (i=1; i<=n; i++)
for j :=1 to k-1 do { parent[i] = -1;
if((x[j] =i) // Two in the same column for i:=1 to n do //Each vertex in different set
or (Abs(x[j]-i) = Abs(j-k))) { // Initialize S. i=0;
// or in the same diagonal S[i] :=false; dist[i]:=cost[v,i]; mincost = 0;
then return false; } while((i<n-1) && (heap not empty))
return true; S[v] :=true; dist[v] :=0.0; //put v in S. {
} for num := 2 to n do Delete a minimum cost edge (u,v) from the heap and re heapify;
{ j = Find(u); k = Find(v); // Find the set
// Determine n - 1 paths from v. if (j != k)
Choose u from among those vertices not {
in S such that dist[u] is minimum; i++;
S[n] :=true;//put u in S. t[i][1] = u;
for (each w adjacent to u with S[w] = false ) do t[i][2] = v;
// Update distances. mincost += cost[u][v];
if(dist[w] > dist[u] + cost[u,w])) then Union(j, k);
dist[w] :=dist[u] + cost[u, w]; }
} if (i != n-1)
} printf(“No spanning tree \n”);
else
return(mincost);
}
}

Time complexity of the above algorithm is O(n log n)

Algorithm Linear search (a, req_ele) place there is no Combine step for the Quick sort. Algorithm for Sorting by partitioning.
{
Flag=0 1. Algorithm QuickSort (p,q)
for i := 1 to n do 2. // Sorts the elements a[p],…, a[q] which reside in the global 1. Algorithm Partition (a,m,p)
{ 3. // array a[1 ;n] into ascending order ; a[n+1] is considered to 2. //Within a[m],a[m+1],….a[p-1] the elements are
If (a[i] = req_ele) then 4. // be defined and must be ≥ all the elements in a[1 :n] 3. //rearranged in such a manner that if initially t = a[m],
{ 5. { 4. // then after completion a[q] = t for some q between m
Flag=1; 6. if (p < q) then // if there are more than one element 5. // and p-1, a[k]≤ t for m≤ k<q, and a [k] ≥ t
Pos = i; 7. { 6. // for q< k<p. q is returned. Set a[p] = ∞.
break; 8. // divide P into two sub problems. 7. {
} 9. j : = Partition (a,p,q +1); 8. v :=a[m], I :=m; j : = p;
} 10. // j is the position of the partitioning element. 9. repeat
If (flag) then 11. // Solve the subproblems. 10. {
Write “element found at ‘pos’ position” 12. QuickSort (p,j -1), 11. repeat
Else 13. QuickSort ( j +1,q) 12. i :=i+1;
Write “element not found” 14. // there is no need for combining solutions. 13. until (a[i]≥v);
End if 15. } 14. repeat
} 16. } 15. j : = j – 1;
16. until (a[j] ≤ v);
17. if (I < i) then interchange (a,I,j);

18. } until (I ≥ j);

19. a[m] : = a[j]; a[j] : = v; return j ;
20. }

1. Algorithm Interchange ( a , i, j)
2. //Exchange a[i] with a [j]
3. {
4. p : = a[i];
5. a [i] : = a[j]; a[j] : p;
6. }

Algorithm Selection Sort (a, n)

// Sort the array a[1 : n] into non decreasing order.
{
for i := 1 to n do
{
min:=i;
for k : i + 1 to n do
If (a[k]< a[min]) then min:=k;
t :=a[i]; a[i] := a[min];a[min]:= t;
}
}