ADVANCED DATA STRUCTURES &ALGORITHM ANALYSIS LAB

Course Objectives:

The objectives of the course is to

acquire practical skills in constructing and managing Data structures

apply the popular algorithm design methods in problem-solving scenarios

Experiments covering the Topics:

Operations on AVL trees, B-Trees, Heap Trees

Graph Traversals

Sorting techniques

Minimum cost spanning trees

Shortest path algorithms

0/1 Knapsack Problem

Travelling Salesperson problem

Optimal Binary Search Trees

N-Queens Problem

Job Sequencing

Experiments:

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 treeinto a new file using in-order.

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

stored in array. Implement searching, insertion and deletion operations.

3. Construct Min and Max Heap using arrays, delete any element and
display

the contentof the Heap.

4. Implement BFT and DFT for given graph, when graph is represented by

a) Adjacency Matrix b) Adjacency Lists

5. Write a program for finding the biconnected components in a given

graph.
6. Implement Quick sort and Merge sort and observe the execution time
for

various inputsizes (Average, Worst and Best cases).

7. Compare the performance of Single Source Shortest Paths using Greedy

method whenthe graph is represented by adjacency matrix and adjacency

lists.

8. Implement Job Sequencing with deadlines using Greedy strategy.

9. Write a program to solve 0/1 Knapsack problem Using Dynamic

Programming.

10. Implement N-Queens Problem Using Backtracking.

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

12. Implement Travelling Sales Person problem using Branch and Bound
approach.

LTPC

0 0 3 1.5

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY KAKINADA

KAKINADA – 533 003, Andhra Pradesh, India

B.Tech CSBS (R23-COURSE STRUCTURE & SYLLABUS)

Reference Books:

1. Fundamentals of Data Structures in C++, Horowitz Ellis, Sahni Sartaj,

Mehta, Dinesh, 2nd Edition, Universities Press

2. Computer Algorithms/C++ Ellis Horowitz, Sartaj Sahni, Sanguthevar

Rajasekaran, 2ndEdition, University Press

3. Data Structures and program design in C, Robert Kruse, Pearson

Education Asia

4. An introduction to Data Structures with applications, Trembley &

Sorenson,

McGrawHill

Online Learning Resources:

1. http://cse01-iiith.vlabs.ac.in/

2. http://peterindia.net/Algorithms.html
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.

#include <stdio.h>

#include <stdlib.h>

// Structure for a node in the AVL tree

struct Node {

int data;

struct Node* left;

struct Node* right;

int height; // Height of the node

};

// Function to create a new node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation error\n");

exit(1);

newNode->data = data;

newNode->left = newNode->right = NULL;

newNode->height = 1; // Initialize height as 1 for a new node

return newNode;

}
// Function to calculate the height of a node

int getHeight(struct Node* node) {

if (node == NULL)

return 0;

return node->height;

// Function to find the maximum of two integers

int max(int a, int b) {

return (a > b) ? a : b;

// Function to perform right rotation

struct Node* rightRotate(struct Node* y) {

struct Node* x = y->left;

struct Node* T2 = x->right;

// Perform rotation

x->right = y;

y->left = T2;

// Update heights

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

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

return x;

}
// Function to perform left rotation

struct Node* leftRotate(struct Node* x) {

struct Node* y = x->right;

struct Node* T2 = y->left;

// Perform rotation

y->left = x;

x->right = T2;

// Update heights

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

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

return y;

// Function to get the balance factor of a node

int getBalanceFactor(struct Node* node) {

if (node == NULL)

return 0;

return getHeight(node->left) - getHeight(node->right);

// Function to insert a node into the AVL tree

struct Node* insert(struct Node* root, int data) {

if (root == NULL)

return createNode(data);

if (data < root->data)

root->left = insert(root->left, data);

else if (data > root->data)

root->right = insert(root->right, data);

else

return root; // Duplicate keys are not allowed

// Update height of current node

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

// Get the balance factor to check if rotation is needed

int balance = getBalanceFactor(root);

// Left-Left case (LL)

if (balance > 1 && data < root->left->data)

return rightRotate(root);

// Right-Right case (RR)

if (balance < -1 && data > root->right->data)

return leftRotate(root);

// Left-Right case (LR)

if (balance > 1 && data > root->left->data) {

root->left = leftRotate(root->left);

return rightRotate(root);

// Right-Left case (RL)

if (balance < -1 && data < root->right->data) {

root->right = rightRotate(root->right);
return leftRotate(root);

return root;

// Function to find the node with the minimum value in the tree

struct Node* findMinValueNode(struct Node* node) {

struct Node* current = node;

while (current->left != NULL)

current = current->left;

return current;

// Function to delete a node from the AVL tree

struct Node* deleteNode(struct Node* root, int data) {

if (root == NULL)

return root;

if (data < root->data)

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

else if (data > root->data)

root->right = deleteNode(root->right, data);

else {

// Node with only one child or no child

if ((root->left == NULL) || (root->right == NULL)) {

struct Node* 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 (smallest

// in the right subtree)

struct Node* temp = findMinValueNode(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 current node

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

// Get the balance factor to check if rotation is needed

int balance = getBalanceFactor(root);

// Left-Left case (LL)

if (balance > 1 && getBalanceFactor(root->left) >= 0)

return rightRotate(root);

// Left-Right case (LR)

if (balance > 1 && getBalanceFactor(root->left) < 0) {

root->left = leftRotate(root->left);

return rightRotate(root);

// Right-Right case (RR)

if (balance < -1 && getBalanceFactor(root->right) <= 0)

return leftRotate(root);

// Right-Left case (RL)

if (balance < -1 && getBalanceFactor(root->right) > 0) {

root->right = rightRotate(root->right);

return leftRotate(root);

return root;

// Function for in-order traversal of the AVL tree

void inOrderTraversal(struct Node* root)

if(root != NULL) {

inOrderTraversal(root->left);
printf("%d ",root->data);

inOrderTraversal(root->right);

// Function to free memory by deallocating nodes

void freeMemory(struct Node* root) {

if (root == NULL)

return;

freeMemory(root->left);

freeMemory(root->right);

free(root);

int main() {

int choice,value;

struct Node* root = NULL;

do

printf("\nAVL TREE OPERATIONS");

printf("\n1. Insertion\n2. Deletion\n3. Display\n4. Exit");

printf("\nEnter your choice: ");

scanf("%d",&choice);

switch(choice)

case 1: printf("Enter the value to be insert: ");

scanf("%d",&value);

root = insert(root, value);

break;

case 2: printf("Enter the value to be deleted: ");

scanf("%d",&value);

root = deleteNode(root, value);

break;

case 3: inOrderTraversal(root);

break;

case 4: freeMemory(root);

break;

default: printf("\nWrong selection!!! Try again!!!");

}while(choice!=4);

return 0;

OUTPUT

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 1

Enter the value to be insert: 1

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 1

Enter the value to be insert: 2

1. Insertion

2. Deletion

3. Display
4. Exit

Enter your choice: 1

Enter the value to be insert: 3

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 1

Enter the value to be insert: 4

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 1

Enter the value to be insert: 5

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 1

Enter the value to be insert: 6

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 3

123456

1. Insertion

2. Deletion
3. Display

4. Exit

Enter your choice: 2

Enter the value to be deleted: 2

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 2

Enter the value to be deleted: 3

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 2

Enter the value to be deleted: 1

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 3

456

1. Insertion

2. Deletion

3. Display

4. Exit

Enter your choice: 4

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

stored in array. Implement searching, insertion and deletion operations.

* For simplicity, provide a basic implementation focusing on insertion,
search, and a simple traversal. We will not include deletion as it is quite
complex and would make the code exceedingly long. In practice, B-tree
deletion requires handling numerous cases to redistribute or merge nodes.
*/

#include <stdio.h>

#include <stdlib.h>

#define MAX_KEYS 3 // Maximum keys in a node (t-1 where t is the

minimum degree)

#define MIN_KEYS 1 // Minimum keys in a node (ceil(t/2) - 1)

#define MAX_CHILDREN (MAX_KEYS + 1) // Maximum children in a node

(t)

typedef struct BTreeNode {

int keys[MAX_KEYS];

struct BTreeNode* children[MAX_CHILDREN];

int numKeys;

int isLeaf;

} BTreeNode;

BTreeNode* createNode(int isLeaf) {

BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));

node->isLeaf = isLeaf;

node->numKeys = 0;

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

node->children[i] = NULL;

return node;

void splitChild(BTreeNode* parent, int index, BTreeNode* child) {

BTreeNode* newChild = createNode(child->isLeaf);

newChild->numKeys = MIN_KEYS;

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

newChild->keys[i] = child->keys[i + MIN_KEYS + 1];

if (!child->isLeaf) {

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

newChild->children[i] = child->children[i + MIN_KEYS + 1];

child->numKeys = MIN_KEYS;

for (int i = parent->numKeys; i >= index + 1; i--) {

parent->children[i + 1] = parent->children[i];

parent->children[index + 1] = newChild;
for (int i = parent->numKeys - 1; i >= index; i--) {

parent->keys[i + 1] = parent->keys[i];

parent->keys[index] = child->keys[MIN_KEYS];

parent->numKeys++;

void insertNonFull(BTreeNode* node, int key) {

int i = node->numKeys - 1;

if (node->isLeaf) {

while (i >= 0 && node->keys[i] > key) {

node->keys[i + 1] = node->keys[i];

i--;

node->keys[i + 1] = key;

node->numKeys++;

} else {

while (i >= 0 && node->keys[i] > key) {

i--;

if (node->children[i + 1]->numKeys == MAX_KEYS) {

splitChild(node, i + 1, node->children[i + 1]);

if (key > node->keys[i + 1]) {

i++;

insertNonFull(node->children[i + 1], key);

void insert(BTreeNode** root, int key) {

BTreeNode* r = *root;

if (r->numKeys == MAX_KEYS) {

BTreeNode* newRoot = createNode(0);

newRoot->children[0] = r;

splitChild(newRoot, 0, r);

int i = 0;

if (newRoot->keys[0] < key) {

i++;

insertNonFull(newRoot->children[i], key);

*root = newRoot;

} else {

insertNonFull(r, key);

void traverse(BTreeNode* root) {

if (root == NULL) return;

int i;

for (i = 0; i < root->numKeys; i++) {

if (!root->isLeaf) {

traverse(root->children[i]);

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

if (!root->isLeaf) {

traverse(root->children[i]);

int main() {

BTreeNode* root = createNode(1);

insert(&root, 10);

insert(&root, 20);

insert(&root, 5);

insert(&root, 6);

insert(&root, 12);

insert(&root, 30);

insert(&root, 7);

insert(&root, 17);

printf("Traversal of the constructed B-tree is:\n");

traverse(root);

return 0;

}
OUTPUT

Traversal of the constructed B-tree is:

5 6 7 10 12 17 20 30

3. Construct Min and Max Heap using arrays, delete any element and
display the content of the Heap.

#include <stdio.h>

// Function to swap two elements

void swap(int *a, int *b) {

int t = *a;

*a = *b;

*b = t;

/* heapify the subtree with root i */

void heapify(int* arr, int n, int i)

// store largest as the root element

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

// now check whether the right and left right is larger than the root or
not

if (left < n && arr[left] > arr[largest])

largest = left;

}
if (right < n && arr[right] > arr[largest])

largest = right;

// if the root is smaller than the children then swap it with the largest
children's value

if (largest != i)

swap(&arr[i], &arr[largest]);

// again heapify that side of the heap where the root has gone

heapify(arr, n, largest);

/* sorts the given array of n size */

void heapsort(int* arr, int n)

// build the binary max heap

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

// sort the max heap

for (int i = n - 1; i >= 0; i--)

// swap the root node and the last leaf node

swap(&arr[i], &arr[0]);

// again heapify the max heap from the root

heapify(arr, i, 0);
}

int main()

int i, count, number[25];

printf("How many elements are u going to enter?: ");

scanf("%d",&count);

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

printf("\nEnter %d element: ", i+1);

scanf("%d",&number[i]);

heapsort(number,count);

printf("Order of Sorted elements: ");

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

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

return 0;

OUTPUT

How many elements are u going to enter?: 10

Enter 1 element: 2

Enter 2 element: 5

Enter 3 element: 8

Enter 4 element: 10

Enter 5 element: 3

Enter 6 element: 1

Enter 7 element: 4
Enter 8 element: 6

Enter 9 element: 7

Enter 10 element: 9

Order of Sorted elements: 1 2 3 4 5 6 7 8 9 10

4.Write a program to implement the Depth First search a graph traversal

methods(DFT).

#include <stdio.h>

int a[20][20], visited[20], n;

void dfs(int v)

int i;

visited[v] = 1;

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

if (a[v][i] && !visited[i])

printf("\n %d->%d", v, i);

dfs(i);

int main( )

int i, j,v, count = 0;

printf("\n Enter number of vertices:");

scanf("%d", &n);
for (i = 1; i <= n; i++)

visited[i] = 0;

for (j = 1; j <= n; j++)

a[i][j] = 0;

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

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

for (j = 1; j <= n; j++)

scanf("%d", &a[i][j]);

printf("Enter the starting vertex: ");

scanf("%d", &v);

dfs(v);

return 0;

OUTPUT

Enter number of vertices:6

Enter the adjacency matrix:

011000

101000

110110

001000

001001

000010

Enter the starting vertex: 2

2->1

1->3
3->4

3->5

5->6

4.Write a program to implement the Breadth First Search graph traversal

methods (BFT).

#include<stdio.h>

// creating queue data structure using arrays

int queue[10];

// defining pointers of the queue to perform pop and push

int front=0,back=0;

// defining push operation on the queue

void enqueue(int var)

queue[back] = var;

back++;

// defining dequeue operation on queue

void dequeue()

queue[front] = 0;

front++;

// creating a visited array to keep the track of visited nodes

int visited[7] = {0};

int main()

int v,n,i,j;
// adjacenty matrix representing graph

int graph[10][10];

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

scanf("%d", &n);

printf("Enter graph data in matrix form: \n");

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

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

scanf("%d", &graph[i][j]);

// adding a starting node in the list

printf("Enter the starting vertex: ");

scanf("%d", &v);

enqueue(v);

while(front != back)

int current = queue[front];

// printing current element

printf("%d ", current);

// popping the front element from the queue

dequeue();

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

// adding non-visited connected nodes of the current node to the

queue

if((graph[current-1][i] == 1) && (visited[i] == 0))

visited[i] = 1; // marking visisted

enqueue(i+1);

}
}

return 0;

OUTPUT

Enter the number of vertices: 6

Enter graph data in matrix form:

011000

101000

110110

001000

001001

000010

Enter the starting vertex: 2

2132456
5. Write a program for finding the biconnected components in a given
graph.

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_NODES 100

// Structure to represent an edge in the graph

typedef struct Edge {

int u;

int v;

} Edge;

// Global variables

int n, m; // Number of nodes and edges

int adj[MAX_NODES][MAX_NODES]; // Adjacency matrix

int disc[MAX_NODES]; // Discovery time of nodes

int low[MAX_NODES]; // Lowest discovery time reachable from a node

int parent[MAX_NODES]; // Parent of a node in DFS tree

bool visited[MAX_NODES]; // Visited nodes

int time; // Time counter for DFS

Edge stack[MAX_NODES * MAX_NODES]; // Stack to store edges

int top = -1; // Top of the stack

// Function to add an edge to the graph

void addEdge(int u, int v) {

adj[u][v] = 1;

adj[v][u] = 1;

// Function to push an edge onto the stack

void push(Edge e) {

stack[++top] = e;

// Function to pop an edge from the stack

Edge pop() {

return stack[top--];

// Function to find biconnected components using DFS

void dfs(int u) {

visited[u] = true;

disc[u] = low[u] = ++time;

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

if (adj[u][v]) {

if (!visited[v]) {

parent[v] = u;

push((Edge){u, v});

dfs(v);
low[u] = (low[u] < low[v]) ? low[u] : low[v];

if (low[v] >= disc[u]) {

printf("Biconnected component:\n");

Edge e;

do {

e = pop();

printf("(%d, %d) ", e.u, e.v);

} while (e.u != u || e.v != v);

printf("\n");

} else if (v != parent[u]) {

low[u] = (low[u] < disc[v]) ? low[u] : disc[v];

// Function to find all biconnected components

void findBiconnectedComponents() {

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

visited[i] = false;

parent[i] = -1;

time = 0;

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

if (!visited[i]) {

dfs(i);

int main() {

// Example usage

n = 5;

m = 6;

addEdge(0, 1);

addEdge(1, 2);

addEdge(2, 0);

addEdge(1, 3);

addEdge(3, 4);

addEdge(4, 1);

findBiconnectedComponents();

return 0;

}
6. Implement Quick sort and observe the execution time for various input
sizes (Average, Worst and Best cases).
#include <stdio.h>

// Function to swap two elements

void swap(int *a, int *b) {

int t = *a;

*a = *b;

*b = t;

void quicksort(int number[25],int first,int last)

int i, j, pivot, temp;

if(first<last)

pivot=first; // Choose the first element as pivot

i=first;

j=last;

while(i<j)

while(number[i]<=number[pivot]&&i<last)

i++;

while(number[j]>number[pivot])
j--;

if(i<j) // swap two elements

swap(&number[i], &number[j]);

// Swap the pivot element with the element at i+1 position

swap(&number[pivot], &number[j]);

// Recursive call on the left of pivot

quicksort(number,first,j-1);

// Recursive call on the right of pivot

quicksort(number,j+1,last);

int main()

int i, count, number[25];

printf("How many elements are u going to enter?: ");

scanf("%d",&count);

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

printf("\nEnter %d element: ", i+1);

scanf("%d",&number[i]);

quicksort(number,0,count-1);

printf("Order of Sorted elements: ");

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

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

return 0;
}

OUTPUT

How many elements are u going to enter?: 10

Enter 1 element: 3

Enter 2 element: 6

Enter 3 element: 9

Enter 4 element: 8

Enter 5 element: 5

Enter 6 element: 2

Enter 7 element: 1

Enter 8 element: 4

Enter 9 element: 7

Enter 10 element: 10

Order of Sorted elements: 1 2 3 4 5 6 7 8 9 10

6. Implement Merge sort and observe the execution time for various input
sizes (Average, Worst and Best cases).

#include <stdio.h>

void merge(int A[], int mid, int low, int high)

int i, j, k, B[100];

i = low;

j = mid + 1;

k = low;

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

if (A[i] < A[j])

{
B[k] = A[i];

i++;

k++;

else

B[k] = A[j];

j++;

k++;

while (i <= mid)

B[k] = A[i];

k++;

i++;

while (j <= high)

B[k] = A[j];

k++;

j++;

// It will copy data from temporary array to array

for (int i = low; i <= high; i++)

A[i] = B[i];

}
void mergeSort(int number[], int low, int high)

int mid;

if(low<high)

// finding the mid value of the array.

mid = (low + high) /2;

// Calling the merge sort for the first half

mergeSort(number, low, mid);

// Calling the merge sort for the second half

mergeSort(number, mid+1, high);

// Calling the merge function

merge(number, mid, low, high);

int main()

int i, count, number[25];

printf("How many elements are u going to enter?: ");

scanf("%d",&count);

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

printf("\nEnter %d element: ", i+1);

scanf("%d",&number[i]);

mergeSort(number,0,count-1);

printf("Order of Sorted elements: ");

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

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

return 0;

OUTPUT

How many elements are u going to enter?: 10

Enter 1 element: 10

Enter 2 element: 1

Enter 3 element: 4

Enter 4 element: 7

Enter 5 element: 8

Enter 6 element: 5

Enter 7 element: 2

Enter 8 element: 3

Enter 9 element: 6

Enter 10 element: 9

Order of Sorted elements: 1 2 3 4 5 6 7 8 9 10

8. Implement Job Sequencing with deadlines using Greedy strategy.

#include <stdio.h>

#include <stdlib.h>

// Structure to represent a job

struct Job {

int id;

int deadline;

int profit;

};

// Function to compare two jobs based on profit

int compare(const void *a, const void *b) {

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

// Function to find the maximum deadline

int findMaxDeadline(struct Job arr[], int n) {

int max = arr[0].deadline;

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

if (arr[i].deadline > max) {

max = arr[i].deadline;

return max;

// Function to implement job sequencing

void jobSequencing(struct Job arr[], int n) {

// Sort jobs in decreasing order of profit

qsort(arr, n, sizeof(struct Job), compare);

// Find maximum deadline

int maxDeadline = findMaxDeadline(arr, n);

// Create an array to store the job sequence

int sequence[maxDeadline];

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

sequence[i] = -1;

// Assign jobs to time slots

int totalProfit = 0;

int jobsScheduled = 0;

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

for (int j = arr[i].deadline - 1; j >= 0; j--) {

if (sequence[j] == -1) {

sequence[j] = arr[i].id;

totalProfit += arr[i].profit;

jobsScheduled++;

break;

// Print the results

printf("Jobs scheduled: ");

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

if (sequence[i] != -1) {
printf("%d ", sequence[i]);

printf("\nTotal profit: %d\n", totalProfit);

int main() {

struct Job arr[] = {

{1, 2, 100},

{2, 1, 19},

{3, 2, 27},

{4, 1, 25},

{5, 3, 15}

};

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

jobSequencing(arr, n);

return 0;

Jobs scheduled: 3 1 5

Total profit: 142

9. Write a program to solve 0/1 Knapsack problem Using Dynamic

Programming.
#include <stdio.h>

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

// Returns the maximum value that can be put in a knapsack of

capacity W

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

int i, w;

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

// Build table 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];

return K[n][W];

int main()

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

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

int W = 50;

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

printf("\nValue = %d", knapsack(W, wt, val, n));

return 0;

Out put: Value = 220

10. Implement N-Queens Problem Using Backtracking.

#include<stdio.h>

#include<math.h>
int a[30],count=0;

int place(int pos) {

int i;

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

if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))

return 0;

return 1;

void print_sol(int n) {

int i,j;

count++;

printf("\n");

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

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

if(a[i]==j)

printf("%d", j);

void queen(int n) {

int k=1;

a[k]=0;

while(k!=0) {

a[k]=a[k]+1;

while((a[k]<=n)&&!place(k))

a[k]++;

if(a[k]<=n) {
if(k==n)

print_sol(n); else {

k++;

a[k]=0;

} else

k--;

int main() {

int i,n;

printf("Enter the number of Queens\n");

scanf("%d",&n);

queen(n);

printf("\n\nTotal Solutions = %d", count);

//getch();

Output:

Enter the number of Queens

2413

3142

Total Solutions = 2

=== Code Execution Successful ===

11. Use Backtracking strategy to solve 0/1 Knapsack problem.
/* knapsack problem using backtracking*/

/* Variable Description….

n – Total no. of items available

w[] – Weight of each item

p[] – Profit of each item

m – Maximum Capacity of the Sack

unit[] – Profit of each item per Unit p[]/w[]

x[] – Final list of items put into the Sack

y[] – Intermediate list of selected items

fp – Final Profit

fw – Final Weight

cp – Current Profit

cw – Current Weight

*/

#include <stdio.h>

#include <conio.h>

#define max 10

int w[max],i,j,p[max];

int n,m;

float unit[max];

int y[max],x[max],fp=-1,fw;

void get()

//Advertisement

printf(“\n Enter total number of items: “);

scanf(“%d”,&n);
printf(“\n Enter the Maximum capacity of the Sack: “);

scanf(“%d”,&m);

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

printf(“\n Enter the weight of the item # %d : “,i+1);

scanf(“%d”,&w[i]);

printf(“\n Enter the profit of the item # %d : “, i+1);

scanf(“%d”, &p[i]);

void show()

float s=0.0;

printf(“\n\tItem\tWeight\tCost\tUnit Profit\tSelected “);

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

printf(“\n\t%d\t%d\t%d\t%f\t%d”,i+1,w[i],p[i],unit[i],x[i]);

printf(“\n\n The Sack now holds following items : “);

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

if(x[i]==1)

printf(“%d\t”,i+1);

s += (float) p[i] * (float) x[i];

printf(“\n Maximum Profit: %f “,s);

/*Arrange the item based on high profit per Unit*/

void sort()

int t,t1;
float t2;

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

unit[i] = (float) p[i] / (float) w[i];

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

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

if(unit[i] < unit[j])

t2 = unit[i];

unit[i] = unit[j];

unit[j] = t2;

t = p[i];

p[i] = p[j];

Advertisement

p[j] = t;

t1 = w[i];

w[i] = w[j];

w[j] =t1;

float bound(float cp,float cw,int k)

float b = cp;

float c = cw;

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

{
c = c+w[i];

if( c < m)

b = b +p[i];

else

return (b+(1-(c-m)/ (float)w[i])*p[i]);

return b;

void knapsack(int k,float cp,float cw)

if(cw+w[k] <= m)

y[k] = 1;

if(k <= n)

knapsack(k+1,cp+p[k],cw+w[k]);

if(((cp+p[k]) > fp) && ( k == n))

fp = cp+p[k];

fw = cw+w[k];

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

x[j] = y[j];

if(bound(cp,cw,k) >= fp)

y[k] = 0;

if( k <= n)

knapsack(k+1,cp,cw);

if((cp > fp) && (k == n))

{

fp = cp;

Advertisement

fw = cw;

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

x[j] = y[j];

void main()

clrscr();

printf(“\n\n\n\t\t ******** KNAPSACK PROBLEM ********”);

printf(“\n\t\t —————————————–“);

get();

printf(“\n The Sack is arranged in the order…\n”);

sort();

knapsack(0,0.0,0.0);

show();

getch();

Output:

******** KNAPSACK PROBLEM ********

——————————————-

Enter total number of items: 3

Enter the Maximum capacity of the Sack: 25

Enter the weight of the item # 1 : 1

Enter the profit of the item # 1 : 11

Enter the weight of the item # 2 : 11

Enter the profit of the item # 2 : 21

Enter the weight of the item # 3 : 21

Enter the profit of the item # 3 : 31

The Sack is arranged in the order…

Item Weight Cost Unit Profit Selected

1 1 11 11.000000 1

2 11 21 1.909091 0

3 21 31 1.476190 1

The Sack now holds following items : 1 3

Maximum Profit: 42.000000

12. Implement Travelling Sales Person problem using Branch and Bound
approach.

*Branch and Bound Algorithm for Travelling Sales Person*/

#include<stdio.h>

#include<conio.h>

int a[10][10], visited[10], n, cost = 0;

void get() {

int i, j;

printf("Enter No. of Cities: ");

scanf("%d", &n);

printf("\nEnter Cost Matrix: \n");

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

printf("\n Enter Elements of Row# : %d\n", i + 1);

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

scanf("%d", &a[i][j]);

visited[i] = 0;

printf("\n\nThe cost list is:\n\n");

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

printf("\n\n");

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

printf("\t % d", a[i][j]);

void mincost(int city) {

int i, ncity;

visited[city] = 1;

printf("%d –>", city + 1);

ncity = least(city);

if (ncity == 999) {

ncity = 0;

printf("%d", ncity + 1);

cost += a[city][ncity];

return;

mincost(ncity);

int least(int c) {

int i, nc = 999;

int min = 999, kmin;

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

if ((a[c][i] != 0) && (visited[i] == 0))

if (a[c][i] < min) {

min = a[i][0] + a[c][i];

kmin = a[c][i];

nc = i;

if (min != 999)

cost += kmin;

return nc;

void put() {

printf("\n\nMinimum cost:");

printf("%d", cost);

void main() {

get();

printf("\n\nThe Path is:\n\n");

mincost(0);

put();
}

Output:

$ gcc TSPBranchBound.c

$ ./a.out

Enter No. of Cities: 6

Enter Cost Matrix:

99 10 15 20 99 8

5 99 9 10 8 99

6 13 99 12 99 5

8 8 9 99 6 99

99 10 99 6 99 99

10 99 5 99 99 99

Enter Elements of Row# : 1

Enter Elements of Row# : 2

Enter Elements of Row# : 3

Enter Elements of Row# : 4

Enter Elements of Row# : 5

Enter Elements of Row# : 6

The Path is:

1 –>6 –>3 –>4 –>5 –>2 –>1

Minimum cost:46