22MIC0017

VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB

CSI 2003
Advanced Algorithms

DIGITAL ASSIGNMENT -1

Submitted to - LAKSHMANAN K

Submitted by
Vedang Mishrra
22MIC0017
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB

Question 1: Write a program to find the LCS of two given sequences

using dynamic programming . Print the LCS table also. Take the
sequences as input from the user.

CODE:
#include <stdio.h>
#include <string.h>

#define MAX_LEN 100

int main() {
char seq1[MAX_LEN], seq2[MAX_LEN];
int m, n;

printf("Enter the first sequence: ");

fgets(seq1, MAX_LEN, stdin);
seq1[strcspn(seq1, "\n")] = '\0';

printf("Enter the second sequence: ");

fgets(seq2, MAX_LEN, stdin);
seq2[strcspn(seq2, "\n")] = '\0';

m = strlen(seq1);
n = strlen(seq2);
int lcs_table[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
lcs_table[i][j] = 0;
} else if (seq1[i - 1] == seq2[j - 1]) {
lcs_table[i][j] = lcs_table[i - 1][j - 1] + 1;
} else {
lcs_table[i][j] =
(lcs_table[i - 1][j] > lcs_table[i][j - 1]) ? lcs_table[i
- 1][j] : lcs_table[i][j - 1];
}
}
}

printf("LCS Table:\n");
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
printf("%d ", lcs_table[i][j]);
}
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB

printf("\n");
}

int lcs_len = lcs_table[m][n];

char lcs_str[lcs_len + 1];
int i = m, j = n, k = lcs_len - 1;

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

if (seq1[i - 1] == seq2[j - 1]) {
lcs_str[k--] = seq1[i - 1];
i--;
j--;
} else if (lcs_table[i][j] == lcs_table[i][j - 1]) {
j--;
} else {
i--;
}
}

lcs_str[lcs_len] = '\0';
printf("Longest Common Subsequence: %s\n", lcs_str);

return 0;
}

OUTPUT:
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB

Question 2: Write a menu driven program (use switch

case) to solve Fibonacci series using
(i)recurrence relation
(ii) top-down approach using dynamic programming,
(iii) bottom-up
approach using dynamic programming. Get the input
from user, say 7 means find F(7).

CODE:
#include <stdio.h>
void fibonacci_recursive(int n) {
if (n <= 1) {
printf("%d ", n);
} else {
fibonacci_recursive(n - 1);
printf("%d ", n);
}
}
int fibonacci_top_down(int n, int *memo) {
if (n <= 1) {
return n;
} else if (memo[n] != -1) {
return memo[n];
} else {
memo[n] = fibonacci_top_down(n - 1, memo) + fibonacci_top_down(n - 2,
memo);
return memo[n];
}
}
void fibonacci_bottom_up(int n) {
int fib[n + 1];
fib[0] = 0;
fib[1] = 1;

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

fib[i] = fib[i - 1] + fib[i - 2];
}

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

printf("%d ", fib[i]);
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB
}
}

int main() {
int n, choice;
while (1) {
printf("\nMenu:\n");
printf("1. Fibonacci using Recursion\n");
printf("2. Fibonacci using Top-Down DP (Memoization)\n");
printf("3. Fibonacci using Bottom-Up (DP)\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:{
printf("Enter the nth term: ");
scanf("%d", &n);
printf("Fibonacci sequence: ");
fibonacci_recursive(n);
printf("\n");
break;
}
case 2:{
printf("Enter the nth term: ");
scanf("%d", &n);

int memo[n + 1];

for (int i = 0; i <= n; i++) {
memo[i] = -1;
}

printf("Fibonacci sequence: ");

for (int i = 0; i <= n; i++) {
fibonacci_top_down(i, memo);
}
printf("\n");
break;
}
case 3:{
printf("Enter the nth term: ");
scanf("%d", &n);
printf("Fibonacci sequence: ");
fibonacci_bottom_up(n);
printf("\n");
break;
}
case 4:{
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB
printf("Exiting...\n");
return 0;
}
default:{
printf("Invalid choice. Please try again.\n");
break;
}
}
}

return 0;
}

OUTPUT:
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB

Question 3: Write a program to solve subset sum by backtracking

approach. The user will provide the set of integers and the target m
CODE:
#include <stdio.h>

#define MAX_SIZE 100

void print_subset(int subset[], int size) {

printf("Subset: { ");
for (int i = 0; i < size; i++) {
printf("%d ", subset[i]);
}
printf("}\n");
}

void subset_sum_util(int set[], int subset[], int n, int target, int sum, int
k, int start) {
if (sum == target) {
print_subset(subset, k);
return;
}

for (int i = start; i < n && sum + set[i] <= target; i++) {
subset[k] = set[i];
subset_sum_util(set, subset, n, target, sum + set[i], k + 1, i + 1);
}
}

void subset_sum(int set[], int n, int target) {

int subset[MAX_SIZE];
subset_sum_util(set, subset, n, target, 0, 0, 0);
}

int main() {
int n, target;

printf("Enter the number of elements in the set: ");

scanf("%d", &n);

int set[MAX_SIZE];
printf("Enter the elements of the set: ");
for (int i = 0; i < n; i++) {
scanf("%d", &set[i]);
}

printf("Enter the target sum: ");

22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB
scanf("%d", &target);

printf("Subsets with sum %d:\n", target);

subset_sum(set, n, target);

return 0;
}

OUTPUT:
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB
QUESTION -4: Write a program to solve the 8-queen problem using
backtracking.
CODE:
#include<stdio.h>
#include<math.h>

int board[20],count;

int main()
{
int n,i,j;
void queen(int row,int n);

printf(" - N Queens Problem Using Backtracking -");

printf("\n\nEnter number of Queens:");
scanf("%d",&n);
queen(1,n);
return 0;
}

//function for printing the solution

void print(int n)
{
int i,j;
printf("\n\nSolution %d:\n\n",++count);

for(i=1;i<=n;++i)
printf("\t%d",i);

for(i=1;i<=n;++i)
{
printf("\n\n%d",i);
for(j=1;j<=n;++j) //for nxn board
{
if(board[i]==j)
printf("\tQ"); //queen at i,j position
else
printf("\t-"); //empty slot
}
}
}

/*funtion to check conflicts

If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row,int column)
{
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB
int i;
for(i=1;i<=row-1;++i)
{
//checking column and digonal conflicts
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
}

return 1; //no conflicts

}

//function to check for proper positioning of queen

void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column; //no conflicts so place queen
if(row==n) //dead end
print(n); //printing the board configuration
else //try queen with next position
queen(row+1,n);
}
}
}
}
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB
OUTPUT: There are 92 distinct solutions for the 8 queen problem and
the above code gives out all the 92 distinct solutions so for reference
we will be using only 2.
Solution 44:

1 2 3 4 5 6 7 8

1 - - - Q - - - -

2 - - - - - - - Q

3 Q - - - - - - -

4 - - Q - - - - -

5 - - - - - Q - -

6 - Q - - - - - -

7 - - - - - - Q -

8 - - - - Q - - -

Solution 84:

1 2 3 4 5 6 7 8

1 - - - - - - Q -

2 - - Q - - - - -

3 Q - - - - - - -

4 - - - - - Q - -

5 - - - - - - - Q

6 - - - - Q - - -

7 - Q - - - - - -

8 - - - Q - - - -
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB
QUESTION 5: Write a program to solve the graph coloring problem
with 3 colors. Get the input (i.e, graph in the form adjacency matrix)
from the user.

CODE:
#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 100

bool is_safe(int vertex, int color, int graph[MAX_VERTICES][MAX_VERTICES], int

coloring[MAX_VERTICES], int num_vertices) {
for (int i = 0; i < num_vertices; i++) {
if (graph[vertex][i] == 1 && coloring[i] == color) {
return false;
}
}
return true;
}

bool graph_coloring_util(int graph[MAX_VERTICES][MAX_VERTICES], int

num_colors, int coloring[MAX_VERTICES], int vertex, int num_vertices) {
if (vertex == num_vertices) {
return true;
}

for (int color = 1; color <= num_colors; color++) {

if (is_safe(vertex, color, graph, coloring, num_vertices)) {
coloring[vertex] = color;
if (graph_coloring_util(graph, num_colors, coloring, vertex + 1,
num_vertices)) {
return true;
}
coloring[vertex] = 0;
}
}

return false;
}

void graph_coloring(int graph[MAX_VERTICES][MAX_VERTICES], int num_colors, int

num_vertices) {
int coloring[MAX_VERTICES];
for (int i = 0; i < num_vertices; i++) {
coloring[i] = 0;
}
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB
if (!graph_coloring_util(graph, num_colors, coloring, 0, num_vertices)) {
printf("Solution does not exist.\n");
return;
}

printf("Graph Coloring:\n");
for (int i = 0; i < num_vertices; i++) {
printf("Vertex %d is colored with Color %d\n", i + 1, coloring[i]);
}
}

int main() {
int num_vertices;
printf("Enter the number of vertices in the graph: ");
scanf("%d", &num_vertices);

int graph[MAX_VERTICES][MAX_VERTICES];

printf("Enter the adjacency matrix (0 for no edge, 1 for an edge):\n");

for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
scanf("%d", &graph[i][j]);
}
}

int num_colors = 3;
graph_coloring(graph, num_colors, num_vertices);

return 0;
}
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB

OUTPUT:
22MIC0017
VEDANG MISHRRA
CSI2003-ADVANCED ALGORITHMS LAB

THANKYOU