Index

S.N. Title Grade Deadline Remarks

Lab no: 4 Date: 6/8/2025

Matrix Chain Multiplication

Matrix Chain Multiplication is an optimization problem that aims to find the most efficient
way to multiply a given sequence of matrices. The goal is to minimize the total number of
scalar multiplications needed. Matrix multiplication is associative, meaning the order of
multiplication can change without affecting the result, but the number of operations can vary
drastically depending on how we parenthesize the matrices. Given three matrices A(10×30),
B(30×5), and C(5×60), you can multiply them in two different ways:
 (A × B) × C → Cost = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500
 A × (B × C) → Cost = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000

Algorithm:

1. Input: An array p[0..n] of dimensions where matrix Ai has dimensions p[i-1] × p[i],
for i = 1 to n.
2. Step 1: Let m[1..n][1..n] be a 2D table to store the minimum number of
multiplications. Initialize m[i][i] = 0 for all i = 1 to n.
3. Step 2: For chain length L from 2 to n:

 For i = 1 to n - L + 1:
o Set j = i + L - 1
o Set m[i][j] = ∞ (a very large number)
o For each possible split point k from i to j - 1:
 Compute the cost q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
 If q < m[i][j], update m[i][j] = q

4. Step 3: Repeat Step 2 until all chain lengths are processed.

5. Output: The minimum number of scalar multiplications needed is stored in m[1][n].

Time Complexity: O(n3)

Space Complexity: O(n2)

Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int MatrixChainOrder(int p[], int i, int j, int **dp, int

**bracket);
void printOptimalParenthesis(int i, int j, int **bracket);

int main()
{
int n,i,j;
printf("Enter the number of matrices: ");
scanf("%d", &n);

int *arr = (int *)malloc(n * sizeof(int));

int **dp = (int **)malloc(n * sizeof(int *));
int **bracket = (int **)malloc(n * sizeof(int *));

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

{
dp[i] = (int *)malloc(n * sizeof(int));
bracket[i] = (int *)malloc(n * sizeof(int));
for (j = 0; j < n; ++j)
{
dp[i][j] = -1;
bracket[i][j] = -1;
}
}

printf("Enter dimensions of matrices:\n");

for (i = 0; i < n; ++i)
{
scanf("%d", &arr[i]);
}

int minMultiplications = MatrixChainOrder(arr, 1, n - 1, dp,

bracket);
printf("Minimum number of multiplications is %d\n",
minMultiplications);

printf("Optimal Parenthesization: ");

printOptimalParenthesis(1, n - 1, bracket);
 printf("\n");

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

{
free(dp[i]);
free(bracket[i]);
}
free(dp);
free(bracket);
free(arr);

return 0;
}

int MatrixChainOrder(int p[], int i, int j, int **dp, int

**bracket)
{
if (i == j)
return 0;

if (dp[i][j] != -1)
return dp[i][j];

int k;
int mini = INT_MAX;
int count;

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

{
count = MatrixChainOrder(p, i, k, dp, bracket) +
MatrixChainOrder(p, k + 1, j, dp, bracket) +
p[i - 1] * p[k] * p[j];

if (count < mini)

{
mini = count;
bracket[i][j] = k;
}
}

dp[i][j] = mini;
return mini;
}

void printOptimalParenthesis(int i, int j, int **bracket)

{
if (i == j)
{
printf("A%d", i);
return;
}

printf("(");
printOptimalParenthesis(i, bracket[i][j], bracket);
printOptimalParenthesis(bracket[i][j] + 1, j, bracket);
printf(")");
}

Output:
Lab no: 4 Date: 6/8/2025

String Edit Distance

The String Edit Distance problem is a classic example of Dynamic Programming. It deals
with finding the minimum number of operations required to convert one string into another.
These operations typically include: Insertion, Deletion and Substitution.

Given two strings A of length m and B of length n, the goal is to transform A into B using the
minimum number of edit operations (insert, delete, replace).The result is known as the Edit
Distance Distance between the two strings.

Algorithm

1. Input: Two strings A[1..m] and B[1..n]

2. Step 1: Create a 2D array dp[0..m][0..n]
3. Step 2: Initialize base cases:
For i = 0 to m: set dp[i][0] = i (deletion)
For j = 0 to n: set dp[0][j] = j (insertion)
4. Step 3: For i = 1 to m:
For j = 1 to n:
If A[i-1] == B[j-1]:
Set dp[i][j] = dp[i-1][j-1]
Else:
Set dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
5. Output: The edit distance is dp[m][n]

Time Complexity: O(m * n)

Space Complexity: O(m * n)

where m and n are lengths of the two strings.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100

int min(int a, int b, int c);

int editDistance(const char *str1, const char *str2);

int main()
{
char str1[MAX], str2[MAX];
printf("Enter the first string: ");
scanf("%s", str1);
printf("Enter the second string: ");
scanf("%s", str2);
int distance = editDistance(str1, str2);

printf("Edit Distance between \"%s\" and \"%s\" is: %d\n",

str1, str2, distance);

return 0;
}

int min(int x, int y, int z)

{
int t = x < y ? x : y;
return t < z ? t : z;
}

int editDistance(const char *str1, const char *str2)

{
int m = strlen(str1);
int n = strlen(str2);

int **dp = (int **)malloc((m + 1) * sizeof(int *));

for (int i = 0; i <= m; ++i)
dp[i] = (int *)malloc((n + 1) * sizeof(int));
 for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 1 + min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
);
}
}

int result = dp[m][n];

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

free(dp[i]);
free(dp);

return result;
}

Output:
Lab no: 4 Date: 6/8/2025

Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is a fundamental algorithm in graph theory used to find the shortest
paths between all pairs of vertices in a weighted graph. It is especially effective for dense graphs and
works for both directed and undirected graphs. Given a graph represented by an adjacency matrix,
where graph[i][j] holds the weight of the edge from vertex i to vertex j (or ∞ if there is no edge), the
goal is to find the shortest distances between every pair of vertices.

Recurrance Relation:

dist[i][j] = min ( dist[i][j], dist[i][k] + dist[k][j] )

Algorithm:

1. Initialize the dist matrix with the given graph weights.

2. For each vertex k from 0 to n-1:
For each vertex i:
For each vertex j:
Update dist[i][j] using the recurrence relation.
3. The final dist[i][j] gives the shortest distance from i to j.

Time Complexity: O(n3)

Space Complexity: O(n2)

,where n is the number of vertices.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
void floydWarshall(int **graph, int V);

int main()
{
int V, i, j, w;
printf("Enter the number of vertices in the graph: ");
scanf("%d", &V);
int **graph = (int **)malloc(V * sizeof(int *));
for (i = 0; i < V; ++i)
{
graph[i] = (int *)malloc(V * sizeof(int));
for (j = 0; j < V; ++j)
{
if (i == j)
{
graph[i][j] = 0;
}
else
{
printf("Enter the weight from vertex %d to
vertex %d (-1 if no edge): ", i, j);
scanf("%d", &w);
if (w == -1)
graph[i][j] = INT_MAX;
else
graph[i][j] = w;
}
}
}

floydWarshall(graph, V);

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

free(graph[i]);
free(graph);

return 0;
}
void floydWarshall(int **graph, int V)
{
int i, j, k;
int **dist = (int **)malloc(V * sizeof(int *));
for (i = 0; i < V; ++i)
{
dist[i] = (int *)malloc(V * sizeof(int));
for (j = 0; j < V; ++j)
{
dist[i][j] = graph[i][j];
}
}

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

{
for (i = 0; i < V; ++i)
{
for (j = 0; j < V; ++j)
{
if (dist[i][k] != INT_MAX && dist[k][j] !=
INT_MAX &&
dist[i][k] + dist[k][j] < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

printf("\nShortest distances between every pair of

vertices:\n");
for (i = 0; i < V; ++i)
{
for (j = 0; j < V; ++j)
{
if (dist[i][j] == INT_MAX)
printf("INF\t");
else
printf("%d\t", dist[i][j]);
}
printf("\n");
}

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

free(dist[i]);
free(dist);
}

Output:
Lab no: 4 Date: 6/8/2025

0/1 Knapsack Problem

The 0/1 Knapsack Problem is a classic problem in combinatorial optimization and dynamic
programming. It derives its name from the real-world scenario of packing a knapsack (bag) with the
most valuable combination of items without exceeding the bag's capacity. Given a set of n items,
each item i has:

 A weight w[i]
 A value v[i]

Each item can be included at most once, hence the name "0/1".

Algorithm:

 Create a 2D array dp[0..n][0..W] to store the maximum value for each subproblem.
 Initialize the first row and first column of dp to 0:
For i = 0 to n:
dp[i][0] = 0
For w = 0 to W:
dp[0][w] = 0
 For each item i from 1 to n:
For each weight w from 1 to W:
If weights[i] <= w:
dp[i][w] = max(dp[i-1][w], values[i] + dp[i-1][w - weights[i]])
Else
dp[i][w] = dp[i-1][w]
 Return dp[n][W] as the maximum value that can be achieved.

Time Complexity: O(n × W)

Code:
Space Complexity: O(n × W)
#include <stdio.h>
int max(int, int);
int knapSack(int, int[], int[], int);

int main()
{
int n, W;
printf("Enter the number of items in a Knapsack: ");
scanf("%d", &n);
int v[n], w[n];
for (int i = 0; i < n; i++)
scanf("%d %d", &v[i], &w[i]);
printf("Enter the capacity of knapsack: ");
scanf("%d", &W);
printf("%d\n", knapSack(W, w, v, n));
return 0;
}
int max(int x, int y)
{
return (x > y) ? x : y;
}
int knapSack(int W, int w[], int v[], int n)
{
int i, wt;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++)
{
for (wt = 0; wt <= W; wt++)
{
if (i == 0 || wt == 0)
K[i][wt] = 0;
else if (w[i - 1] <= wt)
K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i -
1]], K[i - 1][wt]);
else
K[i][wt] = K[i - 1][wt];
}
}
return K[n][W];
}
Output:
Lab no: 4 Date: 6/8/2025

Traveling Salesman Problem

The Travelling Salesman Problem (TSP) is a classic optimization problem in computer science
where the goal is to find the shortest possible route that visits a set of cities exactly once and returns
to the starting city. It is an NP-hard problem, meaning no known algorithm can solve it efficiently for
large inputs. TSP has practical applications in logistics, planning, and network design, and is
commonly solved using brute force, dynamic programming, or approximation methods depending on
the size of the input.

Algorithm:

 Let completed_visit = (1 << n) - 1 represent all cities visited.

 Use a DP table DP[2^n][n] initialized to -1 to store minimum costs.
 Define TSP(mark, position) where mark tracks visited cities and position is current city.
 If all cities are visited (mark == completed_visit), return distance to start city.
 If DP[mark][position] is computed, return it.
 For each unvisited city city, calculate cost:
cost = distan[position][city] + TSP(mark | (1 << city), city)
 Store and return the minimum cost in DP[mark][position].
 Start with TSP(1, 0) for city 0 visited initially.

Time Complexity: O (n2 * 2n)

Space Complexity: O (n * 2n)

Code:
#include <stdio.h>
#include <limits.h>
#define MAX 9999
#define MAX_CITIES 20

int n;
int distan[MAX_CITIES][MAX_CITIES];
int completed_visit;
int DP[1 << MAX_CITIES][MAX_CITIES]; // But 1 << 20 is too
large for stack/heap, so limit n appropriately
int min(int a, int b) {
return (a < b) ? a : b;
}

int TSP(int mark, int position) {

if (mark == completed_visit)
return distan[position][0];

if (DP[mark][position] != -1)
return DP[mark][position];

int answer = MAX;

for (int city = 0; city < n; city++) {
if ((mark & (1 << city)) == 0) {
int newAnswer = distan[position][city] + TSP(mark |
(1 << city), city);
answer = min(answer, newAnswer);
}
}
DP[mark][position] = answer;
return answer;
}

int main() {
printf("Enter the number of cities: ");
scanf("%d", &n);

completed_visit = (1 << n) - 1;

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

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

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

for (int j = 0; j < n; j++) {
DP[i][j] = -1;
}
}
printf("Minimum Distance Travelled -> %d\n", TSP(1, 0));
return 0;
}

Output:

Lab no: 5 Date: 6/8/2025

N-Queen Problem

The N-Queen Problem is a classic backtracking puzzle where the objective is to place N queens on
an N×N chessboard such that no two queens threaten each other. This means no two queens can share
the same row, column, or diagonal. The problem is to find all possible arrangements or just one valid
arrangement of queens satisfying these constraints. It is widely used to demonstrate backtracking and
recursion in algorithm design, as the solution involves placing queens one by one in different rows
and checking for conflicts before proceeding. The N-Queen problem helps in understanding
constraint satisfaction problems and is fundamental in studying recursive algorithms and pruning
techniques to optimize search.

Algorithm

 Start with the first row.

 For each column in the row, check if placing a queen is safe.
 If safe, place the queen and move to the next row.
 If all queens are placed, print the solution.
 If no safe column found, backtrack to previous row.
 Repeat until all solutions are found or completed.

Time Complexity: O(n!)

Space Complexity: O(n2)
Code:

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

#define N 4
void printSolution(int board[N][N]);
bool isSafe(int board[N][N], int row, int col);
bool solveNQUtil(int board[N][N], int col);

int main()
{
int board[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0} };

if (solveNQUtil(board, 0) == false)
{
printf("Solution does not exist\n");
return 0;
}
printSolution(board);
return 0;
}

void printSolution(int board[N][N])

{
int i, j;
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
}

bool isSafe(int board[N][N], 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; i < N && j >= 0; i++, j--)
if (board[i][j])
return false;
return true;
 }

bool solveNQUtil(int board[N][N], int col)

{
if (col >= N)
return true;
int i;
for (i = 0; i < N; i++)
{
if (isSafe(board, i, col))
{
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0;
}
}

return false;
}

Output:

Lab no: 5 Date: 6/8/2025

Subset Sum Problem

The Subset Sum problem asks whether there exists a subset of a given set of integers whose sum
equals a specified target value. Using backtracking, the problem is solved by exploring all possible
subsets. At each step, the algorithm decides whether to include or exclude the current element,
recursively checking if the target sum can be achieved. If a subset with the desired sum is found, the
algorithm stops; otherwise, it backtracks to explore other possibilities. This approach systematically

Code:

#include <stdio.h>
#include <stdbool.h>
bool isSubsetSum(int set[], int n, int sum, int subset[]);
void subsetSum(int set[], int n, int sum);

int main()
{
 int set[] = {3, 34, 4, 12, 5, 2};
int targetSum = 9;
int n = sizeof(set) / sizeof(set[0]);

printf("Subset(s) with sum %d:\n", targetSum);

subsetSum(set, n, targetSum);

return 0;
}

bool isSubsetSum(int set[], int n, int sum, int subset[])

{
if (sum == 0)
{
for (int i = 0; i < n; ++i)
{
if (subset[i] == 1)
{
printf("%d ", set[i]);
}
}
printf("\n");
return true;
}

if (n == 0 && sum != 0)
{
return false;
}

if (set[n - 1] > sum)

{
return isSubsetSum(set, n - 1, sum, subset);
}

subset[n - 1] = 0;
bool withoutLast = isSubsetSum(set, n - 1, sum, subset);

subset[n - 1] = 1;
bool withLast = isSubsetSum(set, n - 1, sum - set[n - 1],
subset);

return withoutLast || withLast;

}

void subsetSum(int set[], int n, int sum)

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

if (!isSubsetSum(set, n, sum, subset))

{
printf("No subset with the given sum found.\n");
}
}

Output:

Lab no: 6 Date: 6/8/2025

Vertex Cover Problem

The Vertex Cover problem is a classic problem in graph theory and combinatorial optimization.

incident to at least one vertex in V′. In other words, for every edge (u,v) ∈ E, either u∈V′ or v∈V'
Given a graph G=(V,E), a vertex cover is a subset of vertices V′⊆V such that every edge in E is

(or both).

The goal is to find a vertex cover of minimum size, i.e., the smallest set of vertices that covers all
Code:

#include <stdio.h>
#include <stdbool.h>
#define MAX_EDGES 100
#define MAX_VERTICES 100
void vertexCoverApproximation(int edges[][2], int numEdges);

int main()
{
int numEdges, i;
printf("Enter the number of edges in the graph: ");
scanf("%d", &numEdges);
int edges[MAX_EDGES][2];
printf("Enter the edges of the graph (format: vertex1 vertex2):\
n");
for (i = 0; i < numEdges; ++i)
{
scanf("%d %d", &edges[i][0], &edges[i][1]);
}
vertexCoverApproximation(edges, numEdges);
return 0;
}

void vertexCoverApproximation(int edges[][2], int numEdges)

{
bool inVertexCover[MAX_VERTICES] = { false };
int i;
for (i = 0; i < numEdges; ++i)
{
inVertexCover[edges[i][0]] = true;
inVertexCover[edges[i][1]] = true;
}
printf("Approximate Vertex Cover: ");
for (i = 0; i < MAX_VERTICES; ++i)
{
if (inVertexCover[i])
{
printf("%d ", i);
}
}
printf("\n");
}
Output: