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

   
   
   

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

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


}











//