Algorithms Lab Course code: B22EF0404

SCHOOL
OF
COMPUTER SCIENCE
AND
ENGINEERING

ALGORITHMS LAB
B22EF0404

Fourth Semester
AY-2023-24
(Prepared in Feb-2024)

Composed by: Dr. Akram Pasha

School of Computer Science and Engineering Page 1

 Algorithms Lab Course code: B22EF0404
INDEX

SL. No Contents Page. no

1 Lab Objectives 3
2 Lab Outcomes 3
3 Lab Requirements 3
4 Guidelines to Students 4
5 List of Lab Exercises and Mini-Projects 5
6 Lab Exercises’ Solutions: 7
PART – A: LAB EXERCISES
Session – 1: Lab Exercise 7
Session – 2a: Lab Exercise 10
Session – 2b: Lab Exercise 15
Session – 3: Lab Exercise 17
Session – 4: Lab Exercise 19
Session – 5: Lab Exercise 22
Session – 6: Lab Exercise 24
Session – 7: Lab Exercise 27
Session – 8a: Lab Exercise 30
Session – 8b: Lab Exercise 32
Session – 9: Lab Exercise 33
Session – 10: Lab Exercise 36
PART – B: MINI-PROJECTS
7 Mini-Project Specification and Evaluation Rubrics 40
8 Project Report Format 43
9 Learning Resources 48

School of Computer Science and Engineering Page 2

 Algorithms Lab Course code: B22EF0404
1. Lab Objectives:

The objectives of this course are to

 Demonstrate performance of algorithms with respect to time and space complexity.

 Explain Graph and Tree traversals techniques.

 Understand the concepts of greedy method and dynamic programming for different applications.

 Illustrate the methods of Backtracking, Branch and bound techniques.

 Familiarize the concepts of deterministic and non-deterministic algorithms.

2. Lab Outcomes:

On successful completion of this course; student shall be able to:

CO# Course Outcomes POs PSOs

1, 2, 3, 5, 9,12 1,3
Implement sorting and searching techniques using different algorithmic
CO1
techniques.
CO2 Implement Tree Traversal method and Greedy Algorithms 1, 2, 3, 5, 9,12 1,3

CO3 Develop the skill set to solve problems using Dynamic Programming concepts.1, 2, 3, 5, 6, 9, 2,3
12
CO4 Illustrate Backtracking, Branch and Bound concept to solve variousproblems 1, 2, 3, 5, 6, 9, 1,2
12
CO5 Demonstrate Time and Space complexities of various algorithms 1, 2, 3, 5, 6, 9, 1,2
12
CO6 Analyze and evaluate different performance analysis methods for non- 1, 2, 3,4, 5, 6, 2,3
deterministic algorithms 9, 12

3. Lab Requirements:

The following are the required hardware and software for this lab.

Hardware Requirements: A standard personal computer or laptop with the following minimum specifications:

1. Processor: Any modern multi-core processor (e.g., Intel Core i5 or AMD Ryzen series).
2. RAM: At least 4 GB of RAM for basic programs; 8 GB or more is recommended for larger data structures
and complex algorithms.
3. Storage: A few gigabytes of free disk space for the development environment and program files.
4. Display: A monitor with a resolution of 1024x768 or higher is recommended for comfortable coding.
5. Input Devices: Keyboard and mouse (or other input devices) for coding and interacting with the development
environment.
Software Requirements:

1. Operating System: You can develop and execute C programs for Algorithms Lab on various operating
systems, including Windows, macOS, and Linux.
2. Text Editor or Integrated Development Environment (IDE):

School of Computer Science and Engineering Page 3

 Algorithms Lab Course code: B22EF0404
 Text Editor: You can use a simple text editor like Notepad (Windows), Nano (Linux/macOS), or any
code-oriented text editor like Visual Studio Code, Sublime Text, or Atom.
 IDE: Consider using a C/C++ integrated development environment like Code::Blocks, Dev-C++, or
Eclipse CDT for a more feature-rich coding experience.
3. C Compiler:
 To compile and execute C programs, you need a C compiler. GCC (GNU Compiler Collection) is a
popular choice for Linux and macOS.
 For Windows, you can use MinGW (Minimalist GNU for Windows) with GCC or Visual C++ from
Microsoft if you prefer a Microsoft development environment.

4. Guidelines to Students:

 Equipment in the lab for the use of the student community. Students need to maintain a proper decorum in the
computer lab. Students must use the equipment with care. Any damage caused is punishable.
 Students are required to carry their observation / programs book with completed exercises while entering the
lab.
 Students are supposed to occupy the machines allotted to them and are not supposed to talk or make noise in
the lab. The allocation is put up on the lab notice board.
 The lab can be used in free time / lunch hours by the students who need to use the systems should get prior
permission from the lab in-charge.
 Lab records need to be submitted on or before the date of submission.
 Students are not supposed to use flash drives.
Practice

Here are some key activities involved in the design and analysis of algorithms:

 Problem Understanding: The first step is to clearly understand the problem at hand. This involves
identifying the input, output, constraints, and any specific requirements.
 Algorithm Design: Once the problem is understood, the next step is to design an algorithm to solve
it. This involves creating a step-by-step procedure or a set of rules that outlines how the problem can
be solved.
 Algorithm Analysis: After designing the algorithm, it is essential to analyze its efficiency and
performance. This analysis includes evaluating the algorithm's time complexity (how the running
time grows as the input size increases) and space complexity (how much memory the algorithm
requires).
 Algorithm Optimization: Based on the analysis, the algorithm can be optimized to improve its
efficiency. This may involve making algorithmic modifications, utilizing data structures that are
better suited for the problem, or applying known optimization techniques.
 Algorithm Correctness: Ensuring the algorithm is correct is crucial. This involves proving its
correctness using formal methods like mathematical proofs or conducting extensive testing to verify
that the algorithm produces the correct output for different input scenarios.
 Algorithm Implementation: Once the algorithm design is finalized and its correctness is established,
the next step is to implement the algorithm in a programming language. This involves translating the
algorithm into code and addressing any specific programming language considerations.
 Experimental Analysis: To validate the algorithm's performance in practice, experimental analysis
can be conducted. This involves running the algorithm on various inputs and measuring its running
time, memory usage, and other relevant metrics. The results can be compared with the theoretical
analysis to verify the algorithm's efficiency.

School of Computer Science and Engineering Page 4

 Algorithms Lab Course code: B22EF0404
These activities are iterative and may involve revisiting earlier stages as the design and analysis process
progresses. The goal is to create efficient and reliable algorithms that can effectively solve specific problems.

5. List of Lab Exercises and Mini-Projects:

Sl No. Title of the Exercise

Part A
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 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
3 Implement 0/1 Knapsack problem using Dynamic Programming.
4 From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's
algorithm.
5 Find the Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.
6 Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.
7 Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve
the same problem instance using any approximation algorithm and determine the error in the
approximation.
8 For a given graph
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.
9 Implement N Queen's problem using Back Tracking
10 Implement All-Pairs Shortest Paths Problem using Floyd's algorithm
Part B
1 Mini Projects on Sorting Algorithm Efficiency Comparison.
2 Mini Projects on Dynamic Programming
3 Mini Projects on Mini Projects on Pathfinding
4 Mini Projects on Graph Traversal Techniques
5 Mini Projects on Traveling Salesman Problem

School of Computer Science and Engineering Page 5

 Algorithms Lab Course code: B22EF0404

PART – A
LAB EXERCISES

School of Computer Science and Engineering Page 6

 Algorithms Lab Course code: B22EF0404
6. Lab Exercises’ Solutions:

Solutions (Part A)
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.
Problem Statement:
The task is to sort a given set of elements using the Quicksort method and measure the time it takes to perform
the sorting. The experiment should be repeated for different values of n, representing the number of elements
in the list to be sorted. Finally, a graph should be plotted, showing the relationship between the time taken and
the number of elements (n). The elements can either be read from a file or generated using a random number
generator.

Solution Overview:
The solution involves implementing the Quicksort algorithm to sort the given set of elements. The time taken
for sorting will be measured using appropriate time-tracking functions. The experiment will be repeated for
various values of n, allowing the observation of how the sorting time scales with the number of elements.

Intuition:
Quicksort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and
partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the
pivot. The process is then applied recursively to the sub-arrays. The efficiency of Quicksort makes it a popular
choice for sorting large datasets.

Code Implementation:
This following program generates random arrays of different sizes, sorts them using the Quicksort method, and
prints the time taken for each experiment. You can use the collected data to plot a graph of time taken versus
the number of elements (n).

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

// Function to partition the array

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

return i + 1;
}

// Quicksort algorithm

School of Computer Science and Engineering Page 7

 Algorithms Lab Course code: B22EF0404
void quicksort(int arr[], int low, int high) {
if (low < high) {
// Find pivot such that elements smaller than pivot are on the left,
// and elements greater than pivot are on the right
int pivotIndex = partition(arr, low, high);

// Recursively sort the sub-arrays

quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}

int main() {
srand(time(0)); // Seed for random number generation
clock_t start, end;

// Experiment for different values of n

for (int n = 1000; n <= 10000; n += 1000) {
int arr[n];

// Generate random elements

for (int i = 0; i < n; i++) {
arr[i] = rand() % 1000; // Random numbers between 0 and 999
}

// Measure the time taken for sorting

start = clock();
quicksort(arr, 0, n - 1);
end = clock();

double timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC;

// Print the results

printf("For n = %d, Time Taken: %lf seconds\n", n, timeTaken);
}

return 0;
}

Sample Output:

For n = 1000, Time Taken: 0.000001 seconds

For n = 2000, Time Taken: 0.000001 seconds
For n = 3000, Time Taken: 0.000001 seconds
...
For n = 10000, Time Taken: 0.000002 seconds

Outcome of the Exercise:

The implementation and experimentation with the Quicksort algorithm yielded valuable insights into the
efficiency of the sorting process. The key observations and outcomes are summarized below:
1. Algorithm Efficiency:
 Quicksort demonstrated efficient sorting, especially for large datasets. The divide-and-conquer approach of
Quicksort allows for effective handling of diverse data sizes.
2. Scalability Analysis:
 The experiment involved sorting different-sized arrays (n) to observe how the algorithm scales with
increasing input sizes. The time taken remained reasonably low even as the number of elements increased,
showcasing the scalability of Quicksort.
3. Time Complexity Analysis:

School of Computer Science and Engineering Page 8

 Algorithms Lab Course code: B22EF0404
 The observed time complexities align with the expected average-case time complexity of Quicksort, which
is O(n log n). This reinforces the algorithm's suitability for real-world applications where efficient sorting
is crucial.
4. Random Element Generation:
 The program's ability to generate random elements for testing provides a realistic simulation of sorting
scenarios. Random data sets help evaluate the algorithm's performance under various input conditions.
5. Graphical Representation:
 The plotted graph of time taken versus the number of elements (n) provides a visual representation of the
algorithm's performance trends. Such visualizations are essential for understanding the algorithm's behavior
as input sizes change.
6. Practical Application:
 The exercise emphasizes the practical application of sorting algorithms, addressing scenarios where datasets
need to be organized efficiently. Quicksort's effectiveness is evident in its quick response to varying data
sizes.
7. Experimental Flexibility:
 The flexibility to experiment with different input sizes and types of elements (random or read from a file)
adds versatility to the analysis. This adaptability allows for a comprehensive exploration of the algorithm's
behavior.
8. Learning Experience:
 The exercise serves as a hands-on learning experience, allowing you to apply theoretical knowledge in a
practical setting. Implementing the algorithm, measuring its performance, and analyzing the outcomes
contribute to a deeper understanding of sorting algorithms.

Viva/Interview Questions:
1. How does the Quicksort algorithm work?
 Answer: Quicksort is a divide-and-conquer algorithm that works by selecting a pivot element and
partitioning the other elements into two sub-arrays based on whether they are less than or greater than
the pivot. The process is applied recursively to the sub-arrays.
2. What is the time complexity of Quicksort?
 Answer: The average-case time complexity of Quicksort is O(n log n), making it an efficient sorting
algorithm. However, in the worst-case scenario, it can degrade to O(n^2) if the pivot selection leads
to unbalanced partitions.
3. How does the choice of the pivot element affect Quicksort's performance?
 Answer: The choice of the pivot element significantly impacts the efficiency of Quicksort. A well-
selected pivot leads to balanced partitions, ensuring better performance. Common strategies include
selecting the first, last, or middle element, or using a random element.
4. What is the significance of partitioning in the Quicksort algorithm?
 Answer: Partitioning is a fundamental step in Quicksort, where elements are rearranged based on their
relationship to the pivot. It divides the array into two sub-arrays, allowing the algorithm to sort each
sub-array independently.
5. How does Quicksort compare to other sorting algorithms, such as Merge Sort or Bubble Sort?
 Answer: Quicksort is often more efficient than Bubble Sort and comparable to Merge Sort in terms of
average-case time complexity. Quicksort is an in-place sorting algorithm, making it memory-efficient,
but its worst-case time complexity is a consideration compared to Merge Sort.
6. Explain the concept of the 'partition' function in the Quicksort algorithm.
 Answer: The partition function is responsible for rearranging elements in the array such that elements
smaller than the pivot are on the left, and elements greater than the pivot are on the right. It returns
the index of the pivot after the partitioning process.
7. Why is Quicksort preferred for large datasets?
 Answer: Quicksort's average-case time complexity of O(n log n) and in-place sorting nature make it
well-suited for large datasets. Its efficiency stems from the divide-and-conquer strategy, enabling it to
quickly sort data by recursively dividing and conquering sub-arrays.
8. How can you handle duplicate elements in Quicksort?
 Answer: Handling duplicate elements involves modifying the partitioning logic. Instead of
considering elements less than or greater than the pivot, you can create partitions for elements equal
to the pivot. This ensures the correct placement of duplicate elements during the sorting process.
9. What are some strategies for selecting the pivot element in Quicksort?

School of Computer Science and Engineering Page 9

 Algorithms Lab Course code: B22EF0404
Answer: Strategies include selecting the first, last, or middle element as the pivot. Another approach
is to choose a random element. Each strategy has its advantages and potential drawbacks, and the
choice can impact the efficiency of the algorithm.
10. How can you optimize Quicksort for nearly sorted data?
 Answer: For nearly sorted data, choosing the middle element as the pivot might be less efficient.
Instead, selecting the median of three elements (first, middle, and last) or using insertion sort for small
sub-arrays can optimize Quicksort's performance.

a. Obtain the Topological ordering of vertices in a given digraph.

2
Problem Statement:
The task is to obtain the topological ordering of vertices in a directed graph (digraph). Topological ordering is
a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering.
The goal is to represent the dependencies among vertices.
Solution Overview:
The solution involves using Depth-First Search (DFS) to perform a topological sort of the vertices. The
algorithm explores each vertex and recursively visits its adjacent vertices, ensuring that vertices are visited
before their dependent vertices.
Intuition:
Topological sorting is based on the idea that vertices with no incoming edges (in-degree zero) should come
first in the ordering. The DFS approach helps explore the graph, visiting vertices and marking them as visited.
The ordering is determined based on the finishing times of the vertices during the DFS traversal.
Code Implementation (Uses the Adjacency List to represent Digraph):
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

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

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

// 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;

School of Computer Science and Engineering Page 10

 Algorithms Lab Course code: B22EF0404
}

// 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;
graph->inDegree = (int*)malloc(numVertices * sizeof(int));

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

graph->adjacencyList[i] = NULL;
graph->inDegree[i] = 0;
}

return graph;
}

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjacencyList[src];
graph->adjacencyList[src] = newNode;

// Increment in-degree of the destination vertex

graph->inDegree[dest]++;
}

// Function to perform topological sorting using DFS

void topologicalSortUtil(struct Graph* graph, int vertex, int visited[], int result[], int* index) {
visited[vertex] = 1;

struct Node* current = graph->adjacencyList[vertex];

while (current != NULL) {
if (!visited[current->data]) {
topologicalSortUtil(graph, current->data, visited, result, index);
}
current = current->next;
}

result[*index] = vertex;

School of Computer Science and Engineering Page 11

 Algorithms Lab Course code: B22EF0404
(*index)++;
}

// Function to perform topological sorting of the graph

void topologicalSort(struct Graph* graph) {
int* result = (int*)malloc(graph->numVertices * sizeof(int));
int visited[MAX_VERTICES];
int index = 0;

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

visited[i] = 0;
}

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

if (!visited[i] && graph->inDegree[i] == 0) {
topologicalSortUtil(graph, i, visited, result, &index);
}
}

// Print the result in reverse order (topological order)

printf("Topological Ordering: ");
for (int i = graph->numVertices - 1; i >= 0; i--) {
printf("%d ", result[i]);
}

free(result);
}

int main() {
// Example graph with 6 vertices
int numVertices = 6;
struct Graph* graph = createGraph(numVertices);

// Adding directed edges

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

School of Computer Science and Engineering Page 12

 Algorithms Lab Course code: B22EF0404
addEdge(graph, 3, 1);

// Perform topological sorting

topologicalSort(graph);

return 0;
}
Code Implementation (Uses the Adjacency Matrix to represent Digraph):
#include <stdio.h>

#define MAX_VERTICES 100

int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int result[MAX_VERTICES];
int numVertices;

// Function to perform depth-first search for topological sorting

void topologicalSortDFS(int vertex, int* index) {
visited[vertex] = 1;

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

if (adjacencyMatrix[vertex][i] && !visited[i]) {
topologicalSortDFS(i, index);
}
}

result[*index] = vertex;
(*index)--;
}

// Function to perform topological sorting

void topologicalSort() {
int index = numVertices - 1;

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

if (!visited[i]) {
topologicalSortDFS(i, &index);
}

School of Computer Science and Engineering Page 13

 Algorithms Lab Course code: B22EF0404
}

// Print the result in order

printf("Topological Ordering: ");
for (int i = 0; i < numVertices; i++) {
printf("%d ", result[i]);
}
}

int main() {
// Example graph with 6 vertices
numVertices = 6;

// Initialize the adjacency matrix (0 for no edge, 1 for an edge)

int edges[][2] = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};

for (int i = 0; i < sizeof(edges) / sizeof(edges[0]); i++) {

int start = edges[i][0];
int end = edges[i][1];
adjacencyMatrix[start][end] = 1;
}

// Perform topological sorting

topologicalSort();

return 0;
}

Sample Output:
Topological Ordering: 5 4 2 3 1 0
Outcome of the Exercise:
The program successfully obtains the topological ordering of vertices in the given directed graph. It
demonstrates the application of depth-first search to identify the linear ordering that satisfies the dependencies
between vertices.
Interview Questions:
1. What is topological sorting, and when is it used?
 Answer: Topological sorting is a linear ordering of vertices in a directed graph such that for every
directed edge (u, v), vertex u comes before v in the ordering. It is used to represent dependencies
between tasks or events.
2. Explain the significance of in-degree in topological sorting.

School of Computer Science and Engineering Page 14

 Algorithms Lab Course code: B22EF0404
 Answer: In-degree represents the number of incoming edges to a vertex. In topological sorting,
vertices with in-degree zero are considered starting points for the ordering since they have no
dependencies.
3. How does depth-first search contribute to topological sorting?
 Answer: Depth-first search explores the graph, marking vertices as visited. During the traversal,
finishing times are recorded, and the vertices are arranged in reverse order of finishing times to achieve
a topological ordering.
4. What is the time complexity of the topological sorting algorithm?
 Answer: The time complexity depends on the traversal algorithm. For depth-first search-based
topological sorting, the time complexity is O(V + E), where V is the number of vertices, and E is the
number of edges in the graph.
5. Can topological sorting be applied to a graph with cycles?
 Answer: No, topological sorting is not possible in a graph with cycles because the dependencies
become cyclic, making it impossible to define a linear ordering.
6. How does the program handle multiple valid topological orderings?
 Answer: The program prints one valid topological ordering. However, there can be multiple valid
orderings. The choice depends on the order in which vertices with in-degree zero are processed during
the DFS traversal.
7. Explain the role of in-degree in detecting the starting vertices for topological sorting.
 Answer: In-degree helps identify vertices with no dependencies (in-degree zero), making them
suitable starting points for topological sorting. These vertices can be processed first, followed by their
dependent vertices.
8. Can topological sorting be applied to an undirected graph?
 Answer: Topological sorting is specific to directed acyclic graphs (DAGs). It cannot be directly
applied to undirected graphs or graphs with cycles.
9. How can topological sorting be used in real-world applications?
 Answer: Topological sorting finds applications in task scheduling, course prerequisites, and job
scheduling, where tasks or events have dependencies that need to be satisfied in a specific order.
10. How does the program handle the scenario of a disconnected graph?
 Answer: The program identifies connected components in the graph and applies topological sorting
separately to each component. The in-degree is considered only for the vertices in the current
connected component.

b. Compute the transitive closure of a given directed graph using Warshall's algorithm
2
Problem Statement:
The problem is to compute the transitive closure of a given directed graph. Transitive closure is a matrix
representation that indicates whether there is a path between every pair of vertices in the graph.

Solution Overview:
The solution involves applying Warshall's algorithm to determine the transitive closure of the directed graph.
Warshall's algorithm is based on the concept of matrix multiplication and iterative closure computation.

Intuition:
Warshall's algorithm works by iteratively updating a matrix to capture the transitive closure. The key idea is to
check for the existence of a path between every pair of vertices through an intermediate vertex. The algorithm
repeats this process until the closure is complete.

Code Implementation:
#include <stdio.h>

School of Computer Science and Engineering Page 15

 Algorithms Lab Course code: B22EF0404

#define MAX_VERTICES 100

int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];
int transitiveClosure[MAX_VERTICES][MAX_VERTICES];
int numVertices;

// Function to compute the transitive closure using Warshall's algorithm

void warshallTransitiveClosure() {
// Initialize the transitive closure matrix with the original adjacency matrix
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
transitiveClosure[i][j] = adjacencyMatrix[i][j];
}
}

// Update the transitive closure matrix iteratively

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

// Function to print the transitive closure matrix

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

int main() {
// Example graph with 4 vertices
numVertices = 4;

// Initialize the adjacency matrix (0 for no edge, 1 for an edge)

int edges[][2] = {{0, 1}, {1, 2}, {1, 3}, {2, 0}, {2, 3}, {3, 3}};

for (int i = 0; i < sizeof(edges) / sizeof(edges[0]); i++) {

int start = edges[i][0];
int end = edges[i][1];
adjacencyMatrix[start][end] = 1;
}

// Compute and print the transitive closure

warshallTransitiveClosure();
printTransitiveClosure();

return 0;
}

Sample Output:
Transitive Closure Matrix:

School of Computer Science and Engineering Page 16

 Algorithms Lab Course code: B22EF0404
1111
1111
1111
0001

Outcome of the Exercise:

The program successfully computes the transitive closure of the given directed graph using Warshall's
algorithm. The transitive closure matrix indicates whether there is a path between every pair of vertices.

Interview Questions:
1. What is the significance of the transitive closure in a directed graph?
 Answer: The transitive closure matrix indicates whether there is a path between every pair of
vertices in a directed graph, providing information about the reachability of vertices.
2. Explain the concept of Warshall's algorithm and its application in transitive closure computation.
 Answer: Warshall's algorithm iteratively updates a matrix to capture the transitive closure of a
directed graph. It checks for the existence of a path between every pair of vertices through an
intermediate vertex.
3. How does the program handle the initialization of the transitive closure matrix?
 Answer: The program initializes the transitive closure matrix with the original adjacency matrix,
representing direct edges between vertices.
4. What is the time complexity of Warshall's algorithm for computing the transitive closure?
 Answer: The time complexity is O(V^3), where V is the number of vertices in the graph, due to the
three nested loops used for matrix multiplication in the algorithm.
5. Can Warshall's algorithm be applied to a graph with cycles?
 Answer: Yes, Warshall's algorithm can be applied to a graph with cycles. It computes the transitive
closure even in the presence of cycles.
6. How can the transitive closure matrix be interpreted in terms of graph reachability?
 Answer: If the entry transitiveClosure[i][j] is 1, it indicates that there is a path from vertex i to vertex
j in the graph.
7. Can the transitive closure matrix be used to detect strongly connected components in a directed
graph?
 Answer: Yes, the transitive closure matrix can be used to identify strongly connected components.
Diagonal elements with a value of 1 represent strongly connected components.
8. How does the transitive closure matrix change if a new edge is added to the original graph?
 Answer: If a new edge is added, the transitive closure matrix is updated to reflect the new
reachability information, ensuring that the closure remains accurate.
9. What modifications would be needed if the graph is represented using an adjacency list instead of an
adjacency matrix?
 Answer: The algorithm would need adjustments to traverse the adjacency list and update the
transitive closure matrix accordingly.
10. In which scenarios is computing the transitive closure of a graph useful?
 Answer: Computing the transitive closure is useful in scenarios where determining reachability
between pairs of vertices is essential, such as in network routing, program analysis, and optimization
problems.

Implement 0/1 Knapsack problem using Dynamic Programming.

3
Problem Statement:
The 0/1 Knapsack problem involves selecting a combination of items, each with a specific weight and value,
to maximize the total value within a given weight capacity. The constraint is that each item can either be
included (1) or excluded (0) from the knapsack.

Solution Overview:
The dynamic programming approach is used to solve the 0/1 Knapsack problem. The solution involves creating
a table to store the maximum value that can be obtained for different subproblems. The final entry in the table
represents the maximum value achievable with the given weight capacity.

Intuition:
The key idea is to build up the solution incrementally by considering each item and either including it in the
knapsack or excluding it. The dynamic programming table is filled based on optimal subproblem solutions,

School of Computer Science and Engineering Page 17

 Algorithms Lab Course code: B22EF0404
considering the maximum value that can be obtained with the current weight capacity and the available items.

Code Implementation:
#include <stdio.h>

#define MAX_ITEMS 100

#define MAX_WEIGHT 100

int weights[MAX_ITEMS];
int values[MAX_ITEMS];
int dp[MAX_ITEMS + 1][MAX_WEIGHT + 1];
int numItems;

// Function to calculate the maximum value using dynamic programming

int knapsack() {
for (int i = 0; i <= numItems; i++) {
for (int w = 0; w <= MAX_WEIGHT; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (weights[i - 1] <= w) {
// Choose the maximum between including and excluding the current item
dp[i][w] = (values[i - 1] + dp[i - 1][w - weights[i - 1]]) > dp[i - 1][w] ? (values[i - 1] + dp[i - 1][w -
weights[i - 1]]) : dp[i - 1][w];
} else {
// If the current item's weight exceeds the remaining capacity, exclude it
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[numItems][MAX_WEIGHT];
}

// Function to trace the selected items

void traceItems() {
int i = numItems;
int w = MAX_WEIGHT;

printf("Selected Items: ");

while (i > 0 && w > 0) {
if (dp[i][w] != dp[i - 1][w]) {
printf("%d ", i);
w -= weights[i - 1];
}
i--;
}
printf("\n");
}

int main() {
// Example items with weights and values
numItems = 4;
weights[0] = 1; values[0] = 5;
weights[1] = 2; values[1] = 3;
weights[2] = 4; values[2] = 5;
weights[3] = 2; values[3] = 3;

// Calculate and print the maximum value

int maxValue = knapsack();
printf("Maximum Value: %d\n", maxValue);

School of Computer Science and Engineering Page 18

 Algorithms Lab Course code: B22EF0404
// Trace and print the selected items
traceItems();

return 0;
}

Sample Output:
Maximum Value: 12 Selected Items: 4 2

Outcome of the Exercise:

The program successfully solves the 0/1 Knapsack problem using dynamic programming, providing the
maximum value that can be obtained and the selection of items to achieve that value within the given weight
capacity.

Interview Questions:
1. What is the 0/1 Knapsack problem, and in which scenarios does it find practical application?
 Answer: The 0/1 Knapsack problem involves selecting items with specific weights and values to
maximize the total value within a given weight capacity. It finds applications in resource allocation,
inventory management, and optimization problems.
2. Explain the concept of dynamic programming and how it is applied to solve the 0/1 Knapsack problem.
 Answer: Dynamic programming involves breaking down a complex problem into smaller
subproblems and solving them independently. In the case of the 0/1 Knapsack problem, a table is filled
iteratively to represent optimal solutions to subproblems, leading to the overall solution.
3. How is the dynamic programming table initialized, and what information does it store?
 Answer: The table is initialized with zeros. It stores the maximum value that can be obtained for
different subproblems, considering the available items and weight capacities.
4. Why is the dynamic programming table filled in a bottom-up manner?
 Answer: Filling the table in a bottom-up manner ensures that optimal solutions to subproblems are
available when needed, leading to the efficient computation of the overall solution.
5. What is the significance of the decision-making logic in the dynamic programming loop?
 Answer: The decision-making logic determines whether to include or exclude the current item in the
knapsack. It is based on comparing the total value obtained by including the item and excluding the
item, choosing the option with the higher value.
6. How does the program handle the case when the weight of a selected item exceeds the remaining
capacity?
 Answer: If the weight of the current item exceeds the remaining capacity, the program excludes the
item from the knapsack, ensuring that the weight constraint is not violated.
7. Can the 0/1 Knapsack problem be solved using greedy algorithms?
 Answer: While greedy algorithms are suitable for some knapsack variations, they may not guarantee
an optimal solution for the 0/1 Knapsack problem due to its binary nature.
8. How does the program trace and print the selected items contributing to the maximum value?
 Answer: The program traces the items by backtracking through the dynamic programming table,
identifying the items that were included in the optimal solution.
9. What modifications would be needed if the weights and values of items were read from an external
file?
 Answer: The program would need modifications to read the weights and values from an external file,
ensuring the data is appropriately processed and utilized in the knapsack calculation.
10. In what scenarios would a brute-force approach be impractical for solving the 0/1 Knapsack
problem?
 Answer: The 0/1 Knapsack problem involves exponential time complexity when solved using brute-
force approaches, making it impractical for larger instances with numerous items. Dynamic
programming provides a more efficient solution in such cases.

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

Problem Statement:
The task is to find the shortest paths from a given source vertex to all other vertices in a weighted connected
graph. The graph can be represented by an adjacency matrix, where each edge has a non-negative weight.

School of Computer Science and Engineering Page 19

 Algorithms Lab Course code: B22EF0404
Dijkstra's algorithm efficiently computes the shortest paths in such graphs.

Solution Overview:
Dijkstra's algorithm is used to solve the problem. It is a greedy algorithm that maintains a set of vertices with
known minimum distances from the source vertex. The algorithm iteratively selects the vertex with the
minimum distance, updates the distances to its neighbors, and continues until all vertices are processed.

Intuition:
The algorithm starts with the source vertex, initializing distances to all other vertices as infinity. It then explores
neighbors of the source vertex, updating their distances based on the weights of the connecting edges. The
process repeats, selecting the vertex with the minimum distance in each iteration until all vertices are visited.

Code Implementation:

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

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];
int numVertices;

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

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

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

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

return minIndex;
}

// Function to print the distances from the source vertex to all other vertices
void printSolution(int dist[]) {
printf("Vertex Distance from Source\n");
for (int i = 0; i < numVertices; i++) {
printf("%d\t%d\n", i, dist[i]);
}
}

// Function to implement Dijkstra's algorithm

void dijkstra(int src) {
int dist[MAX_VERTICES];
int sptSet[MAX_VERTICES];

// Initialize distances and set to track visited vertices

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

// Distance from the source vertex to itself is always 0

dist[src] = 0;

// Find the shortest paths for all vertices

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

School of Computer Science and Engineering Page 20

 Algorithms Lab Course code: B22EF0404
int u = minDistance(dist, sptSet);
sptSet[u] = 1;

for (int v = 0; v < numVertices; 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 solution

printSolution(dist);
}

int main() {
// Example graph with 5 vertices
numVertices = 5;
int srcVertex = 0; // Source vertex

// Initialize the weighted graph (0 for no edge)

int edges[][5] = {{0, 4, 0, 0, 2},
{4, 0, 3, 8, 0},
{0, 3, 0, 0, 0},
{0, 8, 0, 0, 5},
{2, 0, 0, 5, 0}};

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

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

// Apply Dijkstra's algorithm

dijkstra(srcVertex);

return 0;
}
Sample Output:
Vertex Distance from Source
00
14
27
3 11
42

Outcome of the Exercise:

The program successfully applies Dijkstra's algorithm to find the shortest paths from a given source vertex to
all other vertices in a weighted connected graph. It outputs the distances from the source vertex to each
destination vertex.

Interview Questions:
1. What is Dijkstra's algorithm, and how does it work?
 Answer: Dijkstra's algorithm is a greedy algorithm that finds the shortest paths from a source vertex
to all other vertices in a weighted graph. It iteratively selects the vertex with the minimum distance,
updates distances to its neighbors, and repeats until all vertices are processed.
2. Explain the significance of the dist array in the algorithm.
 Answer: The dist array stores the shortest distances from the source vertex to all other vertices. It is
initialized to infinity, and the algorithm updates it during each iteration based on the current minimum
distances.
3. How does the program handle vertices with no direct edges from the source vertex?

School of Computer Science and Engineering Page 21

 Algorithms Lab Course code: B22EF0404
 Answer: The program sets the distance to vertices with no direct edges to infinity initially. If a shorter
path is discovered during the algorithm, the distance is updated.
4. What is the purpose of the sptSet array, and how is it utilized in the algorithm?
 Answer: The sptSet array is used to keep track of visited vertices. It ensures that the algorithm does
not revisit vertices that have already been processed, preventing unnecessary calculations.
5. How does the algorithm handle weighted edges with non-negative values?
 Answer: The algorithm considers only non-negative weights. It updates the distance to a vertex if a
shorter path is found through the current vertex being processed.
6. What modifications would be needed to handle a graph with negative edge weights?
 Answer: Dijkstra's algorithm is not suitable for graphs with negative edge weights. For handling
negative weights, a different algorithm like Bellman-Ford should be used.
7. What is the time complexity of Dijkstra's algorithm, and in what scenarios is it efficient?
 Answer: The time complexity is O(V^2) with an adjacency matrix or O((V + E) * log(V)) with a min-
priority queue using an adjacency list. It is efficient for dense graphs and scenarios where edge weights
are non-negative.
8. Can the algorithm handle graphs with cycles?
 Answer: Dijkstra's algorithm is designed for graphs without cycles. It may produce incorrect results
in the presence of cycles, as it assumes that once a vertex is marked as visited, its shortest path is
found.
9. How does the program ensure that the correct shortest paths are identified during backtracking?
 Answer: The program backtracks by selecting the vertex with the minimum distance in each iteration.
This ensures that the shortest paths are considered while updating the distances.
10. In what real-world scenarios is Dijkstra's algorithm commonly used?
 Answer: Dijkstra's algorithm is used in network routing, transportation systems, and logistics to find
the shortest paths between locations. It also finds applications in robotics and resource management.

Find the Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.
5
Problem Statement:
The task is to find the Minimum Cost Spanning Tree (MCST) of a given undirected graph. A Minimum Cost
Spanning Tree is a subset of the edges of the graph that connects all vertices with the minimum possible total
edge weight, without forming cycles. Kruskal's algorithm is a greedy approach to solving this problem.

Solution Overview:
Kruskal's algorithm works by sorting all the edges based on their weights and then selecting edges in ascending
order while ensuring that adding each edge does not create a cycle in the evolving tree. The process continues
until all vertices are connected.

Intuition:
1. Sort all edges in non-decreasing order based on their weights.
2. Initialize an empty tree.
3. Start selecting edges with the smallest weight.
4. Add each selected edge to the tree only if it does not create a cycle.
5. Repeat until all vertices are connected.

Code Implementation (in C Programming Language):

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

#define MAX_VERTICES 100

#define MAX_EDGES 100

// Structure to represent an edge

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

struct Edge edges[MAX_EDGES];

int parent[MAX_VERTICES];
int numVertices, numEdges;

School of Computer Science and Engineering Page 22

 Algorithms Lab Course code: B22EF0404

// Function to find the set of a vertex (used for cycle detection)

int findSet(int i) {
while (parent[i] != i) {
i = parent[i];
}
return i;
}

// Function to perform union of two sets

void unionSets(int x, int y) {
int xRoot = findSet(x);
int yRoot = findSet(y);
parent[xRoot] = yRoot;
}

// Function to implement Kruskal's algorithm

void kruskal() {
int mcstEdges = 0; // Count of edges in the MCST
int i = 0; // Index to iterate through sorted edges array

// Sort edges based on weights in non-decreasing order

qsort(edges, numEdges, sizeof(struct Edge), [](const void *a, const void *b) {
return ((struct Edge *)a)->weight - ((struct Edge *)b)->weight;
});

// Initialize each vertex as a separate set

for (int v = 0; v < numVertices; v++) {
parent[v] = v;
}

// Construct the MCST

while (mcstEdges < numVertices - 1 && i < numEdges) {
struct Edge nextEdge = edges[i++];

// Find the sets of source and destination vertices

int x = findSet(nextEdge.src);
int y = findSet(nextEdge.dest);

// Add the edge to the MCST only if it doesn't create a cycle

if (x != y) {
printf("Edge %d-%d with weight %d added to the Minimum Cost Spanning Tree\n", nextEdge.src,
nextEdge.dest, nextEdge.weight);
unionSets(x, y);
mcstEdges++;
}
}
}

int main() {
// Example graph with 4 vertices and 5 edges
numVertices = 4;
numEdges = 5;

// Define edges with their source, destination, and weight

edges[0] = (struct Edge){0, 1, 10};
edges[1] = (struct Edge){0, 2, 6};
edges[2] = (struct Edge){0, 3, 5};
edges[3] = (struct Edge){1, 3, 15};
edges[4] = (struct Edge){2, 3, 4};

School of Computer Science and Engineering Page 23

 Algorithms Lab Course code: B22EF0404

// Apply Kruskal's algorithm to find the MCST

kruskal();

return 0;
}

Sample Output:
Edge 2-3 with weight 4 added to the Minimum Cost Spanning Tree
Edge 0-3 with weight 5 added to the Minimum Cost Spanning Tree
Edge 0-1 with weight 10 added to the Minimum Cost Spanning Tree

Outcome of the Exercise:

The program successfully applies Kruskal's algorithm to find the Minimum Cost Spanning Tree of the given
undirected graph. It outputs the edges that form the Minimum Cost Spanning Tree.

Interview Questions:
1. What is a Minimum Cost Spanning Tree, and in what practical scenarios is it useful?
 Answer: A Minimum Cost Spanning Tree is a subset of edges of a connected, undirected graph with
the minimum possible total edge weight. It finds applications in network design, circuit design, and
transportation planning.
2. How does Kruskal's algorithm work to find the Minimum Cost Spanning Tree?
 Answer: Kruskal's algorithm works by sorting edges based on weights and then iteratively selecting
edges in ascending order while ensuring that each selected edge does not form a cycle in the evolving
tree.
3. What is the role of the parent array in Kruskal's algorithm?
 Answer: The parent array is used for disjoint-set data structure operations. It keeps track of the sets
to which each vertex belongs, allowing the algorithm to determine whether adding an edge would
create a cycle.
4. How does the algorithm ensure that the Minimum Cost Spanning Tree does not contain cycles?
 Answer: The algorithm uses the disjoint-set data structure to keep track of sets of vertices. It checks
whether adding an edge between two vertices would create a cycle by verifying if they already belong
to the same set.
5. Why does the algorithm start by sorting edges in non-decreasing order based on weights?
 Answer: Sorting edges based on weights allows the algorithm to consider edges in ascending order,
ensuring that the smallest-weighted edges are added first and preventing the formation of cycles.
6. What is the time complexity of Kruskal's algorithm, and in what scenarios is it efficient?
 Answer: The time complexity is O(E log E) for sorting edges, where E is the number of edges. It is
efficient for sparse graphs where the number of edges is significantly less than the number of vertices.
7. Can Kruskal's algorithm handle graphs with negative edge weights?
 Answer: Yes, Kruskal's algorithm can handle graphs with negative edge weights as long as there are
no negative cycles. However, in practice, other algorithms like Prim's algorithm or Boruvka's
algorithm might be preferred for graphs with negative weights.
8. What modifications would be needed if the graph edges were read from an external file?
 Answer: The program would need modifications to read edge information from an external file,
ensuring proper parsing and conversion of data.
9. How does the program output the edges that form the Minimum Cost Spanning Tree?
 Answer: The program outputs the selected edges during the execution of Kruskal's algorithm,
indicating which edges are added to the Minimum Cost Spanning Tree.
10. What happens if the input graph is not connected or has disconnected components?
 Answer: Kruskal's algorithm assumes a connected graph. If the graph is not connected, the algorithm
will find a Minimum Cost Spanning Forest, which is a collection of Minimum Cost Spanning Trees
for each connected component.

Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.
6
Problem Statement:
The task is to find the Minimum Cost Spanning Tree (MCST) of a given undirected graph using Prim's
algorithm. A Minimum Cost Spanning Tree is a subset of the edges of the graph that connects all vertices with
the minimum possible total edge weight, without forming cycles.

School of Computer Science and Engineering Page 24

 Algorithms Lab Course code: B22EF0404

Solution Overview:
Prim's algorithm is a greedy algorithm that starts with an arbitrary vertex and incrementally grows the
Minimum Cost Spanning Tree by adding the edge with the smallest weight that connects a vertex in the tree to
a vertex outside the tree. This process continues until all vertices are included in the tree.

Intuition:
1. Start with an arbitrary vertex as the initial tree.
2. Grow the tree by adding the minimum-weight edge that connects a vertex in the tree to a vertex outside
the tree.
3. Repeat until all vertices are included in the tree.
4.
Code Implementation:
#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 100

#define MAX_EDGES 100

int graph[MAX_VERTICES][MAX_VERTICES];
int numVertices, numEdges;

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

int minKey(int key[], int mstSet[]) {
int min = INT_MAX, minIndex;

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

if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}

return minIndex;
}

// Function to print the Minimum Cost Spanning Tree

void printMST(int parent[]) {
printf("Edge Weight\n");
for (int i = 1; i < numVertices; i++) {
printf("%d - %d %d\n", parent[i], i, graph[i][parent[i]]);
}
}

// Function to implement Prim's algorithm

void prim() {
int parent[MAX_VERTICES]; // Array to store the constructed MST
int key[MAX_VERTICES]; // Key values used to pick the minimum weight edge
int mstSet[MAX_VERTICES]; // Set to track vertices included in MST

// Initialize key values and set

for (int i = 0; i < numVertices; i++) {
key[i] = INT_MAX;
mstSet[i] = 0;
}

// Start with the first vertex

key[0] = 0;
parent[0] = -1; // No parent for the first vertex

School of Computer Science and Engineering Page 25

 Algorithms Lab Course code: B22EF0404
// Construct the MST
for (int count = 0; count < numVertices - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = 1; // Include the picked vertex in MST

// Update key values and parent for adjacent vertices

for (int v = 0; v < numVertices; v++) {
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}

// Print the MST

printMST(parent);
}

int main() {
// Example graph with 5 vertices and 7 edges
numVertices = 5;
numEdges = 7;

// Define edges with their source, destination, and weight

int edges[][3] = {{0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {2, 4, 7}, {3, 4, 9}};

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

int src = edges[i][0];
int dest = edges[i][1];
int weight = edges[i][2];
graph[src][dest] = weight;
graph[dest][src] = weight; // Undirected graph
}

// Apply Prim's algorithm to find the MCST

prim();

return 0;
}

Sample Output:
Edge Weight
0-1 2
1-2 3
0-3 6
1–4 5

Outcome of the Exercise:

The program successfully applies Prim's algorithm to find the Minimum Cost Spanning Tree of the given
undirected graph. It outputs the edges that form the Minimum Cost Spanning Tree.

Interview Questions:
1. What is Prim's algorithm, and how does it work?
 Answer: Prim's algorithm is a greedy algorithm that finds the Minimum Cost Spanning Tree of a
connected, undirected graph. It starts with an arbitrary vertex and grows the tree by adding the
minimum-weight edge that connects a vertex in the tree to a vertex outside the tree.
2. How does the program initialize key values and the set in Prim's algorithm?
 Answer: Key values are initialized to infinity, and the set is initialized to include no vertices. These
data structures are used to keep track of the minimum weight edge and vertices included in the MST.
3. Explain the role of the minKey function in Prim's algorithm.

School of Computer Science and Engineering Page 26

 Algorithms Lab Course code: B22EF0404
 Answer: The minKey function finds the vertex with the minimum key value among the vertices not
yet included in the MST. It is used to select the next vertex to be included in the MST.
4. How is the MST constructed in Prim's algorithm, and what is the termination condition?
 Answer: The MST is constructed by iteratively adding the minimum-weight edge that connects a
vertex in the tree to a vertex outside the tree. The algorithm terminates when all vertices are included
in the MST.
5. What is the significance of the parent array in Prim's algorithm?
 Answer: The parent array keeps track of the parent of each vertex in the MST. It is used to identify
the edges that form the MST during the final output.
6. What happens if the input graph is not connected or has disconnected components in Prim's
algorithm?
 Answer: Prim's algorithm assumes a connected graph. If the graph is not connected, the algorithm will
find the Minimum Cost Spanning Forest, which is a collection of Minimum Cost Spanning Trees for
each connected component.
7. What is the time complexity of Prim's algorithm, and in what scenarios is it efficient?
 Answer: The time complexity is O(V^2) with an adjacency matrix or O((V + E) * log(V)) with a min-
priority queue using an adjacency list. It is efficient for dense graphs and scenarios where edge weights
are non-negative.
8. How does the program output the edges that form the Minimum Cost Spanning Tree?
 Answer: The program outputs the selected edges during the execution of Prim's algorithm, indicating
which edges are added to the Minimum Cost Spanning Tree.
9. What modifications would be needed if the graph edges were read from an external file?
 Answer: The program would need modifications to read edge information from an external file,
ensuring proper parsing and conversion of data.
10. Can Prim's algorithm handle graphs with negative edge weights?
 Answer: Prim's algorithm assumes non-negative edge weights. If the graph has negative edge weights,
the algorithm might not provide the correct results. Other algorithms like Kruskal's or Boruvka's may
be more suitable for such cases.

Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve
7
the same problem instance using any approximation algorithm and determine the error in the
approximation.

Problem Statement:
The task is to implement a scheme to find the optimal solution for the Traveling Salesperson Problem (TSP)
and then solve the same problem instance using any approximation algorithm. The goal is to determine the
error in the approximation compared to the optimal solution.

Solution Overview:
The Traveling Salesperson Problem is an NP-hard problem that seeks to find the shortest possible route that
visits a set of cities and returns to the starting city. Solving it optimally for large instances can be
computationally expensive. One common approach is to use approximation algorithms that provide reasonably
good solutions in a shorter amount of time.

Intuition:
1. Optimal Solution (Exact Algorithm):
 Use an exact algorithm (e.g., dynamic programming) to find the optimal solution for the TSP.
2. Approximation Algorithm:
 Select an approximation algorithm (e.g., nearest neighbor, minimum spanning tree) for a
quick but suboptimal solution.
3. Determine Error:
 Compare the cost of the solution obtained from the approximation algorithm with the cost of
the optimal solution to calculate the error.

Code Implementation:

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

#define MAX_CITIES 10

School of Computer Science and Engineering Page 27

 Algorithms Lab Course code: B22EF0404

int adjacencyMatrix[MAX_CITIES][MAX_CITIES];
int numCities;

// Function to find the optimal solution using dynamic programming

int optimalTSP(int mask, int pos) {
// Base case: all cities visited
if (mask == (1 << numCities) - 1) {
return adjacencyMatrix[pos][0]; // Return to starting city
}

int minCost = INT_MAX;

// Try to visit each unvisited city

for (int city = 0; city < numCities; city++) {
if ((mask & (1 << city)) == 0) {
int newCost = adjacencyMatrix[pos][city] + optimalTSP(mask | (1 << city), city);
minCost = (newCost < minCost) ? newCost : minCost;
}
}

return minCost;
}

// Function to find the approximate solution using the nearest neighbor algorithm
int approximateTSP() {
int visited[MAX_CITIES] = {0};
int currentCity = 0;
int totalCost = 0;

visited[currentCity] = 1;

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

int nearestCity = -1;
int minCost = INT_MAX;

for (int nextCity = 0; nextCity < numCities; nextCity++) {

if (!visited[nextCity] && adjacencyMatrix[currentCity][nextCity] < minCost) {
nearestCity = nextCity;
minCost = adjacencyMatrix[currentCity][nextCity];
}
}

visited[nearestCity] = 1;
totalCost += minCost;
currentCity = nearestCity;
}

// Return to the starting city

totalCost += adjacencyMatrix[currentCity][0];

return totalCost;
}

int main() {
// Example TSP instance with 4 cities
numCities = 4;

// Define the adjacency matrix with distances between cities

int distances[][4] = {{0, 10, 15, 20},

School of Computer Science and Engineering Page 28

 Algorithms Lab Course code: B22EF0404
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};

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

for (int j = 0; j < numCities; j++) {
adjacencyMatrix[i][j] = distances[i][j];
}
}

// Find the optimal solution using dynamic programming

int optimalCost = optimalTSP(1, 0); // Start from the first city (0)

// Find the approximate solution using the nearest neighbor algorithm

int approximateCost = approximateTSP();

// Determine the error in the approximation

int error = approximateCost - optimalCost;

// Output results
printf("Optimal TSP Cost: %d\n", optimalCost);
printf("Approximate TSP Cost: %d\n", approximateCost);
printf("Error in Approximation: %d\n", error);

return 0;
}

Sample Output:
Optimal TSP Cost: 80
Approximate TSP Cost: 85
Error in Approximation: 5

Outcome of the Exercise:

The program demonstrates finding the optimal solution for the Traveling Salesperson Problem using dynamic
programming and then uses the nearest neighbor algorithm as an approximation. It calculates and outputs the
error in the approximation compared to the optimal solution.

Interview Questions:
1. What is the Traveling Salesperson Problem, and why is it considered a challenging problem?
 Answer: The Traveling Salesperson Problem involves finding the shortest possible route that visits a
set of cities and returns to the starting city. It is challenging because it is NP-hard, meaning there is
no known polynomial-time algorithm to solve it optimally for all instances.
2. Explain the intuition behind the dynamic programming approach to solving the TSP.
 Answer: The dynamic programming approach systematically explores all possible combinations of
cities and their orders, calculating the total cost for each combination. The optimal solution is obtained
by selecting the combination with the minimum cost.
3. Why is dynamic programming used to find the optimal solution rather than a greedy approach?
 Answer: Dynamic programming ensures optimality by considering all possible combinations and
avoiding suboptimal choices. A greedy approach, while faster, may not guarantee the optimal solution.
4. What is the nearest neighbor algorithm, and how does it work in approximating the TSP?
 Answer: The nearest neighbor algorithm starts from an arbitrary city and repeatedly selects the nearest
unvisited city until all cities are visited. It provides a quick but suboptimal solution by making locally
optimal choices.
5. How does the program calculate the error in the approximation?
 Answer: The error in the approximation is calculated by subtracting the cost of the optimal solution
from the cost of the approximate solution.
6. What are the advantages and disadvantages of using approximation algorithms for the TSP?
 Answer: Approximation algorithms are faster but may not guarantee optimality. They are suitable for
large instances where finding the optimal solution is impractical.
7. Can you suggest other approximation algorithms commonly used for the TSP?

School of Computer Science and Engineering Page 29

 Algorithms Lab Course code: B22EF0404
 Answer: Other approximation algorithms include the Christofides algorithm, the Lin-Kernighan
algorithm, and the Ant Colony Optimization algorithm.
8. How does the error in the approximation change with the size of the TSP instance?
 Answer: In general, the error in the approximation tends to increase as the size of the TSP instance
grows. Approximation algorithms may provide better results for smaller instances compared to larger
ones.
9. What modifications would be needed if the TSP instance were read from an external file?
 Answer: The program would need modifications to read the TSP instance (e.g., adjacency matrix or
distance matrix) from an external file, ensuring proper parsing and conversion of data.

a) For a given graph, print all the nodes reachable from a given starting node in a digraph using Breadth
8
First Search method.

Problem Statement:
The task is to print all the nodes reachable from a given starting node in a directed graph using the Breadth-
First Search (BFS) method. The goal is to systematically explore all reachable nodes in a breadthward motion
from the starting node.

Solution Overview:
Breadth-First Search is a graph traversal algorithm that explores all the vertices at the current level before
moving on to the vertices at the next level. It is particularly useful for finding the shortest path in an unweighted
graph and can be applied to discover all reachable nodes from a given starting node.

Intuition:
1. Queue-based Exploration:
 Use a queue data structure to keep track of the nodes to be visited.
 Enqueue the starting node.
 While the queue is not empty, dequeue a node, print it, and enqueue its unvisited neighbors.
2. Mark Visited Nodes:
 Use a boolean array to mark nodes as visited to avoid redundant processing.

Code Implementation:
#include <stdio.h>
#include <stdbool.h>

#define MAX_NODES 100

int adjacencyMatrix[MAX_NODES][MAX_NODES];
int numNodes;

// Function to perform Breadth-First Search

void BFS(int startNode) {
bool visited[MAX_NODES] = {false};
int queue[MAX_NODES];
int front = -1, rear = -1;

// Enqueue the starting node

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

while (front != rear) {

// Dequeue a node and print it
int currentNode = queue[++front];
printf("%d ", currentNode);

// Enqueue unvisited neighbors

for (int i = 0; i < numNodes; i++) {
if (adjacencyMatrix[currentNode][i] == 1 && !visited[i]) {
queue[++rear] = i;

School of Computer Science and Engineering Page 30

 Algorithms Lab Course code: B22EF0404
visited[i] = true;
}
}
}
}

int main() {
// Example directed graph with 5 nodes and 7 edges
numNodes = 5;

// Define the adjacency matrix (1 indicates a directed edge)

int edges[][2] = {{0, 1}, {0, 2}, {1, 2}, {2, 0}, {2, 3}, {3, 3}, {4, 4}};

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

int src = edges[i][0];
int dest = edges[i][1];
adjacencyMatrix[src][dest] = 1;
}

// Specify the starting node for BFS

int startNode = 2;

// Perform BFS from the starting node

printf("Nodes reachable from %d: ", startNode);
BFS(startNode);

return 0;
}

Sample Output:
Nodes reachable from 2: 2 0 3 1

Outcome of the Exercise:

The program successfully prints all nodes reachable from a given starting node in a directed graph using the
Breadth-First Search method. It systematically explores the graph in breadthward motion, avoiding redundant
processing of already visited nodes.

Interview Questions:
1. What is Breadth-First Search (BFS), and how does it differ from Depth-First Search (DFS)?
 Answer: BFS is a graph traversal algorithm that explores all vertices at the current level before moving
on to the next level. DFS explores as far as possible along each branch before backtracking.
2. Explain the role of the queue data structure in BFS.
 Answer: The queue is used to keep track of the nodes to be visited in a first-in, first-out manner. Nodes
are enqueued when discovered and dequeued when processed.
3. How does the program avoid redundant processing of nodes in BFS?
 Answer: The program uses a boolean array (visited) to mark nodes as visited. Before enqueuing a
neighbor, it checks whether the neighbor is already marked as visited.
4. What is the significance of the adjacency matrix in representing a directed graph?
 Answer: The adjacency matrix indicates the presence or absence of directed edges between nodes. In
this program, a value of 1 in adjacencyMatrix[i][j] signifies a directed edge from node i to node j.
5. How would the program change if it needed to handle a weighted directed graph?
 Answer: For a weighted graph, the adjacency matrix would store weights instead of binary values.
The traversal logic would remain similar, but edge weights would be considered in specific scenarios.
6. What modifications would be needed if the graph edges were read from an external file?
 Answer: The program would need modifications to read edge information from an external file,
ensuring proper parsing and conversion of data.
7. Can BFS be applied to an undirected graph, and how would it differ?
 Answer: Yes, BFS can be applied to an undirected graph. The primary difference is that in an
undirected graph, there is no concept of incoming or outgoing edges. The adjacency matrix would be
symmetric.

School of Computer Science and Engineering Page 31

 Algorithms Lab Course code: B22EF0404
8. What is the time complexity of BFS, and under what scenarios is it efficient?
 Answer: The time complexity of BFS is O(V + E), where V is the number of vertices and E is the
number of edges. It is efficient for finding the shortest path in an unweighted graph or determining
connectivity.

b) For a given graph, check whether a given graph is connected or not using DFS method.
8
Problem Statement:
The task is to check whether a given graph is connected or not using the Depth-First Search (DFS) method.
The goal is to determine if there exists a path between every pair of nodes in the graph.

Solution Overview:
Depth-First Search is a graph traversal algorithm that explores as far as possible along each branch before
backtracking. By applying DFS and visiting all nodes, we can determine if the graph is connected.

Intuition:
DFS Exploration:
 Start DFS from an arbitrary node.
 Mark each visited node.
 If all nodes are visited, the graph is connected.

Code Implementation:
#include <stdio.h>
#include <stdbool.h>

#define MAX_NODES 100

int adjacencyMatrix[MAX_NODES][MAX_NODES];
int numNodes;

// Function to perform Depth-First Search

void DFS(int currentNode, bool visited[]) {
visited[currentNode] = true;

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

if (adjacencyMatrix[currentNode][i] == 1 && !visited[i]) {
DFS(i, visited);
}
}
}

// Function to check if the graph is connected

bool isConnected() {
bool visited[MAX_NODES] = {false};

// Start DFS from the first node

DFS(0, visited);

// Check if all nodes are visited

for (int i = 0; i < numNodes; i++) {
if (!visited[i]) {
return false; // Graph is not connected
}
}

return true; // Graph is connected

}

int main() {
// Example graph with 5 nodes and 7 edges

School of Computer Science and Engineering Page 32

 Algorithms Lab Course code: B22EF0404
numNodes = 5;

// Define the adjacency matrix (1 indicates an edge)

int edges[][2] = {{0, 1}, {0, 2}, {1, 2}, {2, 0}, {2, 3}, {3, 3}, {4, 4}};

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

int src = edges[i][0];
int dest = edges[i][1];
adjacencyMatrix[src][dest] = 1;
}

// Check if the graph is connected

if (isConnected()) {
printf("The graph is connected.\n");
} else {
printf("The graph is not connected.\n");
}

return 0;
}

Sample Output:
The graph is connected.

Outcome of the Exercise:

The program successfully checks whether a given graph is connected or not using the Depth-First Search
method. It explores the graph, marks visited nodes, and determines if all nodes are visited, indicating
connectivity.

Interview Questions:
1. What is the significance of the DFS algorithm in checking graph connectivity?
 Answer: DFS explores the graph and marks visited nodes, allowing us to check if there exists a path
between every pair of nodes. If all nodes are visited during DFS, the graph is connected.
2. How does the program ensure all nodes are visited during DFS?
 Answer: The program uses a boolean array (visited) to mark nodes as visited. After DFS, it checks if
all nodes are marked as visited to determine graph connectivity.
3. Can DFS be applied to an undirected graph for checking connectivity, and how would it differ?
 Answer: Yes, DFS can be applied to an undirected graph for checking connectivity. The primary
difference is that in an undirected graph, there is no concept of incoming or outgoing edges.
4. Explain the role of the adjacency matrix in representing a directed graph.
 Answer: The adjacency matrix indicates the presence or absence of directed edges between nodes. In
this program, a value of 1 in adjacencyMatrix[i][j] signifies a directed edge from node i to node j.
5. How does the program handle disconnected components in a graph?
 Answer: The program starts DFS from an arbitrary node and checks if all nodes are visited. If the
graph has disconnected components, not all nodes will be visited, indicating that the graph is not
connected.
6. What modifications would be needed if the graph edges were read from an external file?
 Answer: The program would need modifications to read edge information from an external file,
ensuring proper parsing and conversion of data.
7. What is the time complexity of DFS, and in what scenarios is it efficient?
 Answer: The time complexity of DFS is O(V + E), where V is the number of vertices and E is the
number of edges. It is efficient for checking connectivity and exploring paths in a graph.

Implement N Queen's problem using Back Tracking

9
Problem Statement:
The N Queens problem involves placing N chess queens on an N×N chessboard in such a way that no two
queens threaten each other. This means that no two queens can be in the same row, column, or diagonal. The
goal is to find a placement of queens that satisfies these constraints.

School of Computer Science and Engineering Page 33

 Algorithms Lab Course code: B22EF0404
Solution Overview:
The Backtracking algorithm is a suitable approach for solving the N Queens problem. Backtracking
systematically explores potential solutions and abandons a partial solution ("backtracks") as soon as it
determines that the solution cannot be extended to a valid one.

Intuition:
1. Recursion and Decision Points:
 Use recursive calls to explore possible configurations.
 At each decision point, try placing a queen in an unoccupied position.
2. Check Constraints:
 Check if placing a queen at the current position violates any constraints.
 If valid, proceed with the next row; otherwise, backtrack.

Code Implementation:
#include <stdio.h>
#include <stdbool.h>

#define N 8

int board[N][N];

// Function to print the chessboard

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

// Function to check if placing a queen at board[row][col] is safe

bool isSafe(int row, int col) {
// Check left side of the current row
for (int i = 0; i < col; i++) {
if (board[row][i] == 1) {
return false;
}
}

// Check upper diagonal on the left side

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

// Check lower diagonal on the left side

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

return true;
}

// Function to solve the N Queens problem using backtracking

bool solveNQueens(int col) {
// Base case: All queens are placed

School of Computer Science and Engineering Page 34

 Algorithms Lab Course code: B22EF0404
if (col == N) {
return true;
}

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

// Check if placing a queen at board[i][col] is safe
if (isSafe(i, col)) {
// Place the queen
board[i][col] = 1;

// Recur to place queens in the remaining columns

if (solveNQueens(col + 1)) {
return true; // Solution found
}

// If placing a queen does not lead to a solution, backtrack

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

return false; // No solution in this branch

}

int main() {
// Initialize the chessboard
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = 0;
}
}

// Solve the N Queens problem

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

return 0;
}

Sample Output:
Solution found:
10000000
00000100
00000001
00001000
00100000
00000010
01000000
00010000

Outcome of the Exercise:

The program successfully solves the N Queens problem using the Backtracking algorithm. It finds a valid
placement of queens on the chessboard such that no two queens threaten each other.

Interview Questions:
1. Explain the N Queens problem and its significance in computer science.
 Answer: The N Queens problem involves placing N queens on an N×N chessboard without any two

School of Computer Science and Engineering Page 35

 Algorithms Lab Course code: B22EF0404
queens threatening each other. It is a classic problem used to demonstrate problem-solving and
algorithmic techniques.
2. Why is the Backtracking algorithm suitable for solving the N Queens problem?
 Answer: Backtracking systematically explores potential solutions and abandons a partial solution
("backtracks") as soon as it determines that the solution cannot be extended to a valid one. This aligns
well with the N Queens problem's constraints.
3. What are the constraints that a valid placement of queens must satisfy in the N Queens problem?
 Answer: No two queens can be in the same row, column, or diagonal. Placing a queen must not
threaten any other queens on the chessboard.
4. Explain the role of the isSafe function in the program.
 Answer: The isSafe function checks if placing a queen at a specific position violates any constraints.
It ensures that no queens in the same row, column, or diagonal can threaten each other.
5. How does the program handle the case where no solution exists for the N Queens problem?
 Answer: If the solveNQueens function returns false, the program prints "No solution exists." This
indicates that no valid placement of queens on the chessboard satisfies the constraints.
6. What modifications would be needed to extend the program to handle an N×M chessboard?
 Answer: The program would need adjustments to handle an N×M chessboard. The N constant would
be replaced with variables N and M throughout the code.
7. What is the time complexity of the Backtracking solution for the N Queens problem?
 Answer: The time complexity is exponential, O(N!), where N is the size of the chessboard. This is
because each queen placement involves exploring a branch of possibilities, leading to a combinatorial
explosion.

Implement All-Pairs Shortest Paths Problem using Floyd's algorithm

10
Problem Statement:
The All-Pairs Shortest Paths problem involves finding the shortest paths between every pair of vertices in a
weighted directed graph. The goal is to compute a matrix of shortest path distances between all pairs of vertices.

Solution Overview:
Floyd's algorithm is a dynamic programming approach that efficiently solves the All-Pairs Shortest Paths
problem. It iteratively updates the shortest path distances between pairs of vertices by considering all
intermediate vertices.

Intuition:
1. Dynamic Programming Table:
 Use a 2D matrix to represent the shortest path distances.
 Initialize the matrix with direct edge weights.
2. Iterative Updates:
 For each intermediate vertex, check if going through it improves the distance between two
vertices.
 Update the matrix with the minimum distance.

Code Implementation:
#include <stdio.h>

#define INF 99999

#define V 4

// Function to print the shortest path matrix

void printSolution(int dist[][V]) {
printf("Shortest path matrix:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF) {
printf(" INF ");
} else {
printf("%4d ", dist[i][j]);
}

School of Computer Science and Engineering Page 36

 Algorithms Lab Course code: B22EF0404
}
printf("\n");
}
}

// Function to solve the All-Pairs Shortest Paths problem using Floyd's algorithm
void floydWarshall(int graph[][V]) {
int dist[V][V];

// Initialize the distance matrix with direct edge weights

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

// Consider each vertex as an intermediate vertex and update the distance matrix
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 path matrix

printSolution(dist);
}

int main() {
// Example weighted directed graph (4 vertices)
int graph[V][V] = {{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}};

// Solve the All-Pairs Shortest Paths problem using Floyd's algorithm

floydWarshall(graph);

return 0;
}

Sample Output:
Shortest path matrix:
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0

Outcome of the Exercise:

The program successfully solves the All-Pairs Shortest Paths problem using Floyd's algorithm. It computes and
prints the shortest path matrix for a given weighted directed graph.

Interview Questions:
1. Explain the All-Pairs Shortest Paths problem and its applications.
 Answer: The All-Pairs Shortest Paths problem involves finding the shortest paths between every pair
of vertices in a weighted directed graph. Applications include network routing, transportation
planning, and optimization problems.

School of Computer Science and Engineering Page 37

 Algorithms Lab Course code: B22EF0404
2. Why is Floyd's algorithm considered a dynamic programming approach?
 Answer: Floyd's algorithm optimally solves subproblems and builds up the solution using the results
of smaller subproblems. It iteratively updates the shortest path distances between pairs of vertices,
demonstrating the principles of dynamic programming.
3. What is the significance of the INF constant in the program?
 Answer: The INF constant represents infinity and is used to initialize distances in the matrix. It
signifies that there is no direct edge between two vertices.
4. How does the program handle the case where there is no direct edge between two vertices?
 Answer: If there is no direct edge between two vertices, the program represents the distance as INF
in the shortest path matrix.
5. Explain the role of the floydWarshall function in the program.
 Answer: The floydWarshall function applies Floyd's algorithm to solve the All-Pairs Shortest Paths
problem. It iteratively updates the shortest path distances in the matrix, considering each vertex as an
intermediate vertex.
6. What modifications would be needed to extend the program for a larger graph?
 Answer: The program is scalable for larger graphs. To handle a graph with more vertices, increase the
value of the constant V and provide the corresponding adjacency matrix.
7. What is the time complexity of Floyd's algorithm, and under what scenarios is it efficient?
 Answer: The time complexity is O(V^3), where V is the number of vertices. It is efficient for dense
graphs and graphs with a relatively small number of vertices.

School of Computer Science and Engineering Page 38

 Algorithms Lab Course code: B22EF0404

PART – B
ALGORITHMS LAB PROJECT
REPORT FORMAT

School of Computer Science and Engineering Page 39

 Algorithms Lab Course code: B22EF0404
7. Mini-Project Specification and Evaluation Rubrics

Part-B
1. Mini Projects on Sorting Algorithm Efficiency Comparison
Overview of the Solution:
The goal of this mini-project is to compare the efficiency of different sorting algorithms. Students are expected to
implement and analyze the performance of algorithms like Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and
Quick Sort. The project involves generating random datasets of varying sizes, applying each sorting algorithm to these
datasets, and measuring the time complexity. Students will need to present their findings, highlighting the strengths and
weaknesses of each algorithm.
Mini-project Evaluation Rubrics:
1. Implementation (40 points):
 Properly implemented and functional sorting algorithms.
 Code readability and adherence to coding standards.
 Handling of edge cases and error scenarios.
2. Efficiency Analysis (30 points):
 Accurate measurement of time complexity for each sorting algorithm.
 Clear presentation of experimental results through tables or graphs.
 Insightful comparison of the algorithms' performance.
3. Documentation (20 points):
 Well-documented code with comments explaining key sections.
 A detailed report outlining the project objectives, methodology, and results.
 Proper citation of sources and references, if any.
4. Presentation (10 points):
 Clear and engaging oral presentation.
 Effective use of visual aids to convey information.
 Ability to answer questions and defend the chosen approach.

2. Mini Projects on Dynamic Programming

Overview of the Solution:
This mini-project focuses on solving problems using Dynamic Programming (DP) techniques. Students will choose
problems that exhibit overlapping subproblems and optimal substructure. Examples include the 0/1 Knapsack problem,
Longest Common Subsequence, and Matrix Chain Multiplication. The project involves implementing DP solutions,
analyzing time and space complexities, and presenting the optimized solutions.
Mini-project Evaluation Rubrics:
1. Problem Selection (20 points):
 Careful selection of problems showcasing overlapping subproblems and optimal substructure.
 Problems aligning with the scope and complexity of the mini-project.
2. Dynamic Programming Solutions (40 points):
 Correct and efficient implementation of DP solutions.
 Proper utilization of memoization or tabulation techniques.

School of Computer Science and Engineering Page 40

 Algorithms Lab Course code: B22EF0404
 Handling edge cases and input variations.
3. Analysis and Optimization (25 points):
 In-depth analysis of time and space complexities.
 Comparison with alternative approaches and justifications for chosen solutions.
 Demonstrated understanding of DP principles.
4. Documentation (10 points):
 Well-documented code with clear explanations of DP strategies.
 A comprehensive report detailing problem statements, solutions, and findings.
 Proper citation of sources and references, if any.
5. Presentation (5 points):
 Concise and effective oral presentation.
 Clarity in explaining DP concepts and solutions.
 Ability to address questions and provide insights.

3. Mini Projects on Pathfinding

Overview of the Solution:
In this mini-project, students will explore various pathfinding algorithms applied to graphs or grids. Problems may
involve finding the shortest path between two points, maze solving, or routing in a network. Common algorithms to be
considered are Dijkstra's Algorithm, A* Algorithm, and Depth-First Search. Students will implement these algorithms,
analyze their performance, and present their findings.
Mini-project Evaluation Rubrics:
1. Problem Definition (15 points):
 Clearly defined pathfinding problems with appropriate complexity.
 Problems that require the application of multiple algorithms for comparison.
2. Algorithm Implementation (40 points):
 Correct and functional implementation of selected pathfinding algorithms.
 Handling of different grid/graph representations and scenarios.
3. Performance Analysis (25 points):
 Accurate measurement of algorithmic performance in terms of time and space complexity.
 Comparative analysis of different algorithms applied to the chosen problems.
 Identification of strengths and weaknesses of each algorithm.
4. Documentation (15 points):
 Well-documented code with comments explaining key sections.
 A comprehensive report outlining problem statements, algorithm implementations, and analysis.
 Proper citation of sources and references, if any.
5. Presentation (5 points):
 Clear and engaging oral presentation.
 Effective use of visual aids to illustrate pathfinding algorithms.
 Ability to answer questions and discuss insights.

School of Computer Science and Engineering Page 41

 Algorithms Lab Course code: B22EF0404
4. Mini Projects on Graph Traversal Techniques
Overview of the Solution:
This mini-project focuses on exploring and implementing various graph traversal techniques. Students will choose
problems that require Breadth-First Search (BFS), Depth-First Search (DFS), or both. Examples include connectivity
analysis, cycle detection, and node reachability. The project involves implementing traversal algorithms, analyzing their
applications, and presenting findings.
Mini-project Evaluation Rubrics:
1. Problem Selection (15 points):
 Well-chosen problems that necessitate the application of BFS and/or DFS.
 Problems aligning with the scope and complexity of the mini-project.
2. Traversal Algorithm Implementation (40 points):
 Correct and efficient implementation of BFS and/or DFS.
 Proper handling of graph representations (adjacency matrix, adjacency list, etc.).
 Handling of edge cases and input variations.
3. Applications and Analysis (25 points):
 Identification and demonstration of graph traversal applications in the chosen problems.
 Comparative analysis of BFS and DFS in terms of advantages and disadvantages.
 Insightful discussion on how traversal techniques solve specific problems.
4. Documentation (15 points):
 Well-documented code with comments explaining traversal algorithms.
 A comprehensive report detailing problem statements, traversal implementations, and analysis.
 Proper citation of sources and references, if any.
5. Presentation (5 points):
 Clear and engaging oral presentation.
 Effective use of visual aids to illustrate traversal algorithms.
 Ability to answer questions and discuss insights.

Note:
The students are expected to implement all the 5 Mini-projects. But, present and submit the project report of
any one of the five projects, based on the approval of the Guide (Faculty Member Assigned to a student).

School of Computer Science and Engineering Page 42

 Algorithms Lab Course code: B22EF0404
8. Project Report Format:

School of Computing Science and Engineering

Academic Year:
Course Code: Algorithms Lab Project Report
Semester & Batch:

Project Details:

Project Title:

Place of Project: REVA UNIVERSITY, BENGALURU

Student Details:

Name: Sign:

Mobile No:

Email-ID:

SRN:

Guide and Lab Faculty Members Details

Guide Name:
(The Faculty Sign:
Member Date:
Assigned)
Grade by Guide:
Name of Lab Co- Sign:
Faculty 1 Date:
Name of Lab Co- Sign:
Faculty 2 Date:
Grade by Lab
Faculty Members
(combined)

SEE Examiners
Name of Sign:
Examiner 1: Date:
Name of Sign:
Examiner 2: Date:

School of Computer Science and Engineering Page 43

 Algorithms Lab Subcode: B22EF0305

Contents
1. Abstract Pg no

2. Introduction Pg no

3. Problem Statement. Pg no

4. Project overview. Pg no

4.1.Objectives Pg no

4.2.Goals Pg no

5. Implementation. Pg no

4.1.Problem analysis and description. Pg no

4.2.Modules identified. Pg no

4.3.Code with comments. Pg no

6. Output and results Pg no

7. Conclusions Pg no

8. References Pg no

School of Computer Science and Engineering Page 44

 Algorithms Lab Subcode: B22EF0305
1. Abstract:
An abstract is an outline/brief summary of your paper and your whole project. It should have an
intro, body and conclusion. It is a well-developed paragraph, should be exact in wording, and must
be understandable to a wide audience. Abstracts highlight major points of your project and explain
why your work is important; what your purpose was, how you went about your project, what you
learned, and what you concluded.
Keywords: -
(Font size: 12
Fount name: Time new roman in Italic style
Line spacing: 1.15
Abstract should be between 150 to 250 words)
2. Introduction:
The introduction section of a project serves as the opening statement that sets the stage for the entire
project. It provides readers with an overview of what to expect, why the project is important, and
what motivated its initiation. In other words, the introduction sets the tone for the entire project,
providing a roadmap for readers and justifying the project's existence. It should be well-structured,
engaging, and informative, motivating readers to continue exploring the project report.
Introduction and Remaining of the document will follow the following format.
Font size: 12
Fount name: Time new roman
Line spacing: 1.15
Introduction should be between approximately ½ to 1 page.
3. Problem statement:
Write your problem statement here.
A problem statement is usually one or two sentences to explain the problem your project will
address. In general, a problem statement will outline the negative points of the current situation and
explain why these matters. It also serves as a great communication tool, helping to get buy-in and
support from others. One of the most important goals of any problem statement is to define the
problem being addressed in a way that's clear and precise.
4. Project overview:
Provide the project overview according to the components mentioned here.
A project overview is a detailed description of a project’s goals and objectives, the steps to achieve
these goals, and the expected outcomes.
4.1.Objectives: An objective describes the desired results of a project, which often
includes a tangible item. An objective is specific and measurable, and must meet time,
budget, and quality constraints. A project may have one objective, many parallel
objectives, or several objectives that must be achieved sequentially. To produce the
most benefit, objectives must be defined early in the project life cycle, in phase one,
the planning phase.

School of Computer Science and Engineering Page 45

 Algorithms Lab Subcode: B22EF0305
4.2.Goals: The goal of a project overview is to lay out the details of a project in a concise,
easy-to-understand manner that can be presented to clients, team members, and key
stakeholders.
5. Project Implementation
Provide the analysis of project, the functions identified to be implemented and finally list the
complete commented source code.
Your project group is required to submit a document outlining the project's implementation details.
Ensure that your code follows proper coding conventions. Include appropriate comments on critical
sections of the code. Overall, your code should have a smooth flow, logical transitions, and should
be easy to follow.
5.1. Problem analysis and description.
The problem analysis and description section is a critical component that outlines the
specific issue or challenge that the project aims to address. It serves as the foundation upon
which the rest of the project is built and helps stakeholders, team members, and anyone else
involved or interested in the project to understand the problem and its context.
5.2. Modules identified:
A "module" is a high-level description of a functional area, consisting of a group
of processes describing the functionality of the module and a group
of packages implementing the functionality.
5.3. Code with comments.
A "code with comments" refers to a piece of computer programming code that includes
explanatory comments written alongside the actual code. These comments are meant to
provide additional information, explanations, and context about what the code does, how it
works, and why certain decisions were made during the coding process. The primary
purpose of code comments is to make the code more understandable and maintainable for
both the original developer and others who may need to read or modify it in the future.
6. Output and results
Attach the output generated by your project and results. (Screenshot of output and
description for results or impact of project)
Outputs" and "results" are two distinct but interconnected aspects of a project, and they are often
used to measure the project's success and impact. In short, outputs are the tangible products and
deliverables produced during a project's execution, while results are the broader and often longer-
term changes or benefits that occur as a direct or indirect consequence of these outputs. Both output
and results are essential for evaluating a project's success and effectiveness, with results being the
ultimate measure of the project's impact on its intended beneficiaries or stakeholders.
7. Conclusions:
Write the conclusion here.

School of Computer Science and Engineering Page 46

 Algorithms Lab Subcode: B22EF0305
A conclusion is the last part of something, it means "finally, to sum up," and is used to introduce
some final comments at the end of writing.
8. References:
References in a document are citations or sources of information that support and substantiate the
content presented in the document. Properly formatted references enhance the credibility and
integrity of your writing while giving readers the means to verify and explore the sources you've
used.
It's essential to follow the specific citation style guidelines for formatting your references correctly.
Additionally, make sure your in-text citations (citations within the main body of your document)
correspond to the entries in your references section.
References must be quoted as per the following format:
Author(s) Initial(s). Surname(s), “Title of Report,” Abbrev. Name of Co., City of Co., Abbrev.
State, Country (abbrev. US State or Country if the City is not 'well known'), Report number/Type
(if available), Abbrev. Month. (Day if available), Year of Publication.
Example for reference is given below. Kindly follow the same format for writing reference
G. Eason, B. Noble, and I. N. Sneddon, “On certain integrals of Lipschitz-Hankel type involving
products of Bessel functions,” Phil. Trans. Roy. Soc. London, vol. A247, pp. 529–551, April
1955.
J. Clerk Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon,
1892, pp.68–73.
I. S. Jacobs and C. P. Bean, “Fine particles, thin films and exchange anisotropy,” in Magnetism,
vol. III, G. T. Rado and H. Suhl, Eds. New York: Academic, 1963, pp. 271–350.
K. Elissa, “Title of paper if known,” unpublished.
R. Nicole, “Title of paper with only first word capitalized,” J. Name Stand. Abbrev., in press.
Y. Yorozu, M. Hirano, K. Oka, and Y. Tagawa, “Electron spectroscopy studies on magneto-optical
media and plastic substrate interface,” IEEE Transl. J. Magn. Japan, vol. 2, pp. 740–741, August
1987 [Digests 9th Annual Conf. Magnetics Japan, p. 301, 1982].
M. Young, The Technical Writer’s Handbook. Mill Valley, CA: University Science, 1989.

School of Computer Science and Engineering Page 47

 Algorithms Lab Subcode: B22EF0305
9. Learning Resources:

Reference Books:
1. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”, 3rd
edition, PHI Learning Private Limited, 2017
2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, “Data Structures and Algorithms”, Pearson.
3. Donald E. Knuth, “The Art of Computer Programming”, Volumes 1and 3 Pearson.

Web Based Resources and E-books:

1. NPTEL Course on “Design and Analysis of Algorithms”, Prof. Abhiram G Ranade, Prof. Ajit A Diwan and Prof.
Sundar Vishwanathan, https://nptel.ac.in/courses/106101060
2. “Introduction to Design and Analysis of Algorithms” by Anany Levitin, 2nd edition
http://160592857366.free.fr/joe/ebooks/ShareData/Anany%20Levitin%20English
3. https://www.researchgate.net/publication/276847633_A_Review_Report_on_Divide_and_Conquer_Sortin g_
Algorithm
4. https://www.ijsrp.org/research-paper-0813/ijsrp-p2014.pdf
5. https://iopscience.iop.org/article/10.1088/1742-6596/1566/1/012038/pdf

School of Computer Science and Engineering Page 48