LAB MANUAL

Lab Name : Analysis of Algorithms Lab

Lab Code : 5CS4-23
Branch : Computer Science & Engineering
Year (B.Tech.) : III Year/IV Sem

Global Institute of Technology, Jaipur

Department of Computer Science& Engineering

(Rajasthan Technical University, KOTA)

5CS4-23: Analysis of Algorithms

 INDEX

S No. CONTENT
RTU Syllabus
1.
Do’s & Don’ts
2.

3. Instructions to the Students

4. PEO/ PO/PSO/CO

5. Lab Plan

Experiment as per RTU Syllabus

1. Sort a given set of elements using the Quicksort method and determine the
time required to sort the elements. Repeat the experiment for different values
of n, the number of elements in the list to be sorted and plot a graph of the
time taken versus n. The elements can be read from a file or can be generated
using the random number generator.

2. Implement a parallelized Merge Sort algorithm to sort a given set of elements

and determine the time required to sort the elements. Repeat the experiment
for different values of n, the number of elements in the list to be sorted and
plot a graph of the time taken versus n. The elements can be read from a file or
can be generated using the random number generator.
3. a. Obtain the Topological ordering of vertices in a given digraph. b. Compute
the transitive closure of a given directed graph using Warshall's algorithm.
4. Implement 0/1 Knapsack problem using Dynamic Programming.
5. From a given vertex in a weighted connected graph, find shortest paths to
other vertices using Dijkstra's algorithm
6. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's
algorithm..
7. a. Print all the nodes reachable from a given starting node in a digraph using
BFS method. b. Check whether a given graph is connected or not using DFS
Method.
8. Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s
algorithm.
9. Implement All-Pairs Shortest Paths Problem using Floyd's algorithm.
10. Implement N Queen's problem using Back Tracking.

Experiment Beyond Syllabus

Write a program to find the longest common subsequence.

1.
Write a program for pattern matching.
2.

5CS4-23: Analysis of Algorithms

 Detailed Syllabus

LAB NAME:- Analysis of Algorithms Lab

Class: IV Sem. B.Tech. Evaluation
Branch: CSE Examination Time = Three (3) Hours
Schedule per Week Maximum Marks =100
Practical Hrs : 2 hr/week [ Sessional (60) & End-term (40) ]

S. No. List of Experiments as per RTU Syllabus

1 Sort a given set of elements using the Quicksort method and determine the
time required to sort the elements. Repeat the experiment for different
values of n, the number of elements in the list to be sorted and plot a graph
of the time taken versus n. The elements can be read from a file or can be
generated using the random number generator.
2 Implement a parallelized Merge Sort algorithm to sort a given set of
elements and determine the time required to sort the elements. Repeat the
experiment for different values of n, the number of elements in the list to be
sorted and plot a graph of the time taken versus n. The elements can be read
from a file or can be generated using the random number generator..
3 a. Obtain the Topological ordering of vertices in a given digraph.
b. Compute the transitive closure of a given directed graph using
Warshall's algorithm.
4. Implement 0/1 Knapsack problem using Dynamic Programming.

5. From a given vertex in a weighted connected graph, find shortest paths to

other vertices using Dijkstra's algorithm.

6. Find Minimum Cost Spanning Tree of a given undirected graph using

Kruskal's algorithm.
7. a. Print all the nodes reachable from a given starting node in a digraph using
BFS method.
b. Check whether a given graph is connected or not using DFS method.
8. Find Minimum Cost Spanning Tree of a given undirected graph using
Prim’s algorithm.
9. Implement All-Pairs Shortest Paths Problem using Floyd's algorithm

10. Implement N Queen's problem using Back Tracking.

5CS4-23: Analysis of Algorithms

 DO’S AND DONT’S

DO’s
1. Please switch off the Mobile/Cell phone before entering Lab.
2. Enter the Lab with complete source code and data.
3. Check whether all peripheral are available at your desktop before proceeding for program.
4. Intimate the lab In-charge whenever you are incompatible in using the system or in case
software get corrupted/ infected by virus.
5. Arrange all the peripheral and seats before leaving the lab.
6. Properly shut down the system before leaving lab.
7. Keep the bag outside in the racks.
8. Enter the lab on time and leave at proper time.
9. Maintain the decorum of the lab.
10. Utilize lab hours in the corresponding experiment.
11. Get your CD/Pen drive checked by lab in charge before using it in the lab.

DONT’S
1. No one is allowed to bring storage devices like Pan Drive /Floppy etc. in the lab.
2. Don’t mishandle the system.
3. Don’t leave the system on standing for long
4. Don’t bring any external material in the lab.
5. Don’t make noise in the lab.
6. Don’t bring the mobile in the lab. If extremely necessary then keep ringers off.
7. Don’t enter in the lab without permission of lab In-charge.
8. Don’t litter in the lab.
9. Don’t delete or make any modification in system files. Don’t carry any lab equipments
outside the lab.

5CS4-23: Analysis of Algorithms

 INSTRUCTIONS TO THE STUDENTS

General Instructions
 Maintain separate observation copy for each laboratory.
 Observations or readings should be taken only in the observation copy.
 Get the readings counter signed by the faculty after the completion of the experiment.
 Maintain Index column in the observation copy and get the signature of the faculty before
leaving the lab.

Before entering in the Lab

 All the students are supposed to prepare the theory regarding the next program.
 Students are supposed to bring the practical file and the lab copy.
 Previous programs should be written in the practical file.
 Algorithm of the current program should be written in the lab copy.
 Any student not following these instructions will be denied entry in the lab.

While working in the Lab

 Adhere to experimental schedule as instructed by the lab incharge.
 Get the previously executed program signed by the instructor.
 Get the output of the current program checked by the instructor in the lab copy.
 Each student should work on his/her assigned computer at each turn of the lab.
 Take responsibility of valuable accessories.
 Concentrate on the assigned practical and do not play games.
 If anyone caught red handed carrying any equipment of the lab, then he will have to face
serious consequences.

Before Leaving the Lab

 The equipments/components should be returned back to the lab assistant in good condition
after the completion of the experiment.
 The students should get the signature from the faculty in the observation copy.
 They should also check whether their file is checked and counter signed in the index.

5CS4-23: Analysis of Algorithms

 Department of computer Science & Engineering

List of Program Educational Objectives (PEO)

Core Competence and Successful Career The Graduate of Computer Science and
Engineering shall be able to pursue successfully career as Technical Leaders and
Managers, Software Engineers, Product Developers, Consultants, Entrepreneurs
PEO-1
and to prepare them for Higher Studies and research

Life Long Learning: The Graduate of Computer Science & Engineering shall be
able to learn, innovate, and evolve new technology lifelong.
PEO-2

Professionalism:-Graduates of Computer Science & Engineering of the program

shall have professional and ethical attitude, communication skills,

PEO-3 multidisciplinary approach and competence to relate engineering issues to broader

social perspective.

5CS4-23: Analysis of Algorithms

 List of Program Outcomes

Engineering Knowledge: Apply knowledge of mathematics and science,

PO-1 with fundamentals of Engineering to be able to solve complex engineering
problems related.
Problem Analysis: Identify, Formulate, review research literature and
PO-2 analyze complex engineering problems and reaching substantiated
conclusions using first principles of mathematics, natural sciences and
engineering sciences.
Design/Development of solutions: Design solutions for complex engineering
PO-3 problems and design system components or processes that meet the specified
needs with appropriate consideration for the public health and safety and the
cultural societal and environmental considerations.
Conduct Investigations of Complex problems: Use research–based
PO-4 knowledge and research methods including design of experiments, analysis
and interpretation of data, and synthesis of the information to provide valid
conclusions.
Modern Tool Usage: Create, Select and apply appropriate techniques,
PO-5 resources and modern engineering and IT tools including prediction and
modeling to complex engineering activities with an understanding of the
limitations.
The Engineer and Society: Apply Reasoning informed by the contextual
PO-6 knowledge to assess societal, health, safety, legal and cultural issues and the
consequent responsibilities relevant to the professional engineering practice.
Environment and Sustainability: Understand the impact of the professional
PO-7 engineering solutions in societal and environmental contexts and demonstrate
the knowledge of, and need for sustainable development.
PO-8 Ethics: Apply Ethical Principles and commit to professional ethics and
responsibilities and norms of the engineering practice.
PO-9 Individual and Team Work: Function effectively as an individual and as a
member or leader in diverse teams and in multidisciplinary Settings.
Communication: Communicate effectively on complex engineering
activities with the engineering community and with society at large such as
PO-10 able to comprehend and with write effective reports and design
documentation, make effective presentations and give and receive clear
instructions.
Project Management and Finance: Demonstrate knowledge and
PO-11 understanding of the engineering management principles and apply these to
one’s own work, as a member and leader in a team, to manage projects and in
multi disciplinary environments.
Life-Long Learning: Recognize the need for and have the preparation and
PO-12 ability to engage in independent and life-long learning the broadest context of
technological change.

5CS4-23: Analysis of Algorithms

 List of Program Specific Outcomes (PSO)
Knowledge Enhancement in Computing: The ability to interpret the foundation
and strategy of hardware and software of computer systems. Graduates can solve the
PSO-
problems in the areas related to algorithms, multimedia, data analytics, cloud
1
computing, human computer interface, robotics, artificial intelligence and
networking for efficient design of computer systems.
Software Design and Development: The ability to understand the software
PSO- development lifecycle and methodologies of software systems. Graduate will learn
2 competent skills and knowledge of software design process. Graduate will be
acquaintance to practical proficiency with a broad area of programming concepts.

COURSE OUTCOMES:

The study of subject Data Structures and algorithms 3CS4-21 in undergraduate program in
Computer Science Engineering Branch will achieve the following major objectives-
1. This Lab helps the student to understand the need of data structures and how different data
structures are to be implemented.
2. This lab provide ability to apply algorithms to different problems and identify the best
algorithm in terms of space and time.
3. This lab helps the student to choose appropriate algorithms, optimize their implementations,
and evaluate trade-offs between different approaches. This objective encourages critical
thinking and creativity in algorithm design.
4. This lab helps the students to implement various sorting algorithms, search algorithms, data
structures (linked lists, trees, graphs, etc.), and analyze their performance in terms of time and
space complexity.

COURSE OUTCOMES TO PROGRAM OUTCOMES MAPPING:

Course Program Outcomes

Objective PO- PO- PO- PO- PO PO PO PO PO PO- P P PSO PSO-

1 13 23 33 42 -5
2 -6
- -7
- -8
- -9
- 10
- O
- O
2 -1
3 23
- -
2 3 3 3 2 2 - - - - - - 2 3 3
1 1
3 3 3 3 2 2 - - - - - - 2 3 3
1 2
4 3 3 3 1 2 - - - - - - 2 2 2

Note: Correlation levels 1, 2 or 3 as defined below:

1: Slight (Low) 2: Moderate (Medium) 3: Substantial (High)

5CS4-23: Analysis of Algorithms

 Program 1

Aim: Sort a given set of elements using the Quicksort method and determine the
time required to sort the elements. Repeat the experiment for different values
of n, the number of elements in the list to be sorted and plot a graph of the
time taken versus n. The details can be read from a file or can be generated
using the random number generator.

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

// Function to exchange two elements

void Exch(int *p, int *q) {
int temp = *p;
*p = *q;
*q = temp;
}

// Function to perform QuickSort

void QuickSort(int a[], int low, int high) {
int i, j, key;
if (low >= high)
return;
key = low;
i = low + 1;
j = high;
while (i <= j) {
while (a[i] <= a[key] && i <= high)
i = i + 1;
while (a[j] > a[key])
j = j - 1;
if (i < j)
Exch(&a[i], &a[j]);
}
Exch(&a[j], &a[key]);
QuickSort(a, low, j - 1);
QuickSort(a, j + 1, high);
}

int main() {
int n, a[1000], k, limit; // Added 'limit' variable
clock_t st, et;
double ts;
clrscr();
printf("\nEnter How many Numbers: ");
scanf("%d", &n);
printf("Enter the upper limit for random numbers: "); // Prompt for limit
scanf("%d", &limit);

5CS4-23: Analysis of Algorithms

 printf("\nThe Random Numbers are:\n");
for (k = 1; k <= n; k++) {
a[k] = rand() % (limit + 1); // Generate numbers within the limit
printf("%d\t", a[k]);
}

st = clock();
QuickSort(a, 1, n);
et = clock();
ts = (double)(et - st) / CLOCKS_PER_SEC;
printf("\nSorted Numbers are: \n ");
for (k = 1; k <= n; k++)
printf("%d\t", a[k]);
printf("\nThe time taken is %e", ts);
getch();
return 0;
}

Output:

Enter How many Numbers: 10

Enter the upper limit for random numbers: 1000
The Random Numbers are:
897 802 765 992 1 521 220 380 729 969
Sorted Numbers are:
1 220 380 521 729 765 802 897 969 992
The time taken is 1.000000e-06

5CS4-23: Analysis of Algorithms

 Viva Questions 1

Q1: What is Quicksort and how does Quicksort choose a pivot?

Ans: Quicksort is a widely used sorting algorithm that employs a divide-and-conquer strategy to sort
elements. It involves selecting a pivot element, partitioning the array around the pivot, and recursively
sorting the sub-arrays on either side of the pivot.
Quicksort commonly chooses the pivot as either the first, last, middle, or a random element from the
array.

Q2: What is the average and worst-case time complexity of Quicksort?

Ans: The average-case time complexity of Quicksort is O(n log n), while the worst-case time
complexity is O(n^2). However, with good pivot selection techniques and optimizations, the worst-
case scenario is rarely encountered.

Q3: What is partitioning in Quicksort?

Ans: Partitioning involves rearranging the elements in the array such that all elements smaller than
the pivot are on the left side, and all elements greater than the pivot are on the right side. The pivot
itself is in its correct sorted position.

Q4: What are some advantages of using Quicksort over other sorting algorithms?
Ans: Quicksort is known for its efficient average-case performance, making it one of the fastest
sorting algorithms for larger datasets. It's also an in-place sorting algorithm, meaning it doesn't require
additional memory for sorting. With proper pivot selection, it can perform better than other O(n log n)
algorithms in practice.

Q5: How can you generate different values of 'n' for the experiment?
Ans: You can manually input different sizes of arrays, read 'n' values from a file containing element
details, or use a random number generator to generate arrays of varying lengths.

5CS4-23: Analysis of Algorithms

 Program 2
Aim: Implement a parallelized Merge Sort algorithm to sort a given set of elements
and determine the time required to sort the elements. Repeat the experiment
for different values of n, the number of elements in the list to be sorted and
plot a graph of the time taken versus n. The elements can be read from a file or
can be generated using the random number generator.

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

// Merge two sorted subarrays into one sorted array

void Merge(int a[], int low, int mid, int high) {
int i = low, j = mid + 1, k = low;
int b[20]; // Temporary array to store merged elements

while (i <= mid && j <= high) {

if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}

while (i <= mid)

b[k++] = a[i++];
while (j <= high)
b[k++] = a[j++];

for (k = low; k <= high; k++)

a[k] = b[k];
}

// Recursive function to perform merge sort

void MergeSort(int a[], int low, int high) {
if (low >= high)
return;
int mid = (low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid + 1, high);
Merge(a, low, mid, high);
}

int main() {
int n, k, lim;
clock_t st, et;
double ts;
printf("Enter the number of elements: ");
scanf("%d", &n);

int a[n]; // No need to increase array size

5CS4-23: Analysis of Algorithms

 srand(time(0));
printf("Enter the limit of random numbers: ");
scanf("%d", &lim);

printf("\nThe Random Numbers are:\n");

for (k = 0; k < n; k++) {
a[k] = rand() % lim;
printf("%d\t", a[k]);
}

st = clock();
MergeSort(a, 0, n - 1); // Passing array with indices 0 to n-1
et = clock();
ts = (double)(et - st) / CLOCKS_PER_SEC;
printf("\nSorted Numbers are:\n");
for (k = 0; k < n; k++)
printf("%d\t", a[k]);
printf("\nThe time taken is %e\n", ts);
return 0;
}

Output:

Enter the number of elements: 10

Enter the limit of random numbers: 101
The Random Numbers are:
100 46 36 98 39 95 1 52 15 61
Sorted Numbers are:
1 15 36 39 46 52 61 95 98 100
The time taken is 2.000000e-06

5CS4-23: Analysis of Algorithms

 Viva Questions
Q1: What is Merge Sort?
Ans: Merge Sort is a divide-and-conquer sorting algorithm that divides the input array into
two halves, recursively sorts them, and then merges the sorted halves to produce a fully
sorted array.

Q2: What is parallelized Merge Sort?

Ans: Parallelized Merge Sort is an optimization of the traditional Merge Sort that leverages
multiple processing units to sort different parts of the array simultaneously, improving the
sorting efficiency.

Q3: What is the time complexity of Merge Sort?

Ans: The time complexity of Merge Sort is O(n log n), where 'n' is the number of elements in
the array. This makes it an efficient algorithm for sorting large datasets.

Q4: What is the advantage of using parallelized Merge Sort?

Ans: Parallelized Merge Sort can significantly improve sorting speed for large datasets by
utilizing multiple processors or cores, effectively reducing the time required to sort the array.

Q5: How does Merge Sort handle odd-sized arrays?

Ans: Merge Sort still divides the array into roughly equal halves when dealing with an odd-
sized array. One sub-array may have one more element than the other.

5CS4-23: Analysis of Algorithms

 Program 3
AIM: a. Obtain the Topological ordering of vertices in a given digraph.

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

#define MAX_VERTICES 100

struct Graph {
int V;
int** adjacency_matrix;
};

struct Graph* createGraph(int V) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;

// Allocate memory for the adjacency matrix

graph->adjacency_matrix = (int**)malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
graph->adjacency_matrix[i] = (int*)malloc(V * sizeof(int));
}

// Initialize the adjacency matrix

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
graph->adjacency_matrix[i][j] = 0;
}
}

return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {

graph->adjacency_matrix[src][dest] = 1;
}

void DFS(struct Graph* graph, int v, int* visited, int* topological_order, int* index) {
visited[v] = 1;

for (int i = 0; i < graph->V; i++) {

if (graph->adjacency_matrix[v][i] == 1 && !visited[i]) {
DFS(graph, i, visited, topological_order, index);
}
}

topological_order[(*index)--] = v;
}

void topologicalSort(struct Graph* graph) {

5CS4-23: Analysis of Algorithms

 int V = graph->V;
int* visited = (int*)malloc(V * sizeof(int));
int* topological_order = (int*)malloc(V * sizeof(int));
int index = V - 1;

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

visited[i] = 0;
}

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

if (!visited[i]) {
DFS(graph, i, visited, topological_order, &index);
}
}

printf("Topological Ordering: ");

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

free(visited);
free(topological_order);
}

int main() {
int V, E;
printf("Enter the number of vertices: ");
scanf("%d", &V);

struct Graph* graph = createGraph(V);

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

scanf("%d", &E);

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

int src, dest;
printf("Enter edge %d (source destination): ", i + 1);
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}

printf("Topological Sort Result:\n");

topologicalSort(graph);

return 0;
}

Output:

5CS4-23: Analysis of Algorithms

Enter the number of vertices: 5
Enter the number of edges: 4
Enter edge 1 (source destination): 1
3
Enter edge 2 (source destination): 2
4
Enter edge 3 (source destination): 3
5
Enter edge 4 (source destination): 4
2
Topological Sort Result:
Topological Ordering: 2 4 1 3 0

5CS4-23: Analysis of Algorithms

 Viva Questions

Q1: What is a digraph? And what is the concept of topological ordering of vertices in a
digraph?
Ans: A digraph, or directed graph, is a graph in which edges have a specific direction,
indicating a one-way relationship between vertices.
A topological ordering is a linear ordering of the vertices in a digraph such that for every
directed edge (u, v), vertex u comes before vertex v in the ordering.

Q2: How can you obtain a topological ordering of vertices in a digraph?

Ans: One common algorithm to obtain a topological ordering is the Depth-First Search
(DFS) based approach, where vertices are visited recursively and added to the ordering after
all their adjacent vertices have been visited.

Q3: Is a topological ordering unique for a given digraph?

Ans: No, a digraph can have multiple valid topological orderings. The ordering depends on
the specific ordering of vertices during the DFS traversal.

Q4: What is the key property that a digraph must satisfy for a topological ordering to
exist?
Ans: A digraph must be a Directed Acyclic Graph (DAG) for a valid topological ordering to
exist. Cycles in the graph would create contradictions in the ordering.

Q5: What is the time complexity of obtaining a topological ordering using depth-first
search?
Ans: The time complexity is O(V + E), where V is the number of vertices and E is the
number of edges in the graph.

5CS4-23: Analysis of Algorithms

b. Compute the transitive closure of a given directed graph using Warshall's algorithm.

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

#define MAX_VERTICES 100

void transitiveClosure(int V, int graph[MAX_VERTICES][MAX_VERTICES]) {

int closure[MAX_VERTICES][MAX_VERTICES];

// Initialize the closure matrix with the input graph

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
closure[i][j] = graph[i][j];
}
}

// Compute transitive closure using Warshall's algorithm

for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
closure[i][j] = closure[i][j] || (closure[i][k] && closure[k][j]);
}
}
}

// Print the transitive closure matrix

printf("Transitive Closure Matrix:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf("%d ", closure[i][j]);
}
printf("\n");
}
}

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

int graph[MAX_VERTICES][MAX_VERTICES];

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

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

5CS4-23: Analysis of Algorithms

 }

transitiveClosure(V, graph);

return 0;
}

Output:

Enter the number of vertices: 3

Enter the adjacency matrix:
1
2
4
7
5
6
9
3
12
11
Transitive Closure Matrix:
111
111
111

5CS4-23: Analysis of Algorithms

 Viva Questions

Q1: What is the transitive closure of a directed graph?

Ans: The transitive closure of a directed graph is a matrix that represents the reachability of
all pairs of vertices in the graph. It indicates whether there is a path between every pair of
vertices.

Q2: Explain Warshall's algorithm briefly.

Ans: Warshall's algorithm is used to compute the transitive closure of a graph. It iteratively
updates the transitive closure matrix by considering all possible intermediate vertices to
determine if a path exists between two vertices.

Q3: How does Warshall's algorithm represent the graph and its transitive closure?
Ans: Warshall's algorithm uses an adjacency matrix to represent the graph and updates a
separate matrix to represent the transitive closure.

Q4: What is the time complexity of Warshall's algorithm?

Ans: The time complexity of Warshall's algorithm is O(V^3), where V is the number of
vertices in the graph.

Q5: Can Warshall's algorithm be applied to a weighted graph?

Ans: Warshall's algorithm is designed for unweighted graphs. It doesn't take edge weights
into account; it only determines reachability.

5CS4-23: Analysis of Algorithms

 Program 4
AIM: Implement 0/1 Knapsack problem using Dynamic Programming.

#include <stdio.h>

#define MAX_ITEMS 100

// Structure to represent an item

struct Item {
int weight;
int value;
};

// Function to calculate the maximum of two integers

int max(int a, int b) {
return (a > b) ? a : b;
}

// Function to solve the 0/1 Knapsack problem using dynamic programming

int knapsack(int capacity, struct Item items[], int n) {
int dp[MAX_ITEMS + 1][capacity + 1];

// Initialize the dp table

for (int i = 0; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (items[i - 1].weight <= w) {
dp[i][w] = max(items[i - 1].value + dp[i - 1][w - items[i - 1].weight], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}

return dp[n][capacity];
}

int main() {
int n, capacity;

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

scanf("%d", &n);

struct Item items[MAX_ITEMS];

printf("Enter the weight and value of each item:\n");

for (int i = 0; i < n; i++) {
printf("Item %d (weight value): ", i + 1);

5CS4-23: Analysis of Algorithms

 scanf("%d %d", &items[i].weight, &items[i].value);
}

printf("Enter the knapsack capacity: ");

scanf("%d", &capacity);

int max_value = knapsack(capacity, items, n);

printf("Maximum value in the knapsack: %d\n", max_value);

return 0;
}

Output:

Enter the number of items: 5

Enter the weight and value of each item:
Item 1 (weight value): 10 12
Item 2 (weight value): 8 7
Item 3 (weight value): 11 9
Item 4 (weight value): 9 8
Item 5 (weight value): 12 10
Enter the knapsack capacity: 50
Maximum value in the knapsack: 46

5CS4-23: Analysis of Algorithms

 Viva Questions
Q1: What is the 0/1 Knapsack problem?
Ans: The 0/1 Knapsack problem is a combinatorial optimization problem where you have a
set of items, each with a weight and a value, and you want to select a subset of items to
maximize the total value while not exceeding a given capacity.

Q2: What is Dynamic Programming?

Ans: Dynamic Programming is a technique used to solve complex problems by breaking
them down into smaller subproblems and storing the solutions to these subproblems to avoid
redundant calculations.

Q3: How does Dynamic Programming solve the 0/1 Knapsack problem efficiently?
Ans: Dynamic Programming solves the problem by building a table where each cell
represents the maximum value that can be obtained with a certain weight capacity and a
subset of items. The values are computed iteratively based on previously calculated
subproblems.

Q4: What does dp[i][w] represent in the DP table?

Ans: dp[i][w] represents the maximum value that can be obtained by considering the first 'i'
items and having a weight capacity of 'w'.

Q5: What is the advantage of using Dynamic Programming for the 0/1 Knapsack
problem?
Ans: Dynamic Programming avoids redundant calculations by storing intermediate results,
leading to significant efficiency improvements compared to naive recursive approaches.

5CS4-23: Analysis of Algorithms

 Program 5
AIM: From a given vertex in a weighted connected graph, find shortest paths to other vertices
using Dijkstra's algorithm.

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

// Define the number of vertices in the graph

#define V 5

// Function to find the vertex with the minimum distance value

int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) {

if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}

return min_index;
}

// Function to print the constructed distance array

void printSolution(int dist[]) {
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++) {
printf("%d \t %d\n", i, dist[i]);
}
}

// Function to implement Dijkstra's algorithm

void dijkstra(int graph[V][V], int src) {
int dist[V]; // Array to store the shortest distances from the source
bool sptSet[V]; // Set to keep track of included vertices in the shortest path tree

// Initialize all distances as infinite and sptSet[] as false

for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = false;
}

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find the shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed

5CS4-23: Analysis of Algorithms

 int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex

for (int v = 0; v < V; v++) {
// Update dist[v] only if it's not in sptSet, there's an edge from u to v,
// and the total weight of the path from src to v through u is less than current dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] <
dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

// Print the constructed distance array

printSolution(dist);
}

int main() {
// Example graph represented as an adjacency matrix
int graph[V][V] = {
{0, 4, 0, 0, 0},
{4, 0, 8, 0, 0},
{0, 8, 0, 7, 0},
{0, 0, 7, 0, 9},
{0, 0, 0, 9, 0}
};

int source = 0; // Starting vertex

dijkstra(graph, source);

return 0;
}

Output:

Vertex Distance from Source

0 0
1 4
2 12
3 19
4 28

5CS4-23: Analysis of Algorithms

 Viva Questions

Q1: What is Dijkstra's algorithm used for?

Ans: Dijkstra's algorithm is used to find the shortest path from a source vertex to all other
vertices in a weighted connected graph.

Q2: What are some real-world applications of Dijkstra's algorithm?

Ans: Dijkstra's algorithm is used in various applications, such as routing in computer
networks, navigation systems, airline scheduling, and resource allocation in operating
systems.

Q3: What is the main drawback of Dijkstra's algorithm?

Ans: The main drawback is that it doesn't work with negative edge weights, and it requires
extra effort to handle graphs with negative cycles.

Q4: What is the time complexity of Dijkstra's algorithm?

Ans: With a priority queue, the time complexity of Dijkstra's algorithm is
O((V + E) logV), where V is the number of vertices and E is the number of edges.

Q5: How does Dijkstra's algorithm guarantee finding the shortest paths?
Ans: Dijkstra's algorithm iteratively selects vertices with the smallest tentative distance,
ensuring that all paths are explored and shortest distances are determined.

5CS4-23: Analysis of Algorithms

 Program 6
AIM: Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's
algorithm.

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

// Define the maximum number of vertices and edges

#define MAX_VERTICES 100
#define MAX_EDGES 100

// Structure to represent an edge in the graph

struct Edge {
int src, dest, weight;
};

// Structure to represent the graph

struct Graph {
int V, E;
struct Edge edges[MAX_EDGES];
};

// Function to initialize a graph

struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
return graph;
}

// Function to compare two edges based on their weights

int compareEdges(const void* a, const void* b) {
return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

// Function to find the parent of a vertex in a disjoint-set

int findParent(int parent[], int vertex) {
if (parent[vertex] == -1)
return vertex;
return findParent(parent, parent[vertex]);
}

// Function to perform union of two sets by rank

void unionSets(int parent[], int x, int y) {
int xroot = findParent(parent, x);
int yroot = findParent(parent, y);

if (xroot != yroot) {

5CS4-23: Analysis of Algorithms

 parent[xroot] = yroot;
}
}

// Function to find the Minimum Cost Spanning Tree using Kruskal's algorithm
void kruskalMST(struct Graph* graph) {
int V = graph->V;
struct Edge resultMST[V - 1]; // Stores the edges of the MST
int e = 0; // Index variable for resultMST
int i = 0; // Index variable for sorted edges array

// Sort the edges in ascending order based on their weights

qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);

// Allocate memory for the parent array for disjoint-set

int parent[V];
for (int v = 0; v < V; v++) {
parent[v] = -1;
}

// Keep adding edges to the MST until V-1 edges are added
while (e < V - 1 && i < graph->E) {
struct Edge nextEdge = graph->edges[i++];

int x = findParent(parent, nextEdge.src);

int y = findParent(parent, nextEdge.dest);

// If adding the edge doesn't create a cycle, include it in the MST

if (x != y) {
resultMST[e++] = nextEdge;
unionSets(parent, x, y);
}
}

// Print the MST

printf("Edges in Minimum Cost Spanning Tree:\n");
for (i = 0; i < e; i++) {
printf("%d - %d : %d\n", resultMST[i].src, resultMST[i].dest, resultMST[i].weight);
}
}

int main() {
int V = 4; // Number of vertices
int E = 5; // Number of edges
struct Graph* graph = createGraph(V, E);

// Add edges to the graph

graph->edges[0].src = 0;
graph->edges[0].dest = 1;
graph->edges[0].weight = 10;

5CS4-23: Analysis of Algorithms

 graph->edges[1].src = 0;
graph->edges[1].dest = 2;
graph->edges[1].weight = 6;

graph->edges[2].src = 0;
graph->edges[2].dest = 3;
graph->edges[2].weight = 5;

graph->edges[3].src = 1;
graph->edges[3].dest = 3;
graph->edges[3].weight = 15;

graph->edges[4].src = 2;
graph->edges[4].dest = 3;
graph->edges[4].weight = 4;

kruskalMST(graph);

return 0;
}

Output:

Edges in Minimum Cost Spanning Tree:

2-3:4
0-3:5
0 - 1 : 10

Viva Questions
Q1: What is a Minimum Cost Spanning Tree (MCST) in a graph?
Ans: A Minimum Cost Spanning Tree is a subset of the edges of an undirected graph that
connects all vertices with the minimum possible total edge weight and forms a tree without
any cycles.

Q2: What data structure is commonly used to implement Kruskal's algorithm?

Ans: Kruskal's algorithm often uses a disjoint-set data structure (also known as a union-find
data structure) to keep track of the connected components of the graph efficiently.

Q3: How are edges sorted in Kruskal's algorithm and What is the time complexity of
Kruskal's algorithm?
Ans: Edges are typically sorted in ascending order of their weights to ensure that the smallest
weight edges are considered first.
The time complexity of Kruskal's algorithm is typically O(E log E), where E is the number of
edges in the graph

Q4: When does Kruskal's algorithm terminate?

Ans: Kruskal's algorithm terminates when the Minimum Cost Spanning Tree is complete,
i.e., when it contains (V - 1) edges, where V is the number of vertices in the graph.

5CS4-23: Analysis of Algorithms

Q5: Can Kruskal's algorithm handle graphs with negative-weight edges?
Ans: Kruskal's algorithm is designed for graphs with non-negative edge weights. It may not
work correctly for graphs with negative-weight edges without modifications.

5CS4-23: Analysis of Algorithms

 Program 7
AIM: a. Print all the nodes reachable from a given starting node in a digraph using BFS method.

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

#define MAX_VERTICES 100

// Structure to represent a node in the adjacency list

struct Node {
int data;
struct Node* next;
};

// Structure to represent the adjacency list of the graph

struct Graph {
int numVertices;
struct Node* adjacencyList[MAX_VERTICES];
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to create a graph with a given number of vertices

struct Graph* createGraph(int numVertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = numVertices;

// Initialize the adjacency list with NULL

for (int i = 0; i < numVertices; i++) {
graph->adjacencyList[i] = NULL;
}

return graph;
}

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest) {
// Add an edge from src to dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adjacencyList[src];
graph->adjacencyList[src] = newNode;
}

5CS4-23: Analysis of Algorithms

// Function to perform BFS traversal and print all reachable nodes from the given source
void BFS(struct Graph* graph, int startVertex) {
bool visited[MAX_VERTICES] = {false}; // Mark all vertices as not visited

// Create a queue for BFS

int queue[MAX_VERTICES];
int front = 0, rear = 0;

// Mark the current node as visited and enqueue it

visited[startVertex] = true;
queue[rear++] = startVertex;

printf("Nodes reachable from node %d: ", startVertex);

while (front < rear) {

// Dequeue a vertex from the queue and print it
int currentVertex = queue[front++];
printf("%d ", currentVertex);

// Traverse all adjacent vertices of the dequeued vertex

struct Node* temp = graph->adjacencyList[currentVertex];
while (temp) {
int adjacentVertex = temp->data;
if (!visited[adjacentVertex]) {
visited[adjacentVertex] = true;
queue[rear++] = adjacentVertex;
}
temp = temp->next;
}
}

printf("\n");
}

int main() {
struct Graph* graph = createGraph(6);

addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 4);
addEdge(graph, 3, 5);
addEdge(graph, 4, 5);

int startVertex = 0; // Starting node

BFS(graph, startVertex);

5CS4-23: Analysis of Algorithms

 return 0;
}

Output:

Nodes reachable from node 0: 0 2 1 4 3 5

5CS4-23: Analysis of Algorithms

 Viva Questions

Q1: What is a directed graph (digraph)?

Ans: A directed graph, or digraph, is a graph in which edges have a direction, meaning they
go from one node to another, forming a directed relationship.

Q2: What is BFS in the context of graph traversal and what is the time complexity of
BFS traversal in a graph?
Ans: BFS stands for Breadth-First Search. It is a graph traversal algorithm that explores all
the vertices of a graph in breadthward motion, visiting all the neighbors of a node before
moving to their children.
The time complexity of BFS in a graph is O(V + E), where V is the number of vertices and E
is the number of edges.

Q3: What is the role of a queue in BFS traversal?

Ans: The queue is used to store nodes that need to be visited. Nodes are dequeued (removed)
from the front of the queue and enqueued (added) to the back as they are visited and
explored.

Q4: How do you handle cycles in a graph while performing BFS?

Ans: To handle cycles, you typically maintain a set or array to mark visited nodes. Before
enqueueing a node, you check if it has been visited to avoid revisiting it.

Q5: What is the difference between BFS and Dijkstra's algorithm?

Ans: BFS explores all nodes at the same depth level before moving deeper, while Dijkstra's
algorithm explores nodes with the shortest path from the starting node, making it suitable for
weighted graphs.

5CS4-23: Analysis of Algorithms

b. Check whether a given graph is connected or not using DFS method

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

#define MAX_VERTICES 100

struct Graph {
int V;
int** adjacency_matrix;
};

struct Graph* createGraph(int V) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;

// Allocate memory for the adjacency matrix

graph->adjacency_matrix = (int**)malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
graph->adjacency_matrix[i] = (int*)malloc(V * sizeof(int));
}

// Initialize the adjacency matrix

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
graph->adjacency_matrix[i][j] = 0;
}
}

return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {

graph->adjacency_matrix[src][dest] = 1;
}

void DFS(struct Graph* graph, int v, int* visited, int* topological_order, int* index) {
visited[v] = 1;

for (int i = 0; i < graph->V; i++) {

if (graph->adjacency_matrix[v][i] == 1 && !visited[i]) {
DFS(graph, i, visited, topological_order, index);
}
}

topological_order[(*index)--] = v;
}

5CS4-23: Analysis of Algorithms

void topologicalSort(struct Graph* graph) {
int V = graph->V;
int* visited = (int*)malloc(V * sizeof(int));
int* topological_order = (int*)malloc(V * sizeof(int));
int index = V - 1;

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

visited[i] = 0;
}

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

if (!visited[i]) {
DFS(graph, i, visited, topological_order, &index);
}
}

printf("Topological Ordering: ");

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

free(visited);
free(topological_order);
}

int main() {
int V, E;
printf("Enter the number of vertices: ");
scanf("%d", &V);

struct Graph* graph = createGraph(V);

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

scanf("%d", &E);

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

int src, dest;
printf("Enter edge %d (source destination): ", i + 1);
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}

printf("Topological Sort Result:\n");

topologicalSort(graph);

return 0;
}

Output:

5CS4-23: Analysis of Algorithms

Enter the number of vertices: 4
Enter the number of edges: 3
Enter edge 1 (source destination): 0 1
Enter edge 2 (source destination): 1 2
Enter edge 3 (source destination): 2 3
Topological Sort Result:
Topological Ordering: 0 1 2 3

5CS4-23: Analysis of Algorithms

 Viva Questions
Q1: What is DFS (Depth-First Search), and how is it used to determine if a graph is
connected?
Ans: Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible
along each branch before backtracking. You can start DFS from any vertex in the graph and
traverse as much of the graph as possible. If, during this process, all vertices are visited or
reachable from the starting vertex, then the graph is connected.

Q2: What is the time complexity of the DFS-based graph connectivity check?
Ans: The time complexity is O(V + E), where V is the number of vertices, and E is the
number of edges in the graph.

Q3: What is a connected graph?

Ans: A connected graph is a graph in which there exists a path between every pair of
vertices.

Q4: What is an adjacency list representation of a graph?

Ans: An adjacency list is a data structure that represents a graph as a collection of lists. Each
vertex has a list of its adjacent vertices.

Q5: How does DFS work in the context of graph traversal?

Ans: DFS starts at an initial vertex, explores one adjacent vertex at a time, backtracks when
it reaches a dead end, and continues until all vertices are visited or a specific goal is achieved.

5CS4-23: Analysis of Algorithms

 Program 8
AIM: Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.

#include <stdio.h>

#define MAX_VERTICES 10

int a, b, u, v, i, j, n, noe;
int vi[MAX_VERTICES], min, mc, c[MAX_VERTICES][MAX_VERTICES];

void prims(int c[][MAX_VERTICES], int n);

int main() {

printf("\nPrim's algorithm\n");
printf("\nEnter the number of vertices: ");
scanf("%d", &n);
printf("\nEnter the adjacency matrix:\n");

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

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

prims(c, n);

return 0;
}

void prims(int c[][MAX_VERTICES], int n) {

noe = 1;
mc = 0;

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

vi[i] = 0;
}

printf("\nEdges in the spanning tree are:\n");

vi[1] = 1;

while (noe < n) {

for (i = 1, min = 999; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (c[i][j] < min) {
if (vi[i] == 0) {
continue;

5CS4-23: Analysis of Algorithms

 } else {
min = c[i][j];
a = u = i;
b = v = j;
}
}
}
}

if (vi[u] == 0 || vi[v] == 0) {
noe++;
printf("Edge(%d --> %d): %d\n", a, b, min);
mc += min;
vi[b] = 1;
}

c[a][b] = c[b][a] = 999;

}

printf("\nMinimum cost spanning tree is: %d\n", mc);

}

Output:

Prim's algorithm

Enter the number of vertices: 3

Enter the adjacency matrix:
052
501
010
Edges in the spanning tree are:
Edge(1 --> 3): 2
Edge(3 --> 2): 1

Minimum cost spanning tree is: 3

Viva Questions

5CS4-23: Analysis of Algorithms

Q1: What is Prim's algorithm used for?
Ans: Prim's algorithm is used to find the Minimum Cost Spanning Tree (MCST) of a given
undirected graph.

Q2: What is the time complexity of Prim's algorithm using a straightforward

implementation?
Ans: The time complexity of Prim's algorithm using a straightforward implementation is
O(V^2), where V is the number of vertices in the graph.

Q3: Can Prim's algorithm handle graphs with negative edge weights?
Ans: Prim's algorithm, as traditionally implemented, does not handle negative edge weights.
It assumes that all edge weights are non-negative.

Q4: In what real-world applications can Prim's algorithm be used?

Ans: Prim's algorithm can be used in various applications, including network design, circuit
design, and transportation planning, where the goal is to connect a set of points with
minimum cost while ensuring connectivity.

Q5: What is the difference between Prim's algorithm and Kruskal's algorithm for
finding MCSTs?
Ans: Prim's algorithm starts with a single vertex and grows the tree, while Kruskal's
algorithm starts with all vertices as individual trees and merges them.

5CS4-23: Analysis of Algorithms

 Program 9
AIM: Implement All-Pairs Shortest Paths Problem using Floyd's algorithm.

#include <stdio.h>

#define MAX_VERTICES 100

#define INF 999999

void floydWarshall(int graph[MAX_VERTICES][MAX_VERTICES], int V) {

int dist[MAX_VERTICES][MAX_VERTICES];

// Initialize the distance matrix with the input graph

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}

// Calculate the shortest path for all pairs of vertices

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

// Print the shortest distances

printf("Shortest distances between all pairs of vertices:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF) {
printf("INF\t");
} else {
printf("%d\t", dist[i][j]);
}
}
printf("\n");
}
}

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

int graph[MAX_VERTICES][MAX_VERTICES];

5CS4-23: Analysis of Algorithms

 printf("Enter the adjacency matrix (use INF for infinity):\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
scanf("%d", &graph[i][j]);
if (graph[i][j] == -1) {
graph[i][j] = INF;
}
}
}

floydWarshall(graph, V);

return 0;
}

Output:

Enter the number of vertices: 4

Enter the adjacency matrix (use INF for infinity):
0 3 -1 5
2 0 -1 4
-1 -1 0 1
-1 -1 -1 0
Shortest distances between all pairs of vertices:
0 3 INF 5
2 0 INF 4
INF INF 0 1
INF INF INF 0

5CS4-23: Analysis of Algorithms

 Viva Questions

Q1: What is the All-Pairs Shortest Paths Problem, and what is Floyd's algorithm used
for?
Ans: The All-Pairs Shortest Paths Problem involves finding the shortest path between all
pairs of vertices in a weighted graph. Floyd's algorithm is specifically used to solve this
problem.

Q2: How does Floyd's algorithm work, and what is its time complexity?
Ans: Floyd's algorithm works by iteratively updating the shortest path matrix by considering
all possible intermediate vertices between any pair of vertices. It achieves this while having a
time complexity of O(V^3), where V represents the number of vertices in the graph.

Q3: What are the applications of the All-Pairs Shortest Paths Problem in real life, and
what data structures are commonly used to implement Floyd's algorithm?
Ans: The applications of the All-Pairs Shortest Paths Problem in real life include network
routing, navigation systems, social network analysis, and traffic flow optimization. To
implement Floyd's algorithm, a 2D matrix is commonly used to represent the graph and store
the shortest distances between vertices.

Q4: What is the main advantage of Floyd's algorithm over other algorithms for the All-
Pairs Shortest Paths Problem?
Ans: Floyd's algorithm is advantageous because it computes the shortest paths between all
pairs of vertices in a single pass, while other algorithms like Dijkstra's require multiple
passes.

Q5: What is the difference between Floyd's algorithm and Dijkstra's algorithm?
Ans: Floyd's algorithm finds the shortest paths between all pairs of vertices in a single pass,
while Dijkstra's algorithm finds the shortest path from a single source vertex to all other
vertices.

5CS4-23: Analysis of Algorithms

 Program 10
AIM: Implement N Queen's problem using Back Tracking.
#include <stdio.h>
#include <stdbool.h>

#define N 8 // Define the board size (change this value to solve for different N)

// Function to print the chessboard

void printBoard(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%c ", board[i][j] ? 'Q' : '.');
}
printf("\n");
}
}

// Function to check if it's safe to place a queen at board[row][col]

bool isSafe(int board[N][N], int row, int col) {
int i, j;

// Check the left side of this row

for (i = 0; i < col; i++) {
if (board[row][i]) {
return false;
}
}

// Check upper diagonal on the left side

for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) {
return false;
}
}

// Check lower diagonal on the left side

for (i = row, j = col; i < N && j >= 0; i++, j--) {
if (board[i][j]) {
return false;
}
}

return true;
}

// Recursive function to solve N-Queens problem using backtracking

bool solveNQueens(int board[N][N], int col) {
if (col >= N) {
return true; // All queens are placed successfully
}

5CS4-23: Analysis of Algorithms

 for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1; // Place the queen at board[i][col]

// Recur to place the rest of the queens

if (solveNQueens(board, col + 1)) {
return true;
}

// If placing queen at board[i][col] doesn't lead to a solution, then backtrack

board[i][col] = 0;
}
}

return false; // Queen can't be placed in any row in this column

}

int main() {
int board[N][N];

// Initialize the chessboard

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = 0;
}
}

if (solveNQueens(board, 0)) {
printf("Solution found:\n");
printBoard(board);
} else {
printf("No solution exists.\n");
}

return 0;
}

Output:

Solution found:
Q.......
......Q.
....Q...
.......Q
.Q......
...Q....
.....Q..
..Q.....
Viva Questions

5CS4-23: Analysis of Algorithms

Q1: What is the N-Queens problem?
Ans: The N-Queens problem is a classic combinatorial puzzle that involves placing N chess
queens on an N×N chessboard in such a way that no two queens threaten each other.

Q2: What is backtracking?

Ans: Backtracking is a general algorithmic technique that involves systematically searching
for a solution to a problem by exploring possible options and undoing choices that do not lead
to a valid solution.

Q3: What is the base case in the N-Queens backtracking algorithm?

Ans: The base case is reached when all N queens are successfully placed on the board
without conflicts, and a valid solution is found.

Q4: What is the time complexity of the N-Queens backtracking algorithm?

Ans: The time complexity of the algorithm depends on the specific implementation, but it is
typically exponential, O(N!), due to the large number of possible board configurations.

Q5: How do you represent the chessboard in code for the N-Queens problem?
Ans: The chessboard can be represented using a 2D array where each cell represents a
square on the board, and the presence of a queen is indicated by a specific value.

5CS4-23: Analysis of Algorithms