**1.
Recursive Binary and Linear Search**
Program:
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int key) {
if (n == 0) return -1;
if (arr[n-1] == key) return n-1;
return linearSearch(arr, n-1, key);
}
int binarySearch(int arr[], int low, int high, int key) {
if (low > high) return -1;
int mid = (low + high)/2;
if (arr[mid] == key) return mid;
if (key < arr[mid]) return binarySearch(arr, low, mid-1, key);
return binarySearch(arr, mid+1, high, key);
}
int main() {
int arr[] = {2,4,6,8,10};
int n = 5, key = 8;
cout << "Linear Search Result: " << linearSearch(arr, n, key) << endl;
cout << "Binary Search Result: " << binarySearch(arr, 0, n-1, key) << endl;
}
Output:
Linear Search Result: 3
Binary Search Result: 3
**2. Heap Sort**
Program:
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest=i;
int l=2*i+1, r=2*i+2;
if(l<n && arr[l]>arr[largest]) largest=l;
if(r<n && arr[r]>arr[largest]) largest=r;
if(largest!=i){ swap(arr[i],arr[largest]); heapify(arr,n,largest); }
}
void heapSort(int arr[], int n){
for(int i=n/2-1;i>=0;i--) heapify(arr,n,i);
for(int i=n-1;i>0;i--){ swap(arr[0],arr[i]); heapify(arr,i,0); }
}
int main(){
int arr[]={4,10,3,5,1};
int n=5;
heapSort(arr,n);
for(int i=0;i<n;i++) cout<<arr[i]<<" ";
}
Output:
1 3 4 5 10
**3. Merge Sort**
Program:
#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r){
int n1=m-l+1, n2=r-m;
int a[n1], b[n2];
for(int i=0;i<n1;i++) a[i]=arr[l+i];
for(int i=0;i<n2;i++) b[i]=arr[m+1+i];
int i=0,j=0,k=l;
while(i<n1 && j<n2) arr[k++]=(a[i]<b[j])?a[i++]:b[j++];
while(i<n1) arr[k++]=a[i++];
while(j<n2) arr[k++]=b[j++];
}
void mergeSort(int arr[], int l, int r){
if(l<r){
int m=(l+r)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
}
int main(){
int arr[]={5,2,4,6,1,3};
mergeSort(arr,0,5);
for(int i=0;i<6;i++) cout<<arr[i]<<" ";
}
Output:
1 2 3 4 5 6
**4. Selection Sort**
Program:
#include <iostream>
using namespace std;
int main(){
int arr[]={64,25,12,22,11};
int n=5;
for(int i=0;i<n-1;i++){
int min=i;
for(int j=i+1;j<n;j++) if(arr[j]<arr[min]) min=j;
swap(arr[min],arr[i]);
}
for(int i=0;i<n;i++) cout<<arr[i]<<" ";
}
Output:
11 12 22 25 64
**5. Insertion Sort**
Program:
#include <iostream>
using namespace std;
int main(){
int arr[]={12,11,13,5,6};
int n=5;
for(int i=1;i<n;i++){
int key=arr[i], j=i-1;
while(j>=0 && arr[j]>key){ arr[j+1]=arr[j]; j--; }
arr[j+1]=key;
}
for(int i=0;i<n;i++) cout<<arr[i]<<" ";
}
Output:
5 6 11 12 13
**6. Quick Sort**
Program:
#include <iostream>
using namespace std;
int partitionArr(int arr[], int low, int high){
int pivot=arr[high], i=low-1;
for(int j=low;j<high;j++){
if(arr[j]<pivot){ i++; swap(arr[i],arr[j]); }
}
swap(arr[i+1],arr[high]);
return i+1;
}
void quickSort(int arr[], int low, int high){
if(low<high){
int pi=partitionArr(arr,low,high);
quickSort(arr,low,pi-1);
quickSort(arr,pi+1,high);
}
}
int main(){
int arr[]={10,7,8,9,1,5};
quickSort(arr,0,5);
for(int i=0;i<6;i++) cout<<arr[i]<<" ";
}
Output:
1 5 7 8 9 10
**7. Knapsack (Greedy Approach)**
Program:
#include <iostream>
using namespace std;
int main(){
int w[]={10,20,30};
int p[]={60,100,120};
int n=3, cap=50;
float ratio[n];
for(int i=0;i<n;i++) ratio[i]=(float)p[i]/w[i];
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(ratio[i]<ratio[j]){ swap(ratio[i],ratio[j]); swap(
float profit=0;
for(int i=0;i<n;i++){ if(w[i]<=cap){ profit+=p[i]; cap-=w[i]; } else { profit+=ratio[i]*cap; brea
cout<<"Maximum Profit = "<<profit;
}
Output:
Maximum Profit = 240
**8. Minimum Spanning Tree (Kruskal Algorithm)**
Program:
#include <iostream>
#include <algorithm>
using namespace std;
class Edge{ public:int src,dest,wt; };
int find(int parent[], int i){ return (parent[i]==i)?i:find(parent,parent[i]); }
void unionSet(int parent[], int x, int y){ parent[x]=y; }
int main(){
Edge edges[4]={{0,1,10},{0,2,6},{0,3,5},{2,3,4}};
int parent[4]; for(int i=0;i<4;i++) parent[i]=i;
sort(edges, edges+4, [](Edge a, Edge b){ return [Link]<[Link]; });
cout<<"Edges in MST:\n";
for(int i=0;i<4;i++){
int x=find(parent,edges[i].src);
int y=find(parent,edges[i].dest);
if(x!=y){ cout<<edges[i].src<<" - "<<edges[i].dest<<"\n"; unionSet(parent,x,y); }
}
}
Output:
2 - 3
0 - 3
0 - 1
**9. Minimum Spanning Tree (Prim's Algorithm)**
Program:
#include <iostream>
using namespace std;
#define V 5
int minKey(int key[], bool mstSet[]){
int min=999, idx;
for(int v=0;v<V;v++) if(!mstSet[v] && key[v]<min){ min=key[v]; idx=v; }
return idx;
}
void prim(int graph[V][V]){
int key[V], parent[V]; bool mstSet[V];
for(int i=0;i<V;i++) key[i]=999, mstSet[i]=false;
key[0]=0; parent[0]=-1;
for(int c=0;c<V-1;c++){
int u=minKey(key,mstSet); mstSet[u]=true;
for(int v=0;v<V;v++) if(graph[u][v] && !mstSet[v] && graph[u][v]<key[v]) parent[v]=u, key[v]=
}
for(int i=1;i<V;i++) cout<<parent[i]<<" - "<<i<<"\n";
}
int main(){
int graph[V][V]={{0,2,0,6,0},{2,0,3,8,5},{0,3,0,0,7},{6,8,0,0,9},{0,5,7,9,0}};
prim(graph);
}
Output:
0 - 1
1 - 2
0 - 3
1 - 4
**10. 0/1 Knapsack (Dynamic Programming)**
Program:
#include <iostream>
using namespace std;
int main(){
int val[]={60,100,120};
int wt[]={10,20,30};
int W=50, n=3;
int dp[n+1][W+1];
for(int i=0;i<=n;i++){
for(int w=0;w<=W;w++){
if(i==0||w==0) dp[i][w]=0;
else if(wt[i-1]<=w) dp[i][w]=max(dp[i-1][w], val[i-1]+dp[i-1][w-wt[i-1]]);
else dp[i][w]=dp[i-1][w];
}
}
cout<<"Maximum Profit = "<<dp[n][W];
}
Output:
Maximum Profit = 220