C++ Programming Questions With Their Solutions.

1. Implementation of CRC for detecting error transmission 2. Implementation of Hamming code. 3. Simulation of Sliding window protocol.

Basic

1. Write a C++ program to display sum of two numbers.

Enter value of A : 10
Enter value of B : 20

Sum : 30

Design and Analysis of Algorithm

1. Write a C++ program to implement binary search.

Enter element to search : 10
Element found at 9

2. Write a C++ program to implement Bubble sort.

Before sorting : 9 10 5 3 2 6 4 7 1 8 
After  sorting : 1 2 3 4 5 6 7 8 9 10

3. Write a C++ program to implement linear search.

#include<iostream>
using namespace std;

int main()
{
    int a[10]={1,2,3,4,5,6,7,8,9,10},n=10,ele,i;
    cout<<"Enter element to search : ";
    cin>>ele;
    for(i=0;i<n;i++)
    {
        if(ele==a[i])
            break;
    }

    if(i==n){
        cout<<"Element not found";
    }else{
        cout<<"Element found at "<<i;
    }
}

Enter element to search : 5
Element found at 4

4. Write a C++ program to implement insertion sort.

#include<iostream>
using namespace std;

int main()
{
    int a[10]={10,5,4,2,9,3,7,8,6,1},n=10;
    cout<<"Before sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";

    for(int i=1;i<n;i++)
    {
        int key=a[i];
        int j=i-1;
        while (key<a[j] && j>=0)
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=key;
    }
    
    cout<<"\nAfter  sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
}

Before sorting : 10 5 4 2 9 3 7 8 6 1 
After  sorting : 1 2 3 4 5 6 7 8 9 10

5. Write a C++ program to implement merge sort.

#include<iostream>
using namespace std;

void merge(int a[],int min,int mid,int max)
{
    int farr=mid-min+1, sarr=max-mid;
    int arr1[farr],arr2[sarr];

    for(int i=0;i<farr;i++)
        arr1[i]=a[min+i];
    
    for(int i=0;i<sarr;i++)
        arr2[i]=a[mid+1+i];

    int i=0,j=0,k=min;
    while (i<farr && j<sarr)
    {
        if(arr1[i] <= arr2[j]){
            a[k]=arr1[i];
            i++;
        }else{
            a[k]=arr2[j];
            j++;
        }
        k++;
    }
    
    while (i<farr)
    {
        a[k]=arr1[i];
        i++;
        k++;
    }
    while (j<sarr)
    {
        a[k]=arr2[j];
        j++;
        k++;
    }
}

void merge_sort(int a[],int min,int max)
{
    if(min<max)
    {
        int mid=(min+max)/2;
        merge_sort(a,min,mid);
        merge_sort(a,mid+1,max);
        merge(a,min,mid,max);
    }
}

int main()
{
    int a[10]={10,5,4,2,9,3,7,8,6,1},n=10;
    cout<<"Before sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";

    merge_sort(a,0,n-1);

    cout<<"\nAfter  sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
}

Before sorting : 10 5 4 2 9 3 7 8 6 1
After  sorting : 1 2 3 4 5 6 7 8 9 10

6. Write a C++ program to implement quick sort.

#include<iostream>
using namespace std;

int partition(int a[],int min,int max)
{
    int i=min-1,j=min,pivot=a[max];

    while (j<max)
    {
        if(a[j]<pivot)
        {
            i++;
            int tmp=a[j];
            a[j]=a[i];
            a[i]=tmp;
        }
        j++;
    }
    int tmp=a[i+1];
    a[i+1]=a[max];
    a[max]=tmp;

    return i+1;
}

void quick_sort(int a[],int min,int max)
{
    if(min<max)
    {
        int p=partition(a,min,max);
        quick_sort(a,min,p-1);
        quick_sort(a,p+1,max);
    }
}

int main()
{
    int a[10]={10,5,4,2,9,3,7,8,6,1},n=10;
    cout<<"Before sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    
    quick_sort(a,0,9);

    cout<<"\nAfter  sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
}

Before sorting : 10 5 4 2 9 3 7 8 6 1
After  sorting : 1 2 3 4 5 6 7 8 9 10

7. Write a C++ program to implement selection sort.

#include<iostream>
using namespace std;

int main()
{
    int a[10]={10,5,4,2,9,3,7,8,6,1},n=10;
    cout<<"Before sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";

    for(int i=0;i<n-1;i++)
    {
        for(int j=i;j<n;j++)
        {
            if(a[i]>a[j])
            {
                int tmp=a[i];
                a[i]=a[j];
                a[j]=tmp;
            }
        }
    }
    
    cout<<"\nAfter  sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
}

Before sorting : 10 5 4 2 9 3 7 8 6 1
After  sorting : 1 2 3 4 5 6 7 8 9 10

8. Write a C++ program to implement heap sort.

#include<iostream>
using namespace std;

void heapify(int a[],int n,int parent)
{
    int largest=parent;
    int l=parent*2+1;
    int r=parent*2+2;

    if(l<n && a[l]>a[largest])
        largest=l;
    if(r<n && a[r]>a[largest])
        largest=r;
    if(parent != largest)
    {
        int tmp=a[parent];
        a[parent]=a[largest];
        a[largest]=tmp;
        heapify(a,n,largest);
    }
}

void heap_sort(int a[],int n)
{
    for(int i=n/2-1;i>-1;i--)
        heapify(a,n,i);
    
    for(int i=n-1;i>0;i--)
    {
        int tmp=a[0];
        a[0]=a[i];
        a[i]=tmp;
        heapify(a,i,0);
    }
}

int main()
{
    int a[10]={10,5,4,2,9,3,7,8,6,1},n=10;
    cout<<"Before sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    
    heap_sort(a,n);
    
    cout<<"\nAfter  sorting : ";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
}

Before sorting : 10 5 4 2 9 3 7 8 6 1
After  sorting : 1 2 3 4 5 6 7 8 9 10

9. Write a C++ program to implement counting sort.

10. Write a C++ program to implement radix sort.

11. Write a C++ program to implement fractional knapsack.

#include<iostream>
using namespace std;

void w_p_sort(float w[],float p[],int n)
{
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++)
        {
            if(p[i]/w[i]<p[j]/w[j]){
                float tmp = p[i];
                p[i]=p[j];
                p[j]=tmp;
                tmp=w[i];
                w[i]=w[j];
                w[j]=tmp;
            }
        }
    }
}

int main()
{
    int n=5;
    float w[n]={5,10,20,30,40},W=60;
    float p[n]={30,20,100,90,160};

    w_p_sort(w,p,n);

    float cost=0;
    for(int i=0;i<n;i++)
    {
        if(w[i]<W){
            cost+=p[i];
            W-=w[i];
        }
        else{
            cost+=(W*p[i])/w[i];
            break;
        }
    }
    cout<<cost;
}

12. Write a C++ program to implement integer knapsack.

13. Write a C++ program to implement matrix chain multiplication.

14. Write a C++ program to implement activity selection problem.

#include<iostream>
using namespace std;

int main()
{
    int n=10;
    int s[n]={1,2,3,4,7,8,9,9,11,12};
    int f[n]={3,5,4,7,10,9,11,13,12,14};

    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++)
        {
            if(f[i]>f[j])
            {
                int tmp=f[i];
                f[i]=f[j];
                f[j]=tmp;
                tmp=s[i];
                s[i]=s[j];
                s[j]=tmp;
            }
        }
    }

    int finish_time=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]>=finish_time)
        {
            cout<<"Starting : "<<s[i]<<", finishing : "<<f[i]<<endl;
            finish_time=f[i];
        }
    }
}

Starting : 1, finishing : 3
Starting : 3, finishing : 4
Starting : 4, finishing : 7
Starting : 8, finishing : 9
Starting : 9, finishing : 11
Starting : 11, finishing : 12
Starting : 12, finishing : 14

15. Write a C++ program to implement longest common subsequence.

16. Write a C++ program to implement BFS (Breath First Search).

17. Write a C++ program to implement DFS (Depth First Search).

18. Write a C++ program to implement krushkal.

#include <algorithm>
#include <iostream>
using namespace std;
typedef struct edge{ int u = 0, v = 0, w = 0;} edge;

int sz[100];

int find_set(int u, int p[])
{
    if (p[u] == u)
        return u;
    return p[u] = find_set(p[u], p);
}

void union_set(int u,int v, int a[])
{
    u = find_set(u, a);
    v = find_set(v, a);

    if (u != v)
    {
        if (sz[u] < sz[v])
            swap(u, v);
        a[v] = u;
        sz[u] += sz[v];
    }
}

int main()
{
    int n, m;
    cin >> n;

    int a[n+1];
    for (int i = 1; i < n+1; i++)
    {
        a[i] = i;
        sz[i] = 1;
    }

    cin >> m;
    edge e[m];
    for(int i = 0; i < m; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }

    for(int i = 0; i < m - 1; i++)
    {
        for (int j = i + 1; j < m; j++)
        {
            if (e[i].w > e[j].w)
            {
                edge temp = e[i];
                e[i] = e[j];
                e[j] = temp;
            }
        }
    }

    int cost = 0;
    for (int i = 0; i < m; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        int x = find_set(u, a);
        int y = find_set(v, a);

        if (x == y)
        {
            continue;
        }
        else
        {
            union_set(u, v, a);
            cout << "\nu, v and w : " << e[i].u << " " << e[i].v << " " << e[i].w;
            cost += e[i].w;
        }
    }

    cout<<"\n\nCost : "<<cost<<endl;
}

8 9
1 2 5
2 3 6
4 3 2
1 4 9
3 5 5
5 6 10
6 7 7
7 8 1
8 5 1

u, v and w : 7 8 1
u, v and w : 8 5 1
u, v and w : 4 3 2
u, v and w : 1 2 5
u, v and w : 3 5 5
u, v and w : 2 3 6
u, v and w : 6 7 7

19. Write a C++ program to implement prims.

#include <iostream>
using namespace std;
#define max 33333

int main()
{
    int graph[7][7] = {{0, 28, 0, 0, 0, 10, 0},
                       {28, 0, 16, 0, 0, 0, 14},
                       {0, 16, 12, 0, 0, 0, 0},
                       {0, 0, 12, 0, 22, 0, 18},
                       {0, 0, 0, 22, 0, 25, 24},
                       {10, 0, 0, 0, 25, 0, 0},
                       {0, 14, 0, 18, 24, 0, 0}},n=7;
    int v[n] = {0, 1, 2, 3, 4, 5, 6}, pi[n]={}, w[n] = {0, max, max, max, max, max, max};
    int rem_v[n]={};
    int root = v[0];
    while (1)
    {
        int j = 0, adj[n - 1];
        for (int i = 0; i < n; i++)
            if (graph[root][i] != 0 && rem_v[i]==0)
            {
                adj[j] = i;
                j++;
            }

        rem_v[root]=1;
        if(j==0)break;
        for (int i = 0;i<j; i++)
            if(w[root]+graph[root][adj[i]] < w[adj[i]])
            {
                w[adj[i]]=w[root]+graph[root][adj[i]];
                pi[adj[i]]=root;
            }

        int min_index=adj[0];
        for(int i=1;i<j;i++)
            if(w[min_index] > w[adj[i]])
                min_index = adj[i];

        root = min_index;
    }
    for(int i=0;i<n;i++)
        cout<<"Vertex : "<<v[i]<<"\tParent : "<<pi[i]<<"\tWeight : "<<w[i]<<endl;
}

Vertex : 0      Parent : 0      Weight : 0
Vertex : 1      Parent : 0      Weight : 28
Vertex : 2      Parent : 1      Weight : 44
Vertex : 3      Parent : 4      Weight : 57
Vertex : 4      Parent : 5      Weight : 35
Vertex : 5      Parent : 0      Weight : 10
Vertex : 6      Parent : 4      Weight : 59

20. Write a C++ program to implement dikjastra.

21. Write a C++ program to implement n-queen problem using back tracking.

#include<iostream>
using namespace std;

bool board[100][100];

void print_queen(int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
}

bool isSafe(int row,int col)
{
    for(int i=0;i<=col;i++)
        if(board[row][i]==1)
            return false;
    
    for(int i=row,j=col;j>=0;i--,j--)
    {
        if(board[i][j]==1)
            return false;
    }
    
    for(int i=row,j=col;j>=0;i++,j--)
    {
        if(board[i][j]==1)
            return false;
    }
    return true;
}

bool n_queen(int col,int n)
{
    if(col == n)
        return true;
    
    for(int i=0;i<n;i++)
    {
        if(isSafe(i,col))
        {
            board[i][col]=1;
            if(n_queen(col+1,n))
                return true;

            board[i][col]=0;
        }
    }

    return false;
}

int main()
{
    int n;
    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            board[i][j]=0;
    
    if(n_queen(0,n)){
        print_queen(n);
    }
    else{
        cout<<"Can't possible...";
    }
}

22. Write a C++ program to implement hamiltonian circuit using back tracking.

#include<iostream>
using namespace std;

bool graph[100][100]={{0,1,1,1,0},
                    {1,0,1,0,1},
                    {1,1,0,1,1},
                    {1,0,1,0,1},
                    {0,1,1,1,0}};
int p[100],source=0;

bool isSafe(int v,int pos,int n)
{
    if(graph[p[pos-1]][v]==0)
        return false;

    for(int i=0;i<=pos;i++)
        if(p[i]==v)
            return false;

    return true;
}

bool hamiltonian(int pos,int n)
{
    if(pos==n)
    {
        if(graph[p[pos-1]][p[0]]==1)
        {
            p[pos]=p[0];
            return true;
        }
        else
            return false;
    }

    for(int i=1;i<n;i++)
    {
        if(isSafe(i,pos,n))
        {
            p[pos]=i;
            if(hamiltonian(pos+1,n))
                return true;
            p[pos]=-1;
        }
    }
    
    return false;
}

int main()
{
    int n=5;

    for(int i=0;i<=n;i++)
        p[i]=-1;

    p[0]=source;
    if(hamiltonian(1,n)){
        for(int i=0;i<=n;i++)
        {
            cout<<p[i]<<" ";
        }
    }
    else{
        cout<<"Can't possible...";
    }
}

0 1 2 4 3 0

23. Write a C++ program to implement subset problem using back tracking.

#include<bits/stdc++.h>
using namespace std;

vector<int> subset;

bool isSafe(int s[],int m,int pos,int sum)
{
    if(sum+s[pos]<=m)
        return true;
    else
        return false;
}

bool sub_set(int s[],int m,int pos,int n,int sum)
{
    if(sum==m)
    {
        for(int i=0;i<subset.size();i++)
            cout<<subset[i]<<" ";
        return true;
    }
    
    for(int i=pos;i<n;i++)
    {
        if(isSafe(s,m,i,sum))
        {
            subset.push_back(s[i]);
            sum+=s[i];
            if(sub_set(s,m,i+1,n,sum))
                return true;
            subset.pop_back();
            sum-=s[i];
        }
    }
    return false;
}

int main()
{
    int s[4]={4,6,7,8},m=18,n=4;
    sort(s,s+n);
    if(sub_set(s,m,0,n,0)==false)
        cout<<"Can't possible...";
}

4 6 8

24. Write a C++ program to implement TSP (Travelling Salesman Problem) using back tracking.

#include<bits/stdc++.h>
using namespace std;

int graph[100][100]={{0,5,0,6,0,4,0,7},
                    {5,0,2,4,3,0,0,0},
                    {0,2,0,1,0,0,0,0},
                    {6,4,1,0,7,0,0,0},
                    {0,3,0,7,0,0,6,4},
                    {4,0,0,0,0,0,3,0},
                    {0,0,0,0,6,3,0,2},
                    {7,0,0,0,4,0,2,0}};

void tsp(vector<bool>& v,int currpos,int n,int count,int cost,int& ans)
{
    if(count==n && graph[currpos][0]){
        ans=min(ans,cost+graph[currpos][0]);
        return;
    }

    for(int i=0;i<n;i++)
    {
        if(!v[i] && graph[currpos][i])
        {
            v[i]=true;
            tsp(v,i,n,count+1,cost+graph[currpos][i],ans);
            v[i]=false;
        }
    }
}

int main()
{
    int n=8;
    vector<bool> v;
    for(int i=0;i<n;i++)
        v.push_back(false);

    v[0]=true;
    int ans=INT_MAX;
    tsp(v,0,n,1,0,ans);
    cout<<ans;
}

25. Write a C++ program to implement TSP (Travelling Salesman Problem) using dynamic programming.

#include<bits/stdc++.h>
using namespace std;

int graph[100][100]={{0,10,15,20},
                    {10,0,35,25},
                    {15,35,0,30},
                    {20,25,30,0}};

int tsp(int s,int n)
{
    vector<int> vertex;
    for(int i=0;i<n;i++)
        if(i!=s)
            vertex.push_back(i);

    int min_path = INT_MAX;
    do{
        int current_pathweight =0;
        int k=s;
        for(int i=0;i<vertex.size();i++)
        {
            current_pathweight+=graph[k][vertex[i]];
            k=vertex[i];
        }
        current_pathweight+=graph[k][s];
        min_path=min(min_path,current_pathweight);
    }while (next_permutation(vertex.begin(),vertex.end()));
    
    return min_path;
}

int main()
{
    int n=4,s=0;
    cout<<tsp(s,n);
}

Computer Network

1. Write a C++ Program to implementation of CRC for detecting error transmission.

-----Sender side ------
Enter the data (in binary) : 1010
Enter the key (in binary) : 1111
New data is : 10100000
Remainder is : 101
Final data to send : 10100101

------Reciever side ------
Received data : 10100101
Remainder is : 0
Actual data is : 1010

2. Write a C++ Program to implementation of Hamming code.

Enter data (in binary) : 1010
Number of parity bits is : 3
New data is : 101P0PP
New data length is : 7
Final data to send is : 1010010

3. Write a C++ Program to simulation of Sliding window protocol.

Enter window size : 4
Enter number of frames to transmit : 12
Enter 12 frames : 1 2 3 4 5 6 7 8 9 1 5 9

Window 1 is : 1 2 3 4           Ack 1 Received
Window 2 is : 5 6 7 8           Ack 2 Received
Window 3 is : 9 1 5 9           Ack 3 Received

C++ Programming Questions With Their Solutions.

1 Comments

Contact Form