NAME – JAINENDRA YADAV

ROLL NO. - 2001920140060

KCA253:DATA STRUCTURES & ANALYSIS OF

ALGORITHMS LAB

1.ANS :-

#include <stdio.h>

int main()
{
int m,n,c,d,k,i,j, first[10][10], second[10][10],
sum[10][10],mul[10][10];
printf("Enter the number of rows and columns of
matrix\n");
scanf("%d%d", & m, & n);
printf("Enter the elements of first matrix\n");
for (c = 0; c < m; c++)
for (d = 0; d < n; d++) scanf("%d", & first[c][d]);
printf("Enter the elements of second matrix\n");
for (c = 0; c < m; c++)
for (d = 0; d < n; d++) scanf("%d", & second[c][d]);
printf("Sum of entered matrices:-\n");
for (c = 0; c < m; c++)
{
for (d = 0; d < n; d++)
{
sum[c][d] = first[c][d] + second[c][d];
printf("%d\t", sum[c][d]);
}
printf("\n");
}
printf("multiply of the matrix=\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
 {
mul[i][j]=0;
for(k=0;k<n;k++)
{
mul[i][j]+=first[i][k]*second[k][j];
}
}
}
//for printing result
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",mul[i][j]);
}
printf("\n");
}

return 0;
}
OUTPUT :-
2.ANS :-

#include <stdio.h>

int main()
{
int a[10][10], transpose[10][10], r, c;
printf("Enter rows and columns: ");
scanf("%d %d", &r, &c);

// asssigning elements to the matrix

printf("\nEnter matrix elements:\n");
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
printf("Enter element a%d%d: ", i + 1, j + 1);
scanf("%d", &a[i][j]);
}
}
// printing the matrix a[][]
printf("\nEntered matrix: \n");
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
printf("%d ", a[i][j]);
}
printf("\n");
}

// computing the transpose

for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j) {
transpose[j][i] = a[i][j];
}

// printing the transpose

printf("\nTranspose of the matrix:\n");
 for (int i = 0; i < c; ++i)
for (int j = 0; j < r; ++j) {
printf("%d ", transpose[i][j]);
if (j == r - 1)
printf("\n");
}
return 0;
}

OUTPUT : -
3.ANS : -

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

#define MAX 10

int STACK[MAX],TOP;
/* display stack element*/
void display(int []);

/* push (insert) item into stack*/

void PUSH(int [],int);

/* pop (remove) item from stack*/

void POP (int []);

void main()
{
int ITEM=0;
int choice=0;
TOP=-1;

while(1)
{
/clrscr();/
printf("\nEnter Choice\n");
printf("1: display\n");
printf("2: insert (PUSH)\n");
printf("3: remove(POP)\n");
printf("4: Exit..:\n");
scanf("%d",&choice);

switch(choice)
{
case 1:
display(STACK);
break;
case 2:
printf("Enter Item to be insert :");
scanf("%d",&ITEM);
PUSH(STACK,ITEM);
break;
case 3:
POP(STACK);
break;
case 4:
exit(0);
default:
printf("\nInvalid choice.");
break;
 }
getch();
}// end of while(1)

/* function : display(),
to display stack elements.
*/
void display(int stack[])
{
int i=0;
if(TOP==-1)
{
printf("Stack is Empty .\n");
return;
 }

printf("%d <-- TOP ",stack[TOP]);

for(i=TOP-1;i >=0;i--)
{
printf("\n%d",stack[i]);
}
printf("\n\n");
}

/* function : PUSH(),
to push an item into stack.
*/
void PUSH(int stack[],int item)
{
if(TOP==MAX-1)
 {
printf("\nSTACK is FULL CAN't ADD
ITEM\n");
return;
}
TOP++;
stack[TOP]=item;
}

/* function : POP(),
to pop an item from stack.
*/
void POP(int stack[])
{
int deletedItem;
if(TOP==-1)
 {
printf("STACK is EMPTY.\n");
return;
}

deletedItem=stack[TOP];
TOP--;
printf("%d deleted
successfully\n",deletedItem);
return;
}

OUTPUT :-
4.ANS : -

#include <stdio.h>

#define MAX 50

void insert();
void delete();
void display();
int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
 int choice;
while (1)
{
printf("1.Insert element to queue
\n");
printf("2.Delete element from
queue \n");
printf("3.Display all elements of
queue \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
 insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
} /* End of switch */
} /* End of while */
} /* End of main() */

void insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Inset the element in queue :
");
 scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
} /* End of insert() */

void delete()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
}
else
 {
printf("Element deleted from
queue is : %d\n", queue_array[front]);
front = front + 1;
}
} /* End of delete() */

void display()
{
int i;
if (front == - 1)
printf("Queue is empty \n");
else
{
 printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
} /* End of display() */

OUTPUT : -
5.ANS :-
# include<stdio.h>
# define MAX 5

int cqueue_arr[MAX];
int front = -1;
int rear = -1;

/Begin of insert/
void insert(int item)
{
if((front == 0 && rear == MAX-1) ||
(front == rear+1))
{
printf("Queue Overflow \n");
 return;
}
if (front == -1) /*If queue is empty */
{
front = 0;
rear = 0;
}
else
{
if(rear == MAX-1) /*rear is at last
position of queue */
rear = 0;
else
rear = rear+1;
}
 cqueue_arr[rear] = item ;
}
/End of insert/

/Begin of del/
void del()
{
if (front == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is :
%d\n",cqueue_arr[front]);
 if(front == rear) /* queue has only one
element */
{
front = -1;
rear=-1;
}
else
{
if(front == MAX-1)
front = 0;
else
front = front+1;
}
}
/*End of del() */
/Begin of display/
void display()
{
int front_pos = front,rear_pos = rear;
if(front == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
while(front_pos <= rear_pos)
{
 printf("%d
",cqueue_arr[front_pos]);
front_pos++;
}
else
{
while(front_pos <= MAX-1)
{
printf("%d
",cqueue_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
 printf("%d
",cqueue_arr[front_pos]);
front_pos++;
}
}
printf("\n");
}
/End of display/

/Begin of main/
int main()
{
int choice,item;
do
{
 printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");

printf("Enter your choice : ");

scanf("%d",&choice);

switch(choice)
{
case 1 :
printf("Input the element for
insertion in queue : ");
scanf("%d", &item);
 insert(item);
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("Wrong choice\n");
}
}while(choice!=4);
 return 0;
}

OUTPUT : -
6.ANS :-
#include<stdio.h>
#include<stdlib.h>

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

struct node *head = NULL;

void push(int val)

{
//create new node
 struct node *newNode =
malloc(sizeof(struct node));
newNode->data = val;

//make the new node points to the head

node
newNode->next = head;

//make the new node as head node

//so that head will always point the last
inserted data
head = newNode;
}

void pop()
{
 //temp is used to free the head node
struct node *temp;

if(head == NULL)
printf("Stack is Empty\n");
else
{
printf("Poped element = %d\n", head-
>data);

//backup the head node

temp = head;

//make the head node points to the

next node.
 //logically removing the node
head = head->next;

//free the poped element's memory

free(temp);
}
}

//print the linked list

void printList()
{
struct node *temp = head;

//iterate the entire linked list and print

the data
 while(temp != NULL)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
push(10);
push(20);
push(30);
printf("Linked List\n");
printList();
 pop();
printf("After the pop, the new linked
list\n");
printList();
pop();
printf("After the pop, the new linked
list\n");
printList();

return 0;
}

OUTPUT :-
7.ANS :-

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delete();
void display();
void main ()
{
int choice;
while(choice != 4)
{
printf("\n**********Main
Menu**********\n");

printf("\n============================
====================================
=\n");
printf("\n1.insert an
element\n2.Delete an element\n3.Display
the queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",& choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
 display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
struct node *ptr;
int item;
 ptr = (struct node *) malloc (sizeof(struct
node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;
 rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
void delete ()
{
struct node *ptr;
 if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
void display()
{
struct node *ptr;
 ptr = front;
if(front == NULL)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
while(ptr != NULL)
{
printf("\n%d\n",ptr -> data);
ptr = ptr -> next;
}
}
}
OUTPUT : -
8.ANS :-

#include <stdio.h>
#include <stdlib.h>
#define SIZE 40

struct queue {
int items[SIZE];
int front;
int rear;
};

struct queue* createQueue();

void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);

struct node {
int vertex;
struct node* next;
};

struct node* createNode(int);

struct Graph {
int numVertices;
struct node** adjLists;
int* visited;
};

// BFS algorithm
void bfs(struct Graph* graph, int
startVertex) {
struct queue* q = createQueue();

graph->visited[startVertex] = 1;
enqueue(q, startVertex);

while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
 struct node* temp = graph-
>adjLists[currentVertex];

while (temp) {
int adjVertex = temp->vertex;

if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
// Creating a node
struct node* createNode(int v) {
struct node* newNode =
malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

// Creating a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct
Graph));
graph->numVertices = vertices;
 graph->adjLists = malloc(vertices *
sizeof(struct node*));
graph->visited = malloc(vertices *
sizeof(int));

int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}

return graph;
}

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

// Add edge from dest to src

newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}

// Create a queue
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct
queue));
q->front = -1;
q->rear = -1;
return q;
}

// Check if the queue is empty

int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}
// Adding elements into queue
void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}

// Removing elements from queue

int dequeue(struct queue* q) {
 int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
printf("Resetting queue ");
q->front = q->rear = -1;
}
}
return item;
}
// Print the queue
void printQueue(struct queue* q) {
int i = q->front;

if (isEmpty(q)) {
printf("Queue is empty");
} else {
printf("\nQueue contains \n");
for (i = q->front; i < q->rear + 1; i++) {
printf("%d ", q->items[i]);
}
}
}

int main() {
 struct Graph* graph = createGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);

bfs(graph, 0);

return 0;
}
OUTPUT :-

9.ANS :-

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

typedef struct node

{
struct node *next;
int vertex;
}node;
node *G[20];
//heads of linked list
int visited[20];
int n;
void read_graph();
//create adjacency list
void insert(int,int);
//insert an edge (vi,vj) in te adjacency list
void DFS(int);
void main()
{
int i;
read_graph();
//initialised visited to 0

for(i=0;i<n;i++)
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
node *p;
printf("\n%d",i);
p=G[i];
visited[i]=1;
while(p!=NULL)
{
i=p->vertex;

if(!visited[i])
DFS(i);
p=p->next;
}
}
void read_graph()
{
int i,vi,vj,no_of_edges;
 printf("Enter number of vertices:");

scanf("%d",&n);
//initialise G[] with a null

for(i=0;i<n;i++)
{
G[i]=NULL;
//read edges and insert them in G[]

printf("Enter number of edges:");

scanf("%d",&no_of_edges);
for(i=0;i<no_of_edges;i++)
{
printf("Enter an edge(u,v):");
scanf("%d%d",&vi,&vj);
insert(vi,vj);
}
}
}
void insert(int vi,int vj)
{
node *p,*q;

//acquire memory for the new node

q=(node*)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;
//insert the node in the linked list
number vi
 if(G[vi]==NULL)
G[vi]=q;
else
{
//go to end of the linked list
p=G[vi];

while(p->next!=NULL)
p=p->next;
p->next=q;
}
}
OUTPUT :-
10.ANS :-

#include <stdio.h>

int search(int arr[], int n, int x)

{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}

// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);

// Function call
int result = search(arr, n, x);
(result == -1)
? printf("Element is not present in
array")
: printf("Element is present at index
%d", result);
return 0;
}
OUTPUT :-

11.ANS :-

#include <stdio.h>

// A recursive binary search function. It

returns
// location of x in given array arr[l..r] is
present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;

// If the element is present at the

middle
// itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then

// it can only be present in left
subarray
if (arr[mid] > x)
 return binarySearch(arr, l, mid - 1,
x);

// Else the element can only be

present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}

// We reach here when element is not

// present in array
return -1;
}

int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not
present in array")
: printf("Element is present at
index %d",
result);
return 0;
}

OUTPUT :-
12.ANS :-

#include <stdio.h>

void bubbleSort(int arr[], int n)

{
int i, j, temp, flag=0;
for(i = 0; i < n; i++)
{
for(j = 0; j < n-i-1; j++)
{
 // introducing a flag to monitor
swapping
if( arr[j] > arr[j+1])
{
// swap the elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
// if swapping happens update
flag to 1
flag = 1;
}
}
// if value of flag is zero after all the
iterations of inner loop
// then break out
 if(flag==0)
{
break;
}
}

// print the sorted array

printf("Sorted Array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}

int main()
{
int arr[100], i, n, step, temp;
// ask user for number of elements to be
sorted
printf("Enter the number of elements to
be sorted: ");
scanf("%d", &n);
// input elements if the array
for(i = 0; i < n; i++)
{
printf("Enter element no. %d: ", i+1);
scanf("%d", &arr[i]);
}
// call the function bubbleSort
bubbleSort(arr, n);
 return 0;
}

OUTPUT :-

13.ANS :-

#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n)

{
int i, j, min_idx;

// One by one move boundary of

unsorted subarray
for (i = 0; i < n-1; i++)
{
 // Find the minimum element in
unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;

// Swap the found minimum element

with the first element
swap(&arr[min_idx], &arr[i]);
}
}

/* Function to print an array */

void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver program to test above functions

int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
 return 0;
}

OUTPUT :-

14.ANS :-

#include <math.h>
#include <stdio.h>

/* Function to sort an array using insertion

sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

/* Move elements of arr[0..i-1], that

are
greater than key, to one position
ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
 }
arr[j + 1] = key;
}
}

// A utility function to print an array of size

n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);
printArray(arr, n);

return 0;
}

OUTPUT :-
15.ANS :-

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

// Merges two subarrays of arr[].

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
 int n2 = r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[]

*/
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

/* Merge the temp arrays back into

arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
 /* Copy the remaining elements of L[], if
there
are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if

there
are any */
while (j < n2) {
arr[k] = R[j];
j++;
 k++;
}
}

/* l is for left index and r is right index of

the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow
for
// large l and h
int m = l + (r - l) / 2;
 // Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
 printf("\n");
}

/* Driver code */
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

 printArray(arr, arr_size);
return 0;
}

OUTPUT :-

16.ANS : -

#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i
which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])
largest = l;
 // If right child is larger than largest so
far
if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i) {
swap(arr[i], arr[largest]);

// Recursively heapify the affected

sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from

heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);

// call max heapify on the reduced

heap
 heapify(arr, i, 0);
}
}

/* A utility function to print array of size n

*/
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}

// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);

heapSort(arr, n);

cout << "Sorted array is \n";

printArray(arr, n);
}

OUTPUT :-
17.ANS :-

#include<stdio.h>

#include<conio.h>

int main()

int a[2][2],b[2][2],c[2][2],i,j;

int m1,m2,m3,m4,m5,m6,m7;
printf("Enter the 4 elements of first matrix:
");

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

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

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

printf("Enter the 4 elements of second

matrix: ");

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

for(j=0;j<2;j++)
scanf("%d",&b[i][j]);

printf("\nThe first matrix is\n");

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

printf("\n");

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

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

printf("\nThe second matrix is\n");

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

printf("\n");

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

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

m1= (a[0][0] + a[1][1])*(b[0][0]+b[1][1]);

m2= (a[1][0]+a[1][1])*b[0][0];

m3= a[0][0]*(b[0][1]-b[1][1]);

m4= a[1][1]*(b[1][0]-b[0][0]);
m5= (a[0][0]+a[0][1])*b[1][1];

m6= (a[1][0]-a[0][0])*(b[0][0]+b[0][1]);

m7= (a[0][1]-a[1][1])*(b[1][0]+b[1][1]);

c[0][0]=m1+m4-m5+m7;

c[0][1]=m3+m5;

c[1][0]=m2+m4;

c[1][1]=m1-m2+m3+m6;
printf("\nAfter multiplication using \n");

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

printf("\n");

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

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

} return 0;}

OUTPUT :-
18.ANS :-

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// a structure to represent a weighted
edge in graph
struct Edge {
int src, dest, weight;
};

// a structure to represent a connected,

undirected
// and weighted graph
struct Graph {
// V-> Number of vertices, E-> Number
of edges
int V, E;
 // graph is represented as an array of
edges.
// Since the graph is undirected, the
edge
// from src to dest is also edge from dest
// to src. Both are counted as 1 edge
here.
struct Edge* edge;
};

// Creates a graph with V vertices and E

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

graph->edge = (struct
Edge*)malloc(sizeof( struct Edge)*E);

return graph;
}

// A structure to represent a subset for

union-find
struct subset {
int parent;
int rank;
};
// A utility function to find set of an
element i
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
// find root and make root as parent of i
// (path compression)
if (subsets[i].parent != i)
subsets[i].parent
= find(subsets, subsets[i].parent);

return subsets[i].parent;
}
// A function that does union of two sets
of x and y
// (uses union by rank)
void Union(struct subset subsets[], int x,
int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);

// Attach smaller rank tree under root of

high
// rank tree (Union by Rank)
if (subsets[xroot].rank <
subsets[yroot].rank)
subsets[xroot].parent = yroot;
 else if (subsets[xroot].rank >
subsets[yroot].rank)
subsets[yroot].parent = xroot;

// If ranks are same, then make one as

root and
// increment its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}

// Compare two edges according to their

weights.
// Used in qsort() for sorting an array of
edges
int myComp(const void* a, const void* b)
{
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
}

// The main function to construct MST

using Kruskal's
// algorithm
void KruskalMST(struct Graph* graph)
{
int V = graph->V;
 struct Edge
result[V]; // Tnis will store the
resultant MST
int e = 0; // An index variable, used for
result[]
int i = 0; // An index variable, used for
sorted edges

// Step 1: Sort all the edges in non-

decreasing
// order of their weight. If we are not
allowed to
// change the given graph, we can create
a copy of
// array of edges
 qsort(graph->edge, graph->E,
sizeof(graph->edge[0]),
myComp);

// Allocate memory for creating V

ssubsets
struct subset* subsets
= (struct subset*)malloc(V *
sizeof(struct subset));

// Create V subsets with single elements

for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
 // Number of edges to be taken is equal
to V-1
while (e < V - 1 && i < graph->E) {
// Step 2: Pick the smallest edge. And
increment
// the index for next iteration
struct Edge next_edge = graph-
>edge[i++];

int x = find(subsets, next_edge.src);

int y = find(subsets, next_edge.dest);

// If including this edge does't cause

cycle,
// include it in result and increment
the index
 // of result for next edge
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}

// print the contents of result[] to

display the
// built MST
printf(
"Following are the edges in the
constructed MST\n");
int minimumCost = 0;
 for (i = 0; i < e; ++i)
{
printf("%d -- %d == %d\n",
result[i].src,
result[i].dest, result[i].weight);
minimumCost += result[i].weight;
}
printf("Minimum Cost Spanning tree :
%d",minimumCost);
return;
}

// Driver program to test above functions

int main()
{
 /* Let us create following weighted
graph
10
0--------1
|\ |
6| 5\ |15
| \|
2--------3
4 */
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
struct Graph* graph = createGraph(V, E);

// add edge 0-1

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

// add edge 0-2

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

// add edge 0-3

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

// add edge 1-3

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

// add edge 2-3

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

KruskalMST(graph);

return 0;
}

OUTPUT : -
19.ANS :-

(a): - Insert at end

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = NULL;

struct node *temp = head;

while(temp->next != NULL){
temp = temp->next;
}

temp->next = newNode;

(b) :- Insert at mid

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;

struct node *temp = head;

for(int i=2; i < position; i++) {

if(temp->next != NULL) {
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;

(c) :- Insert at begin

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = head;
head = newNode;

(d) : - Delete at end

struct node* temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
temp->next = NULL;

(e) :- Delete at mid

for(int i=2; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}

temp->next = temp->next->next;

(f) : - Delete at begin

head = head->next;
(g) :- Traverse

struct node *temp = head;

printf("\n\nList elements are - \n");
while(temp != NULL) {
printf("%d --->",temp->data);
temp = temp->next;
}
OUTPUT :-

20.ANS :-
#include <bits/stdc++.h>
using namespace std;
// Structure for the elements in the
// priority queue
struct item {
int value;
int priority;
};

// Store the element of a priority queue

item pr[100000];

// Pointer to the last index

int size = -1;

// Function to insert a new element

// into priority queue
void enqueue(int value, int priority)
{
// Increase the size
size++;

// Insert the element

pr[size].value = value;
pr[size].priority = priority;
}

// Function to check the top element

int peek()
{
int highestPriority = INT_MIN;
int ind = -1;

// Check for the element with

// highest priority
for (int i = 0; i <= size; i++) {

// If priority is same choose

// the element with the
// highest value
if (highestPriority
== pr[i].priority
&& ind > -1
&& pr[ind].value
> pr[i].value) {
highestPriority = pr[i].priority;
 ind = i;
}
else if (highestPriority
< pr[i].priority) {
highestPriority = pr[i].priority;
ind = i;
}
}

// Return position of the element

return ind;
}

// Function to remove the element with

// the highest priority
void dequeue()
{
// Find the position of the element
// with highest priority
int ind = peek();

// Shift the element one index before

// from the position of the element
// with highest priortity is found
for (int i = ind; i < size; i++) {
pr[i] = pr[i + 1];
}

// Decrease the size of the

// priority queue by one
 size--;
}

// Driver Code
int main()
{
// Function Call to insert elements
// as per the priority
enqueue(10, 2);
enqueue(14, 2);
enqueue(16, 4);
enqueue(12, 3);

// Stores the top element

// at the moment
 int ind = peek();

cout << pr[ind].value << endl;

// Dequeue the top element

dequeue();

// Check the top element

ind = peek();
cout << pr[ind].value << endl;

return 0;
}

OUTPUT :-
21.ANS :-

#include <bits/stdc++.h>
using namespace std;

// Hash table size

#define TABLE_SIZE 13

// Used in second hash function.

#define PRIME 7

class DoubleHash {
 // Pointer to an array containing
buckets
int* hashTable;
int curr_size;

public:
// function to check if hash table is full
bool isFull()
{

// if hash size reaches maximum size

return (curr_size == TABLE_SIZE);
}

// function to calculate first hash

int hash1(int key)
{
return (key % TABLE_SIZE);
}

// function to calculate second hash

int hash2(int key)
{
return (PRIME - (key % PRIME));
}

DoubleHash()
{
hashTable = new int[TABLE_SIZE];
curr_size = 0;
 for (int i = 0; i < TABLE_SIZE; i++)
hashTable[i] = -1;
}

// function to insert key into hash table

void insertHash(int key)
{
// if hash table is full
if (isFull())
return;

// get index from first hash

int index = hash1(key);

// if collision occurs
 if (hashTable[index] != -1) {
// get index2 from second hash
int index2 = hash2(key);
int i = 1;
while (1) {
// get newIndex
int newIndex = (index + i *
index2) % TABLE_SIZE;

// if no collision occurs, store

// the key
if (hashTable[newIndex] == -1) {
hashTable[newIndex] = key;
break;
}
 i++;
}
}

// if no collision occurs
else
hashTable[index] = key;
curr_size++;
}

// function to search key in hash table

void search(int key)
{
int index1 = hash1(key);
int index2 = hash2(key);
 int i = 0;
while (hashTable[(index1 + i *
index2) % TABLE_SIZE] != key) {
if (hashTable[(index1 + i * index2)
% TABLE_SIZE] == -1) {
cout << key << " does not exist"
<< endl;
return;
}
i++;
}
cout << key << " found" << endl;
}

// function to display the hash table

void displayHash()
 {
for (int i = 0; i < TABLE_SIZE; i++) {
if (hashTable[i] != -1)
cout << i << " --> "
<< hashTable[i] << endl;
else
cout << i << endl;
}
}
};

// Driver's code
int main()
{
int a[] = { 19, 27, 36, 10, 64 };
 int n = sizeof(a) / sizeof(a[0]);

// inserting keys into hash table

DoubleHash h;
for (int i = 0; i < n; i++) {
h.insertHash(a[i]);
}
// searching some keys
h.search(36); // This key is present in
hash table
h.search(100); // This key does not
exist in hash table
// display the hash Table
h.displayHash();
return 0;
}

OUTPUT : -