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