WEEK 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.

// Including necessary header files

#include <stdio.h>

#include <stdlib.h>

// Structure for a tree node

struct TreeNode {

int data;

struct TreeNode* left;

struct TreeNode* right;

int height; // Height of the node

};

// Function to get the height of a node

int height(struct TreeNode* node) {

if (node == NULL)

return 0;

return node->height;

// Function to get the maximum of two integers

int max(int a, int b) {

return (a > b) ? a : b;
}

// Function to create a new node with a given key

struct TreeNode* createNode(int key) {

struct TreeNode* newNode =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

return newNode;

// Function to right rotate subtree rooted with y

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;

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

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)

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

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

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

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;

Output:

[?2004l

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 1

Enter the key to insert: 20

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit
Enter your choice: 1

Enter the key to insert: 11

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 1

Enter the key to insert: 5

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 1

Enter the key to insert: 32

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 1

Enter the key to insert: 40

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 1

Enter the key to insert: 2

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 1

Enter the key to insert: 4

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 3

In-order Traversal: 2 4 5 11 20 32 40
AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 2

Enter the key to delete: 2

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 3

In-order Traversal: 4 5 11 20 32 40

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 2

Enter the key to delete: 4

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 3

In-order Traversal: 5 11 20 32 40

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 2

Enter the key to delete: 32

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 3

In-order Traversal: 5 11 20 40

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 2

Enter the key to delete: 11

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice: 3

In-order Traversal: 5 20 40

AVL Tree Operations:

1. Insert a node

2. Delete a node

3. In-order Traversal

4. Exit

Enter your choice:4

Exiting...

Week 2

2.Construct B-Tree an order of 5 with a set of 100 random elements stored in array. Implement
searching, insertion and deletion operations.
#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <conio.h>

#define M 4 // Maximum degree of the B-tree

struct BTreeNode

int num_keys; // Number of keys currently in the node

int keys[M-1]; // Array of keys

struct BTreeNode *children[M]; // Array of child pointers

bool is_leaf; // True if node is a leaf

};

// Function to create a new node

struct BTreeNode *createNode(bool is_leaf)

int i;

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

if (newNode == NULL)

perror("Memory allocation failed");

exit(EXIT_FAILURE);

newNode->num_keys = 0;

newNode->is_leaf = is_leaf;
 for (i = 0; i < M; i++) {

newNode->children[i] = NULL;

return newNode;

// Function to split a full child node

void splitChild(struct BTreeNode *parent, int index)

int i;

struct BTreeNode *child = parent->children[index];

struct BTreeNode *newNode = createNode(child->is_leaf);

newNode->num_keys = M/2 - 1;

// Move keys and children to the new node

for ( i = 0; i < M/2 - 1; i++) {

newNode->keys[i] = child->keys[i + M/2];

if (!child->is_leaf)

for (i = 0; i < M/2; i++)

newNode->children[i] = child->children[i + M/2];

child->num_keys = M/2 - 1;

// Shift parent's children to make space for the new node

 for ( i = parent->num_keys; i > index; i--)

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

parent->children[index + 1] = newNode;

// Shift parent's keys to insert the middle key from the child

for ( i = parent->num_keys - 1; i >= index; i--)

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

parent->keys[index] = child->keys[M/2 - 1];

parent->num_keys++;

// Function to insert a key into a non-full node

void insertNonFull(struct BTreeNode *node, int key)

int i = node->num_keys - 1;

if (node->is_leaf)

// Insert key into the sorted order

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

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

i--;

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

node->num_keys++;

else

// Find the child to insert the key

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

i--;

i++;

if (node->children[i]->num_keys == M - 1)

// Split child if it's full

splitChild(node, i);

// Determine which of the two children is the new one

if (node->keys[i] < key)

i++;

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

// Function to insert a key into the B-tree

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

struct BTreeNode *node = *root;

if (node == NULL)

// Create a new root node

*root = createNode(true);

(*root)->keys[0] = key;

(*root)->num_keys = 1;

else

if (node->num_keys == M - 1)

// Split the root if it's full

struct BTreeNode *new_root = createNode(false);

new_root->children[0] = node;

splitChild(new_root, 0);

*root = new_root;

insertNonFull(*root, key);

// Function to traverse and print the B-tree in-order

void traverse(struct BTreeNode *root)

{

if (root != NULL)

int i;

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

traverse(root->children[i]);

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

traverse(root->children[i]);

// Main function to test B-tree implementation

int main()

struct BTreeNode *root = NULL;

insert(&root, 10);

insert(&root, 20);

insert(&root, 5);

insert(&root, 6);

insert(&root, 12);

insert(&root, 30);

printf("In-order traversal of the B-tree: ");

traverse(root);

printf("\n");
 getch();

return 0;

OUTPUT:

Program 3:

Write a C program to Construct Min and Max Heap using arrays, delete any
element and display the content of the Heap.

#include <stdio.h>

#define MAX 100

int size = 0;

// Swap two elements

void swap(int *a, int *b)

int temp = *a;

*a = *b;

*b = temp;

// Insert an element into the Min Heap

void insertMinHeap(int heap[], int element)

heap[size] = element;

int current = size;

 while (current > 0 && heap[current] < heap[(current - 1) / 2])

swap(&heap[current], &heap[(current - 1) / 2]);

current = (current - 1) / 2;

size++;

// Insert an element into the Max Heap

void insertMaxHeap(int heap[], int element)

heap[size] = element;

int current = size;

while (current > 0 && heap[current] > heap[(current - 1) / 2])

swap(&heap[current], &heap[(current - 1) / 2]);

current = (current - 1) / 2;

size++;

// Heapify for Min Heap

void heapifyMin(int heap[], int i)

int smallest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;
 if (left < size && heap[left] < heap[smallest])

smallest = left;

if (right < size && heap[right] < heap[smallest])

smallest = right;

if (smallest != i)

swap(&heap[i], &heap[smallest]);

heapifyMin(heap, smallest);

// Heapify for Max Heap

void heapifyMax(int heap[], int i)

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < size && heap[left] > heap[largest])

largest = left;

if (right < size && heap[right] > heap[largest])

largest = right;
 if (largest != i)

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

heapifyMax(heap, largest);

// Delete element from Min Heap

void deleteMinHeap(int heap[], int element)

int i;

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

if (heap[i] == element)

break;

if (i < size)

swap(&heap[i], &heap[size - 1]);

size--;

heapifyMin(heap, i);

}
}

// Delete element from Max Heap

void deleteMaxHeap(int heap[], int element)

int i;

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

if (heap[i] == element)

break;

if (i < size)

swap(&heap[i], &heap[size - 1]);

size--;

heapifyMax(heap, i);

// Display the heap

void displayHeap(int heap[])

int i;

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

 {

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

printf("\n");

int main()

int minHeap[MAX], maxHeap[MAX];

int choice, element, heapType;

while (1)

printf("\n1. Insert into Min Heap\n2. Insert into Max Heap\n3. Delete from Min Heap\n4. Delete
from Max Heap\n5. Display Min Heap\n6. Display Max Heap\n7. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice)

case 1:

printf("Enter element to insert into Min Heap: ");

scanf("%d", &element);

insertMinHeap(minHeap, element);

break;

case 2:

printf("Enter element to insert into Max Heap: ");

scanf("%d", &element);

insertMaxHeap(maxHeap, element);
 break;

case 3:

printf("Enter element to delete from Min Heap: ");

scanf("%d", &element);

deleteMinHeap(minHeap, element);

break;

case 4:

printf("Enter element to delete from Max Heap: ");

scanf("%d", &element);

deleteMaxHeap(maxHeap, element);

break;

case 5:

printf("Min Heap: ");

displayHeap(minHeap);

break;

case 6:

printf("Max Heap: ");

displayHeap(maxHeap);

break;

case 7:

return 0;

default:

printf("Invalid choice!\n");

}
 return 0;

OUTPUT:
WEEK 4
Write a C Program to Implement BFT and DFT forgiven graph, when graph is represented by
a) Adjacency Matrix b) Adjacency Lists
#include <stdio.h>

#include <stdlib.h>

#define MAX 100

int adjMatrix[MAX][MAX];

int visited[MAX];

int queue[MAX], front = -1, rear = -1;

// Enqueue operation for BFS

void enqueue(int vertex)

if (rear == MAX - 1)

printf("\nQueue Overflow");

else

if (front == -1)

front = 0;

rear = rear + 1;

queue[rear] = vertex;

// Dequeue operation for BFS

int dequeue()

int vertex;

if (front == -1 || front > rear)

printf("\nQueue Underflow");
 return -1;

else

vertex = queue[front];

front = front + 1;

return vertex;

// Breadth-First Traversal using Adjacency Matrix

void BFTMatrix(int n, int startVertex)

int i,vertex;

enqueue(startVertex);

visited[startVertex] = 1;

printf("BFS: ");

while (front <= rear)

vertex = dequeue();

printf("%d ", vertex);

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

if (adjMatrix[vertex][i] == 1 && !visited[i])

enqueue(i);

visited[i] = 1;

}
 }

printf("\n");

// Depth-First Traversal using Adjacency Matrix

void DFTMatrix(int n, int vertex)

int i;

printf("%d ", vertex);

visited[vertex] = 1;

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

if (adjMatrix[vertex][i] == 1 && !visited[i])

DFTMatrix(n, i);

int main()

int n, i, j, startVertex;

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

scanf("%d", &n);

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

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

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

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

printf("Enter the start vertex: ");

scanf("%d", &startVertex);

// BFS

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

visited[i] = 0; // Reset visited array

BFTMatrix(n, startVertex);

// DFS

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

visited[i] = 0; // Reset visited array

printf("DFS: ");

DFTMatrix(n, startVertex);

printf("\n");

scanf("%d",&n);

return 0;

OUTPUT
WEEK 6
Program 1:
Write a c program to implement Quick sort and Merge sort and observe the execution time for
various input sizes (Average, Worst and Best cases).

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define MAX_SIZE 100000 // Maximum array size

// Function to swap two elements

void swap(int* a, int* b)

int temp = *a;

*a = *b;

*b = temp;

// Partition function for QuickSort

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

int pivot = arr[high]; // Pivot element (last element)

int j,i = low - 1;

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

{
 if (arr[j] < pivot)

i++;

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

swap(&arr[i + 1], &arr[high]);

return i + 1;

// QuickSort function

void quickSort(int arr[], int low, int high)

if (low < high)

int pi = partition(arr, low, high); // Partition index

quickSort(arr, low, pi - 1); // Recursively sort the left half

quickSort(arr, pi + 1, high); // Recursively sort the right half

// Function to generate an array with random elements

void generateRandomArray(int arr[], int n)

{
 int i;

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

arr[i] = rand() % n; // Random elements from 0 to n-1

// Function to generate a sorted array (Best case)

void generateSortedArray(int arr[], int n)

int i;

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

arr[i] = i;

// Function to generate a reverse sorted array (Worst case)

void generateReverseSortedArray(int arr[], int n)

int i;

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

arr[i] = n - i;

}
}

// Function to measure execution time for QuickSort

void measureExecutionTime(void (*generateArray)(int[], int), int arr[], int n, const char* caseType)

clock_t start, end;

double cpu_time_used;

generateArray(arr, n); // Generate array based on the case

start = clock(); // Start time

quickSort(arr, 0, n - 1);

end = clock(); // End time

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

printf("%s Case for size %d: %f seconds\n", caseType, n, cpu_time_used);

// Driver function

int main()

int n[] = {10000, 50000, 100000}; // Different input sizes

int i,arr[MAX_SIZE];
 printf("Measuring execution time of Quick Sort:\n\n");

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

printf("Input Size: %d\n", n[i]);

// Average Case: Random Array

measureExecutionTime(generateRandomArray, arr, n[i], "Average");

// Best Case: Sorted Array

measureExecutionTime(generateSortedArray, arr, n[i], "Best");

// Worst Case: Reverse Sorted Array

measureExecutionTime(generateReverseSortedArray, arr, n[i], "Worst");

printf("\n");

return 0;

OUTPUT:
MERGE SORT:
#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void merge(int arr[], int l, int m, int r)

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

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

k++;

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

void generateBestCase(int arr[], int n)

int i;

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

 {

arr[i] = i;

void generateWorstCase(int arr[], int n)

int i;

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

arr[i] = n - i;

void generateAverageCase(int arr[], int n)

int i;

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

arr[i] = rand() % n;

void printArray(int arr[], int n)

{
 int i;

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

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

printf("\n");

double measureExecutionTime(void (*generateCase)(int[], int), int arr[], int n)

clock_t start, end;

generateCase(arr, n);

start = clock();

mergeSort(arr, 0, n - 1);

end = clock();

return ((double)(end - start)) / CLOCKS_PER_SEC;

int main()

int n;

printf("Enter the size of the array: ");

scanf("%d", &n);

int* arr = (int*)malloc(n * sizeof(int));

 double bestTime = measureExecutionTime(generateBestCase, arr, n);

printf("Best Case Time: %f seconds\n", bestTime);

double worstTime = measureExecutionTime(generateWorstCase, arr, n);

printf("Worst Case Time: %f seconds\n", worstTime);

double avgTime = measureExecutionTime(generateAverageCase, arr, n);

printf("Average Case Time: %f seconds\n", avgTime);

free(arr);

getch();

return 0;

Week 7

Compare the performance of Single Source Shortest Paths using Greedy method when the graph
is represented by adjacency matrix and adjacency lists.

#include <stdio.h>

// defining some constants

#define INF 9999
#define MAX 10

// prototyping of the function

void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start);
// defining the function for Dijkstra's Algorithm
void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start)
{
int cost[MAX][MAX], distance[MAX], previous[MAX];
int visited_nodes[MAX], counter, minimum_distance, next_node, i, j;

// creating cost matrix

for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
if (Graph[i][j] == 0)
cost[i][j] = INF;
else
cost[i][j] = Graph[i][j];

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

{
distance[i] = cost[start][i];
previous[i] = start;
visited_nodes[i] = 0;
}

distance[start] = 0;
visited_nodes[start] = 1;
counter = 1;

while (counter < size - 1)

{
minimum_distance = INF;

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

if (distance[i] < minimum_distance && !visited_nodes[i])
{
minimum_distance = distance[i];
next_node = i;
}

visited_nodes[next_node] = 1;
for (i = 0; i < size; i++)
if (!visited_nodes[i])
if (minimum_distance + cost[next_node][i] < distance[i])
{
distance[i] = minimum_distance + cost[next_node][i];
previous[i] = next_node;
}
counter++;
}
 // printing the distance
for (i = 0; i < size; i++)
if (i != start)
{
printf("\nDistance from the Source Node to %d: %d", i, distance[i]);
}
}

// main function
int main()
{

int Graph[MAX][MAX], i, j, size, source;

size = 7;

// declaring the nodes of graph

Graph[0][0] = 0;
Graph[0][1] = 4;
Graph[0][2] = 0;
Graph[0][3] = 0;
Graph[0][4] = 0;
Graph[0][5] = 8;
Graph[0][6] = 0;

Graph[1][0] = 4;
Graph[1][1] = 0;
Graph[1][2] = 8;
Graph[1][3] = 0;
Graph[1][4] = 0;
Graph[1][5] = 11;
Graph[1][6] = 0;

Graph[2][0] = 0;
Graph[2][1] = 8;
Graph[2][2] = 0;
Graph[2][3] = 7;
Graph[2][4] = 0;
Graph[2][5] = 4;
Graph[2][6] = 0;

Graph[3][0] = 0;
Graph[3][1] = 0;
Graph[3][2] = 7;
Graph[3][3] = 0;
Graph[3][4] = 9;
Graph[3][5] = 14;
Graph[3][6] = 0;
 Graph[4][0] = 0;
Graph[4][1] = 0;
Graph[4][2] = 0;
Graph[4][3] = 9;
Graph[4][4] = 0;
Graph[4][5] = 10;
Graph[4][6] = 2;

Graph[5][0] = 0;
Graph[5][1] = 0;
Graph[5][2] = 4;
Graph[5][3] = 14;
Graph[5][4] = 10;
Graph[5][5] = 0;
Graph[5][6] = 2;

Graph[6][0] = 0;
Graph[6][1] = 0;
Graph[6][2] = 0;
Graph[6][3] = 0;
Graph[6][4] = 2;
Graph[6][5] = 0;
Graph[6][6] = 1;

source = 0;
// calling the DijkstraAlgorithm() function by passing the Graph, the number of nodes and the source
node
DijkstraAlgorithm(Graph, size, source);
getch();
return 0;
}

OUTPUT:
Week 8

write a c program to Implement Job sequencing with deadlines using Greedy

strategy.

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

// A structure to represent a Jobs

typedef struct Jobs
{
char id; // Jobs Id
int dead; // Deadline of Jobs
int profit; // Profit if Jobs is over before or on deadline
} Jobs;

// This function is used for sorting all Jobss according to

// profit
int compare(const void* a, const void* b)
{
Jobs* temp1 = (Jobs*)a;
Jobs* temp2 = (Jobs*)b;
return (temp2->profit - temp1->profit);
}

// Find minimum between two numbers.

int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
int main()
{
int i,j;
Jobs arr[] =
{
 { 'a', 2, 100 },
{ 'b', 2, 20 },
{ 'c', 1, 40 },
{ 'd', 3, 35 },
{ 'e', 1, 25 }
};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Following is maximum profit sequence of Jobs: \n");
qsort(arr, n, sizeof(Jobs), compare);
int result[n]; // To store result sequence of Jobs
bool slot[n]; // To keep track of free time slots

// Initialize all slots to be free

for (i = 0; i < n; i++)
slot[i] = false;

// Iterate through all given Jobs

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

// Find a free slot for this Job

for ( j = min(n, arr[i].dead) - 1; j >= 0; j--)
{

// Free slot found

if (slot[j] == false)
{
result[j] = i;
slot[j] = true;
break;
}
}
}
for ( i = 0; i < n; i++)
if (slot[i])
printf("%c ", arr[result[i]].id);
getch();
return 0;
}
Week 9

Write a c 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));

getch();

return 0;

}
OUTPUT: