KONGU ENGINEERING COLLEGE(Autonomous),

PERUNDURAI, ERODE-638 060

DEPARTMENT OF COMPUTER TECHNOLOGY-PG

[Link]. Software Systems

Course Code & Name : 22ISL61 Machine Learning

Semester & Year : VI Semester & III Year

Version : 1

Semester from : Dec 2025 to May 2026

Prepared by : [Link]

1
 Table of Contents

SNo. Lab Exercise Page No.

Exploration of UCI repository datasets and tools like WEKA,

1. Rapid Miner, etc. 4

2. Perform data manipulation using NumPy and pandas and data 10

visualization using matplotlib.

3. Implement linear models to approximate the given data. 17

Find the attribute with maximum information gain and gain

ratio for the given data.
4. 22

5. Implement multi-layer perceptron algorithm and enhance it to 26

other variations.
Implement Naïve Bayesian classification and predict the class
6. label for the given data. 30

7. Implement K-NN (K-Nearest Neighbour) algorithm for the 34

specified data.

8. Implement K-means clustering algorithm for the given data

and visualize and interpret the result.

9. Write a Python program to implement Genetic operators.

10. Write a Python program to implement Q-Learning algorithm

for the given data.

2
 Rubrics for 22ISC41 – Design and Analysis of Algorithms

Scales Level 1 Level 2 Level 3

Maximum
Excellent Good Satisfactory
Dimensions marks (50)
80-100% 50-79% < 50%
Conduct of Experiment – 30 Marks
Preliminary preparation Good preliminary Moderate No Preliminary
(05) preparation done preliminary preparation
preparation
done
Problem solving skill Good problem solving Average Poor problem
(05) 30 skill problem solving skill
solving skill
Output verification for Output verified for the Output verified No output
the given test cases (05) test cases
Program enhancement Able to enhance the Able to enhance the Not able to enhance
(05) program quickly program moderately the program
Record - 15 Marks
Neat Presentation (05) Good presentation Fair presentation Poor presentation

Completion on time (10) 15 Completed on time Completed with Very late submission
short delay
Viva - 15 marks
Viva (15) 15 Answered all the viva Answered few Subject knowledge is
questions and good questions and subject poor
subject knowledge knowledge to be
improved

3
Ex:No:1
Exploration of UCI Repository Dataset Using WEKA Tool
Date:
Aim
● To explore and analyze a dataset from the UCI Machine Learning Repository using the
WEKA tool and study its attributes and instances.

Procedure
The exploration of datasets from the UCI Machine Learning Repository is carried out using the
WEKA tool. This process helps to understand the structure of the dataset, including attributes,
instances, and class labels. It is implemented using the following steps.
● Download a dataset from the UCI Machine Learning Repository in .arff or .csv format.
● Open the WEKA tool and select the Explorer interface from the WEKA GUI Chooser.
● Load the dataset by clicking the Open File option in the Preprocess tab.
● Observe the dataset information such as number of attributes, number of instances, and
attribute types displayed in the WEKA Explorer window.
● Use the Visualize option to analyze the distribution of data and relationships between
attributes.

SAMPLE PROGRAM
//Program – Chi-Square Feature Selection using WEKA

import [Link] as jvm

from [Link] import Loader
from weka.attribute_selection import AttributeSelection, ASEvaluation, ASSearch

# start JVM
[Link]()

# load dataset
loader = Loader(classname="[Link]")
data = loader.load_file("[Link]")
data.class_is_last()

# chi-square evaluator
evaluator = ASEvaluation(classname="[Link]")

4
# ranker search method
search = ASSearch(classname="[Link]")

# perform attribute selection

attsel = AttributeSelection()
[Link](evaluator)
[Link](search)
attsel.select_attributes(data)

# print result
print(attsel.results_string)

# stop JVM
[Link]()
OUTPUT
Ranked attributes:
0.91 MemoryLoss
0.88 Confusion
0.80 LanguageProblem
0.45 Age
EXERCISE PROBLEMS
1. Load a dataset in WEKA and view its summary statistics (attributes, instances, missing
values).
2. Load a dataset in WEKA and apply the RemoveDuplicates to identify and eliminate
duplicate records from the dataset. Compare the dataset before and after removing
duplicate instances

3. Apply preprocessing filters like Normalize, Standardize, or Replace Missing Values.

Observe and explain how preprocessing affects the classifier performance.

VIVA QUESTIONS
1. What is WEKA, and what are its main features?
2. What types of data formats can WEKA work with?
3. How do you load a dataset in WEKA and view its summary information?
4. What are filters in WEKA? Give examples and explain their purpose.

5
Ex:No:2 Data manipulation using NumPy, pandas and visualization using
Date: matplotlib.

Aim
● To perform data manipulation using NumPy and Pandas and visualize the data using
Matplotlib.
Procedure
1. Import the required Python libraries such as NumPy for numerical operations, Pandas for
data manipulation, and Matplotlib for data visualization.
2. Upload the given CSV dataset (oasis_cross-[Link]) into Google Colab and load it
using the pandas.read_csv() function.
3. Display the first few rows of the dataset using head() and view dataset information using
info() to understand the structure, column names, and data types.
4. Obtain the statistical summary of the dataset using describe() and check for missing or null
values using isnull().sum().
5. Handle missing values by replacing them with the mean of the corresponding numeric
columns using fillna().
6. Convert the Age column into a NumPy array and perform numerical operations such as
mean, maximum, minimum, and standard deviation.
7. Perform data manipulation operations such as selecting specific columns, filtering records
based on age, sorting the dataset, and creating a new column (Age_Group).
8. Visualize the data using Matplotlib by plotting a histogram for age distribution, a scatter
plot for Age vs MMSE, and a bar chart for age group distribution.

SAMPLE PROGRAM
import numpy as np
import pandas as pd
import [Link] as plt
df = pd.read_csv("/content/oasis_cross-[Link]")
print("Dataset Loaded Successfully\n")

6
print([Link]())
print("\nDataset Information:")
print([Link]())
print("\nStatistical Summary:")
print([Link]())
print("\nChecking Missing Values:")
print([Link]().sum())
[Link]([Link](numeric_only=True), inplace=True)
print("\nMissing values handled successfully")
age_array = [Link](df['Age'])
print("\nNumPy Operations on Age Column")
print("Mean Age:", [Link](age_array))
print("Maximum Age:", [Link](age_array))
print("Minimum Age:", [Link](age_array))
print("Standard Deviation:", [Link](age_array))
print("\nSelecting Columns (Age, MMSE):")
print(df[['Age', 'MMSE']].head())
print("\nFiltering Patients Age > 70:")
print(df[df['Age'] > 70].head())
print("\nSorting by Age (Descending):")
print(df.sort_values(by='Age', ascending=False).head())
df['Age_Group'] = [Link](df['Age'] >= 60, 'Senior', 'Adult')
print("\nNew Column Added (Age_Group):")
print(df[['Age', 'Age_Group']].head())
[Link]()
[Link](df['Age'], bins=10)
[Link]('Age')

7
 [Link]('Frequency')
[Link]('Age Distribution')
[Link]()
[Link]()
[Link](df['Age'], df['MMSE'])
[Link]('Age')
[Link]('MMSE Score')
[Link]('Age vs MMSE')
[Link]()
[Link]()
df['Age_Group'].value_counts().plot(kind='bar')
[Link]('Age Group')
[Link]('Count')
[Link]('Age Group Distribution')
[Link]()

OUTPUT

Dataset Information:
<class '[Link]'>
RangeIndex: 436 entries, 0 to 435
Data columns (total 12 columns):
# Column Non-Null Count Dtype
0 ID 436 non-null object
1 M/F 436 non-null object
2 Hand 436 non-null object
3 Age 436 non-null int64
4 Educ 235 non-null float64
5 SES 216 non-null float64

8
6 MMSE 235 non-null float64
7 CDR 235 non-null float64
8 eTIV 436 non-null int64
9 nWBV 436 non-null float64
10 ASF 436 non-null float64
11 Delay 20 non-null float64
dtypes: float64(7), int64(2), object(3)
memory usage: 41.0+ KB
None
Missing values handled successfully
NumPy Operations on Age Column
Mean Age: 51.357798165137616
Maximum Age: 96
Minimum Age: 18
Standard Deviation: 25.240866432656176
New Column Added (Age_Group):
Age Age_Group
0 74 Senior
1 55 Adult
2 73 Senior
3 28 Adult
4 18 Adult

9
 EXERCISE PROBLEMS
1. Write a Python program to create a NumPy array of 10 numbers and find the mean, median,
and standard deviation.

2. Write a Python program using Pandas to create a DataFrame containing student names, marks
in three subjects, and calculate the total and average marks.

3. Write a Python program to read a CSV dataset using Pandas and display summary statistics

10
 (mean, max, min, count) of the data.

4. Write a Python program using Matplotlib to plot a line graph showing sales data for 6 months.

5. Write a Python program to create a dataset using Pandas and visualize it using both a bar chart
and a pie chart with Matplotlib.

VIVA QUESTIONS
1. What is the difference between a NumPy array and a Pandas DataFrame?

2. Explain the concept of vectorization in NumPy and its advantages.

3. What are the different types of data structures in Pandas?

4. What is the difference between loc[] and iloc[] in Pandas?

5. How does Pandas handle missing values in a dataset?

6. What is the difference between line plot, bar plot, and scatter plot in Matplotlib?

7. What are the advantages of using NumPy for numerical computation?

8. What is the purpose of groupby() function in Pandas?

9. How can you customize a plot in Matplotlib (labels, title, legend, etc.)?

10. Explain the concept of data aggregation in Pandas.



11
Ex:No:3 Implement linear models to approximate the given data.
Date:
Aim
 To implement a simple linear regression model to approximate the given data.

Procedure

 Initialize the environment in Google Colab by importing required Python libraries for
numerical computation, data handling, visualization, and linear regression modeling.
 Load the dataset using pandas.read_csv() and handle missing numerical values by
replacing them with the mean of the respective columns.
 Select the variables for regression, where Age is chosen as the independent variable (X)
and MMSE as the dependent variable (y).
 Split the dataset into training and testing sets using the train-test split method with 80%
data for training and 20% for testing.
 Create and train a Simple Linear Regression model using the training data to learn the
linear relationship between Age and MMSE.
 Predict MMSE values for the test dataset and compute model parameters such as slope
and intercept.
 Evaluate the model performance using Mean Squared Error (MSE) and R² score to
measure prediction accuracy.
 Visualize the regression results using a scatter plot and regression line, and predict the
MMSE value for a new input age.

SAMPLE PROGRAM
import numpy as np
import pandas as pd
import [Link] as plt
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LinearRegression
from [Link] import mean_squared_error, r2_score
df = pd.read_csv('/content/oasis_cross-[Link]')
[Link]([Link](numeric_only=True), inplace=True)
X = df[['Age']]
y = df['MMSE']
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
model = LinearRegression()
[Link](X_train, y_train)
y_pred = [Link](X_test)

12
print("Slope:", model.coef_[0])
print("Intercept:", model.intercept_)
print("Mean Squared Error:", mean_squared_error(y_test, y_pred))
print("R2 Score:", r2_score(y_test, y_pred))
[Link](X_test, y_test)
[Link](X_test, y_pred)
[Link]('Age')
[Link]('MMSE')
[Link]('Simple Linear Regression')
age_value = [Link]({'Age': [70]})
print("Predicted MMSE for Age 70:", [Link](age_value)[0])
[Link]()

SAMPLE INPUT OUTPUT

Slope: -0.011149810153846043
Intercept: 27.620509691535073
Mean Squared Error: 6.2823540963309625
R2 Score: -0.005917905915383326
Predicted MMSE for Age 70: 26.84002298076585

13
 EXERCISE PROBLEMS
1. Basic Linear Regression
Write a Python program to implement Simple Linear Regression using the dataset:

Task:
Fit a linear model y=mx+cy = mx + cy=mx+c
Find the slope (m) and intercept (c)
Predict the value of Y when X = 6
2. Linear Model using NumPy
Write a Python program to implement linear regression using NumPy for the following
data:

Task:
 Train the linear model
 Plot the best fit line
 Predict marks for 6 hours of study

14
3. Implement a Linear Regression algorithm and evaluate the model performance using
error metrics such as Mean Squared Error.

4. Write a Python program to implement Multiple Linear Regression for predicting output
using more than one input feature.

5. Write a Python program to fit a linear model for given training data and visualize the best
fit line using a graph

VIVA QUESTIONS
1. What is a Linear Model in Machine Learning?

2. What is Linear Regression?

3. Write the equation of a simple linear regression model.

4. What are the main components of the linear regression equation?

5. What is the difference between Simple Linear Regression and Multiple Linear
Regression?

6. What is the role of slope and intercept in a linear model?

7. What is the purpose of using a regression model?

8. What is Mean Squared Error (MSE)?

9. What are the assumptions of Linear Regression?

10. Which libraries are commonly used in Python to implement linear regression?

11. What is the difference between R² score and Mean Squared Error in evaluating a
regression model?
12. Why is it important that independent variables should not be highly correlated in
Multiple Linear Regression?
13. How does gradient descent help in finding optimal parameters in linear models?

14. What happens if the relationship between variables is not linear but we still apply linear
regression?

15. Why do we split data into training and testing sets while building a regression model?

15
Ex:No:4
Information Gain and Gain Ratio to find the best attribute.
Date:
Aim
● To find the attribute with maximum information gain and gain ratio for the given dataset.

Procedure
A spanning tree is one in which all the vertices must be connected. The two disjoint subsets of
vertices must be connected to make a Spanning Tree. They must be connected with the
minimum weight edge to make it a Minimum Spanning Tree.

Algorithm:
Step-01:
a) Randomly choose any vertex.
b) The vertex connecting to the edge having least weight is usually selected.
Step-02:
a) Find all the edges that connect the tree to new vertices.
b) Find the least weight edge among those edges and include it in the existing tree.
c) If including that edge creates a cycle, then reject that edge and look for the next least weight
edge.
Step-03:
a) Keep repeating step-02 until all the vertices are included and Minimum Spanning Tree (MST)
is obtained.

EXERCISE PROBLEMS
1. Write a program to construct the minimum spanning tree (MST) for the given graph
using Prim’s Algorithm.

ALGORITHM:
 Start with a connected, weighted graph.
 Select any vertex as the starting point.
 Initialize the key values of all vertices to infinity (∞), except the starting vertex (set to 0).
 Mark all vertices as unvisited initially.
 Repeat for all vertices:
o Pick the unvisited vertex with the smallest key value.
o Mark it as visited.
o Update its neighboring vertices' key values if a smaller weight edge is found.
 Store the edges forming the MST using a parent array.
 Print the edges and total weight of the Minimum Spanning Tree (MST).
 End.

PROGRAM:
#include <stdio.h>

16
#include <limits.h>
#include <conio.h>
#define MAX 10

int findMinVertex(int key[], int visited[], int vertices) {

int min = INT_MAX, minIndex,i;
for (i = 0; i < vertices; i++) {
if (!visited[i] && key[i] < min) {
min = key[i];
minIndex = i;
}
}
return minIndex;
}

void primsAlgorithm(int graph[MAX][MAX], int vertices) {

int parent[MAX];
int key[MAX];
int visited[MAX] = {0};
int totalCost = 0,i,v,u;

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

key[i] = INT_MAX;
}
key[0] = 0;
parent[0] = -1;

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

u = findMinVertex(key, visited, vertices);
visited[u] = 1;

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

if (graph[u][v] && !visited[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}

printf("Edge \tWeight\n");
for (i = 1; i < vertices; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
totalCost += graph[i][parent[i]];
}
printf("Total Cost: %d\n", totalCost);
}

17
void main() {
int graph[MAX][MAX], vertices,i,j;
clrscr();
printf("Enter number of vertices: ");
scanf("%d", &vertices);

printf("Enter adjacency matrix:\n");

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

primsAlgorithm(graph, vertices);
getch();
}

OUTPUT:

Enter number of vertices: 5

Enter adjacency matrix:
02060
20385
03007
68009
05790
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
Total Cost: 16

1. Write a program to construct the minimum spanning tree (MST) for the given graph using
Kruskal’s Algorithm.

ALGORITHM:
 Start with a connected, weighted graph.
 Sort all edges in ascending order of weight.
 Initialize an empty Minimum Spanning Tree (MST).
 Pick the smallest edge and check if it forms a cycle with the MST using the Disjoint Set
(Union-Find).
 If no cycle, add the edge to the MST.
 Repeat until we have (V - 1) edges in the MST (where V = number of vertices).

18
 Print the edges and total cost of the MST.
 End.

PROGRAM:
#include <stdio.h>
//#include <conio.h>
#define MAX 10
int parent[MAX];
int find(int i) {
while(parent[i] != i)
i = parent[i];
return i;
}
void unionSets(int i, int j) {
int a = find(i);
int b = find(j);
parent[a] = b;
}
void kruskalMST(int cost[MAX][MAX], int n) {
int minCost = 0, i, j, u, v, a, b, min, edgeCount = 0;
for(i = 0; i < n; i++)
parent[i] = i;
printf("\nEdges in Minimum Spanning Tree:\n");
while(edgeCount < n - 1) {
min = 9999;
a = -1;
b = -1;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
if(cost[i][j] < min && find(i) != find(j)) {
min = cost[i][j];
a = i;
b = j;
}
}
}
if(a != -1 && b != -1) {
unionSets(a, b);
printf("Edge %d: (%d - %d) Cost: %d\n", edgeCount + 1, a + 1, b + 1, min);
minCost += min;
edgeCount++;

19
 cost[a][b] = cost[b][a] = 9999;
}
}
printf("\nTotal cost of Minimum Spanning Tree: %d\n", minCost);
}
void main() {
int cost[MAX][MAX], n, i, j;
//clrscr();
printf("Kruskal's Algorithm - Minimum Spanning Tree\n");
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix (use 9999 for no edge):\n");
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
}
}
kruskalMST(cost, n);
//getch();
}

OUTPUT:

Enter number of vertices: 4

Enter adjacency matrix (use 9999 for no edge):
0 1 3 9999
1024
3205
9999 4 5 0
Kruskal's Algorithm - Minimum Spanning Tree
Enter number of vertices: 4
Enter adjacency matrix (use 9999 for no edge):
Edges in Minimum Spanning Tree:
Edge 1: (1 - 2) Cost: 1
Edge 2: (2 - 3) Cost: 2
Edge 3: (2 - 4) Cost: 4

Total cost of Minimum Spanning Tree: 7

[Link] the program for warshall algoriothm.

ALGORITHM:
 Start with the given adjacency matrix.
 Use each node as an intermediate node → for (k = 0; k < n; k++)

20
  Check all starting nodes → for (i = 0; i < n; i++)
 Check all ending nodes → for (j = 0; j < n; j++)
 Update the shortest path if a better path is found → D[i][j] = min(D[i][j], D[i][k] +
D[k][j]);
 Repeat until all shortest paths are found.
 Print the final matrix with shortest paths.

PROGRAM:
#include <stdio.h>
#include <conio.h>
#define MAX 10
void warshall(int graph[MAX][MAX], int n) {
int k,i,j;
for ( k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);
}
}
}
}
void printMatrix(int graph[MAX][MAX], int n) {
int i,j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
}
void main() {
int n, graph[10][10],i,j;
clrscr();
printf("Warshall Algorithm\n");
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for (i = 0; i < n; i++) {
for ( j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
warshall(graph, n);
printf("Transitive Closure :\n");
printMatrix(graph, n);
getch();

21
}

OUTPUT:

Enter number of vertices: 4

Enter adjacency matrix:
1101
0110
0011
1001
Transitive Closure :
1111
0111
0011
1111

[Link] a program for Floyd warshall algorithm.

ALGORITHM:
 Initialize the distance matrix dist[i][j] = graph[i][j] for all edges, and dist[i][j] = INF for
no edge.
 Iterate over all intermediate nodes: for (k = 0; k < n; k++)
 Check all pairs of nodes: for (i = 0; i < n; i++)
 For each pair of nodes (i, j), check if going through node k gives a shorter path:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
 Repeat the process for all intermediate nodes.
 The final matrix dist[i][j] contains the shortest path from node i to node j.

PROGRAM:
#include<stdio.h>
#include<conio.h>
#define MAX 10
#define INF 999
void printMatrix(int n, int dist[MAX][MAX]) {
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (dist[i][j] == INF)
printf("INF ");
else
printf("%d ", dist[i][j]);
}
printf("\n");
}
}
void floydWarshall(int n, int graph[MAX][MAX]) {

22
int dist[MAX][MAX];
int i, j, k;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (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");
printMatrix(n, dist);
}
void main() {
int n, i, j;
int graph[10][10];
clrscr();
printf("Floyd Warshall\n");
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix(9999 for infinity):\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
floydWarshall(n, graph);
getch();
}

OUTPUT:

Enter the number of vertices: 4

Enter the adjacency matrix (9999 for infinity):
0 3 9999 7
9999 0 2 4
9999 9999 0 5

23
2 9999 9999 0
Floyd Warshall
Shortest distances between every pair of vertices:
0357
5024
7 10 0 5
2570
5. Write a program using of knapsack algorithm.

ALGORITHM:
 Create a table dp[i][w], where i is the number of items and w is the weight capacity of
the knapsack.
 Initialize
Set dp[0][w] = 0 for all w (0 items → 0 value), and dp[i][0] = 0 for all i (0 capacity → 0
value).
 Loop through each item: For each item i from 1 to n, where n is the total number of
items.
 Loop through each weight capacity: For each weight capacity w from 0 to W (the
knapsack’s maximum capacity).
 Check if the current item can fit in the knapsack (if weights[i-1] <= w).
 If it fits:
o Choose the maximum value between not including the item (dp[i-1][w]) or
including it (dp[i-1][w - weights[i-1]] + values[i-1]).
 If it doesn’t fit:
o Set dp[i][w] = dp[i-1][w] (carry over the value from the previous item).
 Repeat steps 3-7 for all items and capacities.
 Final result: The maximum value will be in dp[n][W] (the value for n items and
knapsack capacity W).

PROGRAM:
#include <stdio.h>
#include <string.h>
#include<conio.h>
#define MAX 100
int knapsack(int W, int wt[], int val[], char items[][MAX], int n)
{
int dp[MAX][MAX]; // DP table
int i, w;
int totalProfit;
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i-1] <= w)

24
dp[i][w] = (val[i-1] + dp[i-1][w-wt[i-1]] > dp[i-1][w]) ? (val[i-1] + dp[i-1][w-wt[i-1]]) : dp[i-1]
[w];
else
dp[i][w] = dp[i-1][w];
}
}
totalProfit = dp[n][W];
printf("\nItems included in the knapsack:\n");
w = W;
for (i = n; i > 0 && totalProfit > 0; i--)
{
if (totalProfit != dp[i-1][w]) {
printf("Item: %s, Weight: %d, Profit: %d\n", items[i-1], wt[i-1], val[i-1]);
totalProfit -= val[i-1];
w -= wt[i-1];
}
}
return dp[n][W];
}
void main()
{
int n, W, i;
char items[10][MAX];
int val[20], wt[20];
int maxProfit;
clrscr();
printf("Enter the number of items: ");
scanf("%d", &n);
printf("Enter the capacity of the knapsack: ");
scanf("%d", &W);
for (i = 0; i < n; i++)
{
printf("Enter name of item %d: ", i+1);
scanf("%s", items[i]);
printf("Enter weight of item %d: ", i+1);
scanf("%d", &wt[i]);
printf("Enter profit (value) of item %d: ", i+1);
scanf("%d", &val[i]);
}
maxProfit = knapsack(W, wt, val, items, n);
printf("\nTotal profit of the included items: %d\n", maxProfit);
getch();
}

OUTPUT:
Enter the number of items: 4

25
Enter the capacity of the knapsack: 50
Enter name of item 1: Laptop
Enter weight of item 1: 10
Enter profit (value) of item 1: 60
Enter name of item 2: Phone
Enter weight of item 2: 20
Enter profit (value) of item 2: 100
Enter name of item 3: Headphones
Enter weight of item 3: 30
Enter profit (value) of item 3: 120
Enter name of item 4: Book
Enter weight of item 4: 15
Enter profit (value) of item 4: 50
Items included in the knapsack:
Item: Phone, Weight: 20, Profit: 100
Item: Laptop, Weight: 10, Profit: 60

Total profit of the included items: 160

6. Write a program for Fibonacci series using memorization.

ALGORITHM:

 Initialize an array memo[] to store the results of previously computed Fibonacci

numbers.
 Define a function Fibonacci(n, memo[]):
 If n is 0 or 1, return n (Base case).
 If memo[n] is already computed, return memo[n].
 Otherwise, compute Fibonacci(n-1) + Fibonacci(n-2), store the result in memo[n], and
return memo[n].
 Call the Fibonacci function with the desired value of n.
 Print the result.

PROGRAM:
#include <stdio.h>
#include <conio.h>
#define MAX 100
int memo[MAX];
void initializeMemo() {
int i;
for (i = 0; i < MAX; i++) {
memo[i] = -1;
}
}
int fibonacci(int n) {
if (n <= 1) {
return n;

26
}
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
void main() {
int n;
clrscr();
initializeMemo();
printf("Enter the value of n: ");
scanf("%d", &n);
if (n < 0 || n >= MAX) {
printf("Please enter a number between 0 and %d.\n", MAX - 1);
return 1;
}
printf("Fibonacci of %d = %d\n", n, fibonacci(n-1));
getch();
}

OUTPUT:
Enter the value of n: 10
Fibonacci of 10 = 55
VIVA QUESTIONS
1. Let G be an undirected connected graph with distinct edge weight. Let ‘emax’ be the edge
with maximum weight and ‘emin’ the edge with minimum weight. Justify that if ‘emax’ is in a
minimum spanning tree, then its removal must disconnect G
2. Spanning trees are always acyclic in the case of a spanning tree of a graph G. Justify.
3. Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Justify that Graph
M has 3 distinct minimum spanning trees, each of cost 2.

4. Given an undirected unweighted connected graph consisting of n vertices and m edges. The
task is to find any spanning tree of this graph using Kruskal’s algorithm such that the maximum
degree over all vertices is maximum possible. The order in which you print the output edges does
not matter and an edge can be printed in reverse also i.e. (u, v) can also be printed as (v, u).
Input:
1
/\
2 5
\/
3
|

27
 4
5. Consider a complete graph G with 4 vertices. How many spanning trees does the graph G has?
6. How do you solve the travelling salesman problem using a minimum spanning tree? Explain.
7. Consider a undirected graph G with vertices {A, B, C, D, E}. In graph G, every edge has
distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum
weight. Then, Justify that no minimum spanning tree contains AB is false.
8. Justify the application of minimum spanning tree problem in telephone network. What are the
advantages?.
9. An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi ,
vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A
sample graph with n = 4 is shown below. What will be the cost of the minimum spanning tree
(MST) of such a graph with n nodes?

10. Consider a weighted complete graph G on the vertex set {v1,v2 ,v} such that the weight of
the edge (v,,v) is 2|i-j|. The weight of a minimum spanning tree of G is_____________.

Ex:No:5
DYNAMIC PROGRAMMING
Date:
Aim
Construct the huffman code for the given data. Also perform encoding and decoding (use Greedy
technique).

Procedure
Steps to build Huffman Tree
Input is an array of unique characters along with their frequency of occurrences and output is
Huffman Tree.
1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min
Heap is used as a priority queue. The value of frequency field is used to compare two

28
 nodes in min heap. Initially, the least frequent character is at root)
2. Extract two nodes with the minimum frequency from the min heap.
3. Create a new internal node with a frequency equal to the sum of the two nodes
frequencies. Make the first extracted node as its left child and the other extracted node as
its right child. Add this node to the min heap.
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the
root node and the tree is complete

ALGORITHM
Algorithm Huffman (c)
{
n= |c|

Q=c
for i<-1 to n-1

do
{

temp <- get node ()

left (temp] Get_min (Q) right [temp] Get Min (Q)

a = left [templ b = right [temp]

F [temp]<- f[a] + [b]

insert (Q, temp)

return Get_min (0)

}
PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MAX_TREE_HT 100

struct MinHeapNode {
char data;

29
 float freq;
struct MinHeapNode *left, *right;
};

struct MinHeap {
unsigned size;
unsigned capacity;
struct MinHeapNode **array;
};

struct MinHeapNode* newNode(char data, float freq) {

struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}

struct MinHeap* createMinHeap(unsigned capacity) {

struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct
MinHeapNode*));
return minHeap;
}

void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {

struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}

void minHeapify(struct MinHeap* minHeap, int idx) {

int smallest,left,right;
smallest = idx;
left = 2 * idx + 1;
right = 2 * idx + 2;

if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)

30
 smallest = left;
if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]-
>freq)
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}

struct MinHeapNode* extractMin(struct MinHeap* minHeap) {

struct MinHeapNode* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}

void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {

int i;
i = minHeap->size++;
while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}

struct MinHeap* buildMinHeap(char data[], float freq[], int size) {

int i;
struct MinHeap* minHeap = createMinHeap(size);
for (i = 0; i < size; ++i)
minHeap->array[i] = newNode(data[i], freq[i]);
minHeap->size = size;
for (i = (minHeap->size - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
return minHeap;
}

struct MinHeapNode* buildHuffmanTree(char data[], float freq[], int size) {

31
 struct MinHeapNode *left, *right, *top;
struct MinHeap* minHeap = buildMinHeap(data, freq, size);
while (minHeap->size > 1) {
left = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}

void printCodes(struct MinHeapNode* root, int arr[], int top) {

int i;
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (!(root->left) && !(root->right)) {
printf("%c: ", root->data);
for ( i = 0; i < top; i++)
printf("%d", arr[i]);
printf("\n");
}
}

void HuffmanCodes(char data[], float freq[], int size) {

struct MinHeapNode* root = buildHuffmanTree(data, freq, size);
int arr[MAX_TREE_HT], top = 0;
printCodes(root, arr, top);
}

void main() {
int size,i;
char *data = (char*)malloc(size * sizeof(char));

32
 float *freq = (float*)malloc(size * sizeof(float));
clrscr();
printf("Enter number of characters: ");
scanf("%d", &size);

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

printf("Enter character %d: ", i + 1);
scanf(" %c", &data[i]);
printf("Enter frequency of '%c': ", data[i]);
scanf("%f", &freq[i]);
}

HuffmanCodes(data, freq, size);

free(data);
free(freq);
getch();
}

OUTPUT:
Enter number of characters: 5
Enter character 1: A
Enter frequency of 'A': 0.4
Enter character 2: B
Enter frequency of 'B': 0.3
Enter character 3: C
Enter frequency of 'C': 0.2
Enter character 4: D
Enter frequency of 'D': 0.1
Enter character 5: E
Enter frequency of 'E': 0.05
Huffman Codes:
A: 0
B: 10
C: 110
D: 1110
E: 1111
[Link] a program to implement the Dijkstra Algorithm.

33
ALGORITHM:
1. Start with the source node and set its distance to 0, while all others are infinity (∞).
2. Pick the unvisited node with the smallest distance.
3. Update distances of its neighboring nodes if a shorter path is found.
4. Mark the current node as visited (processed).
5. Repeat steps 2-4 until all nodes are visited or shortest paths are found.

PROGRAM:
#include <stdio.h>
#include <conio.h>
#include <limits.h>

#define V 10

int minDistance(int dist[], int sptSet[], int n) {

int min = INT_MAX, min_index,v;
for ( v = 0; v < n; v++) {
if (!sptSet[v] && dist[v] < min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}

void dijkstra(int graph[V][V], int n, int src) {

int dist[V], sptSet[V],i,count,u,v;
for (i = 0; i < n; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
dist[src] = 0;

for (count = 0; count < n - 1; count++) {

u = minDistance(dist, sptSet, n);
sptSet[u] = 1;
for (v = 0; v < n; v++) {
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v]) {

34
 dist[v] = dist[u] + graph[u][v];
}
}
}

printf("\nVertex \t Distance from Source\n");

for (i = 0; i < n; i++) {
printf("%d \t %d\n", i, dist[i]);
}
}

void main() {
int n, graph[V][V], i, j, source;
clrscr();

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter adjacency matrix:\n");

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

printf("Enter source vertex: ");

scanf("%d", &source);

dijkstra(graph, n, source);

getch();
}

OUTPUT:
Enter number of vertices: 5
Enter adjacency matrix:
0 10 0 30 100
10 0 50 0 0
0 50 0 20 10
30 0 20 0 60

35
100 0 10 60 0
Enter source vertex: 0
Vertex Distance from Source
0 0
1 10
2 50
3 30
4 60

VIVA QUESTIONS
1. Calculate the time complexity of Huffman code algorithm.
2. Consider the following message BCCABBDDAECCBBAEDDCC find the no of bits
requiered for huffman encoding of above message.
3. The following message is: GATE2018GAATTTEEEE22000011188What is the average
length of bits required for encoding each letter using Huffman coding___?
4. Is there any difference in between draw tree for huffman coding and optimal merge pattern if
yes please give detailed explanation.
5. What would be huffman coding for following : CharacterFrequencya10l15i12o3u4s13t1.
1. Which of the following data structure cannot be used for efficient implementation of Huffman
encoding? a. Binary min heap b. Binary max heap [Link] tree (height balanced tree)
7. What is the time complexity of Huffman algorithms when the input is already sorted
8. Compare dynamic programming with divide and conquer.
9. Compare dynamic programming with greedy method.
10. A file contain charecters a,e,i,o,u,s,t with frequencies 10,15,12,3,4,13,&1 respectively , if we
use huffman codeing for data compression then avg code length will be ______.

36
Ex:No:6 IMPLEMENT SUM OF SUBSETS PROBLEM USING
Date: BACKTRACKING
Aim
● To solve sum of subset problem using backtracking.

Procedure
Sum of Subsets:
In this problem, there is a given set with some integer elements. And another some value is
also provided, we have to find a subset of the given set whose sum is the same as the given sum
value.
Here backtracking approach is used for trying to select a valid subset when an item is not
valid, we will backtrack to get the previous subset and add another element to get the solution.

ALGORITHM
Algorithm SumOfSub(s, k, r)
{ k-1 n
// s = ∑ w[j] * x[j]; r = ∑ w[j];
j=1 j=k
// w[j]’s are in non-decreasing order

// Generate left child

x[k] := 1;
if (s+w[k] = m) then
write ( x[1:k] ); // subset found
else
SumOfSub (s+w[k], k+1, r-w[k]);

// Generate right child

if ((s+r-w[k] >= m) and (s+w[k+1] <= m)) then
{
x[k]:=0;
SumOfSub (s, k+1, r-w[k]);
}
}

EXERCISE PROBLEMS
1. Write a program to implement sum of subsets problem using backtracking.

Subset Sum Problem Algorithm

37
 Step 1: Input the number of elements n, the elements of the array arr[n], and the target
sum.
Step 2: Initialize an empty array subset[n] to store the current subset.
Step 3: Call the recursive function find_subsets with the following parameters:
 arr[]: The input array.
 n: Number of elements in the array.
 target: Desired sum.
 index: Current index in the array (starting from 0).
 subset[]: Current subset being formed.
 subset_size: Current size of the subset (starting from 0).
 current_sum: Sum of elements in the current subset (starting from 0).
Step 4: In the recursive function find_subsets:
 a. Base Case 1: If current_sum == target, print the current subset.
 b. Base Case 2: If index == n or current_sum > target, return (no further subset
possible).
 c. Recursive Case:
o Include arr[index] in the subset and recursively call the function with
index + 1, updating subset_size and current_sum.
o Exclude arr[index] and recursively call the function with index + 1
without changing subset_size or current_sum.
Step 5: The recursion explores all possible combinations of the array elements to find
subsets that sum up to the target.

CODE

#include <stdio.h>

void find_subsets(int arr[], int n, int target, int index, int subset[], int subset_size, int
current_sum) {
if (current_sum == target) {
printf("Subset found: { ");
for (int i = 0; i < subset_size; i++) {
printf("%d ", subset[i]);
}
printf("}\n");
return;
}

if (index == n || current_sum > target) {

38
 return;
}

subset[subset_size] = arr[index];
find_subsets(arr, n, target, index + 1, subset, subset_size + 1, current_sum +
arr[index]);

find_subsets(arr, n, target, index + 1, subset, subset_size, current_sum);

}

int main() {
int n, target;

printf("Enter number of elements: ");

scanf("%d", &n);

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

printf("Enter target sum: ");

scanf("%d", &target);

int subset[n];
printf("Subsets with sum %d:\n", target);
find_subsets(arr, n, target, 0, subset, 0, 0);

return 0;
}

OUTPUT
Enter number of elements: 5
Enter elements: 3 3 4 2 5
Enter target sum: 5
Subsets with sum 5:
Subset found: { 3 2 }
Subset found: { 3 2 }

39
 Subset found: { 5 }

2. Write a program to implement Hamiltonian cycle problem using backtracking.

Hamiltonian Cycle Algorithm (Backtracking Approach)

Step 1: Input the number of vertices v and the adjacency matrix graph[v][v].
Step 2: Initialize an array path[v] to keep track of the current path. Set all elements to -1
(indicating unvisited vertices).
Step 3: Set the starting vertex as path[0] = 0.
Step 4: Call the recursive function hamiltonianCycleUtil to find the Hamiltonian cycle.
Step 5: In the recursive function:
 a. If pos == v, check if the last vertex is connected to the first vertex
(graph[path[pos - 1]][path[0]] == 1).
o If true, print the Hamiltonian cycle.
o If false, backtrack.
 b. For each vertex v from 1 to v-1:
o Check if it's safe to add vertex v to the current path:
 It must be connected to the previous vertex.
 It must not already be in the current path.
o If safe:
 Add vertex v to path[pos].
 Recursively call hamiltonianCycleUtil with pos + 1.
 If the recursion fails, backtrack (remove v from path[pos]).
Step 6: If a Hamiltonian cycle is found, print the cycle. If no cycle exists, print "No
Hamiltonian Cycle found."

CODE
#include <stdio.h>
#include <conio.h>
#define MAX 10

void printCycle(int path[], int v) {

int i;
printf("Hamiltonian Cycle: ");
for (i = 0; i < v; i++)
printf("%d ", path[i]);
printf("%d\n", path[0]);
}

40
int isSafe(int v, int graph[MAX][MAX], int path[], int pos) {
int i;
if (graph[path[pos - 1]][v] == 0)
return 0;

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

if (path[i] == v)
return 0;

return 1;
}

int hamiltonianCycleUtil(int graph[MAX][MAX], int path[], int pos, int v) {

int vertex;
if (pos == v) {
if (graph[path[pos - 1]][path[0]] == 1) {
printf("Final step: %d -> %d (Back to start)\n", path[pos - 1], path[0]);
return 1;
}
return 0;
}

for (vertex = 1; vertex < v; vertex++) {

if (isSafe(vertex, graph, path, pos)) {
path[pos] = vertex;
printf("Moving to vertex: %d (Step %d)\n", vertex, pos + 1);

if (hamiltonianCycleUtil(graph, path, pos + 1, v))

return 1;

path[pos] = -1;
printf("Backtracking from vertex: %d (Step %d)\n", vertex, pos + 1);
}
}
return 0;
}

void hamiltonianCycle(int graph[MAX][MAX], int v) {

int path[MAX],i;
for (i = 0; i < v; i++)

41
 path[i] = -1;

path[0] = 0;
printf("Starting at vertex 0\n");

if (hamiltonianCycleUtil(graph, path, 1, v) == 0) {
printf("No Hamiltonian Cycle found\n");
return;
}

printCycle(path, v);
}

int main() {
int v,graph[MAX][MAX],i,j;
clrscr();
printf("hameltonion cycle\n");
printf("Enter the number of vertices: ");
scanf("%d", &v);
printf("Enter the adjacency matrix (%dx%d):\n", v, v);
for (i = 0; i < v; i++)
for ( j = 0; j < v; j++)
scanf("%d", &graph[i][j]);

hamiltonianCycle(graph, v);
return 0;
}

OUTPUT

hameltonion cycle
Enter the number of vertices: 5
Enter the adjacency matrix (5x5):
01010
10100
01011
10101
00110
Starting at vertex 0
Moving to vertex: 1 (Step 2)

42
 Moving to vertex: 2 (Step 3)
Moving to vertex: 3 (Step 4)
Moving to vertex: 4 (Step 5)
Backtracking from vertex: 4 (Step 5)
Backtracking from vertex: 3 (Step 4)
Moving to vertex: 4 (Step 4)
Moving to vertex: 3 (Step 5)
Final step: 3 -> 0 (Back to start)
Hamiltonian Cycle: 0 1 2 4 3 0
VIVA QUESTIONS
1. “Dynamic problem solution of sum of subset problem is faster than recursive solution in terms
of time complexity”. How?
2. Under what condition any set A will be a subset of B”.
3. Can you apply backtracking to solve sudoku puzzle? Explain.
4. A n x n board is made in a way so that 1 or 0 can be placed in each box where 1 is for valid
path for moving towards exit and 0 is the closed path. Find the path to exit using backtracking
algorithm.

5. How many unique colors will be required for proper vertex coloring of an empty graph having
n vertices?
6. How many unique colors will be required for proper vertex coloring of a line graph having n
vertices?
7. “In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles
through any fixed edge is always even.” Justify.
8. How many Hamiltonian paths does the following graph have?

9. You are studying for an exam and you have to study N questions. The questions take {t1, t2,

43
t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum
of T hours. You can either study a question or leave it. Choose the questions in such a way that
your score is maximized
10. You are given a knapsack that can carry a maximum weight of 60. There are 4 items with
weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items
you can carry using the knapsack? How do you apply backtracking to this problem?

Ex:No:7 TRAVELLING SALESMAN PROBLEM USING BRANCH

Date: AND BOUND
Aim
● Solve the travelling salesman problem of the given graph using branch and bound
technique.

Procedure
Branch and Bound
Branch and bound is an algorithm design paradigm which is generally used for solving
combinatorial optimization problems. These problems are typically exponential in terms of time
complexity and may require exploring all possible permutations in worst case. The Branch and
Bound Algorithm technique solves these problems relatively quickly.
Travelling salesman problem
You are given-
 A set of some cities
 Distance between every pair of cities

Travelling Salesman Problem states-

 A salesman has to visit every city exactly once.
 He has to come back to the city from where he starts his journey.
 What is the shortest possible route that the salesman must follow to complete his tour?

ALGORITHM

1. Draw and initialize the root node (see below for details).
2. Repeat the following step until a solution (i.e., a complete circuit, represented by a
terminal node) has been found and no unexplored non-terminal node has a smaller bound
than the length of the best solution found: – Choose an unexplored non-terminal node
with the smallest bound, and process it (see page 2 for details about this step).

44
 3. When a solution has been found and no unexplored non-terminal node has a smaller
bound than the length of the best solution found, then the best solution found is optimal.

EXERCISE PROBLEMS
[Link] a program to solve travelling salesman problem by using branch and bound method.

Travelling Salesman Problem (TSP) Algorithm

Step 1: Input the number of cities N.

Step 2: Input the cost matrix costMatrix[N][N].
Step 3: Initialize minCost = INT_MAX and visited[N] = {0}.
Step 4: Define a recursive function tsp(start, currentCity, visited, count, currentCost):
 Base Case: If all cities are visited and a return path exists, update minCost if the
current cost is lower.
 Recursive Case: For each unvisited city with a path, mark it as visited, recurse, then
backtrack.
Step 5: Start recursion with tsp(0, 0, visited, 1, 0).
Step 6: Output minCost as the minimum traveling cost.

CODE
#include <stdio.h>
#include <limits.h>
#include <conio.h>
#define MAX 10

int N;
int costMatrix[MAX][MAX];
int minCost = INT_MAX;

int isAvailable(int city, int visited[]) {

return !visited[city];
}

void tsp(int start, int currentCity, int visited[], int count, int currentCost) {
int city;
if (count == N && costMatrix[currentCity][start]) {
if (currentCost + costMatrix[currentCity][start] < minCost) {
minCost = currentCost + costMatrix[currentCity][start];
}
return;

45
 }

for (city = 0; city < N; city++) {

if (isAvailable(city, visited) && costMatrix[currentCity][city]) {
visited[city] = 1;
tsp(start, city, visited, count + 1, currentCost + costMatrix[currentCity][city]);
visited[city] = 0;
}
}
}

void main() {
int visited[MAX] = {0}, i,j;
clrscr();
printf("Enter the number of cities: ");
scanf("%d", &N);

printf("Enter the cost matrix (%d x %d):\n", N, N);

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

visited[0] = 1;
tsp(0, 0, visited, 1, 0);

printf("Minimum Travelling Cost: %d\n", minCost);

getch();
}

OUTPUT
Enter the number of cities: 5
Enter the cost matrix (5 x 5):
03158
30679
16042
57403
89230
Minimum Travelling Cost: 16

46
[Link] Job Assignment Problem

Algorithm For Job Assignment Problem

Step 1: Input the number of workers/jobs N.

Step 2: Input the cost matrix costMatrix[N][N], where costMatrix[i][j] represents the cost
of assigning worker i to job j.
Step 3: Initialize minCost to INT_MAX to keep track of the minimum assignment cost.
Step 4: Create an array assignedJobs[N] and initialize all elements to 0 (indicating that
no jobs are assigned yet).
Step 5: Define a recursive function assignJobs(worker, assignedJobs, currentCost) to
explore all job assignments:
 If worker == N (all workers are assigned):
o If currentCost < minCost, update minCost with currentCost.
o Return to the previous recursive step.
 Else: For each job j from 0 to N-1:
o If assignedJobs[j] == 0 (job is available):
 Assign job j to the current worker (assignedJobs[j] = 1).
 Recursively call assignJobs(worker + 1, assignedJobs,
currentCost + costMatrix[worker][j]).
 Backtrack: After recursion, unassign the job (assignedJobs[j]
= 0).
Step 6: Start the recursive process by calling assignJobs(0,
assignedJobs, 0).
Step 7: After recursion completes, output the minimum
assignment cost stored in minCost.

CODE
#include <stdio.h>
#include <limits.h>
#define MAX 10
int minCost = INT_MAX;
int costMatrix[MAX][MAX];
int N;

int isAvailable(int job, int assignedJobs[]) {

return !assignedJobs[job];
}

47
 void assignJobs(int worker, int assignedJobs[], int currentCost) {
int job;
if (worker == N) {
if (currentCost < minCost) {
minCost = currentCost;
}
return;
}

for (job = 0; job < N; job++) {

if (isAvailable(job, assignedJobs)) {
assignedJobs[job] = 1;
assignJobs(worker + 1, assignedJobs, currentCost + costMatrix[worker][job]);
assignedJobs[job] = 0;
}
}
}

void main() {
int assignedJobs[MAX] = {0},i,j;

printf("Enter the size of the cost matrix: ");

scanf("%d", &N);

printf("Enter the cost matrix (%d x %d):\n", N, N);

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

assignJobs(0, assignedJobs, 0);

printf("Minimum Assignment Cost: %d\n", minCost);

}
OUTPUT

48
 Enter the size of the cost matrix: 3
Enter the cost matrix (3 x 3):
934
784
10 5 2
Minimum Assignment Cost: 12

VIVA QUESTIONS
1. Which data structure is most suitable for implementing best first branch and bound strategy?

3. What is the time complexity of travelling salesman problem?

4. Compute the time efficiency of job assignment problem.
5. Why is branch and bound less efficient than backtracking? Explain
6. “Branch and bound can traverse in DFS as well as BFS manner whereas backtracking
traverses only in DFS manner.”
7. Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of
different Hamiltonian cycles in G is equal to _____.
8. Which of the following problems is not NP-hard?
a. Hamiltonian circuit problem
b. The 0/1 Knapsack problem
c. Finding bi-connected components of a graph
d. The graph coloring problem
11. Which type of algorithm is used to solve the "8 Queens" problem ?
12. Find all the possible solution for sum of subset problem for the instance m=35 and
S=<1,2,5,7,8,10,15,20,25 using Backtracking.

49
50