wap in c++ for linear search

#include<iostream.h>
#include<conio.h>
#include<process.h>
void main()
{
clrscr();
int a[10],n;
cout<<"\nEnter the no. of element\t";
cin>>n;
cout<<"\nEnter the element in array\n";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"Enter the element to be search\t";
int num;
cin>>num;
for(i=0;i<n;i++)
{
if(num==a[i])
{
cout<<"Searched element is "<<a[i]<<" found at a["<<i+1<<"]";
getch();
exit(0);
}
}
cout<<"\nThe element is not available in tne array";
getch();
}

Difference between Divide & conquer and Dynamic programming

Divide & Conquer

1. The divide-and-conquer paradigm involves three steps at each level of the recursion:
• Divide the problem into a number of sub problems.
• Conquer the sub problems by solving them recursively. If the sub problem sizes are small enough, however, just solve the sub problems in a straightforward manner.
• Combine the solutions to the sub problems into the solution for the original problem.

2. They call themselves recursively one or more times to deal with closely related sub problems.

3. D&C does more work on the sub-problems and hence has more time consumption.

4. In D&C the sub problems are independent of each other.

5. Example: Merge Sort, Binary Search


Dynamic Programming

1. The development of a dynamic-programming algorithm can be broken into a sequence of four steps.a. Characterize the structure of an optimal solution.b. Recursively define the value of an optimal solution. c. Compute the value of an optimal solution in a bottom-up fashion.d. Construct an optimal solution from computed information

2. Dynamic Programming is not recursive.

3. DP solves the sub problems only once and then stores it in the table.

4. In DP the sub-problems are not independent.

5. Example : Matrix chain multiplication

wap in c++ to merge two sorted arrays.

#include<iostream.h>
#include<conio.h>


void main()
{
clrscr();
int a[10],b[10],c[20];
int i,j,k,m,n;
cout<<"\nNo. of elementin A\t";
cin>>n;
cout<<"\nEnter the element in array\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"\nNo. of elementin B\t";
cin>>m;
cout<<"\nEnter the element in array\n";
for(j=0;j<m;j++)
{
cin>>b[j];
}
i=0;j=0;k=0;
while(i<n&&j<m)
{
if(a[i]<b[j])
{
c[k]=a[i];
i++;
}
else
{
c[k]=b[j];
j++;
}
k++;
}


if(i>=n)
{
for(int p=j;p<m;p++)
{
c[k]=b[p];
k++;
}
}
else
{
for(int p=i;p<n;p++)
{
c[k]=a[p];
k++;
}
}
cout<<"\nMerged array\n";
for(i=0;i<k;i++)
{
cout<<c[i]<<endl;
}
getch();
}

wap in c++ to implement link-list.

// Following operation has been done:
1. Create
2. Insert at Beginning
3. Traverse
4. Insert at end
5. Search
6. Delete from Beginning




 #include<iostream.h>

 #include<conio.h>

 #include<alloc.h>

 #include<process.h>

 struct node

 {

 int info;

 struct node *link;

 };

 void main()

 {

 clrscr();

 void create(struct node **);

 void traverse(struct node *);

 void insbeg(struct node **,int);

 void search(struct node *,int);

 void delbeg(struct node **);

 void insend(struct node **,int);

 int item,item1,item2,choice;

 struct node *start,*ptr;

 do

{

cout<<"\n1. Create:"<<"\n2. Traverse:"

<<"\n3. Insbeg:"<<"\n4. Insend:"

<<"\n5. Search"<<"\n6. Delbeg:"

<<"\n7. Exit:\n";

cout<<"Enter ur choice:\t";

cin>>choice;

switch(choice)

{

case 1:create(&start);

break;

case 2:traverse(start);

break;

case 3:cout<<"\nenter the item to be insert:\t";

cin>>item;

insbeg(&start,item);

break;

case 5:cout<<"\nenter item to be search:\t";

cin>>item1;

search(start,item1);

break;

case 4:cout<<"\nenter item to be insert:\t";

cin>>item2;

 insend(&start,item2);

break;

case 6:delbeg(&start);

break;

}

}

 while(choice!=7);

 getch();

 }

 void create(struct node **start)

 {

 *start=NULL;

 cout<<"\nLinklist created sucessfully!\n";

 }

void traverse(struct node *start)

{

struct node *ptr;

ptr=start;

while(ptr!=NULL)

{

cout<<ptr->info<<endl;

ptr=ptr->link;

}

}

 void insbeg(struct node **start,int item)

 {

 struct node *ptr;

 ptr=(struct node *)malloc(sizeof(struct node *));

 ptr->info=item;

 if(*start==NULL)

 {

 ptr->link=NULL;

 *start=ptr;

 }

 else

 {

 ptr->link=*start;

 *start=ptr;

 }

 }

void search(struct node *start,int item1)

{

struct node *ptr;

ptr=start;

if(start==NULL)

{

cout<<"\nEmpty List\n";

getch();

exit(0);

}

else

{

while(ptr!=NULL)

{

if(ptr->info==item1)

{

cout<<"\nFound at "<<ptr;

getch();

exit(0);

}

else

{

ptr=ptr->link;

}

}

cout<<"\nElement not present\n";

}

}

 void insend(struct node **start,int item2)

 {

 struct node *ptr1,*ptr2,*save;

 ptr1=(struct node *)malloc(sizeof(struct node *));

 ptr1->info=item2;

 ptr1->link=NULL;

 ptr2=*start;

 while(ptr2!=NULL)

 {

 save=ptr2;

 ptr2=ptr2->link;

 }

 save->link=ptr1;

 }

void delbeg(struct node **start)

{

struct node *ptr;

ptr=*start;

if(*start==NULL)

{

cout<<"\nUNDERFLOW CASE\n";

getch();

exit(0);

}

else

{

*start=(*start)->link;

cout<<"\nInfo deleted\t"<<ptr->info;

cout<<endl;

}

}

wap in c++ to insert an element in an array.

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int a[10];
int i,j,n,loc,item;
cout<<"\nEnter the no. of element\t";
cin>>n;
cout<<"\nEnter the element in array\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"\nEnter the location on which to insert\t";
cin>>loc;
cout<<"\nenter the element to insert\t";
cin>>item;


for(j=n-1;j>=loc;j--)
{
a[j+1]=a[j];
}
a[loc]=item;
n=n+1;
cout<<"\nModified array is\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;
}
getch();
}

wap in c++ to delete an element from an array.

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int a[10];
int i,j,n,loc,item;
cout<<"\nEnter the no. of element\t";
cin>>n;
cout<<"\nEnter the element in array\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"\nEnter the location from where to delete\t";
cin>>loc;
item=a[loc];


for(j=loc;j<n-1;j++)
{
a[j]=a[j+1];
}
n=n-1;
cout<<"\nDeleted element is\t"<<item<<endl;
cout<<"\nModified array is\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;
}
getch();
}

wap in c++ to do bubble sort.

#include<iostream.h>
#include<conio.h>


void main()
{
clrscr();
int a[10],n,i,j;
cout<<"\nNo of element in array\t";
cin>>n;
cout<<"enter the element\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
int t;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
cout<<"\nSorted array is\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;
}
getch();
}

wap in c++ for binary search.

#include<iostream.h>
#include<conio.h>


void main()
{
clrscr();
int a[10],n,beg,end,mid,item;
cout<<"\nNo of element in array\t";
cin>>n;
cout<<"enter the element\n";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"\nenter item to be searched\t";
cin>>item;
beg=0;end=n;
mid=(beg+end)/2;
while(beg<=end&&a[mid]!=item)
{
if(item<a[mid])
{
end=mid-1;
}
else
{
beg=mid+1;
}
mid=(beg+end)/2;
}
if(a[mid]==item)
{
cout<<"\nitem found at loc "<<mid+1;
}
else
{
cout<<"\nitem not found";
}
getch();
}