Merge Sort

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


using namespace std;


//function to merge two halves
// arr[l..m] abd arr[m+1 ... r]

void merge(int arr[], int l, int m, int r)
{
   
    int n1 = m - l + 1; // total elements in first half
    int n2 = r - m;// in second half
    int i = 0, j = 0, k = 0;
    int L[n1], R[n2];

    // copy data to temp arrays
    for ( i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for ( j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // merge temp arrays back to a[l..r];
    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++;
        }
    }

    /* Copy the remaining elements of L[] , if there are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there are any */
    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++)
        cout << A[i];
    printf("\n");
}


int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);

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

    mergeSort(arr, 0, arr_size - 1);

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

Merge sort on Linked List

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

struct node
{
    int data;
    struct node* next;
};

// function prototypes
struct node* SortedMerge(struct node* a, struct node* b);
void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef);

//sorts linked list by changing next pointers
void MergeSort(struct node** headRef)
{
    struct node* head = *headRef;
    struct node* a;
    struct node* b;

    //base case , when there are one or no elements
    if (head == NULL || head->next == NULL)
        return;

    // split head into a nd b sublists
    FrontBackSplit(head, &a, &b);

    // recursively sort sublist
    MergeSort(&a);
    MergeSort(&b);

    // answer = head of the merged list
    *headRef = SortedMerge(a,b);

}

struct node* SortedMerge(struct node* a, struct node* b)
{
    struct node* result = NULL;

    /* Base cases */
    if (a == NULL)
        return(b);
    else if (b == NULL)
        return(a);

    /* Pick either a or b, and recur */
    if (a->data <= b->data)
    {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else
    {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return(result);
}

// using fast slow pointer techniques to split the list in two halves
void  FrontBackSplit(struct  node* source, struct node** frontRef, struct node** backRef)
{
    struct node* fast;
    struct node* slow;
    if (source == NULL || source->next == NULL)
    {
        //length < 2 cases
        *frontRef = source;
        *backRef = NULL;
    }
    else
    {
        slow = source;
        fast = NULL;

        //advance fast two nodes and slow notes
        while (fast != NULL)
        {
            fast = fast->next;
            if (fast != NULL)
            {
                slow = slow->next;
                fast = fast->next;
            }
        }

        //slow is before midpoint in list , split in two halfs
        *frontRef = source;
        *backRef = slow->next;
        slow->next = NULL;
    }
}

/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}


void push(struct node** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node =
        (struct node*) malloc(sizeof(struct node));

    /* put in the data  */
    new_node->data = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

int main()
{
  /* Start with the empty list */
 
  struct node* a = NULL;

  /* Let us create a unsorted linked lists to test the functions
   Created lists shall be a: 2->3->20->5->10->15 */
  push(&a, 15);
  push(&a, 10);
  push(&a, 5);
  push(&a, 20);
  push(&a, 3);
  push(&a, 2);

  /* Sort the above created Linked List */
  MergeSort(&a);

  printf("\n Sorted Linked List is: \n");
  printList(a);          

  getchar();
  return 0;
}

Insertion sort

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

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

        //move elements between arr[0.. i-1] one position
        //ahead of theie current position, whhich are greater then key
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;

    }
}

Optimised bubble sort




void bubbleSort(int arr[], int n)

{

   int i, j;

   bool swapped;

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

   {

     swapped = false;

     for (j = 0; j < n-i-1; j++)

     {

        if (arr[j] > arr[j+1])

        {

           swap(&arr[j], &arr[j+1]);

           swapped = true;

        }

     }

 

     //if no elements are swapped by inner loop  , then break

     if (swapped == false)

        break;

   }

}

 

Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

#include<iostream>
#include<conio.h>
using namespace std;

void printUnsorted(int arr[], int n);
int main()
{
    int arr[] = { 10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    printUnsorted(arr,arr_size);
    getchar();
    return 0;
}

void printUnsorted(int arr[], int n)
{
    int s = 0, e = n - 1, i, max, min;

    //scan from left to right and find the first element which is
    //greater then its next element
    for (s = 0; s < n - 1; s++)
    {
        if (arr[s] > arr[s + 1])
            break;
    }
    if (s == n - 1)
    {
        printf("the complete array is sorted");
        return;
    }

    //scan from right to left and find the index of first elemnt which is smaller then next element
    for (e = n - 1; e > 0; --e)
    if (arr[e] < arr[e - 1]) break;


    //find the minimum and smallest element between arr[s..e] subarray
    max = arr[s];  min = arr[s];
    for (i = s + 1; i <= e; ++i)
    {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    //find the first element in arr[0..s - 1] which is greater than min
    for (i = 0; i < s; i++)
    {
        if (arr[i] > min)
        {
            s = i;
            break;
        }
    }

    //find the first element in arr[e+1 .. n-1] which is greater than min
    for (i = n - 1; i >= e + 1; --i)
    {
        if (arr[i] < max)
        {

            e = i;
            break;
        }
    }

    printf(" The unsorted subarray which makes the given array "
        " sorted lies between the indees %d and %d", s, e);
    return;


}

Hamiltonion Cycle

// hamiltionian cycle - backtracking

#include<stdio.h>
#include<conio.h>

// ttl vertices
#define V 5
void printSolution(int path[]);

bool isSafe(int v, bool graph[V][V], int path[], int pos)
{
        // check if added vertex is adjacent vertex of previously added vertex
    if (graph[path[pos - 1]][v] == 0)
        return false;

    // check if vertex has already been included
    for (int i = 0; i < pos; ++i)
    if (path[i] == v) return false;

    return true;
}

bool hamCycleUtil(bool graph[V][V], int path[], int pos)
{
    //base case
    if (pos == V)
    {
        if (graph[path[pos - 1]][path[0]] == 1) // if there exist an edge bw last included to firstvertex
            return true;
        else
            return false;


    }

    //try different verticies as next candidate in hamiltonian cycle
    for (int v = 1; v < V; ++v)
    {
        if (isSafe(v, graph, path, pos))
        {
            path[pos] = v;
            //recur to contruct rest of the path
            if (hamCycleUtil(graph, path, pos + 1) == true)
                return true;

            //else backtrack
            path[pos - 1];
        }

    }

    //if no vertex can be added to cycle ,return false
    return false;
}


bool hamCycle(bool graph[V][V])
{
    int *path = new int[V];
    for (int i = 0; i < V; i++)
        path[i] = -1;

    /* Let us put vertex 0 as the first vertex in the path. If there is
    a Hamiltonian Cycle, then the path can be started from any point
    of the cycle as the graph is undirected */
    path[0] = 0;
    if (hamCycleUtil(graph, path, 1) == false)
    {
        printf("\nSolution does not exist");
        return false;
    }

    printSolution(path);
    return true;
}

/* A utility function to print solution */
void printSolution(int path[])
{
    printf("Solution Exists:"
        " Following is one Hamiltonian Cycle \n");
    for (int i = 0; i < V; i++)
        printf(" %d ", path[i]);

    //  print the first vertex again to show the complete cycle
    printf(" %d ", path[0]);
    printf("\n");
}

// driver program to test above function
int main()
{
    /* Let us create the following graph
    (0)--(1)--(2)
    |   / \   |
    |  /   \  |
    | /     \ |
    (3)-------(4)    */
    bool graph1[V][V] = { { 0, 1, 0, 1, 0 },
    { 1, 0, 1, 1, 1 },
    { 0, 1, 0, 0, 1 },
    { 1, 1, 0, 0, 1 },
    { 0, 1, 1, 1, 0 },
    };

    // Print the solution
    hamCycle(graph1);

    /* Let us create the following graph
    (0)--(1)--(2)
    |   / \   |
    |  /   \  |
    | /     \ |
    (3)       (4)    */
    bool graph2[V][V] = { { 0, 1, 0, 1, 0 },
    { 1, 0, 1, 1, 1 },
    { 0, 1, 0, 0, 1 },
    { 1, 1, 0, 0, 0 },
    { 0, 1, 1, 0, 0 },
    };

    // Print the solution
    hamCycle(graph2);
    getchar();
    return 0;
}

Back Tracking - m coloring problem

#include<stdio.h>

//total vertices of ours graph
#define V 4

void printSol(int color[]);




// utility function to check whther assighning a color to vertex is safe
bool isSafe(int v, bool graph[V][V], int color[], int c)
{
    //check for adjacent vertices which dont have same color as 'c'
    for (int i = 0; i < V; ++i)
    {
        if (graph[v][i] && c == color[i])
            return false ;
    }
    return true;
}

//recursive util to solve m coloring prblm

bool graphColornUtil(bool graph[V][V], int m, int color[], int v)
{
    //base case if all vertices are colored
    if (v == V)
        return true;

    //consider all colors for this vertex v
    for (int c = 1; c <= m; ++c)
    {
        if (isSafe(v, graph, color,c))
        {
            color[v] = c;
            if (graphColornUtil(graph, m, color, v + 1) == true)
                return true;
            //backtrack
            color[v] = 0;

        }
    }

    return false; // if no color can be assighned
}


bool graphColoring(bool graph[V][V], int m)
{
    // Initialize all color values as 0. This initialization is needed
    // correct functioning of isSafe()
    int *color = new int[V];
    for (int i = 0; i < V; i++)
        color[i] = 0;

    // Call graphColoringUtil() for vertex 0
    if (graphColornUtil(graph, m, color, 0) == false)
    {
        printf("Solution does not exist");
        return false;
    }

    // Print the solution
    printSol(color);
    return true;
}

/* function to print solution */
void printSol(int color[])
{
    printf("Sol Exists:"
        " Following r the assigned colors \n");
    for (int i = 0; i < V; i++)
        printf(" %d ", color[i]);
    printf("\n");
}

// driver program to test above function
int main()
{
    /* Create following graph and test whether it is 3 colorable
    (3)---(2)
    |      /   |
    |    /     |
    | /       |
    (0)---(1)
    */

    //adjaceny matrix
    bool graph[V][V] = { { 0, 1, 1, 1 },
    { 1, 0, 1, 0 },
    { 1, 1, 0, 1 },
    { 1, 0, 1, 0 },
    };
    int m = 3; // Number of colors
    graphColoring(graph, m);
    getchar();
    return 0;
}

Backtracking - permuation of a string

    //permuatiions using backtracking
    //programme to generate permutations of a string
//Algorithm Paradigm: Backtracking
//Time Complexity : O(n*n!)

#include<iostream>
#include<stdlib.h>
using namespace std;

void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;

}
// @params i is start index
// @params n is end index
void permute(char *a, int i, int n)
{
    int j;
    if (i == n)
        cout << "\n" << a;
    else
    {
        for (j = i; j <= n; ++j)
        {
            if( (a + i ) == ( a + j )  && i != j) continue;
            swap((a + i), (a + j));
            permute(a, i + 1, n);
            swap((a + i), (a + j)); //backtrack
        }
    }
}

/* Driver program to test above functions */
int main()
{
    char a[] = "ABC";
    permute(a, 0, 2);
    getchar();
    return 0;
}

Backttracking - n queens prblm

#include<iostream>
#include<conio.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++)
            printf(" %d ", board[i][j]);
        printf("\n");
    }
}

//utility function to check if placing a queen is safe

bool isSafe(int board[N][N], int row, int col)
{
    //check from the left side of upper diagonal from queen's  present position
    for (int i = row, j = col; i >= 0 && j >= 0; --i, --j)
    {
        if (board[i][j] )
            return false;
    }

    //similarly check from queens bottom diagonal from the lefts side
    for (int i = row, j = col; i < N && j >= 0; ++i, --j)
    {
        if (board[i][j])
            return false;
    }

    //check for queens left col
    for (int i = 0; i <col ; ++i)
    if (board[row][i])
        return false;

    return true;

}


// a utility function to solve n queens problem recursively
bool solveNQueenUtil(int board[N][N], int col)
{
    //base case
    if (col >= N)
        return true;

    //considering each row once for a column
    for (int i = 0; i < N; ++i)
    {
        if (isSafe(board, i, col))
        {
            board[i][col] = 1;
            if (solveNQueenUtil(board, col + 1) )
                return true;
            //backtrack
            board[i][col] = 0;
        }
    }

    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 }
    };

    if (solveNQueenUtil(board, 0) == false)
    {
        printf("Solution does not exist");
        return false;
    }

    printSolution(board);
    return true;
}

// driver program to test above function
int main()
{
    solveNQ();

    getchar();
    return 0;
}

Knight Tour Problem - BackTracking

The knight is placed on the first block of an empty board and,
moving according to the rules of chess, must visit each square exactly once

#include<stdlib.h>
#include<iostream>
#define N 8

int solveKnightTourUtil(int x, int y, int movei, int sol[N][N], int xMove[N], int yMove[N]);

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[],
    int yMove[]);

//check if i,j are valid indexes on N*N chess board
int isSafe(int x, int y, int sol[N][N])
{
    if (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1)
    {
        return 1;
    }
    return 0;
}

void printSolution(int sol[N][N])
{
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
            printf(" %2d ", sol[x][y]);
        printf("\n");
    }
}

bool solveKnightTour(){
    int sol[N][N];

    //initialise solution matrix
    for (int x = 0; x < N; x++)
    for (int y = 0; y < N; y++)
        sol[x][y] = -1;

    // define next move of knight as xMove[] and yMove[]
   
    int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

    //knight is at first block
    sol[0][0] = 0;


    // xplore all tours using solveKnightTourUtil() starting from 0,0
    if (solveKnightTourUtil(0, 0, 1, sol, xMove, yMove) == false)
    {
        printf("Solution does not exist");
        return false;
    }
    else
        printSolution(sol);

    return true;
}


// recursive function to solve knight tour problem
int solveKnightTourUtil(int x, int y, int movei, int sol[N][N], int xMove[N], int yMove[N])
{
    int k, next_x, next_y;
    //solution vector completes
    if (movei == N*N)
        return true;

    //try all moves from cuurent position x, y
    for (k = 0; k < 8; ++k)
    {
        next_x = x + xMove[k];
        next_y = y + yMove[k];

        if (isSafe(next_x, next_y, sol))
        {
            sol[next_x][next_y] = movei;
            if (solveKnightTourUtil(next_x, next_y, movei + 1,sol, xMove, yMove))
                return true;

            else
                sol[next_x][next_y] = -1; //backtrack
        }
    }

    return false;
}



int main()
{
    solveKnightTour();
    getchar();
    return 0;
}

OPTIMAL BINARY SEARCH TREE - DYNAMIC PROGRAMMING

/*
    Optimal BST using dynamic programming approach
    cost[n][n] auxiliary array to store the solution of subproblem
    cost[0][n-1] holds the final result

    First fill all diagonal entries i.e cost[i][i] and then
    values above the diagonal - cost[i][i+1] , cost[i][i+2]

    Uses a chain length variable L and increment it iteratively to calculate
    'j' using 'i' and 'L'

*/

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

using namespace std;


//utility function to get sum of array withing bounds specified
int sum(int freq[], int i, int j);



//function deploying dynamic programming approcah to calculate minimum cost of
//BST

int optimalSearchTree(int keys[], int freq[], int  n)
{
    int cost[3][3];


    //cost[i][j] is optimal cost of bst formed from keys[i] to keys[j]

    //for single key cost is equal to frequency of the key
    for (int i = 0; i < n; ++i)
        cost[i][i] = freq[i];

    //consider chains of length 2, 3 ,..and stuff like this
    //where L would be the chain length

    for (int L = 2; L <= n; ++L)
    {

        for (int i = 0; i < n - L + 1; ++i)
        {
            int j = i + L - 1;
            cost[i][j] = INT_MAX;

       

            //make all key bw interval keys[i..j] as root
            for (int r = i; r <= j; ++r)
            {
                            //c = cost of keys[r] acting as root of this subtree
                int c = ((r > i) ? cost[i][r - 1] : 0) + ((r < j) ? cost[r + 1][j] : 0)
                    + sum(freq, i, j);
                if (c < cost[i][j])
                    cost[i][j] = c;
            }
        }

       
    }
    return cost[0][n - 1];
}


//utility function to get sum of array withing bounds specified
int sum(int freq[], int i, int j)
{
    int s = 0;
    for (int k = i; k <= j; ++k)
        s += freq[k];
    return s;
}

    // Driver program to test above functions
    int main()
    {
        int keys[] = { 10, 12, 20 };
        int freq[] = { 34, 8, 50 };
        int n = sizeof(keys) / sizeof(keys[0]);
        printf("Cost of Optimal BST is %d ", optimalSearchTree(keys, freq, n));
        getchar();
        return 0;
    }

   
   
   

If I Switch

/*#include<iostream>
#include<conio.h>
using namespace std;
int main()
{

    int a = 2, b = 5;
    switch (a)
    {
    case 1:cout << "case 1 \n";
        // ...
        cout << "bw i and 2  \n";
        if (b == 2)
        {
    case 2:  cout << "case 2 \n";
        cout << "in if  after case  2  \n";
        // ...
        }
        else case 3:
        {
            cout << "else case 3   \n";
            // ...
            for (b = 0; b < 10; b++)
            {
        case 5: cout <<"case 5 \n"; cout << "loop \n";
            // ...
            }
        }
            break;

        case 4:
            cout << "case 4  \n";
            // ...
            break;
    }
    getchar();
}

LONGEST INCREASING SUBSEQUENCE - DYNAMIC PROGRAMMING

//LONGEST INCREASING SUBSEQUENCE - DYNAMIC PROGRAMMING APPROACH - O(n^2)

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

using namespace std;

//lis() returns length of longest increasing subsequence in arr[] of size n
int lis(int arr[], int n)
{
    int* lis, i, j, max = 0;
    lis = ( int * )malloc( sizeof(sizeof(int)* n) ) ;

    //initialise lis values for all indexes
    for (int i = 0; i < n; ++i)
        lis[i] = 0;

    //bottom up uproach for dynamically calculating optimized LIS value
    for (int i = 1; i < n; ++i)
    for (int j = 0; j < i; ++j)
    if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
        //update lis[i]
        lis[i] = lis[j] + 1;

    //pick max of lis values
    for (i = 0; i < n; ++i)
    if (max < lis[i])
        max = lis[i];
   

    //free memory avoiding memory leaks
    free(lis);

    return max;


 }



int main()
{

    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Lenght of LIS is %d \n ", lis(arr, n));

    getchar();

    return 0;
}

LONGEST COMMON SUBSEQUENCE - DYNAMIC PROGRAMMING

//a dynamic approach to LCS probelm
// prints the LCS of two strings  O(mn)

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

using namespace std;


int max(int a, int b)
{
    return a > b ? a : b;
}

//evaluates length  of LCS n print it  for X[ 0 .. m-1] , Y[ 0 ... n-1 ]
void lcs(char *X, char * Y, int m, int n)
{
    int L[m + 1][n + 1];
    for (int i = 0; i <= m; ++i)
    {

        for (int j = 0; j <= n; ++j)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);

        }
      

    }

    int i = m, j = n;
    int index = L[m][n];

    //array with final LCS
    char lcs[index + 1];

    lcs[index] = '\0'; // string terminator


    while (i > 0 && j > 0)
    {
        if (X[i - 1] == Y[j - 1])
        {

            lcs[index - 1] = X[i - 1];
            --i, --j, --index;
        }


        else if (L[i - 1][j] > L[i][j - 1])
            --i;
        else
            --j;

    }

    cout << " LCS OF  " << X << " and " << Y << " is " << lcs;


}









/* Driver program to test above function */
int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int m = strlen(X);
    int n = strlen(Y);
    lcs(X, Y, m, n);
    return 0;
}

O-1 knapsack - dynamic programming

/*
    Dynamic programming approach to 0-1 knapsack problem - O(mn)
    Two cases arises for each  nd every item - include or discard - 0-1
     n This should be the f$ckin rule of life too :P

    Max value is obtained from n items is max of the  following -

    1 - max value obtained from n-1 items with W as weight
    (excluding nth item).

    2- value of nth item plus max value oobtained by n-1 items and weight as (W - weight(nth) ) item 
    (including nth item)

    If weight of nth > W then only case left is 1st , 0-1 hence

*/

#include<stdio.h>

int max(int a, int b) { return (a > b) ? a : b; };

//returns max value to be sacked in a knapsack of capacity W
int knapSack(int W,int wt[], int val[], int n)
{
    int i, w;
    int K[n + 1][W + 1];

    //build table K[][] in bottom up manner
    for (i = 0; i <= n; ++i)
    {

        for (w = 0; w <= W; ++w)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            //include
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1] ], K[i - 1][w]);
            else
                //discard
                K[i][w] = K[i - 1][w];
        }
    }

    return K[n][W];
}


int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int  W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    getchar();
    return 0;
}

Doubly Linked List using c++

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

struct _node_student;

#define CREATE_NODE  ( struct _node_student* ) malloc(sizeof(_node_student) )

using namespace std;

// a struct to represent a student in a queue as a node of a doubly linked list
struct _node_student{
    //the student number
    unsigned int _std_num = 0;
    //pointer to next student node
    _node_student* next;
    //pointer to previous student node
    _node_student* prev;

} *ptr;


//class implementing a doubly linked list for queue at the department


class Queue{
    //total students PROCESSED  in queue at any instance 
    unsigned int _ttl_stdnt_procsd;

    //pointer to front of the queue
    _node_student* front;
    //pointer to end of the queue
    _node_student* end;

public:

    //constructor
    Queue(){
        _ttl_stdnt_procsd = 0;

        //make fornt and end point eachother
        front = CREATE_NODE;
        end = CREATE_NODE;

        front->next = NULL;
        front->prev = NULL;

        end->prev = front;
        end->next = NULL;

        front->next = end;
    }

    //accessor and manipulation functions
    void  addAtHead(unsigned int _ttl_stud);
    void  addAfter(unsigned int _stud_num);
    void  addBefore(unsigned int _stud_num);
    void  removeStudent(unsigned int num);
    void display();

    //getter and setter for total student processed
    int getTtlStdProcsd(){ return _ttl_stdnt_procsd; };
    void incrmntTtlStdProcsd(){ ++_ttl_stdnt_procsd; };


};


//functions add students at the end of queue
void Queue::addAtHead(unsigned int _ttl_stud)
{
    //get the  student number of first student  to be added this time as index
    unsigned int  index = getTtlStdProcsd() + 1;

    // update total student
    _ttl_stud += getTtlStdProcsd();

    //add all students at at end of the queue
    while (index <= _ttl_stud)
    {


        //get  end  student node already in queue
        _node_student* u = CREATE_NODE;
        u = end->prev;


        //create a new student node and initialise its number
        _node_student* v = CREATE_NODE;

        //update the queue by adding student node v after u in the queue
        v->next = end;
        v->prev = u;
        v->_std_num = index;


        u->next = v;
        end->prev = v;


        ++index;

        //increment total student processed
        incrmntTtlStdProcsd();
    }


}



// test function to display the queue

void Queue::display()
{
    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->next != NULL)
    {
        cout << ptr->_std_num << " ";
        ptr = ptr->next;
    }



}


// add a student node before his/her's best  friend ;)
void Queue::addBefore(unsigned int _stud_num) {

    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->_std_num != _stud_num)
    {

        ptr = ptr->next;

    }

    _node_student* v = CREATE_NODE;
    _node_student* u = CREATE_NODE;


    u = ptr->prev;

    //add v before his friend _stud_num
    v->next = ptr;
    v->prev = ptr->prev;

    ptr->prev = v;
    u->next = v;

    incrmntTtlStdProcsd();
    v->_std_num = getTtlStdProcsd();



}


// add a student node after his/her's best  friend :P
void Queue::addAfter(unsigned int _stud_num)
{
    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->_std_num != _stud_num)
    {

        ptr = ptr->next;

    }

    _node_student* v = CREATE_NODE;
    _node_student* w = CREATE_NODE;

    w = ptr->next;

    //add v after student _stud_num
    v->next = ptr->next;
    v->prev = ptr;

    w->prev = v;
    ptr->next = v;

    incrmntTtlStdProcsd();
    v->_std_num = getTtlStdProcsd();


}


// kick out students from the queue
void Queue::removeStudent(unsigned int _stud_num)
{


    for (unsigned int i = 0; i < _stud_num; ++i)
    {
        _node_student* tmp = front;
        front = front->next;
        free(tmp);

    }


}

Bellman-Ford's single source shortest path algorithm

// program for Bellman-Ford's single source shortest path algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include<conio.h>

// a structure to represent a weighted edge in graph
struct Edge
{
    int src, dest, weight;
};

// a structure to represent a connected, directed and weighted graph
struct Graph
{
    // V-> Number of vertices, E-> Number of edges
    int V, E;

    // graph is represented as an array of edges.
    struct Edge* edge;
};

// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;

    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));

    return graph;
}

// A utility function used to print the solution
void printArr(int dist[], int n)
{
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < n; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

// The main function that finds shortest distances from src to all other
// vertices using Bellman-Ford algorithm.  The function also detects negative
// weight cycle
void BellmanFord(struct Graph* graph, int src)
{
    int V = graph->V;
    int E = graph->E;
    int dist[5];

    // Step 1: Initialize distances from src to all other vertices as INFINITE
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
    // to any other vertex can have at-most |V| - 1 edges
    for (int i = 1; i <= V - 1; i++)
    {
        for (int j = 0; j < E; j++)
        {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    // Step 3: check for negative-weight cycles.  The above step guarantees
    // shortest distances if graph doesn't contain negative weight cycle. 
    // If we get a shorter path, then there is a cycle.
    for (int i = 0; i < E; i++)
    {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] + weight < dist[v])
            printf("Graph contains negative weight cycle");
    }

    printArr(dist, V);

    return;
}

// Driver program to test above functions
int main()
{
    /* Let us create the graph given in above example */
    int V = 5;  // Number of vertices in graph
    int E = 8;  // Number of edges in graph
    struct Graph* graph = createGraph(V, E);

    // add edge 0-1 (or A-B in above figure)
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;

    // add edge 0-2 (or A-C in above figure)
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;

    // add edge 1-2 (or B-C in above figure)
    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;

    // add edge 1-3 (or B-D in above figure)
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;

    // add edge 1-4 (or A-E in above figure)
    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;

    // add edge 3-2 (or D-C in above figure)
    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;

    // add edge 3-1 (or D-B in above figure)
    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;

    // add edge 4-3 (or E-D in above figure)
    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;

    BellmanFord(graph, 0);
    getchar();
    return 0;
}

Warshall Algorithm - All pairs shortest path

//programme for floyd warshall algroithms -  all pair shortest path 
// Complexity - O(V ^ 3) where V is total vertices
#include<stdio.h>
#include<conio.h>

//number of vertices in ours graphh 
#define V 4 

/*
* Define Indefinite as large as possible to represent vertices
* not connected to eachother
*/

#define INF 99999

// a function to print solution matrix of  all pair shortest paths
void printSolution(int dist[][V]);

//solves the all- pair shortest path problem 
void floydWarshell(int graph[][V]){

//dist[][] will be the output matrix tht will  have shortest
//path 
int dist[V][V], i, j, k;

//initial solution matrix same as graph matrix
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];

for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

// Print the shortest distance matrix
printSolution(dist);








}


void printSolution(int dist[][V])
{
printf("Following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}



int main()
{
/* create the following weighted graph
     10
(0)------->(3)
|             /|\
   5   |              |1
|              | 
       \|/             |
      (1)------->(2)
     3         
 
*/
int graph[V][V] = 
{
{ 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 }
};

// Print the solution
floydWarshell(graph);
getchar();
return 0;
}

Dynamic Programming - Overlapping subprobelm paradigm

/* Dynamic programming explained using a simple Fibonacci numbers
* 1- Overlapping subproblem type 
*  Recrusive style 
*/

int fib(int n)
{
if (n <= 1)
return n;
else
return fib(n - 1) + fib(n - 2); 


}

Recursion tree for fib(5) -

Notice  that the fib(3) is being calculated two times
And many more are subproblem recalcualtion is present too .
So if we can save the result of subproblems, then the overlapped subproblems
can be solved efficiently .

Two ways -
1 - Memoization - top down
2 - Tabulationn - bottom up


//Memoizazed Fibonacci numbers evaluation 



#include<stdio.h>
#define NIL -1 
#define MAX 100 

int lookup[MAX];

// function to initialize the look up table 
void _intialize()
{
int i;
for (i = 0; i < MAX; ++i)
lookup[i] = NIL;

}



int fib(int n)
{
if (lookup[n] == NIL)
{
if (n <= 1)
lookup[n] = n; 
else
lookup[n] = fib(n - 1) + fib(n - 2); 

}

return lookup[n];


}



 //driver main function
int main()
{
int n = 40; 
_intialize();
printf("the  40th  Fibbonacci number  %d  ", fib(n)); 
getchar();
return 0; 
 

 }



Tabulated version of nth Fibbonacci numbers


int fib(int n)
{
int f[n + 1];
int i; 
f[0] = 0; 
f[1] = 1;
for (i = 2; i <= n; ++i)
f[i] = f[i - 1] + f[i - 2];

return f[n];


}











//

Bucket Sort

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; 

void bucketSort(float arr[] , int  n) ;

int main()
{
float arr[] = { 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434 };
int n = sizeof(arr)/ sizeof(arr[0]);

bucketSort(arr, n); 
cout << " sorted array is \n  ";
for (int i = 0; i < n; ++i)
{
cout << arr[i] << " "; 

}

getchar();
return 0; 


}

void bucketSort(float arr[],const int n ) { 
// make a vector of n  empty buckets
vector <float> bucket[6];

//put array elemnts in different buckets 
for (int i = 0; i < n; ++i){
int bi = n * arr[i];
bucket[bi].push_back[arr[i]];



}
//sort individual buckets
for (int i = 0; i < n; ++i)
sort(bucket[i].begin(), bucket[i].end());
int index = 0;
//concatanate all buckets into 
for (int i = 0 ; i < n ; ++i)
for (int j = 0; j < bucket[i].size(); ++j)
arr[index++] = bucket[i][j];

}