BRANCH AND BOUND : C CODE for JOB ASSIGNMENT PROBLEM

C code to solve JOB ASSIGNMENT problem using Branch and Bound.

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#define MAX_JOBS 10

int costMatrix[MAX_JOBS][MAX_JOBS];

int numJobs;

int minCost = INT_MAX;

int bestAssignment[MAX_JOBS];

void branchAndBound(int assignment[MAX_JOBS], int numAssigned, int costSoFar)

{

 if (numAssigned == numJobs) {

 // All jobs have been assigned, so update the best assignment if the current cost is lower

 if (costSoFar < minCost) {

 minCost = costSoFar;

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

 bestAssignment[i] = assignment[i];

 }

 }

 } else {

 // Assign the next job to each available worker and branch on the resulting cost

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

 if (assignment[i] == -1) {

 // This job has not been assigned yet

 int newAssignment[MAX_JOBS];

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

 newAssignment[j] = assignment[j];

 }

 newAssignment[i] = numAssigned;

 int newCost = costSoFar + costMatrix[numAssigned][i];

 if (newCost < minCost) {

 // Only explore this branch if it could potentially lead to a better solution

 branchAndBound(newAssignment, numAssigned + 1, newCost);

 }

 }

 }

 }

}

int main()

{

 // Read input from file or user input

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

 scanf("%d", &numJobs);

 printf("Enter the cost matrix:\n");

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

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

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

 }

 }

 // Initialize the assignment to all unassigned

 int assignment[MAX_JOBS];

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

 assignment[i] = -1;

 }

 // Solve the problem using branch and bound

 branchAndBound(assignment, 0, 0);

 // Print the best assignment and its cost

 printf("Best assignment: ");

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

 printf("(%d, %d) ", bestAssignment[i], i);

 }

 printf("\nCost: %d\n", minCost);

 return 0;

}

GRAPH ALGORITHMS : C PROGRAM for FORD-FULKERSON maximum flow ALGORITHM with User Input

 FORD-FULKERSON maximum flow ALGORITHM with User Input

 #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,top;

int q[MAX_NODES + 2];

int path[MAX_NODES];

void enqueue(int x) {

q[tail] = x;

tail++;

color[x] = B;

}

int dequeue() {

int x = q[head];

head++;

color[x] = C;

return x;

}

void push(int x){

path[top]=x;

top++;

}

int pop(){

int output = path[top];

top--;

return output;

}

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

}

void residual_graph(){

int i,j;

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

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

if(capacity[i][j]!=0){

printf("\n%d - %d capacity left: %d",i,j,capacity[i][j]-

flow[i][j]);

if((capacity[i][j]-flow[i][j])==0)

printf(" Path is blocked");

}

}

}

}

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

}

top=0;

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

push(u);

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

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

}

push(u);

// Adding the path flows

max_flow += increment;

printf("\nPath chosen: ");

pop();

while(top>=0){

printf("%d ",pop());

}

residual_graph();

printf("\n");

}

return max_flow;

}

int main() {

int start,end,c,source,sink,i,j;

printf("Enter number of vertices: \n");

scanf("%d",&n);

printf("Enter number of edges: \n");

scanf("%d",&e);

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

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

capacity[i][j] = 0;

}

}

//int i;

for(i=1;i<=e;i++){

printf("Enter start vertex,end vertex and capacity for edge %d\n",i);

scanf("%d%d%d",&start,&end,&c);

capacity[start][end] = c;

}

printf("\n Enter source and sink vertices\n");

scanf("%d%d",&source,&sink);

printf("Max Flow: %d\n", fordFulkerson(source, sink));

}

    

GRAPH ALGORITHMS : C PROGRAM for BELLMANFORD DETECTING negative(-ve) CYCLE WITH USER INPUT

 C PROGRAM TO IMPLEMENT BELLMANFORD DETECTING -VE CYCLE WITH USER INPUT 

 #include <stdio.h>

#include <stdlib.h>

#define INFINITY 99999

struct Edge {

    int u;

    int v;

    int w;

};

struct Graph {

    int V;

    int E;

    struct Edge *edge;

};

void bellmanford(struct Graph *g, int source);

void display(int arr[], int size);

int main(void){

int i;

    struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));

    printf("Enter number of edges : ");

    scanf("%d",&g->E);

    printf("\nEnter number of vertices : ");

    scanf("%d",&g->V);

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

    for(i=0;i<g->E;i++){

        printf("Enter vertices and weight value of edge %d : ",i+1);

        scanf("%d %d %d",&g->edge[i].u,&g->edge[i].v,&g->edge[i].w);

    }

    bellmanford(g, 0);

    return 0;

}

void bellmanford(struct Graph *g, int source) {

    int i, j, u, v, w;

    int tV = g->V;

    int tE = g->E;

    int d[tV];

    int p[tV];

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

        d[i] = INFINITY;

        p[i] = 0;

    }

    d[source] = 0;

    for (i = 1; i <= tV - 1; i++) {

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

            u = g->edge[j].u;

            v = g->edge[j].v;

            w = g->edge[j].w;

            if (d[u] != INFINITY && d[v] > d[u] + w) {

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

                p[v] = u;

            }

        }

    }

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

        u = g->edge[i].u;

        v = g->edge[i].v;

        w = g->edge[i].w;

        if (d[u] != INFINITY && d[v] > d[u] + w) {

            printf("Negative weight cycle detected!");

            printf("Edge value are %d %d %d",u,v,w);

            return;

        }

    }

    printf("Distance array: ");

    display(d, tV);

    printf("Predecessor array: ");

    display(p, tV);

}

void display(int arr[], int size) {

    int i;

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

        printf("%d ", arr[i]);

    }

    printf("\n");

}

Output : 

EXCERCISE PROBLEM: STRING MACHINE AND NETWORK FLOW

Amortized Analysis : Accounting Method

Amortized Analysis : Introduction and Aggregate analysis

Graph coloring using backtracking

 

C pointers

                                         C pointers

 C pointers are a powerful tool that gives strength to the C language more than others.

What is the output?

#include<stdio.h>

void crazy(int,int);

void crazy(int m, int n)

 {

int *ptr;

m=0;

ptr=&m;

n=*ptr;

*ptr=1;

printf("%d %d",m,n);

}

void main()

{

            crazy(2,2);

}

O/p:

C programming

                                                           Structure in C

struct add                                         //abstract data type

{

    int A,B;

 }x,sum;

int main()

{

   printf("Enter first no\n");

   scanf("%d", &x.A);

   printf("Enter second no \n");

   scanf("%d", &x.B);

                                                                                    // adding nos

   sum.A=x.A+x.B;

   printf("Sum is = %d", sum.A);

  return 0;

}

Webmining

Web scraping in python

1. Write a program (using nltk toolkit in python environment) to tokenize

a) Sentence

b) Multiple sentences

c) A paragraph

d) Information of a complete web page

Python code

import nltk 

from nltk.tokenize import word_tokenize

from nltk.text import Text

mystring = "I am currently studying in XYZ UNIVERSITY atDELHI. Cuurently in 4th year studying placements and tyring for the masters too as i was tooearly to start the programming. Currently tyring to ops as datascientist at any product based copany as a data scientist i need to learn all the python programmming at the professionally and we have to be good at statistics and the machine learnng models which model will suit for which problem"

tokens = word_tokenize(mystring)

tokens

O/p:

['I', 'am', 'currently', 'studying', 'in', 'XYZ', 'UNIVERSITY', 'at', 'DELHI', '.', 'Cuurently', 'in', '4th', 'year', 'studying', 'placements', 'and', 'tyring', 'for', 'the', 'masters', 'too', 'as', 'i', 'was', 'too', 'early', 'to', 'start', 'the', 'programming', '.', 'Currently', 'tyring', 'to', 'ops', 'as', 'datascientist', 'at', 'any', 'product', 'based', 'copany', 'as', 'a', 'data', 'scientist', 'i', 'need', 'to', 'learn', 'all', 'the', 'python', 'programmming', 'at', 'the', 'professionally', 'and', 'we', 'have', 'to', 'be', 'good', 'at', 'statistics', 'and', 'the', 'machine', 'learnng', 'models', 'which', 'model', 'will', 'suit', 'for', 'which', 'problem']

Python code

nltk.download('punkt')

O/p:

[nltk_data] Downloading package punkt to

[nltk_data]     C:\Users\Viru\AppData\AMK\nltk_data...

[nltk_data]   Package punkt is already up-to-date!

True

 

Tokenizing multiple sentences

Python code

print("Enter multiple sentences: ")

lines = []

tok = []

while True: 

    line = input() 

    if line: 

        lines.append(line) 

    else:

        break

        

    for t in lines:

        t = word_tokenize(t)

        tok.append(t)

print("Tokens for multiple sentences are as follows: ",tok)

 

O/p:

Enter multiple sentences:

Modern humans arrived on the Indian subcontinent from Africa no later than 55,000 years ago

Their long occupation, initially in varying forms of isolation as hunter-gatherers, has made the region highly diverse, second only to Africa in human genetic diversity.

In the early medieval era, Christianity, Islam, Judaism, and Zoroastrianism became established on India's southern and western coasts

 

Tokens for multiple sentences are as follows:  [['Modern', 'humans', 'arrived', 'on', 'the', 'Indian',…

 

Tokenizing the Paragraph

Python code

##Information of a complete web page

#bs4 module to crawl webpage

from bs4 import BeautifulSoup

import urllib.request

#requesting php.net for information

 

response = urllib.request.urlopen('https://en.wikipedia.org/wiki/India')

html = response.read()

#cleaning grabbed text

soup = BeautifulSoup(html,"html5lib")

text = soup.get_text(strip=True)

tokens_web = word_tokenize(text)

print("Tokens for this web page are: ",tokens_web[:])

#declare a dictionary

word_freq = {}

for tok in tokens_web:

    tok = tok.split()

    for t in tok:

        if t in word_freq:

            word_freq[t] += 1

        else:

            word_freq[t] = 1

 

 

O/p:

Tokens for this web page are:  ['India', '-', 'Wikipediadocument.documentElement.className=', "''", 'client-js', "''", ';', 'RLCONF=', '{', '``', 'wgBreakFrames', "''", ':', 'false', ',', "''", 'wgSeparatorTransformTable', "''", ':', '[', '``', "''", ',', "''", "''", ']', ',', "''", 'wgDigitTransformTable', "'

 

Numpy tutorial

 Numpy tutorial

NumPy is the fundamental package for scientific computing in Python. It is a Python library that provides a multidimensional array object, various derived objects (such as masked arrays and matrices), and an assortment of routines for fast operations on arrays, including mathematical, logical, shape manipulation, sorting, selecting, I/O, discrete Fourier transforms basic linear algebra, basic statistical operations, random simulation and much more.

The following tutorial will help you to learn Numpy.

1. Create an array of 6 zeros

import numpy as np np.zeros(6)

 O/p:

array([0., 0., 0., 0., 0., 0.])

Data Structures and Algorithms[CODES]

 

Stack using array in C

 #include<stdio.h>

#include<stdlib.h>

#define Size 4

int Top=-1, inp_array[Size];

void Push();

void Pop();

void show();

int main()

{

    int choice;

     while(1)   

    {

        printf("\nOperations performed by Stack");

        printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");

        printf("\n\nEnter the choice:");

        scanf("%d",&choice);

        switch(choice)

        {

            case 1: Push();

                    break;

            case 2: Pop();

                    break;

            case 3: show();

                    break;

            case 4: exit(0);

            

            default: printf("\nInvalid choice!!");

        }

    }

}

 void Push()

{

    int x;

     if(Top==Size-1)

    {

        printf("\nOverflow!!");

    }

    else

    {

        printf("\nEnter element to be inserted to the stack:");

        scanf("%d",&x);

        Top=Top+1;

        inp_array[Top]=x;

    }

}

  void Pop()

{

    if(Top==-1)

    {

        printf("\nUnderflow!!");

    }

    else

    {

        printf("\nPopped element:  %d",inp_array[Top]);

        Top=Top-1;

    }

}

 void show()

{

     if(Top==-1)

    {

        printf("\nUnderflow!!");

    }

    else

    {

        printf("\nElements present in the stack: \n");

        for(int i=Top;i>=0;--i)

            printf("%d\n",inp_array[i]);

    }

}

Dynamic programming

Greedy algorithm

Dynamic Programming in C

 

Longest Common Subsequence in C

 #include<stdio.h>

#include<string.h>

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

char x[20],y[20],b[20][20];

 void printFunction(int i,int j)

{

                if(i==0 || j==0)

                                return;

                if(b[i][j]=='c')

                {

                                printFunction(i-1,j-1);

                                printFunctionf("%c",x[i-1]);

                }

                else if(b[i][j]=='u')

                                printFunction(i-1,j);

                else

                                printFunction(i,j-1);

}

 

void LongComSub()

{

                m=strlen(x);

                n=strlen(y);

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

                                c[i][0]=0;

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

                                c[0][i]=0;

                                

 //c, u and l denotes cross, upward and downward directions respectively

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

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

                                {

                                                if(x[i-1]==y[j-1])

                                                {

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

                                                                b[i][j]='c';

                                                }

                                                else if(c[i-1][j]>=c[i][j-1])

                                                {

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

                                                                b[i][j]='u';

                                                }

                                                else

                                                {

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

                                                                b[i][j]='l';

                                                }

                                }

}

int main()

{

                printf("Provide first sequence:");

                scanf("%s",x);

                printf("Provide second sequence:");

                scanf("%s",y);

                printf("\nThe LongComSub is ");

                LongComSub();

                printFunction(m,n);

return 0;

}

Recursion in C

Find the output of the following recursive algorithm.

 #include<stdio.h>

  int counter = 0;

  int calc(int a, int b) {

  int c;

  counter++;

  if (b==3) {

  return (a*a*a);

          }

  else {

    c = calc(a, b/3);

    return (c*c*c);

 }

}

int main (){

  calc(4, 81);

  printf ("%d", counter);

  }

Output: 4

C codes for Greedy Algorithms

                        

              Job Sequencing using Greedy method in C

 

#include<stdio.h>

#define MAX 100

typedef struct Job {

  char id[6];

  int deadline;

  int profit;

} Job;

void JobSeq(Job jobs[], int n);

// minimum of two jobs.

int Min(int x, int y) {

  if(x < y) return x;

  return y;

}

int main(void) {

  /*variables*/

  int i, j;

  /*jobs with deadline and profit*/

  Job jobs[6] = {

    {"j1", 60,  200},

    {"j2", 40,  180},

    {"j3", 30,  190},

    {"j4", 20,  300},

    {"j5", 40,  120},

    {"j6", 70,  120},

  };

  /*need one temp variable*/

  Job temp;

  //total  jobs

  int n = 6;

   /*sort profit  in descending order*/

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

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

      if(jobs[j+1].profit > jobs[j].profit) {

        temp = jobs[j+1];

        jobs[j+1] = jobs[j];

        jobs[j] = temp;  //

      }

    }

  }

  printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");

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

    printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);

  }

  JobSeq(jobs, n);

  return 0;

}

void JobSeq(Job jobs[], int n) {

    /*variables*/

  int i, j, k, maxprofit;

  //free time slots

  int timeslot[MAX];

  //filled time slots

  int filledTimeSlot = 0;

  //find max deadline value

  int dmax = 0;

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

    if(jobs[i].deadline > dmax) {

      dmax = jobs[i].deadline;

    }

  }

  //Initially let us keep all free empty slot as -1

  for(i = 1; i <= dmax; i++) {

    timeslot[i] = -1;

  }

  printf("dmax: %d\n", dmax);

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

    k = Min(dmax, jobs[i - 1].deadline);

    while(k >= 1) {

      if(timeslot[k] == -1) {

        timeslot[k] = i-1;

        filledTimeSlot++;

        break;

      }

      k--;

    }

    //if all time slots are filled then stop

    if(filledTimeSlot == dmax) {

      break;

    }

  }

   /*Sequenced jobs*/

  printf("\nSequenced Jobs: ");

  for(i = 1; i <= dmax; i++) {

    printf("%s", jobs[timeslot[i]].id);

    if(i < dmax) {

      printf(" --> ");

    }

  }

  // profit

  maxprofit = 0;

  for(i = 1; i <= dmax; i++) {

    maxprofit += jobs[timeslot[i]].profit;

  }

  printf("\nMax Profit: %d\n", maxprofit);

}