Insertion Sort:
#include <stdio.h>

void insertionSort(int arr[], int n)
{
	int i, key, j;
	int innerCounter = 0;
	int outerCounter = 0;
	for (i = 1; i < n; i++) {
		key = arr[i];
		j = i - 1;

		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j = j - 1;

			innerCounter++;
		}
		arr[j + 1] = key;
		outerCounter++;
	}
	printf("In Insertion Sort value of \nOuterCounter = %d and InnerCounter = %d\n", outerCounter, innerCounter);
	printf("After Implementing Insertion Sort : ");
}

void printArray(int arr[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}


int main()
{
    int U[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(U)/sizeof(U[0]);

    int V[] = {6, 5, 4, 3, 2, 1};
    int m = sizeof(V)/sizeof(V[0]);

    int W[] = {1, 3, 4, 5, 2, 6};
    int o = sizeof(W)/sizeof(W[0]);

    printf("                                                ");
    printf("\nName: Kartik Yeole\n");
    printf("________________________________________________");

    printf("\nGiven Array: W = ");
    printArray(W,o);
    insertionSort(W,o);
    printArray(W,o);

    printf("\nGiven Array: U = ");
    printArray(U,n);
    insertionSort(U,n);
    printArray(U,n);

    printf("\nGiven Array: V = ");
    printArray(V,m);
    insertionSort(V,m);
    printArray(V,m);


    printf("________________________________________________");


    return 0;
}



Selection Sort:

#include <stdio.h>
#include <stdlib.h>

void selectionSort(int arr[], int n)
{
    int i, j, min_idx, temp;
    int innerCounter = 0;
    int outerCounter = 0;

    for (i = 0; i < n-1; i++)
    {
        min_idx = i;
        for (j = i+1; j < n; j++)
        {
           if (arr[j] < arr[min_idx])
          {
              min_idx = j;
          }
          innerCounter++;
        }

        temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;

        outerCounter++;
    }
    printf("In Selection Sort value of \nOuterCounter = %d and InnerCounter = %d\n", outerCounter, innerCounter);
    printf("After Implementing Selection Sort : ");
}

void printArray(int arr[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

int main()
{
    int U[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(U)/sizeof(U[0]);

    int V[] = {6, 5, 4, 3, 2, 1};
    int m = sizeof(V)/sizeof(V[0]);

    int W[] = {1, 3, 4, 5, 2, 6};
    int o = sizeof(W)/sizeof(W[0]);

    printf("                                                ");
    printf("\nName: Kartik Yeole\n");
    printf("________________________________________________");

    printf("\nGiven Array: W = ");
    printArray(W,o);
    selectionSort(W,o);
    printArray(W,o);

    printf("\nGiven Array: U = ");
    printArray(U,n);
    selectionSort(U,n);
    printArray(U,n);

    printf("\nGiven Array: V = ");
    printArray(V,m);
    selectionSort(V,m);
    printArray(V,n);

    printf("________________________________________________");
    return 0;
}

Recurrance Relation:

#include <bits/stdc++.h>
#include <iostream>
#include <string.h>

using namespace std;

class Quadratic{

public:
    //print root of quadratic equation

    void findRoots(int a, int b, int c)
    {
        if(a == 0)
        {
            cout << "Invalid";
            return;
        }

        int d = b*b - 4*a*c;
        float sqrt_val = sqrt(abs(d));

        //real and distinct roots
        if(d > 0)
        {
            cout<< "Roots are real and different" << endl;
            cout<< fixed << std::setprecision(1)
                        << float((-b + sqrt_val) / (2 * a)) << endl;
            cout << fixed << std::setprecision(1)
                        << float((-b - sqrt_val) / (2 * a)) << endl;
            cout << "The General Solution will be: " << endl;
            cout << "t(n) = c1 " <<float((-b + sqrt_val) / (2 * a)) <<"^n + c2 "<< float((-b - sqrt_val) / (2 * a)) <<"^n"<< endl;
        }

        else if(d == 0)
        {
            cout<< "Roots are real and same" << endl;
            cout<< fixed << std::setprecision(1)
                        << float((-b + sqrt_val) / (2 * a)) << endl;
            cout << fixed << std::setprecision(1)
                        << float((-b + sqrt_val) / (2 * a)) << endl;
            cout << "The General Solution will be: " << endl;
            cout << "t(n) = c1 * e^" <<float((-b + sqrt_val) / (2 * a)) <<"n + c2 * e^"<< float((-b - sqrt_val) / (2 * a)) <<"n"<< endl;
        }

        //Imaginary roots
        else if(d < 0)
        {
            cout << "Roots are complex" << endl;
            cout << fixed << std::setprecision(1)
                 << float(b / (2.0 * a)) << " + i"
                 << sqrt_val << endl;
            cout << fixed << std::setprecision(1)
                 << float(b / (2.0 * a)) << " - i"
                 << sqrt_val << endl;
            cout << "The General Solution will be: " << endl;
            cout << "t(n) = " << float(b / (2.0 * a))<<"^n( c1*cos(nx) + c2*sin(nx))" << endl;
        }
    }

};

int main()
{
    Quadratic obj;
    int a, b, c;
    cout << "Kartik Yeole" << endl;
    cout << "Enter values of a, b, c" << endl;
    cin >>a>>b>>c;
    obj.findRoots(a,b,c);

    return 0;
}


Merge Sort:

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];


    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }


    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int A[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}


int main()
{
    int i, arr[10];
        for (i=0;i<=9;i++) {
            scanf("%d",&arr[i]);
        }
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("");
    scanf("");

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

Quick Sort:

#include <stdio.h>

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

int partition(int array[], int low, int high) {

  int pivot = array[high];

  int i = (low - 1);

  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) {


      i++;

      swap(&array[i], &array[j]);
    }
  }

  swap(&array[i + 1], &array[high]);

  return (i + 1);
}

void quickSort(int array[], int low, int high) {
  if (low < high) {

    int pi = partition(array, low, high);

    quickSort(array, low, pi - 1);

    quickSort(array, pi + 1, high);
  }
}

void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

int main() {
  int z, data[10];
        for (z=0;z<=10;z++) {
            scanf("%d",&data[z]);
        }
  int n = sizeof(data) / sizeof(data[0]);

  printf("Unsorted Array\n");
  printArray(data, n);

  quickSort(data, 0, n - 1);

  printf("Sorted array in ascending order: \n");
  printArray(data, n);
}

Knapsack:

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

int main()
{
    int n;
    cout << "Enter the number of items in a knapsack: ";
    cin >> n;
    vector< pair<int,int> > w,v;
    vector< pair<float,int> > knap;
    for(int i=0;i<n;i++)
    {
        int value,weight;
        cout << "Enter the value and weight: ";
        cin >> value >>  weight;
        w.push_back(make_pair(weight,i+1));
        v.push_back(make_pair(value,i+1));
        knap.push_back(make_pair((float)value/(float)weight, i+1));
    }
    sort(w.begin(), w.end());
    sort(v.rbegin(), v.rend());
    sort(knap.rbegin(), knap.rend());

    for(int i=0;i<n;i++)
    {
    //  cout << w[i].first << " " << w[i].second << endl;
     // cout << v[i].first << " " << v[i].second << endl;
       cout << knap[i].first << " " << knap[i].second << endl;
    }
    int num,W,sum=0;
    cout << "Enter the maximum value of weight : ";
    cin >> W;
    cout << endl;
    cout << "Choose the operation to perform: \n 1.Most valuable first \n 2.Lightest first \n 3.Largest value per weight \n";
    cin >> num;

    switch(num)
    {
    case 1: //Most valuable first
        for(int i=0;i<n;i++)
        {
            if(W > 0 && W >= w[v[i].second-1].first)
            {

                sum += v[i].first;
                W = W - w[v[i].second-1].first;
            }
            else if(W < w[v[i].second-1].first && W != 0)
            {
                sum +=  ((w[v[i].second-1].first - W)*v[i].first)/w[v[i].second-1].first;
                W=0;
            }
            if(W == 0)
                break;
        }
        cout << "Max Value : " << sum << endl;
        break;

    case 2:

        for(int i=0;i<n;i++)
        {

          if(W > 0 && W >= w[i].first)
             {
                  for(int j=0;j<n;j++)
                  {
                      if(w[i].second == v[j].second)
                    {
                     sum += v[j].first;
                     W -= w[i].first;
                     cout << sum << " ";
                     break;
                    }
                  }
             }
          else if (W > 0 && W < w[i].first)
          {
               for(int j=0;j<n;j++)
                  {
                      if(w[i].second == v[j].second)
                    {
                     sum += (W*v[j].first) / w[i].first;
                    }
                  }
          }
        }
         cout << "Max Value : " << sum << endl;
        break;

    case 3:
         for(int i=0;i<n;i++)
         {
             for(int j=0;j<n;j++){
                         if(knap[i].second == w[j].second)
                         {
                            if(W > 0 && w[j].first <= W){
                             W -= w[j].first;
                             for(int k=0;k<n;k++)
                             {
                                 if(knap[i].second == v[k].second)
                                 {
                                     sum += v[k].first;

                                 }
                             }
                            }
                            else if(W > 0 && W < w[j].first)
                            {
                                for(int k=0;k<n;k++)
                             {
                                 if(knap[i].second == v[k].second)
                                 {
                                     sum +=  (W * v[k].first) / w[j].first;
                                     cout << W << " " << (w[j].first - W) * v[k].first << " ";
                                     W=0;
                                 }
                             }
                            }
                         }
         }
         }
          cout << "Max Value : " << sum << endl;
        break;
    }
}



Floyd Warshall:
#include<iostream>
#include<iomanip>
#define NODE 4
#define INF 999
using namespace std;
//Cost matrix of the graph
int costMat[NODE][NODE] = {
   {0, INF, -2, INF},
   {4, 0, 3, INF},
   {INF, INF, 0, 2},
   {INF, -1, INF, 0},
};
void floydWarshal(){
   int cost[NODE][NODE]; //defind to store shortest distance from any node to any node
   for(int i = 0; i<NODE; i++)
      for(int j = 0; j<NODE; j++)
         cost[i][j] = costMat[i][j]; //copy costMatrix to new matrix
         for(int k = 0; k<NODE; k++){
            for(int i = 0; i<NODE; i++)
               for(int j = 0; j<NODE; j++)
                  if(cost[i][k]+cost[k][j] < cost[i][j])
                     cost[i][j] = cost[i][k]+cost[k][j];
   }
   cout << "The matrix:" << endl;
   for(int i = 0; i<NODE; i++){
      for(int j = 0; j<NODE; j++)
         cout << setw(3) << cost[i][j];
      cout << endl;
   }
}
int main(){
   floydWarshal();
}


TSP:

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

// implementation of traveling Salesman Problem
int travllingSalesmanProblem(int graph[][V], int s)
{
    // store all vertex apart from source vertex
    vector<int> vertex;
    for (int i = 0; i < V; i++)
        if (i != s)
            vertex.push_back(i);

    // store minimum weight Hamiltonian Cycle.
    int min_path = INT_MAX;
    do {

        // store current Path weight(cost)
        int current_pathweight = 0;

        // compute current path weight
        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];

        // update minimum
        min_path = min(min_path, current_pathweight);

    } while (
        next_permutation(vertex.begin(), vertex.end()));

    return min_path;
}

// Driver Code
int main()
{
    // matrix representation of graph
    int graph[][V] = { { 0, 10, 15, 20 },
                       { 10, 0, 35, 25 },
                       { 15, 35, 0, 30 },
                       { 20, 25, 30, 0 } };
    int s = 0;
    cout << "The minimum cost path is: "<< travllingSalesmanProblem(graph, s) << endl;
    return 0;
}




Graph Color:

#include <iostream>
using namespace std;

#define V 6

void printSolution(int color[]);

bool isSafe(int v, bool graph[V][V],
            int color[], int c)
{
    for(int i = 0; i < V; i++)
        if (graph[v][i] && c == color[i])
            return false;

    return true;
}

bool graphColoringUtil(bool graph[V][V], int m,
                    int color[], int v)
{

    if (v == V)
        return true;

    for(int c = 1; c <= m; c++)
    {

        if (isSafe(v, graph, color, c))
        {
            color[v] = c;

            if (graphColoringUtil(
                graph, m, color, v + 1) == true)
                return true;

            color[v] = 0;
        }
    }

    return false;
}

bool graphColoring(bool graph[V][V], int m)
{

    int color[V];
    for(int i = 0; i < V; i++)
        color[i] = 0;

    if (graphColoringUtil(graph, m, color, 0) == false)
    {
        cout << "Solution does not exist";
        return false;
    }

    printSolution(color);
    return true;
}

void printSolution(int color[])
{
    cout << "Solution Exists:"
        << " Following are the assigned colors"
        << "\n";
    for(int i = 0; i < V; i++)
        cout << " " << color[i] << " ";

    cout << "\n";
}

int main()
{

    bool graph[V][V] = { { 0, 1, 1, 0, 0, 0 },
                         { 1, 0, 1, 1, 0, 0 },
                         { 1, 1, 0, 1, 1, 1 },
                         { 0, 1, 1, 0, 1, 0 },
                         { 0, 0, 1, 1, 0, 1 },
                         { 0, 0, 1, 0, 1, 0 },};

    int m = 3;
    graphColoring(graph, m);
    return 0;
}



8 Queen’s:

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

void printSolution(int board[N][N])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << " " << board[i][j] << " ";
        printf("\n");
    }
}

bool isSafe(int board[N][N], int row, int col)
{
    int i, j;

    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;

    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return false;

    for (i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j])
            return false;

    return true;
}

bool solveNQUtil(int board[N][N], int col)
{

    if (col >= N)
        return true;

    for (int i = 0; i < N; i++) {

        if (isSafe(board, i, col)) {
            board[i][col] = 1;

             if (solveNQUtil(board, col + 1))
                return true;

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

    return false;
}

bool solveNQ()
{
    int board[N][N] = { { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 } };

    if (solveNQUtil(board, 0) == false) {
        cout << "Solution does not exist";
        return false;
    }

    printSolution(board);
    return true;
}

int main()
{
    solveNQ();
    return 0;
}