1.         STRASSENS MATRIX(2*2)

#include<stdio.h>

int main()

{

int a[2][2],b[2][2],c[2][2],i,j;

int m1,m2,m3,m4,m5,m6,m7;

printf("\nEnter elements of first matrix : ");

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

{

for(j=0;j<2;j++)

{

scanf("%d",&a[i][j]);

}

}

printf("\nEnter elements of second matrix : ");

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

{

for(j=0;j<2;j++)

{

scanf("%d",&b[i][j]);

}

}

printf("\nFirst Matrix is : \n");

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

{

for(j=0;j<2;j++)

{

printf("%d\t",a[i][j]);

}

}

printf("\nSecond Matrix is : \n");

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

{

for(j=0;j<2;j++)

{

printf("%d\t",b[i][j]);

}

}

m1 = (a[0][0]+a[1][1]) * (b[0][0]+b[1][1]);

m2 = (a[0][1]-a[1][1]) * (b[1][0]+b[1][1]);

m3 = (a[0][0]-a[1][0]) * (b[0][0]+b[0][1]);

m4 = (a[0][0]+a[0][1]) * (b[1][1]);

m5 = (a[1][0]+a[1][1]) * (b[0][0]);

m6 = (a[0][0]) * (b[0][1]-b[1][1]);

m7 = (a[1][1]) * (b[1][0]-b[0][0]);

c[0][0] = m1+m2-m4+m7;

c[0][1] = m4+m6;

c[1][0] = m5+m7;

c[1][1] = m1-m3-m5+m6;

printf("\nResultant Matrix after strassen multiplication is : \n");

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

{

for(j=0;j<2;j++)

{

printf("%d\t",c[i][j]);

}

}

return 0;

}

2.         STRASSENS MATRIX(N*N)

#include <stdio.h>

void main()

{

int i,j,k,m,n,n1,n2,n3,n4,o=0;

/*Input first matrix*/

printf("\nEnter the order of 1st Matrix:");

scanf("%d%d",&n1,&n2);

int A[n1][n2];

for(i=0;i<n1;i++){

printf("Enter the elements of the %d-th row:",i+1);

for(j=0;j<n2;j++)

scanf(" %d",&A[i][j]);

}

/*Input second matrix*/

printf("\n\nEnter the order of 2nd Matrix:");

scanf("%d%d",&n3,&n4);

int B[n3][n4];

for(i=0;i<n3;i++){

printf("Enter the elements of the %d-th row:",i+1);

for(j=0;j<n4;j++)

scanf(" %d",&B[i][j]);

}

/*Creating square matrix of order 2^n for all and initializing all elements to 0 except

prefixed*/

n4=n1>n2?n1:n2;

n=n3>n4?n3:n4;

while(n>(m=power(2,++o)));

int a[m][m],b[m][m],C[m][m];

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

for(j=0;j<m;j++){

a[i][j]=0;

b[i][j]=0;

}

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

for(j=0;j<n2;j++)

a[i][j]=A[i][j];

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

for(j=0;j<n3;j++)

b[i][j]=B[i][j];

/*Printing first matrix*/

printf("\nThe first matrix is :");

for(i=0;i<n1;i++){

printf("\n\n\n");

for(j=0;j<n2;j++)

printf("\t%d",a[i][j]);

}

/*Printing second matrix*/

printf("\n\n\nThe second matrix is :");

for(i=0;i<n2;i++){

printf("\n\n\n");

for(j=0;j<n3;j++)

printf("\t%d",b[i][j]);

}

strassen(a,b,C,m); //Calling the function.

/*Printing the final matrix*/

printf("\n\n\nThe final matrix is :");

for(i=0;i<n1;i++){

printf("\n\n\n");

for(j=0;j<n3;j++)

printf("\t%d",C[i][j]);

}

}

int power(int base, int exp){

int i=0, p=1;

while(++i<exp+1 && 1*(p*=base));

return p;

}

void add(int* A, int* B, int* C, int n, int x){

int i,j, m=x>0?n/2:n;

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

for (j=0;j<m;j++)

*(C+i*m+j) = *(A+i*n+j) + *(B+i*n+j);

}

void sub(int* A, int* B, int* C, int n, int x){

int i,j, m=x>0?n/2:n;

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

for (j=0;j<m;j++)

*(C+i*m+j) = *(A+i*n+j) - *(B+i*n+j);

}

void strassen(int* A, int* B, int* C, int n){

int i,j;

if(n==2){

int P=(*A+*(A+n+1))*(*B+*(B+n+1)); //P=(A[0][0]+A[1][1])*(B[0][0]+B[1][1])

int Q=(*(A+n)+*(A+n+1))*(*B); //Q=(A[1][0]+A[1][1])*B[0][0]

int R=(*A)*(*(B+1)-*(B+n+1)); //R=A[0][0]*(B[0][1]-B[1][1])

int S=(*(A+n+1))*(*(B+n)-*B); //S=A[1][1]*(B[1][0]-B[0][0])

int T=(*A+*(A+1))*(*(B+n+1)); //T=(A[0][0]+A[0][1])*B[1][1]

int U=(*(A+n)-*A)*(*B+*(B+1)); //U=(A[1][0]-A[0][0])*(B[0][0]+B[0][1])

int V=(*(A+1)-*(A+n+1))*(*(B+n)+*(B+n+1)); //V=(A[0][1]-A[1][1])*(B[1][0]+B[1][1])

*         C=P+S-T+V;

*(C+1)=R+T;

*(C+n)=Q+S;

*(C+n+1)=P+R-Q+U;

}

else{

int m=n/2, x[m][m], y[m][m], o[n][n];

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

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

o[i][j]=0;

/*P=(A[0][0]+A[1][1])*(B[0][0]+B[1][1])*/

int P[m][m];

add(A, A+m*(n+1), x, n, 1);

add(B, B+m*(n+1), y, n, 1);

strassen(x, y, P, m);

/*Q=(A[1][0]+A[1][1])*B[0][0]*/

int Q[m][m];

add(A+m*n, A+m*(n+1), x, n, 1);

add(B, o, y, n, 1);

strassen(x, y, Q, m);

/*R=A[0][0]*(B[0][1]-B[1][1])*/

int R[m][m];

add(A, o, x, n, 1);

sub(B+m, B+m*(n+1), y, n, 1);

strassen(x, y, R, m);

/*S=A[1][1]*(B[1][0]-B[0][0])*/

int S[m][m];

add(A+m*(n+1), o, x, n, 1);

sub(B+m*n, B, y, n, 1);

strassen(x, y, S, m);

/*T=(A[0][0]+A[0][1])*B[1][1]*/

int T[m][m];

add(A, A+m, x, n, 1);

add(B+m*(n+1), o, y, n, 1);

strassen(x, y, T, m);

/*U=(A[1][0]-A[0][0])*(B[0][0]+B[0][1])*/

int U[m][m];

sub(A+m*n, A, x, n, 1);

add(B, B+m, y, n, 1);

strassen(x, y, U, m);

/*V=(A[0][1]-A[1][1])*(B[1][0]+B[1][1])*/

int V[m][m];

sub(A+m, A+m*(n+1), x, n, 1);

add(B+m*n, B+m*(n+1), y, n, 1);

strassen(x, y, V, m);

/*Calculating the 4 parts for the result matrix*/

int W[m][m], X[m][m], Y[m][m], Z[m][m];

sub(V,T,x,m,0);

add(S,x,y,m,0);

add(P,y,W,m,0); // W=P+S-T+V

add(R,T,X,m,0); // X==R+T

add(Q,S,Y,m,0); // Y=Q+S

sub(U,Q,x,m,0);

add(R,x,y,m,0);

add(P,y,Z,m,0); // Z=P+R-Q+U

/*Conquering 4 parts in the result matrix*/

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

for (j=0;j<m;j++){

*(C+i*n+j) = W[i][j]; //C[0][0]=W

*(C+i*n+j+m) = X[i][j]; //C[0][1]=X

*(C+(i+m)*n+j) = Y[i][j]; //C[1][0]=Y

*(C+(i+m)*n+j+m) = Z[i][j]; //C[1][1]=Z

}

}

}

3. KARATSUBA

#include <stdio.h>

#include <math.h>

// Get size of the numbers

int getSizeOfNumber(long num)

{

int count = 0;

while (num > 0)

{

count++;

num /= 10;

}

return count;

}

long karatsuba(long firstNumber, long secondNumber)

{

// Base Case

if (firstNumber < 10 || secondNumber < 10)

return firstNumber * secondNumber;

// determine the size of X and Y

int size = fmax(getSizeOfNumber(firstNumber), getSizeOfNumber(secondNumber));

// Split X and Y

int n = (int)ceil(size / 2.0);

long p = (long)pow(10, n);

long a = (long)floor(firstNumber / (double)p);

long b = firstNumber % p;

long c = (long)floor(secondNumber / (double)p);

long d = secondNumber % p;

// Recur until base case

long ac = karatsuba(a, c);

long bd = karatsuba(b, d);

long e = karatsuba(a + b, c + d) - ac - bd;

// return the equation

return (long)(pow(10 * 1L, 2 * n) * ac + pow(10 * 1L, n) * e + bd);

}

int main()

{

long int num1,num2;

printf("karatsuba's Fast multiplication execution : \n ");

printf("Enter the first number : ");

scanf("%ld",&num1);

printf("Enter the second number : ");

scanf("%ld",&num2);

printf("The result of multiplication : %ld",karatsuba(num1,num2));

return 0;

}

4. GRAPH COLORING

#include<stdio.h>

int G[10][10],m,edges,color_tab[10],v1,v2,i,j,n,a,b;

void Gen_Col_Value(int,int);

void Gr_coloring(int,int);

int main()

{

printf("\nEnter the number of nodes & edges\n");

scanf("%d%d",&n,&edges);

m=n-1;

printf("\nEnter the edges of the graph\n\n");

for (i=1;i<=edges; i++)

{

printf("Enter value of x,y\n");

scanf("%d%d",&v1,&v2);

G[v1][v2] = G[v2][v1] = 1;

printf("\n");

}

Gr_coloring(1,n);

printf("\n The Vertices To be Colored As...\n");

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

printf("\n V%d:=%d",i,color_tab[i]);

return 0;

}

void Gen_Col_Value(int k,int n)

{

while(1)

{

a=color_tab[k]+1;

b=m+1;

color_tab[k] = a%b;

if(color_tab[k]==0) return;

for(j=1;j<=n;j++)

{

if(G[k][j] && color_tab[k]==color_tab[j])

break;

}

if(j==n+1) return;

}

}

void Gr_coloring(int k,int n)

{

Gen_Col_Value(k,n);

if(color_tab[k]==0) return;

if(k==n)  return;

else Gr_coloring(k+1,n);

}

5. JOB SEQUENCING

//write a c program to implement  job sequencing with deadline take input from user

#include<stdio.h>

#define MAX 100

int main()

{

int n,i;

int Deadline[MAX], Profit[MAX];

printf("Enter the number of jobs: ");

scanf("%d", &n);

printf("\nEnter the deadlines and profits of each job:\n");

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

{

printf("Job %d: ", i+1);

scanf("%d %d", &Deadline[i], &Profit[i]);

}

int maxProfit = 0;

int maxDeadline = 0;

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

{

if (Deadline[i] > maxDeadline)

maxDeadline = Deadline[i];

}

int slot[maxDeadline];

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

slot[i] = -1;

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

{

int j = Deadline[i] - 1;

while (j >= 0)

{

if (slot[j] == -1)

{

slot[j] = i;

maxProfit += Profit[i];

break;

}

j--;

}

}

printf("\nThe maximum profit is: %d\n", maxProfit);

printf("\nThe sequence of jobs are: ");

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

{

if (slot[i] != -1)

printf("%d ", slot[i]+1);

}

printf("\n");

return 0;

}

6. Matrix Chain Multiplication

#include<stdio.h>

#include<limits.h>

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n

int MatrixChainMultiplication(int p[], int n)

{

int m[n][n];

int i, j, k, L, q;

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

m[i][i] = 0; //number of multiplications are 0(zero) when there is only

one matrix

//Here L is chain length. It varies from length 2 to length n.

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

{

for (i=1; i<n-L+1; i++)

{

j = i+L-1;

m[i][j] = INT_MAX; //assigning to maximum value

for (k=i; k<=j-1; k++)

{

q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if (q < m[i][j])

{

m[i][j] = q; //if number of multiplications found less that number

will be updated.

}

}

}

}

return m[1][n-1]; //returning the final answer which is M[1][n]

}

int main()

{

int n,i;

printf("Enter number of matrices\n");

scanf("%d",&n);

n++;

int arr[n];

printf("Enter dimensions \n");

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

{

printf("Enter d%d : ",i);

scanf("%d",&arr[i]);

}

int size = sizeof(arr)/sizeof(arr[0]);

printf("Minimum number of multiplications is %d ",

MatrixChainMultiplication(arr, size));

return 0;

}

7. longest common subsequence

#include <stdio.h>

#include <string.h>

int i, j, m, n, LCS_table[20][20];

char S1[20] = "ACGTTCGA", S2[20] = "BCTBBCA", b[20][20];

void lcsAlgo() {

m = strlen(S1);

n = strlen(S2);

// Filling 0's in the matrix

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

LCS_table[i][0] = 0;

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

LCS_table[0][i] = 0;

// Building the mtrix in bottom-up way

for (i = 1; i <= m; i++)

for (j = 1; j <= n; j++) {

if (S1[i - 1] == S2[j - 1]) {

LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1;

} else if (LCS_table[i - 1][j] >= LCS_table[i][j - 1]) {

LCS_table[i][j] = LCS_table[i - 1][j];

} else {

LCS_table[i][j] = LCS_table[i][j - 1];

}

}

int index = LCS_table[m][n];

char lcsAlgo[index + 1];

lcsAlgo[index] = '\0';

int i = m, j = n;

while (i > 0 && j > 0) {

if (S1[i - 1] == S2[j - 1]) {

lcsAlgo[index - 1] = S1[i - 1];

i--;

j--;

index--;

}

else if (LCS_table[i - 1][j] > LCS_table[i][j - 1])

i--;

else

j--;

}

// Printing the sub sequences

printf("S1 : %s \nS2 : %s \n", S1, S2);

printf("LCS: %s", lcsAlgo);

}

int main() {

printf("Name : Harsha Dulhani\n");

printf("Register NO : 22MCB0012\n");

lcsAlgo();

printf("\n");

}

8. N-QUEENS PROBLEM

#include <stdio.h>

#include <stdbool.h>

int board[10][10], n;

/*A utility function to check if a queen can be placed on board[row][col]*/

bool isSafe(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;

}

/* A recursive utility function to solve N Queen problem */

bool solveNQUtil(int col){

if(col == n){

return true;

}

int i;

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

if(isSafe(i, col)){

board[i][col] = 1;

if(solveNQUtil(col+1))

return true;

board[i][col] = 0;

}

}

return false;

}

/* This function solves the N Queen problem using Backtracking. It mainly uses solveNQUtil() to solve the problem. It returns false if queens cannot be placed, otherwise return true and prints placement of queens in the form of 1s. Please note that there may be more than one solutions, this function prints one  of the feasible solutions.*/

bool solveNQ(){

if(solveNQUtil(0) == false){

printf("Solution does not exist");

return false;

}

int i, j;

printf("\nSolution:\n");

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

for(j=0; j<n; j++){

printf("%d\t", board[i][j]);

}

printf("\n");

}

return true;

}

int main(){

printf("\nEnter the number of Queens: ");

scanf("%d", &n);

solveNQ();

return 0;

}

9. SUM OF SUBSET

#include <stdio.h>

#include <stdlib.h>

int x[20],w[20],d,count=0;

void subset(int cs,int k,int r)

{

int i;

x[k]=1;

if(cs+w[k]==d)

{

printf("\nSubset %d\n",++count);

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

if(x[i]==1)

printf("%d\t",w[i]);

}

else if(cs+w[k]+w[k+1]<=d)

subset(cs+w[k],k+1,r-w[k]);

if((cs+r-w[k]>=d)&&(cs+w[k+1]<=d))

{

x[k]=0;

subset(cs,k+1,r-w[k]);

}

}

int main()

{

int i,n,sum=0;

printf("Enter the no. of elements:");

scanf("%d",&n);

printf("\nEnter the elements in ascending order:\n");

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

{

scanf("%d",&w[i]);

sum+=w[i];

}

printf("\nEnter the sum value to obtain:");

scanf("%d",&d);

if(sum<d)

{

printf("No subset possible");

exit(0);

}

subset(0,0,sum);

if(count==0)

printf("\nNo subset possible");

return 0;

}

10. FORD FULKERSON

#include <stdio.h>

#define A 0

#define B 1

#define C 2

#define MAX_NODES 1000

#define O 1000000000

int n;

int e;

int capacity[MAX_NODES][MAX_NODES];

int flow[MAX_NODES][MAX_NODES];

int color[MAX_NODES];

int pred[MAX_NODES];

int min(int x, int y) {

return x < y ? x : y;

}

int head, tail;

int q[MAX_NODES + 2];

void enqueue(int x) {

q[tail] = x;

tail++;

color[x] = B;

}

int dequeue() {

int x = q[head];

head++;

color[x] = C;

return x;

}

// Using BFS as a searching algorithm

int bfs(int start, int target) {

int u, v;

for (u = 0; u < n; u++) {

color[u] = A;

}

head = tail = 0;

enqueue(start);

pred[start] = -1;

while (head != tail) {

u = dequeue();

for (v = 0; v < n; v++) {

if (color[v] == A && capacity[u][v] - flow[u][v] > 0) {

enqueue(v);

pred[v] = u;

}

}

}

return color[target] == C;

}

// Applying fordfulkerson algorithm

int fordFulkerson(int source, int sink) {

int i, j, u;

int max_flow = 0;

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

for (j = 0; j < n; j++) {

flow[i][j] = 0;

}

}

// Updating the residual values of edges

while (bfs(source, sink)) {

int increment = O;

for (u = n - 1; pred[u] >= 0; u = pred[u]) {

increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]);

}

for (u = n - 1; pred[u] >= 0; u = pred[u]) {

flow[pred[u]][u] += increment;

flow[u][pred[u]] -= increment;

}

// Adding the path flows

max_flow += increment;

}

return max_flow;

}

int main() {

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

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

capacity[i][j] = 0;

}

}

n = 6;

e = 7;

capacity[0][1] = 8;

capacity[0][4] = 3;

capacity[1][2] = 9;

capacity[2][4] = 7;

capacity[2][5] = 2;

capacity[3][5] = 5;

capacity[4][2] = 7;

capacity[4][3] = 4;

int s = 0, t = 5;

printf("Max Flow: %d\n", fordFulkerson(s, t));

}

11. EDMOND KARP

#include<cstdio>

#include<cstdio>

#include<queue>

#include<cstring>

#include<vector>

#include<iostream>

#include<conio.h>

using namespace std;

int capacities[10][10];

int flowPassed[10][10];

vector<int> graph[10];

int parentsList[10];

int currentPathCapacity[10];

int bfs(int startNode, int endNode)

{

memset(parentsList, -1, sizeof(parentsList));

memset(currentPathCapacity, 0, sizeof(currentPathCapacity));

queue<int> q;

q.push(startNode);

parentsList[startNode] = -2;

currentPathCapacity[startNode] = 999;

while(!q.empty())

{

int currentNode = q.front();

q.pop();

for(int i=0; i<graph[currentNode].size(); i++)

{

int to = graph[currentNode][i];

if(parentsList[to] == -1)

{

if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)

{

parentsList[to] = currentNode;

currentPathCapacity[to] = min(currentPathCapacity[currentNode],

capacities[currentNode][to] - flowPassed[currentNode][to]);

if(to == endNode)

{

return currentPathCapacity[endNode];

}

q.push(to);

}

}

}

}

return 0;

}

int edmondsKarp(int startNode, int endNode)

{

int maxFlow = 0;

while(true)

{

int flow = bfs(startNode, endNode);

if (flow == 0)

{

break;

}

maxFlow += flow;

int currentNode = endNode;

while(currentNode != startNode)

{

int previousNode = parentsList[currentNode];

flowPassed[previousNode][currentNode] += flow;

flowPassed[currentNode][previousNode] -= flow;

currentNode = previousNode;

}

}

return maxFlow;

}

int main(){

int nodesCount, edgesCount;

cout<<"enter the number of nodes and edges\n";

cin>>nodesCount>>edgesCount;

int source, sink;

cout<<"enter the source and sink\n";

cin>>source>>sink;

for(int edge = 0; edge < edgesCount; edge++)

{

cout<<"enter the start and end vertex alongwith capacity\n";

int from, to, capacity;

cin>>from>>to>>capacity;

capacities[from][to] = capacity;

graph[from].push_back(to);

graph[to].push_back(from);

}

int maxFlow = edmondsKarp(source, sink);

cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl;

}

12. PUSH RELABEL

#include <bits/stdc++.h>

using namespace std;

struct Edge

{

int flow;

int capacity;

int u, v;

Edge(int flow, int capacity, int u, int v)

{

this->flow = flow;

this->capacity = capacity;

this->u = u;

this->v = v;

}

};

struct Vertex

{

int height, e_flow;

Vertex(int height, int e_flow)

{

this->height = height;

this->e_flow = e_flow;

}

};

// To represent a flow network

class Graph

{

int V;

vector<Vertex> vertex;

vector<Edge> edge;

bool push(int u);

void relabel(int u);

void preflow(int source);

void ReverseEdgeFlowUpdate(int i, int flow);

public:

Graph(int V);

void addEdge(int u, int v, int w);

int getMaximumFlow(int source, int sink);

};

Graph::Graph(int V)

{

this->V = V;

for (int i = 0; i < V; i++)

vertex.push_back(Vertex(0, 0));

}

// To push flow from overflowing Vertex u

bool Graph::push(int u)

{

for (int i=0; i <edge.size(); i++)

{

if (edge[i].u == u)

{

if (edge[i].flow == edge[i].capacity)

continue;

if (vertex[u].height > vertex[edge[i].v].height)

{

int flow = min(edge[i].capacity - edge[i].flow,

vertex[u].e_flow);

vertex[u].e_flow = vertex[u].e_flow-flow;

vertex[edge[i].v].e_flow = vertex[edge[i].v].e_flow + flow;

edge[i].flow = edge[i].flow + flow;

ReverseEdgeFlowUpdate(i, flow);

return true;

}

}

}

return false;

}

// function to Relabel vertex u

void Graph::relabel(int u)

{

int maximum_height = INT_MAX;

int n=edge.size();

// To Find the adjacent with minimum height

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

{

if (edge[i].u == u)

{

if (edge[i].flow == edge[i].capacity)

continue;

// for Updating the minimum height

if (vertex[edge[i].v].height < maximum_height)

{

maximum_height = vertex[edge[i].v].height;

// updating the height of u

vertex[u].height = maximum_height + 1;

}

}

}

}

void Graph::preflow(int source)

{

vertex[source].height = vertex.size();

int n=edge.size();

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

{

if (edge[i].u == source)

{

edge[i].flow = edge[i].capacity;

// Initialize excess flow for adjacent v

vertex[edge[i].v].e_flow = vertex[edge[i].v].e_flow + edge[i].flow;

edge.push_back(Edge(-edge[i].flow, 0, edge[i].v, source));

}

}

}

void Graph::addEdge(int u, int v, int capacity)

{

edge.push_back(Edge(0, capacity, u, v));

}

// To Update reverse flow for flow added on ith Edge

void Graph::ReverseEdgeFlowUpdate(int i, int flow)

{

int u = edge[i].v;

int v = edge[i].u;

int j=0, n=edge.size();

while (j < n)

{

if (edge[j].v == v && edge[j].u == u)

{

edge[j].flow -= flow;

return;

}

j++;

}

// adding the reverse Edge in the residual graph

Edge e = Edge(0, flow, u, v);

edge.push_back(e);

}

//Function to return an index of overflowing Vertex

int overFlowVertex(vector<Vertex>& vertex)

{

int n=vertex.size();

for (int i = 1; i < n - 1; i++)

if (vertex[i].e_flow > 0)

return i;

return -1;

}

// The main function is to print the maximum flow of the graph

int Graph::getMaximumFlow(int source, int sink)

{

preflow(source);

while (overFlowVertex(vertex) != -1)

{

int u = overFlowVertex(vertex);

if (!push(u))

relabel(u);

}

return vertex.back().e_flow;

}

// Driver Code

int main()

{

int V;

cout << "\nEnter the number of vertices : ";

cin >> V;

Graph g(V);

int E;

cout << "\nEnter the number of edges : ";

cin >> E;

int a,b,c;

cout << "\nEnter edges like.....vertex1[space]vertex2[space]weight :";

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

cin >> a >> b >> c;

g.addEdge(a,b,c);

}

int source;

int sink;

cout << "\nEnter source and destination : ";

cin >> source >> sink;

cout << "\nMaximum flow is " << g.getMaximumFlow(source, sink);

return 0;

}

13. RELABEL TO FRONT

14. CYCLE CANCELLATION

#include <iostream>

#include <list>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <string>

#include <sstream>

#include <queue>

#define int_max 100000

using namespace std;

// An edge is represented as a struct

// Fields:

// destination - denotes the ending node of an edge. For example, 'v' in u--

>v

// capacity - the maximum capacity of an edge

// residualFlow - the residual amount of flow that can flow through the edge

// counterEdge - a pointer to the counter edge in residual graph for

performance optimization

struct Edge{

int destination;

int capacity;

int residualFlow;

int cost;

Edge* counterEdge;

};

// A graph is represented as a struct

// Fields:

// numVertices - denotes the number of vertices in the graph

// adj - Adjacency list : Collection of unordered lists one for each vertex

struct Graph{

int numVertices;

vector<Edge*> *adj;

};

Graph g;

Graph resGraph;

// Generates a new edge (allocating space dynamically) and returns a pointed to

the edge

Edge* genEdge(int destination, int capacity, int residualFlow, int cost){

Edge* e1 = new Edge;

e1->destination = destination;

e1->capacity = capacity;

e1->residualFlow = residualFlow;

e1->cost = cost;

return e1;

}

// Prints all the edges in the graph

// Output:

// List of edges where each edge is represented by

// u(start node) v(end node) flow capacity

int printGraph(Graph g){

for(int i=0; i<g.numVertices; i++){

for(int j=0; j<g.adj[i].size(); j++){

cout << i+1 << " " << g.adj[i][j]->destination+1 << " " << (g.adj[i][j]-

>capacity - g.adj[i][j]->residualFlow) << " " << g.adj[i][j]->cost << endl;

}

}

return 0;

}

void printParams(int parentVertex[], int distance[]){

cout << "Parents Vertex:\n";

for(int i=0; i<g.numVertices; i++){

cout << parentVertex[i] << " ";

}

cout << endl;

cout << "Distance Vertex:\n";

for(int i=0; i<g.numVertices; i++){

cout << distance[i] << " ";

}

cout << endl;

}

// Detects the presence of negative cycles in graph

// Output:

// -1 if no negative cycles present

// node_num index of a node in negative cycle

// Lists parentVertex and parentEdge are updated and can be used to reconstruct

the negative cycle

int BFCycleDetection(Graph resGraph, int source, int parentVertex[], Edge*

parentEdge[]){

// Initialize variables that will be needed

int cycle_node = -1;

int numVertices = resGraph.numVertices;

vector<Edge*> *adj = resGraph.adj;

int distance[numVertices];

// Initialize visited, parentVertex and distance

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

parentVertex[i] = -1;

distance[i] = INT_MAX;

}

// BF - Relax edges repeatedly

distance[source] = 0;

for(int i=0; i<numVertices-1; i++){

// loop on all edges

for(int u=0; u<numVertices; u++){

for(int e=0; e<adj[u].size(); e++){

if(adj[u][e]->residualFlow > 0){

int v = adj[u][e]->destination;

int w = adj[u][e]->cost;

if(distance[v]>distance[u]+w){

distance[v] = distance[u]+w;

parentVertex[v] = u;

parentEdge[v] = adj[u][e];

}

}

}

}

}

// Check for negative weight cycle - loop on all edges

for(int u=0; u<numVertices; u++){

for(int e=0; e<adj[u].size(); e++){

if(adj[u][e]->residualFlow > 0){

int v = adj[u][e]->destination;

int w = adj[u][e]->cost;

if(distance[v]>distance[u]+w){

return v; // Negative cycle detected!

}

}

}

}

return cycle_node;

}

// Cancels all negative cycles

// Output:

// costSaved amount of cost saved by cycle detection and cancellation

int cancelNegativeCycles(Graph resGraph){

int costSaved=0, cyclePossible=1, u, v;

Edge *te1, *te2;

int numVertices = resGraph.numVertices;

while(cyclePossible){

cyclePossible=0;

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

int parent[g.numVertices];

Edge* parentEdge[g.numVertices];

int node_num = BFCycleDetection(resGraph, i, parent, parentEdge);

if(node_num!=-1){ // A cycle is detected

cyclePossible=1;

// Calculate path flow

int path_flow = INT_MAX;

v=node_num; u = parent[v]; te1 = parentEdge[v];

path_flow = min(path_flow, te1->residualFlow);

for (v=u; v!=node_num; v=parent[v]){

u = parent[v];

te1 = parentEdge[v];

path_flow = min(path_flow, te1->residualFlow);

}

// Update graph by removing the cycle

v=node_num; u = parent[v];

te1 = parentEdge[v];

te2 = te1->counterEdge;

te1->residualFlow -= path_flow;

te2->residualFlow += path_flow;

costSaved += path_flow*(te1->cost);

for (v=u; v != node_num; v=parent[v]){

u = parent[v];

te1 = parentEdge[v];

te2 = te1->counterEdge;

te1->residualFlow -= path_flow;

te2->residualFlow += path_flow;

costSaved += path_flow*(te1->cost);

}

}

}

}

return -1*costSaved;

}

// Finds the shortest path from source to sink

// Output:

// 0 if no path exists from source to sink

// 1 if there is a path from source to sink

// Lists parentVertex and parentEdge are updated and can be used to reconstruct

the shortest path

bool BF(Graph resGraph, int source, int sink, int parentVertex[], Edge*

parentEdge[]){

// Initialize variables that will be needed

int numVertices = resGraph.numVertices;

vector<Edge*> *adj = resGraph.adj;

int distance[numVertices];

// Initialize visited, parentVertex and distance

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

parentVertex[i] = -1;

distance[i] = INT_MAX;

}

// printParams(parentVertex, distance);

// BF

distance[source] = 0;

for(int i=0; i<numVertices-1; i++){

// loop on all edges

for(int u=0; u<numVertices; u++){

for(int e=0; e<adj[u].size(); e++){

if(adj[u][e]->residualFlow > 0){

int v = adj[u][e]->destination;

int w = adj[u][e]->cost;

if(distance[v]>distance[u]+w){

distance[v] = distance[u]+w;

parentVertex[v] = u;

parentEdge[v] = adj[u][e];

}

}

}

}

// printParams(parentVertex, distance);

}

if(parentVertex[sink] == -1){

return false;

}else{

return true;

}

}

// Calculates the cost of flow 'requiredFlow' from 's' to 't'

// Returns 'INT_MAX' if such a flow is not possible

int calcMinCostFlow(int s, int t, int requiredFlow){

int u, v, currFlow=0, runningCost=0;

Edge *te1, *te2;

// Detect negative cycles and remove

int benifit = cancelNegativeCycles(resGraph);

if(benifit){

cout << "Negative cycle detected and removed. Resulting cost benifit is "

<< benifit << endl;

}

// Run shortest path augmentation

int parent[g.numVertices];

Edge* parentEdge[g.numVertices];

while (BF(resGraph, s, t, parent, parentEdge)){

int path_flow = INT_MAX;

for (v=t; v!=s; v=parent[v]){

u = parent[v];

te1 = parentEdge[v];

path_flow = min(path_flow, te1->residualFlow);

}

path_flow = min(path_flow, requiredFlow-currFlow);

for (v=t; v != s; v=parent[v]){

u = parent[v];

te1 = parentEdge[v];

te2 = te1->counterEdge;

te1->residualFlow -= path_flow;

te2->residualFlow += path_flow;

runningCost += path_flow*(te1->cost);

}

currFlow += path_flow;

if(currFlow == requiredFlow){

break;

}

}

if(currFlow == requiredFlow){

return runningCost;

}else{

return INT_MAX;

}

}

int main(){

cout<<"******Name : Harsha Dulhani******"<<endl;

cout<<"******Register No : 22MCB0012******"<<endl;

int numVertices, numEdges, source, destination, flow;

int tu, tv, tcap, tcost, tflow;

// Scan the graph and question configurations

cout<<"Enter No of Vertices, No .of Edges, Possible Flow, Source,

Destination respectively"<<endl;

cin >> numVertices >> numEdges;

cin >> flow;

cin >> source >> destination;

source--; destination--; // as indexing starts from 0

// Initialize the graphs

g.numVertices = numVertices;

g.adj = new vector<Edge*>[numVertices];

resGraph.numVertices = numVertices;

resGraph.adj = new vector<Edge*>[numVertices];

cout<<"Edge data"<<endl;

cout<<"Enter u, v, Capacity, Cost, Edge_flow respectively"<<endl;

// Input graph parameters

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

cin >> tu >> tv >> tcap >> tcost >> tflow;

cout<<"Edge from "<<tu <<" to "<<tv<<" Data completed"<<endl<<endl;

tu--; tv--; // as indexing starts from 0

// Add edge to graph and edge and counter-edge to residual graph

Edge* tmpEdge1 = genEdge(tv, tcap, tcap-tflow, tcost);

Edge* tmpEdge2 = genEdge(tu, tcap, tflow, -1*tcost);

tmpEdge1->counterEdge = tmpEdge2;

tmpEdge2->counterEdge = tmpEdge1;

g.adj[tu].push_back(tmpEdge1);

resGraph.adj[tu].push_back(tmpEdge1);

resGraph.adj[tv].push_back(tmpEdge2);

}

// Print initial state of graph

cout << "Initial Graph:\n";

printGraph(g);

//cout << "hello\n";

// Run min-cost flow algorithm

int mincost = calcMinCostFlow(source, destination, flow);

// Print final state of graph

if(mincost == INT_MAX){

// cout << "The given flow is not possible!\n";

}else{

cout << "The minimum cost for the additional flow is " << mincost <<

endl;

cout << "Final Graph:\n";

printGraph(g);

}

return 0;

}

Naive string matching

#include <stdio.h>

#include <string.h>

int naive_string_match(char text[], char pattern[]) {

int text_len = strlen(text);

int pattern_len = strlen(pattern);

for (int i = 0; i <= text_len - pattern_len; i++) {

int j;

for (j = 0; j < pattern_len; j++) {

if (text[i + j] != pattern[j]) {

break;

}

}

if (j == pattern_len) {

return i;

}

}

return -1;

}

int main() {

char text[] = "abcdeabcdeabcde";

char pattern[] = "abcde";

int position = naive_string_match(text, pattern);

if (position != -1) {

printf("Pattern found at position %d\n", position);

} else {

printf("Pattern not found\n");

}

return 0;

}

kmp string matching

#include <stdio.h>

#include <string.h>

void compute_lps(char pattern[], int m, int lps[]) {

int len = 0;

lps[0] = 0;

int i = 1;

while (i < m) {

if (pattern[i] == pattern[len]) {

len++;

lps[i] = len;

i++;

} else {

if (len != 0) {

len = lps[len - 1];

} else {

lps[i] = 0;

i++;

}

}

}

}

int kmp_string_match(char text[], char pattern[]) {

int n = strlen(text);

int m = strlen(pattern);

int lps[m];

compute_lps(pattern, m, lps);

int i = 0, j = 0;

while (i < n) {

if (pattern[j] == text[i]) {

i++;

j++;

}

if (j == m) {

return i - j;

} else if (i < n && pattern[j] != text[i]) {

if (j != 0) {

j = lps[j - 1];

} else {

i = i + 1;

}

}

}

return -1;

}

int main() {

char text[] = "abcdeabcdeabcde";

char pattern[] = "abcde";

int position = kmp_string_match(text, pattern);

if (position != -1) {

printf("Pattern found at position %d\n", position);

} else {

printf("Pattern not found\n");

}

return 0;

}

rabin KARP

#include <stdio.h>

#include <string.h>

#include <math.h>

#define d 256

void rabin_karp(char text[], char pattern[], int q) {

int n = strlen(text);

int m = strlen(pattern);

int p = 0;

int t = 0;

int h = 1;

int j;

int flag = 0;

for (int i = 0; i < m - 1; i++) {

h = (h * d) % q;

}

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

p = (d * p + pattern[i]) % q;

t = (d * t + text[i]) % q;

}

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

if (p == t) {

for (j = 0; j < m; j++) {

if (text[i + j] != pattern[j]) {

break;

}

}

if (j == m) {

flag = 1;

printf("Pattern found at index %d\n", i);

}

}

if (i < n - m) {

t = (d * (t - text[i] * h) + text[i + m]) % q;

if (t < 0) {

t = t + q;

}

}

}

if(!flag)

printf("Pattern not found\n");

}

int main() {

char text[] = "abcdeabcdeabcde";

char pattern[] = "abcde";

int q = 101;

rabin_karp(text, pattern, q);

return 0;

}