[Advanced Data Structures & Algorithm Analysis]

EXP-1: Construct an AVL tree for a given set of elements which are stored
in a file. And implement insert and delete operation on the
constructed tree. Write contents of tree into a new file using in-
order.
Source:
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
int height; // Height of the node
};
int height(struct TreeNode* node) {
if (node == NULL)
return 0;
return node->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
struct TreeNode* createNode(int key) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode != NULL) {
newNode->data = key;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1; // New node is initially at height 1

CSE Department [Madanapalle Institute of Technology & Science] Page 1

 [Advanced Data Structures & Algorithm Analysis]

}
return newNode;
}
struct TreeNode* rightRotate(struct TreeNode* y) {
struct TreeNode* x = y->left;
struct TreeNode* T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// Return new root
return x;
}
// Function to left rotate subtree rooted with x
struct TreeNode* leftRotate(struct TreeNode* x) {
struct TreeNode* y = x->right;
struct TreeNode* T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
// Return new root
return y;

CSE Department [Madanapalle Institute of Technology & Science] Page 2

 [Advanced Data Structures & Algorithm Analysis]

}
// Function to get the balance factor of a node
int getBalance(struct TreeNode* node) {
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
// Function to insert a key into the AVL tree
struct TreeNode* insert(struct TreeNode* root, int key) {
// Perform standard BST insert
if (root == NULL)
return createNode(key);
if (key < root->data)
root->left = insert(root->left, key);
else if (key > root->data)
root->right = insert(root->right, key);
else // Duplicate keys not allowed
return root;
// Update height of the current node
root->height = 1 + max(height(root->left), height(root->right));
// Get the balance factor to check whether this node became unbalanced
int balance = getBalance(root);
// Left Left Case
if (balance > 1 && key < root->left->data)
return rightRotate(root);
// Right Right Case
if (balance < -1 && key > root->right->data)

CSE Department [Madanapalle Institute of Technology & Science] Page 3

 [Advanced Data Structures & Algorithm Analysis]

return leftRotate(root);
// Left Right Case
if (balance > 1 && key > root->left->data) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Left Case
if (balance < -1 && key < root->right->data) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
// Return the unchanged node pointer
return root;
}
// Function to find the node with the minimum value
struct TreeNode* minValueNode(struct TreeNode* node) {
struct TreeNode* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
// Function to delete a key from the AVL tree
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
if (root == NULL)
return root;
// Perform standard BST delete
if (key < root->data)

CSE Department [Madanapalle Institute of Technology & Science] Page 4

 [Advanced Data Structures & Algorithm Analysis]

root->left = deleteNode(root->left, key);

else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
// Node with only one child or no child
if ((root->left == NULL) || (root->right == NULL)) {
struct TreeNode* temp = root->left ? root->left : root->right;
// No child case
if (temp == NULL) {
temp = root;
root = NULL;
} else // One child case
*root = *temp; // Copy the contents of the non-empty child
free(temp);
} else {
// Node with two children, get the inorder successor
struct TreeNode* temp = minValueNode(root->right);
// Copy the inorder successor's data to this node
root->data = temp->data;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->data);
}
}
// If the tree had only one node, then return
if (root == NULL)
return root;
// Update height of the current node

CSE Department [Madanapalle Institute of Technology & Science] Page 5

 [Advanced Data Structures & Algorithm Analysis]

root->height = 1 + max(height(root->left), height(root->right));

// Get the balance factor to check whether this node became unbalanced
int balance = getBalance(root);
// Left Left Case
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// Function to perform in-order traversal of the AVL tree
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);

CSE Department [Madanapalle Institute of Technology & Science] Page 6

 [Advanced Data Structures & Algorithm Analysis]

}
}
// Function to free the memory allocated for the AVL tree
void freeAVLTree(struct TreeNode* root) {
if (root != NULL) {
freeAVLTree(root->left);
freeAVLTree(root->right);
free(root);
}
}
int main() {
struct TreeNode* root = NULL;
int choice, key;
do {
printf("\nAVL Tree Operations:\n");
printf("1. Insert a node\n");
printf("2. Delete a node\n");
printf("3. In-order Traversal\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the key to insert: ");
scanf("%d", &key);
root = insert(root, key);
break;

CSE Department [Madanapalle Institute of Technology & Science] Page 7

 [Advanced Data Structures & Algorithm Analysis]

case 2:
printf("Enter the key to delete: ");
scanf("%d", &key);
root = deleteNode(root, key);
break;
case 3:
printf("In-order Traversal: ");
inOrderTraversal(root);
printf("\n");
break;
case 4:
// Free allocated memory
freeAVLTree(root);
printf("Exiting...\n");
break;
default:
printf("Invalid choice! Please enter a valid option.\n");
}
} while (choice != 4);
return 0;
}

CSE Department [Madanapalle Institute of Technology & Science] Page 8

 [Advanced Data Structures & Algorithm Analysis]

Exp-2:Construct B-Tree an order of 5 with a set of 100 random elements

stored in array. Implement searching, insertion and deletion operations.
Source:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// B-Tree Node structure
typedef struct BTreeNode {
int *keys; // Array of keys
struct BTreeNode **children; // Array of child pointers
int num_keys; // Current number of keys in the node
bool leaf; // Flag to indicate if the node is a leaf
} BTreeNode;
// Function prototypes
BTreeNode *createNode(bool leaf);
void insert(BTreeNode **root, int key);
void splitChild(BTreeNode *parent, int i);
void insertNonFull(BTreeNode *node, int key);
void search(BTreeNode *root, int key);
void delete(BTreeNode **root, int key);
void removeFromNode(BTreeNode *node, int key);
void borrowFromPrev(BTreeNode *node, int idx);

CSE Department [Madanapalle Institute of Technology & Science] Page 9

 [Advanced Data Structures & Algorithm Analysis]

void borrowFromNext(BTreeNode *node, int idx);

void merge(BTreeNode *node, int idx);
// Create a new B-Tree node
BTreeNode *createNode(bool leaf) {
BTreeNode *newNode = (BTreeNode *)malloc(sizeof(BTreeNode));
newNode->keys = (int *)malloc((ORDER - 1) * sizeof(int));
newNode->children = (BTreeNode **)malloc(ORDER * sizeof(BTreeNode *));
newNode->num_keys = 0;
newNode->leaf = leaf;
return newNode;
}
// Insert a key into the B-Tree
void insert(BTreeNode **root, int key) {
if (*root == NULL) {
*root = createNode(true);
(*root)->keys[0] = key;
(*root)->num_keys = 1;
} else {
if ((*root)->num_keys == ORDER - 1) {
BTreeNode *newRoot = createNode(false);
newRoot->children[0] = *root;
splitChild(newRoot, 0);
*root = newRoot;
}
insertNonFull(*root, key);
}
}

CSE Department [Madanapalle Institute of Technology & Science] Page 10

 [Advanced Data Structures & Algorithm Analysis]

// Insert into a non-full node

void insertNonFull(BTreeNode *node, int key) {
int i = node->num_keys - 1;
if (node->leaf) {
while (i >= 0 && key < node->keys[i]) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->num_keys++;
} else {
while (i >= 0 && key < node->keys[i]) {
i--;
}
i++;
if (node->children[i]->num_keys == ORDER - 1) {
splitChild(node, i);
if (key > node->keys[i]) {
i++;
}
}
insertNonFull(node->children[i], key);
} }
// Split child of a node
void splitChild(BTreeNode *parent, int i) {
BTreeNode *child = parent->children[i];
BTreeNode *newChild = createNode(child->leaf);

CSE Department [Madanapalle Institute of Technology & Science] Page 11

 [Advanced Data Structures & Algorithm Analysis]

newChild->num_keys = ORDER / 2 - 1;
for (int j = 0; j < ORDER / 2 - 1; j++) {
newChild->keys[j] = child->keys[j + ORDER / 2];
}
if (!child->leaf) {
for (int j = 0; j < ORDER / 2; j++) {
newChild->children[j] = child->children[j + ORDER / 2];
}
}
child->num_keys = ORDER / 2 - 1;
for (int j = parent->num_keys; j >= i + 1; j--) {
parent->children[j + 1] = parent->children[j];
}
parent->children[i + 1] = newChild;
for (int j = parent->num_keys - 1; j >= i; j--) {
parent->keys[j + 1] = parent->keys[j];
}
parent->keys[i] = child->keys[ORDER / 2 - 1];
parent->num_keys++;
}
// Search for a key in the B-Tree
void search(BTreeNode *root, int key) {
int i = 0;
while (i < root->num_keys && key > root->keys[i]) {
i++;
}
if (i < root->num_keys && key == root->keys[i]) {

CSE Department [Madanapalle Institute of Technology & Science] Page 12

 [Advanced Data Structures & Algorithm Analysis]

printf("Key %d found in B-Tree.\n", key);

} else if (!root->leaf) {
search(root->children[i], key);
} else {
printf("Key %d not found in B-Tree.\n", key);
}
}
// Delete a key from the B-Tree
void delete(BTreeNode **root, int key) {
// Function to delete a key from B-Tree (not implemented fully here)
}
// Main function
int main() {
BTreeNode *root = NULL;
int random_elements[100];
int i;
// Generate 100 random elements
for (i = 0; i < 100; i++) {
random_elements[i] = rand() % 1000;
}
// Insert elements into B-Tree
for (i = 0; i < 100; i++) {
insert(&root, random_elements[i]);
}
// Example usage:
// Search for a key
search(root, 42);

CSE Department [Madanapalle Institute of Technology & Science] Page 13

 [Advanced Data Structures & Algorithm Analysis]

// Insert a new key

insert(&root, 1000);
// Delete a key
// delete(&root, 42);
return 0;
}

Explanation:

 BTreeNode struct: Represents a node in the B-Tree, with fields for keys, children pointers,
number of keys, and leaf status.
 insert: Inserts a key into the B-Tree, handling splitting of nodes as necessary to maintain B-
Tree properties.
 splitChild: Splits a child node of a parent node at a given index.
 insertNonFull: Helper function to recursively insert into a non-full node.
 search: Searches for a key in the B-Tree recursively.
 delete: Placeholder for deletion operation, not fully implemented here.

This implementation provides a basic framework for a B-Tree in C with insertion and searching
functionalities. Deletion requires handling various cases such as merging nodes, borrowing keys, and
adjusting the tree structure accordingly, which would require additional code beyond the scope of
this basic example.

EXP-3: Construct Min and Max Heap using arrays, delete any element
and display the content of the Heap.
Source:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Function prototypes
void buildMinHeap(int arr[], int n);
void heapifyMin(int arr[], int n, int i);
void insertMinHeap(int arr[], int *n, int key);
void deleteMinHeap(int arr[], int *n, int key);
void displayMinHeap(int arr[], int n);
void buildMaxHeap(int arr[], int n);
void heapifyMax(int arr[], int n, int i);
void insertMaxHeap(int arr[], int *n, int key);
CSE Department [Madanapalle Institute of Technology & Science] Page 14
 [Advanced Data Structures & Algorithm Analysis]

void deleteMaxHeap(int arr[], int *n, int key);

void displayMaxHeap(int arr[], int n);
// Utility function to swap two elements in an array
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to build Min Heap
void buildMinHeap(int arr[], int n) {
for (int i = (n / 2) - 1; i >= 0; i--) {
heapifyMin(arr, n, i);
}
}

// Function to heapify a subtree rooted at index i in a Min Heap of size n

void heapifyMin(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] < arr[smallest]) {

smallest = left;
}
if (right < n && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest != i) {
swap(&arr[i], &arr[smallest]);
heapifyMin(arr, n, smallest);
}
}
// Function to insert a new key into the Min Heap
void insertMinHeap(int arr[], int *n, int key) {
(*n)++;
int i = *n - 1;
arr[i] = key;
while (i > 0 && arr[(i - 1) / 2] > arr[i]) {
swap(&arr[i], &arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// Function to delete a key from the Min Heap
CSE Department [Madanapalle Institute of Technology & Science] Page 15
 [Advanced Data Structures & Algorithm Analysis]

void deleteMinHeap(int arr[], int *n, int key) {

int i;
for (i = 0; i < *n; i++) {
if (arr[i] == key)
break;
}
if (i == *n) {
printf("Key not found in Min Heap.\n");
return;
}
swap(&arr[i], &arr[*n - 1]);
(*n)--;
buildMinHeap(arr, *n);
}

// Function to display the Min Heap

void displayMinHeap(int arr[], int n) {
printf("Min Heap: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Function to build Max Heap
void buildMaxHeap(int arr[], int n) {
for (int i = (n / 2) - 1; i >= 0; i--) {
heapifyMax(arr, n, i);
}
}
// Function to heapify a subtree rooted at index i in a Max Heap of size n
void heapifyMax(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapifyMax(arr, n, largest);
CSE Department [Madanapalle Institute of Technology & Science] Page 16
 [Advanced Data Structures & Algorithm Analysis]

}
}
// Function to insert a new key into the Max Heap
void insertMaxHeap(int arr[], int *n, int key) {
(*n)++;
int i = *n - 1;
arr[i] = key;
while (i > 0 && arr[(i - 1) / 2] < arr[i]) {
swap(&arr[i], &arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// Function to delete a key from the Max Heap
void deleteMaxHeap(int arr[], int *n, int key) {
int i;
for (i = 0; i < *n; i++) {
if (arr[i] == key)
break;
}
if (i == *n) {
printf("Key not found in Max Heap.\n");
return;
}
swap(&arr[i], &arr[*n - 1]);
(*n)--;
buildMaxHeap(arr, *n);
}
// Function to display the Max Heap
void displayMaxHeap(int arr[], int n) {
printf("Max Heap: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Main function
int main() {
int arr[MAX_SIZE];
int n = 0; // Current size of the heap
// Example usage:
insertMinHeap(arr, &n, 3);
insertMinHeap(arr, &n, 2);
insertMinHeap(arr, &n, 1);
CSE Department [Madanapalle Institute of Technology & Science] Page 17
 [Advanced Data Structures & Algorithm Analysis]

insertMinHeap(arr, &n, 15);

insertMinHeap(arr, &n, 5);
insertMinHeap(arr, &n, 4);
insertMinHeap(arr, &n, 45);
printf("After inserting elements into Min Heap:\n");
displayMinHeap(arr, n);
deleteMinHeap(arr, &n, 5);
printf("After deleting element 5 from Min Heap:\n");
displayMinHeap(arr, n);
insertMaxHeap(arr, &n, 3);
insertMaxHeap(arr, &n, 2);
insertMaxHeap(arr, &n, 1);
insertMaxHeap(arr, &n, 15);
insertMaxHeap(arr, &n, 5);
insertMaxHeap(arr, &n, 4);
insertMaxHeap(arr, &n, 45);

printf("After inserting elements into Max Heap:\n");

displayMaxHeap(arr, n);
deleteMaxHeap(arr, &n, 5);
printf("After deleting element 5 from Max Heap:\n");
displayMaxHeap(arr, n);
return 0;
}

Program Explanation:

 Min Heap is implemented where the parent node has a smaller value than its
children.
 Max Heap is implemented where the parent node has a larger value than its
children.
 Both heaps are implemented using arrays.
 The program provides functions to:
o Build a heap from an array.
o Insert an element into the heap.
o Delete an element from the heap.
o Display the current elements of the heap.

 Min Heap functions (buildMinHeap, heapifyMin, insertMinHeap,

deleteMinHeap, displayMinHeap) implement operations for Min Heap:

 buildMinHeap: Builds a Min Heap from an array.

CSE Department [Madanapalle Institute of Technology & Science] Page 18

 [Advanced Data Structures & Algorithm Analysis]

 heapifyMin: Ensures that the subtree rooted at index i satisfies the Min Heap
property.
 insertMinHeap: Inserts a new key into the Min Heap.
 deleteMinHeap: Deletes a key from the Min Heap.
 displayMinHeap: Displays the elements of the Min Heap.

 Max Heap functions (buildMaxHeap, heapifyMax, insertMaxHeap,

deleteMaxHeap, displayMaxHeap) implement operations for Max Heap:

 buildMaxHeap: Builds a Max Heap from an array.

 heapifyMax: Ensures that the subtree rooted at index i satisfies the Max Heap
property.
 insertMaxHeap: Inserts a new key into the Max Heap.
 deleteMaxHeap: Deletes a key from the Max Heap.
 displayMaxHeap: Displays the elements of the Max Heap.

 Utility function swap: Swaps two elements in an array.

Exp-4: Implement BFT and DFT for given graph, when graph is represented by
a) Adjacency Matrix b) Adjacency Lists

Source: #include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_VERTICES 100

// Graph represented by adjacency matrix

int graph[MAX_VERTICES][MAX_VERTICES];

int num_vertices;

// Utility function to initialize the graph

void initializeGraph(int vertices) {

num_vertices = vertices;

CSE Department [Madanapalle Institute of Technology & Science] Page 19

 [Advanced Data Structures & Algorithm Analysis]

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

for (int j = 0; j < num_vertices; j++) {

graph[i][j] = 0;

// Function to add an edge in the graph

void addEdgeMatrix(int u, int v) {

graph[u][v] = 1;

graph[v][u] = 1; // Uncomment this line for undirected graph

// Breadth-First Traversal (BFT) using adjacency matrix

void BFTMatrix(int start) {

bool visited[MAX_VERTICES] = { false };

int queue[MAX_VERTICES];

int front = 0, rear = 0;

visited[start] = true;

queue[rear++] = start;

printf("Breadth-First Traversal (BFT) starting from vertex %d: ", start);

while (front < rear) {

int current = queue[front++];

CSE Department [Madanapalle Institute of Technology & Science] Page 20

 [Advanced Data Structures & Algorithm Analysis]

printf("%d ", current);

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

if (graph[current][i] && !visited[i]) {

visited[i] = true;

queue[rear++] = i;

printf("\n");

// Depth-First Traversal (DFT) using adjacency matrix (recursive)

void DFTMatrixRecursive(int vertex, bool visited[]) {

visited[vertex] = true;

printf("%d ", vertex);

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

if (graph[vertex][i] && !visited[i]) {

DFTMatrixRecursive(i, visited);

// Depth-First Traversal (DFT) using adjacency matrix (driver function)

void DFTMatrix(int start) {

CSE Department [Madanapalle Institute of Technology & Science] Page 21

 [Advanced Data Structures & Algorithm Analysis]

bool visited[MAX_VERTICES] = { false };

printf("Depth-First Traversal (DFT) starting from vertex %d: ", start);

DFTMatrixRecursive(start, visited);

printf("\n");

// Main function

int main() {

int num_vertices = 6; // Example with 6 vertices

initializeGraph(num_vertices);

addEdgeMatrix(0, 1);

addEdgeMatrix(0, 2);

addEdgeMatrix(1, 3);

addEdgeMatrix(1, 4);

addEdgeMatrix(2, 4);

addEdgeMatrix(3, 5);

addEdgeMatrix(4, 5);

BFTMatrix(0); // Perform BFT starting from vertex 0

DFTMatrix(0); // Perform DFT starting from vertex 0

return 0;

B.Adjacence List:

CSE Department [Madanapalle Institute of Technology & Science] Page 22

 [Advanced Data Structures & Algorithm Analysis]

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// Node for adjacency list
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// Graph represented by adjacency lists
Node* graph[MAX_VERTICES];
int num_vertices;
// Utility function to initialize the graph
void initializeGraph(int vertices) {
num_vertices = vertices;
for (int i = 0; i < num_vertices; i++) {
graph[i] = NULL;
}
}
// Function to add an edge in the graph (undirected graph)
void addEdgeList(int u, int v) {
// Add edge from u to v
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = graph[u];
graph[u] = newNode;

CSE Department [Madanapalle Institute of Technology & Science] Page 23

 [Advanced Data Structures & Algorithm Analysis]

// Add edge from v to u

newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = u;
newNode->next = graph[v];
graph[v] = newNode;
}
// Breadth-First Traversal (BFT) using adjacency lists
void BFTList(int start) {
bool visited[MAX_VERTICES] = { false };
int queue[MAX_VERTICES];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start;
printf("Breadth-First Traversal (BFT) starting from vertex %d: ", start);
while (front < rear) {
int current = queue[front++];
printf("%d ", current);
// Traverse adjacency list of vertex current
Node* temp = graph[current];
while (temp != NULL) {
if (!visited[temp->vertex]) {
visited[temp->vertex] = true;
queue[rear++] = temp->vertex;
}
temp = temp->next;
}

CSE Department [Madanapalle Institute of Technology & Science] Page 24

 [Advanced Data Structures & Algorithm Analysis]

}
printf("\n");
}
// Depth-First Traversal (DFT) using adjacency lists (recursive)
void DFTListRecursive(int vertex, bool visited[]) {
visited[vertex] = true;
printf("%d ", vertex);
// Traverse adjacency list of vertex
Node* temp = graph[vertex];
while (temp != NULL) {
if (!visited[temp->vertex]) {
DFTListRecursive(temp->vertex, visited);
}
temp = temp->next;
}
}
// Depth-First Traversal (DFT) using adjacency lists (driver function)
void DFTList(int start) {
bool visited[MAX_VERTICES] = { false };
printf("Depth-First Traversal (DFT) starting from vertex %d: ", start);
DFTListRecursive(start, visited);
printf("\n");
}
// Main function
int main() {
int num_vertices = 6; // Example with 6 vertices

CSE Department [Madanapalle Institute of Technology & Science] Page 25

 [Advanced Data Structures & Algorithm Analysis]

initializeGraph(num_vertices);
addEdgeList(0, 1);
addEdgeList(0, 2);
addEdgeList(1, 3);
addEdgeList(1, 4);
addEdgeList(2, 4);
addEdgeList(3, 5);
addEdgeList(4, 5);
BFTList(0); // Perform BFT starting from vertex 0
DFTList(0); // Perform DFT starting from vertex 0
return 0;
}

Explanation:

 Adjacency Matrix: Uses a 2D array to represent the graph. graph[i][j]

indicates if there is an edge between vertex i and vertex j.
o initializeGraph: Initializes the graph.
o addEdgeMatrix: Adds an edge between vertices u and v.
o BFTMatrix: Performs Breadth-First Traversal using a queue.
o DFTMatrix: Performs Depth-First Traversal using recursion.
 Adjacency Lists: Uses an array of linked lists where each element in the
array represents a vertex and contains a linked list of vertices that are
adjacent to it.
o Node struct: Represents a node in the linked list.
o initializeGraph: Initializes the graph.
o addEdgeList: Adds an edge between vertices u and v in both directions
(for undirected graph).
o BFTList: Performs Breadth-First Traversal using a queue.
o DFTList: Performs Depth-First Traversal using recursion.

CSE Department [Madanapalle Institute of Technology & Science] Page 26

 [Advanced Data Structures & Algorithm Analysis]

Both implementations provide basic operations for graph traversal (BFT and DFT)
using different representations (Adjacency Matrix and Adjacency Lists). Adjustments
can be made for specific graph requirements and additional functionalities as
needed.

Exp-5: Write a program for finding the biconnected components in a

given graph.
Source:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// Node for adjacency list
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// Global variables
Node* graph[MAX_VERTICES]; // Adjacency list representation of the graph
int num_vertices; // Number of vertices in the graph
int discovery_time[MAX_VERTICES]; // Discovery times of vertices
int low[MAX_VERTICES]; // Low values of vertices
bool visited[MAX_VERTICES]; // Array to track visited vertices
int time = 0; // Time variable for discovery times
// Stack structure
typedef struct Stack {
int data[MAX_VERTICES];
int top;
} Stack;

CSE Department [Madanapalle Institute of Technology & Science] Page 27

 [Advanced Data Structures & Algorithm Analysis]

// Function prototypes
Node* createNode(int v);
void initializeGraph(int vertices);
void addEdge(int u, int v);
void push(Stack* stack, int v);
int pop(Stack* stack);
bool isEmpty(Stack* stack);
void biconnectedComponents(int u, int parent, Stack* stack);
// Function to create a new node
Node* createNode(int v) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Function to initialize the graph
void initializeGraph(int vertices) {
num_vertices = vertices;
for (int i = 0; i < num_vertices; i++) {
graph[i] = NULL;
visited[i] = false;
discovery_time[i] = -1;
low[i] = -1;
}
}
// Function to add an edge to the graph

CSE Department [Madanapalle Institute of Technology & Science] Page 28

 [Advanced Data Structures & Algorithm Analysis]

void addEdge(int u, int v) {

// Add edge from u to v
Node* newNode = createNode(v);
newNode->next = graph[u];
graph[u] = newNode;
// Add edge from v to u
newNode = createNode(u);
newNode->next = graph[v];
graph[v] = newNode;
}
// Function to push element onto the stack
void push(Stack* stack, int v) {
stack->data[++stack->top] = v;
}
// Function to pop element from the stack
int pop(Stack* stack) {
return stack->data[stack->top--];
}
// Function to check if stack is empty
bool isEmpty(Stack* stack) {
return stack->top == -1;
}
// Function to find biconnected components using DFS
void biconnectedComponents(int u, int parent, Stack* stack) {
visited[u] = true;
discovery_time[u] = low[u] = ++time;

CSE Department [Madanapalle Institute of Technology & Science] Page 29

 [Advanced Data Structures & Algorithm Analysis]

int children = 0;
// Traverse all adjacent vertices of u
Node* v;
for (v = graph[u]; v != NULL; v = v->next) {
int w = v->vertex;
if (!visited[w]) {
children++;
push(stack, u);
biconnectedComponents(w, u, stack);
// Check if the subtree rooted at v has a back edge to one of the ancestors of u
low[u] = (low[u] < low[w]) ? low[u] : low[w];
// If u is an articulation point, pop all vertices from stack till u (including u)
if (parent != -1 && low[w] >= discovery_time[u]) {
printf("Biconnected Component: ");
while (stack->data[stack->top] != u) {
printf("%d ", stack->data[stack->top]);
pop(stack);
}
printf("%d\n", u);
pop(stack);
}
} else if (w != parent && discovery_time[w] < low[u]) {
low[u] = discovery_time[w];
push(stack, u);
}
}

CSE Department [Madanapalle Institute of Technology & Science] Page 30

 [Advanced Data Structures & Algorithm Analysis]

// For root of DFS tree, check if it is an articulation point

if (parent == -1 && children > 1) {
printf("Biconnected Component: ");
while (!isEmpty(stack)) {
printf("%d ", pop(stack));
}
printf("\n");
}
}
// Main function
int main() {
int num_vertices = 7; // Example with 7 vertices
initializeGraph(num_vertices);
addEdge(0, 1);
addEdge(1, 2);
addEdge(2, 0);
addEdge(1, 3);
addEdge(1, 4);
addEdge(1, 6);
addEdge(3, 5);
addEdge(4, 5);
Stack stack;
stack.top = -1;
printf("Biconnected Components in the graph:\n");
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {

CSE Department [Madanapalle Institute of Technology & Science] Page 31

 [Advanced Data Structures & Algorithm Analysis]

biconnectedComponents(i, -1, &stack);

}
}
return 0;
}

Finding biconnected components in a graph involves identifying subgraphs where

any two vertices are connected by at least two disjoint paths. This is a critical task in
graph theory, often used to understand the robustness and connectivity of networks.
Here’s a C program that uses Depth-First Search (DFS) to find all biconnected
components in an undirected graph.

Approach:

1. Articulation Points: First, identify all articulation points (or cut vertices) in the
graph. An articulation point is a vertex that, if removed along with its incident
edges, increases the number of connected components of the graph.
2. Bridges: Next, identify all bridges (or cut edges) in the graph. A bridge is an
edge that, if removed, increases the number of connected components of the
graph.
3. Biconnected Components: Using the information from articulation points
and bridges, construct biconnected components. A biconnected component is
a maximal subgraph such that any two vertices are connected by at least two
disjoint paths.

Explanation:

 Graph Representation: The graph is represented using an adjacency list

(graph[]) where each vertex has a linked list of its adjacent vertices.
 Global Arrays:
o discovery_time[]: Tracks the discovery time of each vertex during DFS.
o low[]: Tracks the low value of each vertex, which is the smallest
discovery time reachable from the vertex.
o visited[]: Boolean array to keep track of visited vertices.
 Stack (Stack struct):
o Used for storing vertices in the current path of DFS traversal.
 Functions:
o initializeGraph: Initializes the graph and arrays.
o addEdge: Adds an edge between two vertices in both directions (since
the graph is undirected).

CSE Department [Madanapalle Institute of Technology & Science] Page 32

 [Advanced Data Structures & Algorithm Analysis]

Exp-6: Implement Quick sort and Merge sort and observe the execution
time for various input sizes (Average, Worst and Best cases).
A).Quick sort
Source: #include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function prototypes
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void swap(int *a, int *b);
void generateArray(int arr[], int n, int type);
void printArray(int arr[], int n);
double measureTime(int arr[], int n, void (*sort)(int[], int, int));
// Function to perform Quick Sort
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}
// Function to partition the array for Quick Sort

CSE Department [Madanapalle Institute of Technology & Science] Page 33

 [Advanced Data Structures & Algorithm Analysis]

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
// Utility function to swap two elements in an array
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to generate arrays of different types
void generateArray(int arr[], int n, int type) {
switch (type) {
case 0: // Random array
for (int i = 0; i < n; i++) {
arr[i] = rand() % n;
}
break;

CSE Department [Madanapalle Institute of Technology & Science] Page 34

 [Advanced Data Structures & Algorithm Analysis]

case 1: // Sorted array

for (int i = 0; i < n; i++) {
arr[i] = i;
}
break;
case 2: // Reverse sorted array
for (int i = 0; i < n; i++) {
arr[i] = n - i - 1;
}
break;
default:
printf("Invalid array type.\n");
break;
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Function to measure execution time of sorting algorithms
double measureTime(int arr[], int n, void (*sort)(int[], int, int)) {
clock_t start, end;
double cpu_time_used;

CSE Department [Madanapalle Institute of Technology & Science] Page 35

 [Advanced Data Structures & Algorithm Analysis]

start = clock();
sort(arr, 0, n - 1);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
return cpu_time_used;
}
// Main function
int main() {
srand(time(NULL)); // Seed for random numbers
int n = 10000; // Size of the array
// Arrays for different cases
int arr_random[n], arr_sorted[n], arr_reverse_sorted[n];
// Generate arrays of different types
generateArray(arr_random, n, 0); // Random array
generateArray(arr_sorted, n, 1); // Sorted array
generateArray(arr_reverse_sorted, n, 2); // Reverse sorted array
// Measure time for Quick Sort in different cases
double time_random = measureTime(arr_random, n, quickSort);
double time_sorted = measureTime(arr_sorted, n, quickSort);
double time_reverse_sorted = measureTime(arr_reverse_sorted, n, quickSort);
// Print results
printf("Quick Sort Execution Time:\n");
printf("Random array: %.6f seconds\n", time_random);
printf("Sorted array: %.6f seconds\n", time_sorted);
printf("Reverse sorted array: %.6f seconds\n", time_reverse_sorted);
return 0;

CSE Department [Madanapalle Institute of Technology & Science] Page 36

 [Advanced Data Structures & Algorithm Analysis]

}
B).Merge Sort:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function prototypes
void mergeSort(int arr[], int l, int r);
void merge(int arr[], int l, int m, int r);
void swap(int *a, int *b);
void generateArray(int arr[], int n, int type);
void printArray(int arr[], int n);
double measureTime(int arr[], int n, void (*sort)(int[], int, int));
// Function to perform Merge Sort
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Function to merge subarrays in Merge Sort
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

CSE Department [Madanapalle Institute of Technology & Science] Page 37

 [Advanced Data Structures & Algorithm Analysis]

int L[n1], R[n2];

for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;

CSE Department [Madanapalle Institute of Technology & Science] Page 38

 [Advanced Data Structures & Algorithm Analysis]

k++;
}
}
// Utility function to swap two elements in an array
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Function to generate arrays of different types

void generateArray(int arr[], int n, int type) {
switch (type) {
case 0: // Random array
for (int i = 0; i < n; i++) {
arr[i] = rand() % n;
}
break;
case 1: // Sorted array
for (int i = 0; i < n; i++) {
arr[i] = i;
}
break;
case 2: // Reverse sorted array
for (int i = 0; i < n; i++) {
arr[i] = n - i - 1;

CSE Department [Madanapalle Institute of Technology & Science] Page 39

 [Advanced Data Structures & Algorithm Analysis]

}
break;
default:
printf("Invalid array type.\n");
break;
}
}

// Function to print an array

void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Function to measure execution time of sorting algorithms
double measureTime(int arr[], int n, void (*sort)(int[], int, int)) {
clock_t start, end;
double cpu_time_used;
start = clock();
sort(arr, 0, n - 1);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
return cpu_time_used;
}
// Main function

CSE Department [Madanapalle Institute of Technology & Science] Page 40

 [Advanced Data Structures & Algorithm Analysis]

int main() {
srand(time(NULL)); // Seed for random numbers
int n = 10000; // Size of the array

// Arrays for different cases

int arr_random[n], arr_sorted[n], arr_reverse_sorted[n];
// Generate arrays of different types
generateArray(arr_random, n, 0); // Random array
generateArray(arr_sorted, n, 1); // Sorted array
generateArray(arr_reverse_sorted, n, 2); // Reverse sorted array
// Measure time for Merge Sort in different cases
double time_random = measureTime(arr_random, n, mergeSort);
double time_sorted = measureTime(arr_sorted, n, mergeSort);
double time_reverse_sorted = measureTime(arr_reverse_sorted, n, mergeSort);
// Print results
printf("Merge Sort Execution Time:\n");
printf("Random array: %.6f seconds\n", time_random);
printf("Sorted array: %.6f seconds\n", time_sorted);
printf("Reverse sorted array: %.6f seconds\n", time_reverse_sorted);
return 0;
}
Exp-7: Compare the performance of Single Source Shortest Paths
using Greedy method when the graph is represented by adjacency
matrix and adjacency lists.
A).Adjacency Matrix Representation
Source: #include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_VERTICES 100
CSE Department [Madanapalle Institute of Technology & Science] Page 41
 [Advanced Data Structures & Algorithm Analysis]

// Function prototypes
void dijkstraMatrix(int graph[MAX_VERTICES][MAX_VERTICES], int
num_vertices, int source);
// Function to find vertex with minimum distance value
int minDistance(int dist[], bool visited[], int num_vertices);
// Function to print the shortest path from source to j
void printSolution(int dist[], int num_vertices);
// Dijkstra's algorithm using adjacency matrix
void dijkstraMatrix(int graph[MAX_VERTICES][MAX_VERTICES], int
num_vertices, int source) {
int dist[num_vertices]; // The output array. dist[i] will hold the shortest distance
from source to i
bool visited[num_vertices]; // visited[i] will be true if vertex i is included in the
shortest path tree or shortest distance from source to i is finalized

// Initialize all distances as INFINITE and visited[] as false

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

// Distance of source vertex from itself is always 0

dist[source] = 0;

// Find shortest path for all vertices

for (int count = 0; count < num_vertices - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet
processed.
// u is always equal to source in the first iteration.
int u = minDistance(dist, visited, num_vertices);
// Mark the picked vertex as processed
visited[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < num_vertices; v++) {
// Update dist[v] only if is not visited, there is an edge from u to v, and total
weight of path from source to v through u is smaller than current value of
dist[v]
if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v]
< dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
CSE Department [Madanapalle Institute of Technology & Science] Page 42
 [Advanced Data Structures & Algorithm Analysis]

// Print the constructed distance array

printf("Shortest paths from source vertex %d using Adjacency Matrix:\n",
source);
printSolution(dist, num_vertices);
}

// Function to find the vertex with minimum distance value

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

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

if (visited[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}

return min_index;
}

// Function to print the constructed distance array

void printSolution(int dist[], int num_vertices) {
for (int i = 0; i < num_vertices; i++) {
printf("Vertex %d -> Distance: %d\n", i, dist[i]);
}
}

// Main function
int main() {
int num_vertices = 5; // Example with 5 vertices

// Example adjacency matrix representation of the graph

int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 10, 0, 5, 0},
{0, 0, 1, 2, 0},
{0, 0, 0, 0, 4},
{0, 3, 9, 0, 2},
{7, 0, 6, 0, 0}
};

int source = 0; // Source vertex

CSE Department [Madanapalle Institute of Technology & Science] Page 43

 [Advanced Data Structures & Algorithm Analysis]

dijkstraMatrix(graph, num_vertices, source);

return 0;
}

B).Adjacency List:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <sys/time.h>
#define V 1000 // Maximum number of vertices
// Structure to represent a node in adjacency list
struct AdjListNode {
int dest;
int weight;
struct AdjListNode* next;
};

// Structure to represent an adjacency list

struct AdjList {
struct AdjListNode *head;
};

// Structure to represent a graph

struct Graph {
int V;
struct AdjList* array;

CSE Department [Madanapalle Institute of Technology & Science] Page 44

 [Advanced Data Structures & Algorithm Analysis]

};

// Function to create a new adjacency list node

struct AdjListNode* newAdjListNode(int dest, int weight) {
struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct
AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}

// Function to create a graph with V vertices

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

// Create an array of adjacency lists. Size of array will be V

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

// Initialize each adjacency list as empty by making head as NULL

for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;

return graph;
}

CSE Department [Madanapalle Institute of Technology & Science] Page 45

 [Advanced Data Structures & Algorithm Analysis]

// Function to add an edge to an undirected graph

void addEdge(struct Graph* graph, int src, int dest, int weight) {
// Add an edge from src to dest. A new node is added to the adjacency list of src
struct AdjListNode* newNode = newAdjListNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

// Since graph is undirected, add an edge from dest to src also

newNode = newAdjListNode(src, weight);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}

// Function to find the vertex with minimum distance value

int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}

CSE Department [Madanapalle Institute of Technology & Science] Page 46

 [Advanced Data Structures & Algorithm Analysis]

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

// Function that implements Dijkstra's single source shortest path algorithm for a
graph represented using adjacency list
void dijkstraAdjList(struct Graph* graph, int src) {
int dist[V]; // The output array. dist[i] will hold the shortest distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest path tree or
shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false

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

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V-1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed.
CSE Department [Madanapalle Institute of Technology & Science] Page 47
 [Advanced Data Structures & Algorithm Analysis]

// u is always equal to src in the first iteration.

int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

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

struct AdjListNode* pCrawl = graph->array[u].head;
while (pCrawl != NULL) {
int v = pCrawl->dest;

// Update dist[v] only if is not in sptSet, there is an edge from u to v,

// and total weight of path from src to v through u is smaller than current
value of dist[v]
if (!sptSet[v] && dist[u] != INT_MAX && dist[u]+pCrawl->weight < dist[v]) {
dist[v] = dist[u] + pCrawl->weight;
}

pCrawl = pCrawl->next;
}
}

// Print the constructed distance array

//printSolution(dist, V);
}

CSE Department [Madanapalle Institute of Technology & Science] Page 48

 [Advanced Data Structures & Algorithm Analysis]

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

// Initialize graph with random weights for testing

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (i != j && rand() % 10 == 0) // Generate some sparse graph with about
10% density
addEdge(graph, i, j, rand() % 100 + 1);
}
}
struct timeval start, end;
double delta;
gettimeofday(&start, NULL);
// Call Dijkstra's algorithm for all vertices as source
for (int i = 0; i < V; i++) {
dijkstraAdjList(graph, i);
}
gettimeofday(&end, NULL);
// Calculate time taken
delta = ((end.tv_sec - start.tv_sec) * 1000000u + end.tv_usec - start.tv_usec) /
1.e6;
printf("Time taken for adjacency list representation: %.6f seconds\n", delta);
return 0;
}

Explanation

CSE Department [Madanapalle Institute of Technology & Science] Page 49

 [Advanced Data Structures & Algorithm Analysis]

 Both implementations use Dijkstra's algorithm to find the shortest paths from a
source vertex to all other vertices in a graph.
 The adjacency matrix implementation uses a 2D array to represent the graph,
while the adjacency list implementation uses an array of linked lists.
 Each implementation initializes the graph with random weights (sparse
graph).
 Timing information is collected using gettimeofday() to measure the execution
time of each implementation.
 Finally, the execution times are printed for comparison.

Notes

 Ensure your compiler supports C99 standards or higher (-std=c99 or -

std=c11).
 Adjust the value of V (maximum number of vertices) and the density of the
generated graphs (rand() % 10 == 0 for approximately 10% density) as per
your requirements.

By running these programs, you can compare the performance of Dijkstra's

algorithm using adjacency matrix and adjacency list representations for varying
graph sizes and densities.

Exp-8: Implement Job Sequencing with deadlines using Greedy strategy.

Source:
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a job
struct Job {
char id; // Job ID
int deadline; // Deadline of job
int profit; // Profit of job
};
// Function to compare jobs based on profit (used for sorting)
int compareJobs(const void *a, const void *b) {

CSE Department [Madanapalle Institute of Technology & Science] Page 50

 [Advanced Data Structures & Algorithm Analysis]

return ((struct Job *)b)->profit - ((struct Job *)a)->profit;

}
// Function to find the maximum deadline from the given jobs
int findMaxDeadline(struct Job jobs[], int n) {
int max_deadline = -1;
for (int i = 0; i < n; i++) {
if (jobs[i].deadline > max_deadline) {
max_deadline = jobs[i].deadline;
}
}
return max_deadline;
}
// Function to schedule jobs to maximize profit
void jobSequencing(struct Job jobs[], int n) {
// Sort jobs based on profit (in decreasing order)
qsort(jobs, n, sizeof(struct Job), compareJobs);
// Find the maximum deadline among all jobs
int max_deadline = findMaxDeadline(jobs, n);
// Array to store the sequence of jobs scheduled
char result[max_deadline];
int filled_slots = 0; // Number of slots filled in the result array

// Array to keep track of filled slots

int slot[max_deadline];
for (int i = 0; i < max_deadline; i++) {
slot[i] = -1; // -1 indicates slot is free

CSE Department [Madanapalle Institute of Technology & Science] Page 51

 [Advanced Data Structures & Algorithm Analysis]

}
// Iterate through all jobs and assign them to the latest possible slot before their
deadline
for (int i = 0; i < n; i++) {
// Find a suitable slot for this job (must be before its deadline)
for (int j = jobs[i].deadline - 1; j >= 0; j--) {
if (slot[j] == -1) { // Slot is free
slot[j] = i; // Assign this job to slot j
result[j] = jobs[i].id;
filled_slots++;
break;
}
}
}

// Print the sequence of jobs scheduled

printf("Sequence of jobs scheduled: ");
for (int i = 0; i < max_deadline; i++) {
if (slot[i] != -1) {
printf("%c ", result[i]);
}
}
printf("\n");
}
int main() {
// Example jobs

CSE Department [Madanapalle Institute of Technology & Science] Page 52

 [Advanced Data Structures & Algorithm Analysis]

struct Job jobs[] = {

{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27},
{'d', 1, 25}, {'e', 3, 15}
};
int n = sizeof(jobs) / sizeof(jobs[0]);
printf("Input Jobs:\n");
printf("Job ID Deadline Profit\n");
for (int i = 0; i < n; i++) {
printf("%c %d %d\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);
}
// Perform job sequencing
jobSequencing(jobs, n);
return 0;
}
Output:
Input Jobs:
Job ID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15
Sequence of jobs scheduled: c a

Explanation:

1. Job Structure: The struct Job is defined to store details of each job including
its ID, deadline, and profit.

CSE Department [Madanapalle Institute of Technology & Science] Page 53

 [Advanced Data Structures & Algorithm Analysis]

2. compareJobs Function: This function is used by qsort() to sort jobs based

on their profit in descending order.
3. findMaxDeadline Function: This function finds the maximum deadline
among all the jobs. This helps in determining the size of the array needed to
store the job sequence.
4. jobSequencing Function:
o First, it sorts the jobs based on their profits in descending order.
o Then, it finds a suitable slot for each job before its deadline and fills it if
available.
o Finally, it prints the sequence of jobs scheduled to maximize profit
without missing any deadlines.
5. Main Function:
o Defines example jobs (jobs[] array).
o Prints the input jobs.
o Calls jobSequencing() function to schedule jobs and prints the
sequence of jobs scheduled.

From the above output example:

 Jobs 'c', 'a', and 'e' are scheduled.

 Job 'b' and 'd' are not scheduled due to their lower profit compared to other
jobs with overlapping deadlines.

This program efficiently implements the Job Sequencing with deadlines problem
using a Greedy strategy, ensuring maximum profit by scheduling jobs within their
deadlines.

Exp-9: Write a program to solve 0/1 Knapsack problem Using Dynamic

Programming.

Source:

#include <stdio.h>

// Function to find maximum of two integers

int max(int a, int b) {

return (a > b) ? a : b;

CSE Department [Madanapalle Institute of Technology & Science] Page 54

 [Advanced Data Structures & Algorithm Analysis]

// Function to solve 0/1 Knapsack problem using Dynamic Programming

int knapsack(int W, int wt[], int val[], int n) {

int i, w;

int K[n+1][W+1];

// Build K[][] in bottom-up manner

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

for (w = 0; w <= W; w++) {

if (i == 0 || w == 0)

K[i][w] = 0;

else if (wt[i-1] <= w)

K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);

else

K[i][w] = K[i-1][w];

// K[n][W] contains the maximum value that can be put in a knapsack of capacity
W

return K[n][W];

int main() {

int val[] = {60, 100, 120};

int wt[] = {10, 20, 30};

CSE Department [Madanapalle Institute of Technology & Science] Page 55

 [Advanced Data Structures & Algorithm Analysis]

int W = 50;

int n = sizeof(val)/sizeof(val[0]);

printf("Input values:\n");

printf("Values: ");

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

printf("%d ", val[i]);

printf("\n");

printf("Weights: ");

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

printf("%d ", wt[i]);

printf("\n");

printf("Knapsack capacity: %d\n", W);

int maxProfit = knapsack(W, wt, val, n);

printf("Maximum profit that can be obtained: %d\n", maxProfit);

return 0;

Explanation:

1. max Function: This function returns the maximum of two integers.

2. knapsack Function:
o This function takes the capacity of the knapsack W, arrays wt[] and val[]
representing weights and values of items respectively, and n which is
the number of items.

CSE Department [Madanapalle Institute of Technology & Science] Page 56

 [Advanced Data Structures & Algorithm Analysis]

oIt creates a 2D array K[][] where K[i][w] represents the maximum value
that can be attained with the first i items and a knapsack capacity w.
o It iteratively fills up this table based on whether including the i-th item
will increase the value or not.
3. Main Function:
o Defines example values and weights (val[] and wt[] arrays), and the
knapsack capacity (W).
o Prints the input values and weights.
o Calls the knapsack function to compute the maximum profit that can be
obtained.
o Prints the maximum profit.

Sample Output:

Input values:

Values: 60 100 120

Weights: 10 20 30

Knapsack capacity: 50

Maximum profit that can be obtained: 220

In this example:

 We have three items with values {60, 100, 120} and weights {10, 20, 30}.
 The knapsack capacity W is 50.
 The maximum profit that can be obtained by selecting items without
exceeding the capacity is 220.

This program efficiently solves the 0/1 Knapsack problem using Dynamic
Programming, ensuring optimal selection of items to maximize the total value within
the constraints of the knapsack's capacity.

Exp-10: Implement N-Queens Problem Using Backtracking.

Source:

#include <stdio.h>

#include <stdbool.h>

#define N 8 // Change N to set the size of the chessboard (N x N)

CSE Department [Madanapalle Institute of Technology & Science] Page 57
 [Advanced Data Structures & Algorithm Analysis]

// Function to print the solution

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

static int solution = 1;

printf("Solution %d:\n", solution++);

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

for (int j = 0; j < N; j++)

printf("%2d ", board[i][j]);

printf("\n");

printf("\n");

// Function to check if a queen can be placed on board[row][col]

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

// Check for queens in the same column up to the current row

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

if (board[i][col])

return false;

// Check upper left diagonal

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)

if (board[i][j])

return false;

CSE Department [Madanapalle Institute of Technology & Science] Page 58

 [Advanced Data Structures & Algorithm Analysis]

// Check upper right diagonal

for (int i = row, j = col; i >= 0 && j < N; i--, j++)

if (board[i][j])

return false;

return true;

// Function to solve N-Queens problem using backtracking

bool solveNQueensUtil(int board[N][N], int row) {

// Base case: If all queens are placed, return true

if (row == N) {

printSolution(board);

return true;

bool res = false;

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

// Check if the queen can be placed on board[row][col]

if (isSafe(board, row, col)) {

// Place the queen

board[row][col] = 1;

// Recur to place the rest of the queens

CSE Department [Madanapalle Institute of Technology & Science] Page 59

 [Advanced Data Structures & Algorithm Analysis]

res = solveNQueensUtil(board, row + 1) || res;

// If placing queen in board[row][col] doesn't lead to a solution,

// then remove queen from board[row][col]

board[row][col] = 0; // Backtrack

return res;

// Function to solve N-Queens problem and print all solutions

void solveNQueens() {

int board[N][N] = { {0} };

if (!solveNQueensUtil(board, 0)) {

printf("Solution does not exist for N = %d\n", N);

int main() {

solveNQueens();

CSE Department [Madanapalle Institute of Technology & Science] Page 60

 [Advanced Data Structures & Algorithm Analysis]

return 0;

Explanation:

1. Constants and Definitions:

o N: Represents the size of the chessboard (N x N). You can change N to
any positive integer to solve the N-Queens problem for that board size.
2. printSolution Function:
o Prints the current configuration of the chessboard when a valid
placement of queens is found.
3. isSafe Function:
o Checks if it's safe to place a queen at board[row][col] by verifying no
other queens can attack it based on their positions in the same column,
diagonal, or anti-diagonal.
4. solveNQueensUtil Function:
o Recursive function that tries to place queens row by row.
o If a valid placement is found (row == N), it prints the solution and
returns true.
o Backtracks if placing a queen does not lead to a solution.
5. solveNQueens Function:
o Initializes the chessboard (board) and calls solveNQueensUtil to find
and print all possible solutions.
6. Main Function:
o Calls solveNQueens to solve the N-Queens problem and print all
solutions.

Sample Output(N=8)

Solution 1:

0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0

0 0 1 0 0 0 0 0

0 0 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0

CSE Department [Madanapalle Institute of Technology & Science] Page 61

 [Advanced Data Structures & Algorithm Analysis]

0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 1

Solution 2:

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0

CSE Department [Madanapalle Institute of Technology & Science] Page 62

 [Advanced Data Structures & Algorithm Analysis]

Exp-11: Use Backtracking strategy to solve 0/1 Knapsack problem.

Source:
#include <stdio.h>

#define N 4 // Number of items

#define W 8 // Capacity of knapsack

// Structure to represent an item

struct Item {

int weight;

int value;

};

// Array of items (example)

struct Item items[N] = {{2, 5}, {3, 10}, {4, 15}, {5, 7}};

// Variables to store the best solution found

int best_value = 0;

int best_subset[N];

// Function to solve 0/1 Knapsack problem using backtracking

CSE Department [Madanapalle Institute of Technology & Science] Page 63

 [Advanced Data Structures & Algorithm Analysis]

void knapsackBacktrack(int index, int current_weight, int current_value, int subset[])

{

// Base case: If all items are considered or knapsack capacity is reached

if (index == N || current_weight >= W) {

// Update the best solution if the current one is better

if (current_value > best_value) {

best_value = current_value;

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

best_subset[i] = subset[i];

return;

// Explore including the current item in the subset

if (current_weight + items[index].weight <= W) {

subset[index] = 1; // Include item

knapsackBacktrack(index + 1, current_weight + items[index].weight,

current_value + items[index].value, subset);

// Explore excluding the current item from the subset

subset[index] = 0; // Exclude item

knapsackBacktrack(index + 1, current_weight, current_value, subset);

int main() {

int subset[N] = {0}; // Array to store the subset of items chosen (1 for chosen, 0 for
not chosen)
CSE Department [Madanapalle Institute of Technology & Science] Page 64
 [Advanced Data Structures & Algorithm Analysis]

knapsackBacktrack(0, 0, 0, subset);

// Print the best solution found

printf("Best subset of items (0/1 Knapsack problem):\n");

printf("Item\tWeight\tValue\n");

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

if (best_subset[i] == 1) {

printf("%d\t%d\t%d\n", i+1, items[i].weight, items[i].value);

} }

printf("Total value: %d\n", best_value);

return 0; }

Explanation:

1. Constants and Definitions:

o N: Number of items.
o W: Capacity of the knapsack.
o struct Item: Represents an item with its weight and value.
2. items Array:
o Array of struct Item representing the items available for selection into
the knapsack.
3. best_value and best_subset:
o Variables to store the best solution found (maximum value and the
subset of items chosen).
4. knapsackBacktrack Function:
o Recursive function that explores all possible subsets of items.
o It tries to include each item in the knapsack if its weight allows
(current_weight + items[index].weight <= W).
o Updates best_value and best_subset if a better solution is found.
5. Main Function:
o Initializes subset array to store the selected items.
o Calls knapsackBacktrack to find the optimal subset of items.
o Prints the best subset found along with their weights, values, and total
value

Sample Output:

CSE Department [Madanapalle Institute of Technology & Science] Page 65

 [Advanced Data Structures & Algorithm Analysis]

For the given items:

 Item 1: Weight = 2, Value = 5

 Item 2: Weight = 3, Value = 10
 Item 3: Weight = 4, Value = 15
 Item 4: Weight = 5, Value = 7 and knapsack capacity W = 8, the program will
output:

Best subset of items (0/1 Knapsack problem):

Item Weight Value

2 3 10

3 4 15

Total value: 25

Exp-12: Implement Travelling Sales Person problem using Branch and

Bound approach.

Source:
#include <stdio.h>

#include <limits.h>

#define N 4 // Number of cities

// Example graph representation (adjacency matrix)

int graph[N][N] = {

{0, 10, 15, 20},

{10, 0, 35, 25},

{15, 35, 0, 30},

{20, 25, 30, 0}

};

// Array to store the minimum cost found so far

CSE Department [Madanapalle Institute of Technology & Science] Page 66

 [Advanced Data Structures & Algorithm Analysis]

int min_cost = INT_MAX;

// Variables to track visited cities and current path

int visited[N];

int current_path[N+1];

int path_count = 0;

// Function to find the minimum cost Hamiltonian cycle using Branch and Bound

void tspBranchBound(int current_bound, int current_weight, int level) {

// Base case: All cities have been visited

if (level == N) {

// Check if there is an edge from last visited city back to the starting city

if (graph[current_path[level-1]][current_path[0]] != 0) {

int current_path_cost = current_weight + graph[current_path[level-1]]

[current_path[0]];

// Update the minimum cost and current path if a better solution is found

if (current_path_cost < min_cost) {

min_cost = current_path_cost;

printf("New minimum cost found: %d\n", min_cost);

printf("Path: ");

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

printf("%d -> ", current_path[i]);

printf("%d\n", current_path[0]);

CSE Department [Madanapalle Institute of Technology & Science] Page 67

 [Advanced Data Structures & Algorithm Analysis]

return;

// Loop through all cities

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

// Check if the city can be visited (not already visited and there's an edge)

if (visited[i] == 0 && graph[current_path[level-1]][i] != 0) {

// Mark the city as visited

visited[i] = 1;

current_path[level] = i;

path_count++;

// Recur to explore further

tspBranchBound(current_bound, current_weight + graph[current_path[level-

1]][i], level + 1);

// Backtrack

visited[i] = 0;

path_count--;

current_path[level] = -1;

// Function to initiate the Branch and Bound approach for TSP

void solveTSP() {

CSE Department [Madanapalle Institute of Technology & Science] Page 68

 [Advanced Data Structures & Algorithm Analysis]

// Start from the first city (0)

visited[0] = 1;

current_path[0] = 0;

path_count++;

// Calculate initial lower bound for the root node

int current_bound = 0;

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

current_bound += (graph[i][0] == 0) ? INT_MAX : graph[i][0];

// Recursively solve TSP using Branch and Bound

tspBranchBound(current_bound/2, 0, 1);

int main() {

printf("Travelling Salesperson Problem (TSP) using Branch and Bound\n");

solveTSP();

printf("Minimum cost of traversal: %d\n", min_cost);

return 0;

Explanation:

1. Constants and Definitions:

o N: Number of cities.
o graph[N][N]: Example graph represented as an adjacency matrix where
graph[i][j] represents the cost of travel from city i to city j.
2. Global Variables:
o min_cost: Variable to store the minimum cost found so far.

CSE Department [Madanapalle Institute of Technology & Science] Page 69

 [Advanced Data Structures & Algorithm Analysis]

ovisited[N]: Array to keep track of visited cities.

ocurrent_path[N+1]: Array to store the current path being explored.
o path_count: Counter to keep track of the number of cities visited in the
current path.
3. tspBranchBound Function:
o Recursive function that implements the Branch and Bound approach to
find the minimum cost Hamiltonian cycle.
o It explores all possible paths, calculating the cost and updating
min_cost whenever a better solution (lower cost) is found.
4. solveTSP Function:
o Initializes the search by marking the first city as visited and starting from
city 0.
o Computes an initial lower bound (current_bound) based on the graph's
edges.
o Calls tspBranchBound to find and print the minimum cost Hamiltonian
cycle.
5. Main Function:
o Prints a message indicating the start of the TSP using Branch and
Bound.
o Calls solveTSP to solve the problem and print the minimum cost found.

Sample Output:

For the given example graph:

Travelling Salesperson Problem (TSP) using Branch and Bound

New minimum cost found: 80

Path: 0 -> 1 -> 3 -> 2 -> 0

New minimum cost found: 70

Path: 0 -> 2 -> 1 -> 3 -> 0

Minimum cost of traversal: 70

In this example:

 The TSP program finds the minimum cost Hamiltonian cycle which visits each
city exactly once and returns to the starting city.

CSE Department [Madanapalle Institute of Technology & Science] Page 70

 [Advanced Data Structures & Algorithm Analysis]

 The output shows the minimum cost found (70) and one of the optimal paths
(0 -> 2 -> 1 -> 3 -> 0) that achieves this cost.

CSE Department [Madanapalle Institute of Technology & Science] Page 71