Tuesday, September 27, 2022
Monday, September 26, 2022
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);
}
GRAPH ALGORITHMS : FLOYD-WARSHAL -Displaying DISTANCE MATRIX and PI MATRIX using C PROGRAM
Modify the following Floyd-Warshall algorithm by introducing a π( pi ) table as per the class’s discussion. Here you can write one function...
-
Web scraping in python 1. Write a program (using nltk toolkit in python environment) to tokenize a) Sentence b) Multiple sentences c) ... -
Stack using array in C #include<stdio.h> #include<stdlib.h> #define Size 4 int Top=-1, inp_array[Size]; void Push...
-
Numpy tutorial N umPy is the fundamental package for scientific computing in Python. It is a Python library that provides a multidimension...
