ADA ( Analysis and Designs of Algorithms) Practical Lab

1)Binary Search Recursively
#include<iostream.h>
#include<conio.h>
void BS(int a[10],int sk,int lb,int ub)
{
 int mid;
 if(lb>ub)
 cout<<"key not found\n";
 else
   {
    mid=(lb+ub)/2;
    if(sk==a[mid])
    cout<<"element found";
    else
       {
     if(sk>a[mid])
     BS(a,sk,mid+1,ub);
     else
     BS(a,sk,lb,mid-1);
     }
     }
     }
void main()
{
clrscr();
int b,c,d;
int e[10];
cout<<"enter the no.in the array in sorted manner";

for(int i=0;i<10;i++)
  {
  cin>>e[i];
  cout<<"\n";
  }
  cout<<"enter the search key";
  cin>>d;
  BS(e,d,0,10);
  getch();
  }

 2) Quick Sort Recursively

#include<stdio.h>
#include<conio.h>
void quicksort(int arr[20], int low, int high);
void main();
{
  int arr[20], n, i;
  printf("Enter the size of the array\n");
  scanf("%d", &n);

  printf("Enter the elements to be sorted\n");
  for(i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  quicksort(arr, 0, n-1);

  printf("Sorted array\n");
  for(i = 0; i < n; i++)
    printf("%d ", arr[i]);

  getch();
}
void quicksort(int arr[20], int low, int high)
{
  int pivot, i, j, temp;
  if(low < high)
  {
    pivot = low; // select a pivot element
    i = low;
    j = high;
    while(i < j)
     {
      // increment i till you get a number greater than the pivot element
      while(arr[i] <= arr[pivot] && i <= high)
    i++;
      // decrement j till you get a number less than the pivot element
      while(arr[j] > arr[pivot] && j >= low)
    j--;
      // if i < j swap the elements in locations i and j
      if(i < j) {
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
      }
    }

    // when i >= j it means the j-th position is the correct position
    // of the pivot element, hence swap the pivot element with the
    // element in the j-th position
    temp = arr[j];
    arr[j] = arr[pivot];
    arr[pivot] = temp;
    // Repeat quicksort for the two sub-arrays, one to the left of j
    // and one to the right of j
    quicksort(arr, low, j-1);
    quicksort(arr, j+1, high);
  }
}





3 )Stack Push and Pop operation
#include<stdio.h>
#include<conio.h>
#define max 5
int top=-1,a[max];
void push(int n1)
{  int i,q;

if(top==max-1)
{
printf("stack is full");
 }
else
{
top=top+1;
  a[top]=n1;
}

for(i=top;i>=0;i--)
{ printf("elements r %d\n",a[i]);
}
}
void pop()
{int n;
if(top==-1)
{printf("stack is empty");
}
else
{n=a[top];
top=top-1;
printf("deleted element is %d",n);
}
}
void main()
{ int d,b;
//int top=-1;
char c;
clrscr();
do
{
printf("1=push\n");
printf("2=pop\n");
printf("enter ur choice");
scanf("%d",&d);
switch(d)
{ case 1:
  printf("enter the element");
  scanf("%d",&b);
  push(b);
  break;
  case 2:
  pop();
  break;
  default:
  printf("invalid choice");
  }
  printf("do u want to continue");
  scanf("%s",&c);
  }
  while(c=='y');
  getch();
  }
 
4) Floyd Warshall Program

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void shortest_path(int cost[3][3],int A[3][3],int n)
{
int i,j,k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
A[i][j]=cost[i][j];
}
}
printf("Floyd Warshall:");
printf("\nGiven Graph:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",cost[i][j]);
}
printf("\n");
}
for(k=0;k<n;k++)
{
for(j=0;j<n;j++)
{
for(i=0;i<n;i++)
{
A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
}
}
}
printf("Shortest Path Matrix:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",cost[i][j]);
}
printf("\n");
}
}
void main()
{
int cost[3][3]={{0,4,11},{6,0,2},{3,999,0}};
int A[3][3],n=3;
clrscr();
shortest_path(cost,A,n);
getch();
}