V.S.B.

ENGINEERING COLLEGE
(An Autonomous Institution)
KARUDAYAMPALAYAM, KARUR – 639 111.

RECORD NOTE BOOK

Name :

Reg. No. :

Subject :

Semester :

1
 V.S.B. ENGINEERING COLLEGE
(An Autonomous Institution)
KARUDAYAMPALAYAM, KARUR – 639 111.

RECORD
NAME: CLASS:

REGISTER NO.

ROLL NO.

Certified that this is a bonafide record of work done by the

above student during the year 20 - 20

Date: Lab in-charge Head of the Department

Submitted for the “END SEMESTER PRACTICAL EXAMINATION”

held on ……………………………….

Internal Examiner External Examiner

2
 CONTENTS
Page Marks
Sl.No. Date Name of Experiment Sign.
No. Award

3
 CONTENTS
Page Marks
Sl.No. Date Name of Experiment Sign.
No. Award

4
 CO,PO,PSO MAPPING

CO PO PSO
S.No Name of the Experiment Mapping
Mapping Mapping
1 Implement Linear Search. Determine the time required to CO1
search for an element. Repeat the experiment for different 1,2,3,4,9,
1,2,3
values of n, the number of elements in the list to 10,11,12
be searched and plot a graph of the time taken versus n.
2 Implement recursive Binary Search. Determine the time CO1
required to search an element. Repeat the experiment for 1,2,3,4,9,
different values of n, the number of elements in the list to 1,2,3
be searched and plot a graph of the time taken versus n. 10,11,12
3 Given a text txt [0...n-1] and a pattern pat [0...m-1], write a CO1
function search (char pat [ ], char txt [ ]) that prints all 1,2,3,4,9,
occurrences of pat [ ] in txt [ ]. You may assume that n > 1,2,3
10,11,12
m.
4 Sort a given set of elements using the Insertion sort and CO1
Heap sort methods and determine the time required to sort
1,2,3,4,9,
the elements. Repeat the experiment for different values of 1,2,3
n, the number of elements in the list to be 10,11,12
sorted and plot a graph of the time taken versus n.
5 Develop a program to implement graph traversal using CO2 1,2,3,4,5,9,
Breadth First Search 10,11,12 1,2,3
6 Develop a program to implement graph traversal using CO2 1,2,3,4,5,9,
Depth First Search 10,11,12 1,2,3
7 From a given vertex in a weighted connected graph,
CO2 1,2,3,4,5,9,
develop a program to find the shortest paths to other 1,2,3
10,11,12
vertices using Dijkstra’s algorithm.
8 Find the minimum cost spanning tree of a given undirected 1,2,3,4,5,9,
CO2 1,2,3
graph using Prim’s algorithm. 10,11,12
9 Implement Floyd’s algorithm for the All-Pairs- Shortest- CO2 1,2,3,4,5,9,
Paths problem. 10,11,12 1,2,3
10 Compute the transitive closure of a given directed graph 1,2,3,4,5,9,
using Warshall's algorithm. CO2 1,2,3
10,11,12
11 Develop a program to find out the maximum and
CO3 1,2,3,4,5,9,
minimum numbers in a given list of n numbers using the 1,2,3
divide and conquer technique. 10,11,12
12 Implement Merge sort and Quick sort methods to sort an
array of elements and determine the time required to sort. CO3
1,2,3,4,5,9,
Repeat the experiment for different values of n, the 1,2,3
number of elements in the list to be sorted and plot a graph 10,11,12
of the time taken versus n.
13 Implement N Queens problem using Backtracking. 1,2,3,4,9,
CO4 1,2,3
10,11,12
14 Implement any scheme to find the optimal solution for the
Traveling Salesperson problem and then solve the same CO5 1,2,3,4,5,9,
problem instance using any approximation algorithm and 1,2,3
10,11,12
determine the error in the approximation.
15 Implement randomized algorithms for finding the kth 1,2,3,4,5,9,
smallest number. CO5 1,2,3
10,11,12

5
 V.S.B. Engineering College, Karur

(An Autonomous Institution)

Department of Computer Science and Engineering

ACADEMIC YEAR: 2024-2025(Even Semester)
VISION, MISSION, PEOs, POs and PSOs
Vision of the Institution:

We endeavour to impart futuristic technical education of the highest quality to the student
community and to inculcate discipline in them to face the world with self-confidence and thus we
prepare them for life as responsible citizens to uphold human values and to be of service at large.
We strive to bring of the Institution as an Institution of academic excellence of International
standard.

Mission of the Institution:

We transform persons into personalities by the state-of the art infrastructure, time consciousness,
quick response and the best academic practices through assessment and advice.

Vision of the Department:

• To produce competent Computer Science Engineers through Quality Education and

Research.

Mission of the Department:

The Department strives to contribute to the expansion of knowledge in the discipline of Computer
Science and Engineering by,
• adopting an efficient teaching learning process in correlation with industrial needs.
• ensuring technical proficiency, facilitating to pursue higher studies and carry out
R&D activities.
• developing problem solving and analytical skills with sound knowledge in basic
sciences and Computer Science Engineering.
• inculcating managerial skills to become socially responsible, ethical and competitive
professionals.

6
 Programme Educational Objectives (PEOs)

The Graduates of Computer Science and Engineering are able to

• PEO #1: Work in Multinational companies and become successful IT professionals.
• PEO#2: Pursue higher studies and have their career in educational institutions
research organizations, or be entrepreneurs.
• PEO #3: Possess social responsibility, team work skills, leadership capabilities and
urge for learning in their professional fields.
Program Outcomes (PO)
PO 1: Engineering knowledge
Apply the knowledge of mathematics, science, engineering fundamentals, and an engineering
specialization to the solution of complex engineering problems.
PO2: Problem analysis
Identify, formulate, research literature, and analyze complex engineering problems reaching
substantiated conclusions using first principles of mathematics, natural sciences, and engineering
sciences.
PO3: Design/development of solutions
Design solutions for complex engineering problems and design system components or processes
that meet the specified needs with appropriate consideration for the public health and safety, and the
cultural, societal, and environmental considerations.
PO4: Conduct investigations of complex problems
Use research-based knowledge and research methods including design of experiments, analysis and
interpretation of data, and synthesis of the information to provide valid conclusions.
PO5: Modern tool usage
Create, select, and apply appropriate techniques, resources, and modern engineering and IT tools
including prediction and modeling to complex engineering activities with an understanding of the
limitations.
PO6: The engineer and society
Apply reasoning informed by the contextual knowledge to assess societal, health, safety, legal and
cultural issues and the consequent responsibilities relevant to the professional engineering practice.

7
 PO7: Environment and sustainability
Understand the impact of the professional engineering solutions in societal and
environmental contexts, and demonstrate the knowledge of, and need for sustainable
development.
.PO8: Ethics
Apply ethical principles and commit to professional ethics and responsibilities and norms of
the engineering practice.
PO9: Individual and team work
Function effectively as an individual, and as a member or leader in diverse teams, and in
multidisciplinary settings.
PO10: Communication
Communicate effectively on complex engineering activities with the engineering community
and with society at large, such as, being able to comprehend and write effective reports and
design documentation, make effective presentations, and give and receive clear instructions.
PO11: Project management and finance
Demonstrate knowledge and understanding of the engineering and management principles
and apply these to one’s own work, as a member and leader in a team, to manage projects
and in multidisciplinary environments.
PO12: Life-long learning
Recognize the need for, and have the preparation and ability to engage in independent and
life-long learning in the broadest context of technological change.

Program Specific Outcome (PSO)

PSO1: Addressing societal problems through design and development of software and
firmware solutions using latest Computer Science tools and technologies.

PSO2: Involving enthusiastically in software development, software testing,

storage, computing and business intelligence sectors.

PSO3: Use their technical expertise in latest technologies and update their knowledge
continuously in Computer Science and Engineering to excel in their career.

8
COURSE OBJECTIVES:
• To understand and apply the algorithm analysis techniques on searching
and sorting algorithms
• To critically analyze the efficiency of graph algorithms
• To understand different algorithm design techniques
• To solve programming problems using state space tree
• To understand the concepts behind NP Completeness, Approximation
algorithms and randomized algorithms.

COURSE OUTCOMES:
At the end of this course, the students will be able to:
CO1: Analyze the efficiency of algorithms using various frameworks
CO2: Apply graph algorithms to solve problems and analyze their efficiency.
CO3: Make use of algorithm design techniques like divide and conquer,
dynamic programming and greedy techniques to solve problems
CO4: Use the state space tree method for solving problems.
CO5: Solve problems using approximation algorithms and randomized algorithms

9
 SYLLABUS
L T P C
ALGORITHMS
23CST404
3 0 2 4

PRACTICAL EXERCISES: 30 PERIODS

Searching and Sorting Algorithms
1. Implement Linear Search. Determine the time required to search for an element. Repeat
the experiment for different values of n, the number of elements in the list to be searched and plot
a graph of the time taken versus n.
2. Implement recursive Binary Search. Determine the time required to search an element.
Repeat the experiment for different values of n, the number of elements in the list to be searched
and plot a graph of the time taken versus n.
3. Given a text txt [0...n-1] and a pattern pat [0...m-1], write a function search (char pat [ ],
char txt [ ]) that prints all occurrences of pat [ ] in txt [ ]. You may assume that n > m.
4. Sort a given set of elements using the Insertion sort and Heap sort methods and determine
the time required to sort the elements. Repeat the experiment for different values of n, the number
of elements in the list to be sorted and plot a graph of the time taken versus n.

Graph Algorithms
1. Develop a program to implement graph traversal using Breadth First Search
2. Develop a program to implement graph traversal using Depth First Search
3. From a given vertex in a weighted connected graph, develop a program to find the shortest
paths to other vertices using Dijkstra’s algorithm.
4. Find the minimum cost spanning tree of a given undirected graph using Prim’s algorithm.
5. Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.
6. Compute the transitive closure of a given directed graph using Warshall's algorithm.

Algorithm Design Techniques

1. Develop a program to find out the maximum and minimum numbers in a given list of n
numbers using the divide and conquer technique.
2. Implement Merge sort and Quick sort methods to sort an array of elements and determine
the time required to sort. Repeat the experiment for different values of n, the number of elements
in the list to be sorted and plot a graph of the time taken versus n.

State Space Search Algorithms

1. Implement N Queens problem using Backtracking.

Approximation Algorithms Randomized Algorithms

1. Implement any scheme to find the optimal solution for the Traveling Salesperson problem
and then solve the same problem instance using any approximation algorithm and determine the
error in the approximation.
2. Implement randomized algorithms for finding the kth smallest number. The programs can
be implemented in C/C++/JAVA/ Python

10
EX NO:1 Implement Linear Search. Determine the time required to search for an
element. Repeat the experiment for different values of n, the number of
Date: elements in the list to be searched and plot a graph of the time taken versus n.

AIM:
To write a C program to implement Linear Search. Determine the time required to search
for an element.

ALGORITHM:

Step 1: First, read the search element (Target element) in the array.
Step 2: In the second step compare the search element with the first element in the array.
Step 3: If both are matched, display “Target element is found” and terminate the Linear Search
function.
Step 4: If both are not matched, compare the search element with the next element in the array.
Step 5: In this step, repeat steps 3 and 4 until the search (Target) element is compared with the
last element of the array.
Step 6 – If the last element in the list does not match, the Linear Search Function will be
terminated, and the message “Element is not found” will be displayed.
PROGRAM:
#include <stdio.h>
int main()
{
int array[100], search, c, n;
printf("Enter the number of elements in array\n");
scanf("%d",&n);
printf("Enter %d integer(s)\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter the number to search\n");
scanf("%d", &search);
for (c = 0; c < n; c++)
{
if (array[c] == search) /* if required element found */
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
if (c == n)
printf("%d is not present in array.\n", search);
return 0;
}

11
OUTPUT:
Enter the number of elements in array
5
Enter 5 integer(s)
12
34
02
05
18
Enter the number to search
02
2 is present at location 3.

Time Complexity Analysis Linear Search time complexity analysis is done below.
Best case time complexity = O(1).
Average Case time complexity = O(n)
Worst case time complexity = O(n).
Thus, we have Time Complexity of Linear Search Algorithm is O(n).

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

12
EX NO:2 Implement recursive Binary Search. Determine the time required to search an
element. Repeat the experiment for different values of n, the number of
Date: elements in the list to be searched and plot a graph of the time taken versus n.

AIM:
To write a C program to implement recursive Binary Search Determine the time required to
search an element.
ALGORITHM:
Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return ‘element found’ and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.

PROGRAM:

#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
if (end_index >= start_index){
int middle = start_index + (end_index - start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] > element)
return recursiveBinarySearch(array, start_index, middle-1, element);
return recursiveBinarySearch(array, middle+1, end_index, element);
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 9;
int found_index = recursiveBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in the array ");
}
else {
printf("Element found at index : %d",found_index);
}
return 0;
}

13
OUTPUT:
Element found at index : 3

Time Complexity
Worst case time complexity: O(log n)
Average case time complexity: O(log n)
Best case time complexity: O(1)

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

14
EX NO: 03 Given a text txt [0...n-1] and a pattern pat [0...m-1], write a function
search (char pat [ ], char txt [ ]) that prints all occurrences of pat [ ] in txt [ ].
Date: You may assume that n > m.

AIM:
To write a C program and to write a function search (char pat [ ], char txt [ ]) that prints all
occurrences of pat [ ] in txt [ ].
ALGORITHM:
Step 1: Start the program
Step 2: Initially calculate the hash value of the pattern..
Step 3: Start iterating from the starting of the string.
Step 4 Calculate the hash value of the current substring having length m..
Step 5: If they are same, store the starting index as a valid answer. Otherwise, continue for the next
substrings.
Step6: Return the starting indices as the required answer.
Step 7: Stop the program

PROGRAM:
#include <stdio.h>
#include <string.h>
void search(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;if (j == M)
printf("Pattern found at index %d \n", i);// if pat[0...M-1] //= txt[i, i+1, ...i+M-1]
}
}
int main(){
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
search (pat,txt);
return 0;
}

15
OUTPUT:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

16
 Sort a given set of elements using the Insertion sort methods and determine
EX NO : 4(a)
the time required to sort the elements. Repeat the experiment for different
values of n, the number of elements in the list to be sorted and plot a graph of
Date:
the time taken versus n.

AIM :
To write a C program for Sort a given set of elements using the Insertion sort methods and
determine the time required to sort the elements.
ALGORITHM :
Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step2 - Pick the next element, and store it separately in a key.
Step3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then move to the
next element. Else, shift greater elements in the array towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.
PROGRAM :
// C program for insertion sort
#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;

17
 }
}

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

18
OUTPUT :
5 6 11 12 13

Time Complexity
Worst case time complexity: O(n^2)
Average case time complexity: O(n^2)
Best case time complexity: O(n)

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

19
 Sort a given set of elements using the Heap sort methods and determine the
EX NO : 4(b)
time required to sort the elements. Repeat the experiment for different values
of n, the number of elements in the list to be sorted and plot a graph of the time
Date:
taken versus n.

AIM:
To write a C program to Sort a given set of elements using the Heap sort methods and
determine the time required to sort the elements
ALGORITHM:
Step 1: Start the program
Step 2: Build a max heap from the input data.
Step 3: At this point, the maximum element is stored at the root of the heap. Replace it with the
last item of the heap followed by reducing the size of the heap by 1. Finally, heapify the root of
the tree.
Step 4: Repeat step 2 while the size of the heap is greater than 1.
Step 5: Stop the program

PROGRAM:

// Heap Sort in C

#include <stdio.h>

// Function to swap the position of two elements

void swap(int* a, int* b)

{

int temp = *a;

*a = *b;

*b = temp;
}

// 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)
{
// Find largest among root, left child and right child

// Initialize largest as root

int largest = i;

// left = 2*i + 1
int left = 2 * i + 1;

// right = 2*i + 2
int right = 2 * i + 2;

20
// If left child is larger than root
if (left < N && arr[left] > arr[largest])

largest = left;

// If right child is larger than largest

// so far
if (right < N && arr[right] > arr[largest])

largest = right;

// Swap and continue heapifying if root is not largest

// 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 max heap

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

heapify(arr, N, i);

// Heap sort
for (int i = N - 1; i >= 0; i--) {

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

// Heapify root element to get highest element at

// root again
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++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver's code

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

// Function call
heapSort(arr, N);
printf("Sorted array is\n");
printArray(arr, N);
}

OUTPUT:
Sorted array is
5 6 7 11 12 13

Time Complexity: O(N log N)

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

22
EX NO : 5
Develop a program to implement graph traversal using Breadth First Search
Date:

AIM:
To write a C program to implement graph traversal using Breadth First Search
ALGORITHM:
Step 1: Start program
Step 2 Start by putting any one of the graph's vertices at the back of a queue.
Step 3: Take the front item of the queue and add it to the visited list.
Step 4: Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the back of the queue.
Step 5: Keep repeating steps 2 and 3 until the queue is empty.
Step 6:Stop the program.

PROGRAM:
// BFS algorithm in C

#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) {

23
 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

24
 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;
}
}

25
 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;
}

26
OUTPUT:
Queue contains
0 Resetting queue Visited 0
Queue contains
2 1 Visited 2

Queue contains
1 4 Visited 1

Queue contains
4 3 Visited 4

Queue contains
3 Resetting queue Visited 3
The time complexity of the BFS algorithm is represented in the form of O(V + E), where V is the
number of nodes and E is the number of edges.
The space complexity of the algorithm is O(V).

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

27
EX NO : 6
Develop a program to implement graph traversal using Depth First Search
Date:

AIM:-
To write a ‘C ' program to implement graph traversal using Depth First
Search.

ALGORITHM:-

Step 1 : Start the program

Step 2 : Insert the root node or starting node of a tree or a graph in the stack.
Step 3 : Pop the top item from the stack and add it to the visited list.
Step 4 : Find all the adjacent nodes of the node marked visited and add the ones that are not
yet visited, to the stack.
Step 5 : Repeat steps 2 and 3 until the stack is empty.
Step 6 : Stop the program

PROGRAM :-
#include <stdio.h>
#include <stdlib.h>

// Structure to Represent a Node of Adjacency List

struct node
{
// Vertex Number will represent the Vertex which is connected from the Node
// To which the adjacency list is associated
int vertexNumber;

// This pointer will be used to point to the next vertex in the adjacency list
// NULL will denote that this vertex was the last connected vertex
// with the vertex associated with the adjacency list
struct node *pointerToNextVertex;
};

// Structure to Represent the Graph in C

struct Graph
{
// Total Number of Vertices will be needed so that we can know upto which node we have
to traverse
int numberOfVertices;

// A boolean flag will be maintained to know whether we have already visited the node or
not
int *visitedRecord;

// Adjacency Lists is a 2 dimensioanl array

// It will be used to maintain the adjacency list for each vertex of the graph
// For example: adjacencyLists[1] will denote the adjacency list of 1st vertex of graph

28
 // And it will contain all nodes connected to the 1st vertex of the graph
struct node **adjacencyLists;
};

/* ---------------------------------- Required Helper Functions ---------------------------------- */

// Function to create a Node
// It will be used to create the node for which the structure is defined above
// Parameters: An integer Vertex, to represent the vertex number
struct node *createNodeForList(int v)
{
// Use malloc to dynamically allocate Memory
struct node *newNode = malloc(sizeof(struct node));

// Allocate the vertex Number

// Means the "v" vertex is connected to the vertex whose adjacency list contains this entire
node
newNode->vertexNumber = v;

// Assign the next vertex to NULL

// COnsider it is the last connected vertex
newNode->pointerToNextVertex = NULL;
return newNode;
}

// Function to add Edge in the Graph

// Parameters: A pointer to Graph Structure and Edge (Source to Destination)
void addEdgeToGraph(struct Graph *graph, int source, int destination)
{
// Create New Node it is required before adding Edge to Graph
// Provide Destination as the vertexNumber because the source will be used to access the
required node
// We will add this node to the adjacency list of source Node
struct node *newNode = createNodeForList(destination);

// Now provide the pointer stored for the adjacency list of source node to the newNode
newNode->pointerToNextVertex = graph->adjacencyLists[source];

// And assign the new Node as the starting point of our adjacency list of the source node
// In this way we are adding the newNode at the starting of the adjacency list
// because traversing to the end and then inserting will be an overhead
graph->adjacencyLists[source] = newNode;

// In the similar way we have to add edge from destination to source

// Because we are working with undirected graphs
newNode = createNodeForList(source);
newNode->pointerToNextVertex = graph->adjacencyLists[destination];
graph->adjacencyLists[destination] = newNode;
}

// Function to Create Graph

29
// Parameters: Number of Vertices
struct Graph *createGraph(int vertices)
{
// Declare iterator variable for loop purpose
int i;

// Create graph Structure

struct Graph *graph = malloc(sizeof(struct Graph));

// Set the number of vertices

graph->numberOfVertices = vertices;

// Create the total "vertices" adjacency lists, means the array of adjacency lists
// Because still if we don't have the connection with any particular vertex
// The empty adjacency list is necessary
graph->adjacencyLists = malloc(vertices * sizeof(struct node *));

// Create the array visitedRecord to store the information about which nodes have been
visited till now.
graph->visitedRecord = malloc(vertices * sizeof(int));

// Initialize the visited record with 0, because at the time of the creation of a graph
// None of the vertex is visited
// And initialize the all adjacencyLists with NULL, because we don't have any edges while
creating the graph
for (i = 0; i < vertices; i++)
{
graph->adjacencyLists[i] = NULL;
graph->visitedRecord[i] = 0;
}

// Return the graph structure to use further

return graph;
}

/* ---------------------------------- Depth First Search Algorithm ---------------------------------- */

// Function to apply Depth First Search on graph
// Parameter: Graph and starting vertex Number, because it is necessary to define a starting
point
void depthFirstSearch(struct Graph *graph, int vertexNumber)
{
struct node *adjList = graph->adjacencyLists[vertexNumber];
struct node *temp = adjList;

graph->visitedRecord[vertexNumber] = 1;
printf("%d ", vertexNumber);

while (temp != NULL)

{
int connectedVertex = temp->vertexNumber;

30
 if (graph->visitedRecord[connectedVertex] == 0)
{
depthFirstSearch(graph, connectedVertex);
}
temp = temp->pointerToNextVertex;
}
}

int main()
{
int numberOfVertices, numberOfEdges, i;
int source, destination;
int startingVertex;

printf("Enter Number of Vertices and Edges in the Graph: ");

scanf("%d%d", &numberOfVertices, &numberOfEdges);
struct Graph *graph = createGraph(numberOfVertices);

printf("Add %d Edges of the Graph(Vertex numbering should be from 0 to %d)\n",

numberOfEdges, numberOfVertices - 1);
for (i = 0; i < numberOfEdges; i++)
{
scanf("%d%d", &source, &destination);
addEdgeToGraph(graph, source, destination);
}

printf("Enter Starting Vertex for DFS Traversal: ");

scanf("%d", &startingVertex);

if (startingVertex < numberOfVertices)

{
printf("DFS Traversal: ");
depthFirstSearch(graph, startingVertex);
}
return 0;
}

31
OUTPUT :

Enter the Number of Vertices and Edges in the Graph: 6 7

Add 7 Edges of the Graph(Vertex numbering should be from 0 to 5)
01
12
02
23
43
53
54
Enter Starting Vertex for DFS Traversal: 2
DFS Traversal: 2 3 5 4 0 1

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

32
EX NO : 7
From a given vertex in a weighted connected graph, develop a program to
find the shortest paths to other vertices using Dijkstra’s algorithm
Date:

AIM:-
To write a ‘C ' program to find the shortest paths to other vertices using Dijkstra’s
algorithm.

ALGORITHM:-

Step 1 : Start the program

Step 2 : Initialize the distance to all nodes as infinite, except for the start node which
is 0.
Step 3 : Create a set of unvisited nodes and add all nodes to the set
Step 4: Set the current node as the start node and its distance as 0.
Step 5 : While there are still unvisited nodes , do the following:
a. Find the node with the smallest distance from the start node. This will be the current
node

b. For each neighbor of the current node, calculate the distance to the neighbor through
the current node.

c. If the calculated distance is less than the previously recorded distance to the
neighbor, update the distance to the neighbor.

d. Mark the current node as visited and remove it from the set of unvisited nodes.

Step 6 : Return the shortest distances to all nodes.

Step 7 : Stop the program

PROGRAM :-

#include <limits.h>
#include <stdio.h>
#define V 9
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;
}
int printSolution(int dist[], int n) {
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
bool sptSet[V];

33
 for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] <
dist[v]) dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
int main() {
int graph[V][V] = { { 0, 6, 0, 0, 0, 0, 0, 8, 0 },
{ 6, 0, 8, 0, 0, 0, 0, 13, 0 },
{ 0, 8, 0, 7, 0, 6, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 6, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 13, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
};
dijkstra(graph, 0);
return 0;
}

34
OUTPUT :

Vertex Distance from Source

00
16
2 14
3 21
4 21
5 11
69
78
8 15

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

35
EX NO : 8
Find the minimum cost spanning tree of a given undirected graph using
Prim’s algorithm
Date:

AIM:-
To write a C program for implementing the minimum cost spanning tree of a given
undirected graph using Prim’s algorithm.

ALGORITHM:-

Step 1 : Start the program

Step 2 : Determine the arbitrary starting vertex.
Step 3 : Keep repeating steps 3 and 4 until the fringe vertices (vertices not included in
MST)remain.
Step 4 : Select an edge connecting the tree vertex and fringe vertex having the
minimum
weight
Step 5: Add the chosen edge to MST if it doesn’t form any closed cycle.
Step 6 : Stop the program

PROGRAM :-
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

// Number of vertices in the graph

#define V 5

// A utility function to find the vertex with

// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;

return min_index;
}

// A utility function to print the

// constructed MST stored in parent[]
int printMST(int parent[], int graph[V][V])
{
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)

36
 printf("%d - %d \t%d \n", parent[i], i,
graph[i][parent[i]]);
}

// Function to construct and print MST for

// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
// Array to store constructed MST
int parent[V];
// Key values used to pick minimum weight edge in cut
int key[V];
// To represent set of vertices included in MST
bool mstSet[V];

// Initialize all keys as INFINITE

for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.

// Make key 0 so that this vertex is picked as first
// vertex.
key[0] = 0;

// First node is always root of MST

parent[0] = -1;

// The MST will have V vertices

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

// Pick the minimum key vertex from the

// set of vertices not yet included in MST
int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of

// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for (int v = 0; v < V; v++)

// graph[u][v] is non zero only for adjacent

// vertices of m mstSet[v] is false for vertices
// not yet included in MST Update the key only
// if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false
&& graph[u][v] < key[v])

37
 parent[v] = u, key[v] = graph[u][v];
}

// print the constructed MST

printMST(parent, graph);
}

// Driver's code
int main()
{
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };

// Print the solution

primMST(graph);

return 0;
}

OUTPUT :

Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

38
EX NO : 09
Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.
Date:

AIM:-
To write a ‘C ' program for implementing the Floyd’s algorithm for the All-
Pairs- Shortest-Paths problem
ALGORITHM:-

Step 1: Start the process.

Step 2: Initialize the shortest paths between any 2 vertices with Infinity.
Step 3: Find all pair shortest paths that use 0 intermediate vertices, then find the
shortest
paths that use 1 intermediate vertex and so on.. until using all N vertices as
intermediate nodes.
Step 4: Minimize the shortest paths between any 2 pairs in the previous operation.
Step 5: For any 2 vertices (i,j) , one should actually minimize the distances between
this
pair using the first K nodes, so the shortest path will be:
min(dist[i][k]+dist[k][j],dist[i][j])
dist[i][k] represents the shortest path that only uses the first K vertices,
dist[k][j]
represents the shortest path between the pair k,j.
Step6: As the shortest path will be a concatenation of the shortest path from i to k,
then
from k to j.
Step7: Stop the process.

PROGRAM :-
// C Program for Floyd Warshall Algorithm
#include <stdio.h>
// Number of vertices in the graph
#define V 4
/* Define Infinite as a large enough
value. This value will be used
for vertices not connected to each other */
#define INF 99999
// A function to print the solution matrix
void printSolution(int dist[][V]);

// Solves the all-pairs shortest path

// problem using Floyd Warshall algorithm
void floydWarshall(int dist[][V])
{
int i, j, k;

/* Add all vertices one by one to

the set of intermediate vertices.
---> Before start of an iteration, we

39
 have shortest distances between all
pairs of vertices such that the shortest
distances consider only the
vertices in set {0, 1, 2, .. k-1} as
intermediate vertices.
----> After the end of an iteration,
vertex no. k is added to the set of
intermediate vertices and the set
becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++) {
// If vertex k is on the shortest path from
// i to j, then update the value of
// dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

// Print the shortest distance matrix

printSolution(dist);
}

/* A utility function to print solution */

void printSolution(int dist[][V])
{
printf(
"The following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}

// driver's code
int main()
{
int graph[V][V] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },

40
 { INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };

// Function call
floydWarshall(graph);
return 0;
}
OUTPUT :
The following matrix shows the shortest distances between every pair of vertices
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 017

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

41
EX NO : 10
Compute the transitive closure of a given directed graph using Warshall's
algorithm
Date:

AIM:-
To write a ‘C ' program to Compute the transitive closure of a given directed
graph using Warshall's algorithm
ALGORITHM:-

Step 1: Start the process.

Step 2: Initialize a matrix T with the same size as the adjacency matrix of the input
graph.
Set T(i,j) = 1 if there is a directed edge from node i to node j in the input
graph,
and 0 otherwise.
Step 3: For each node k in the graph, perform the following steps:
a. For each pair of nodes i and j in the graph, if T(i,j) = 0 and T(i,k) = 1 and
T(k,j)
= 1, set T(i,j) = 1.
Step 4: Repeat step 2 for each node in the graph.
Step 5: The resulting matrix T represents the transitive closure of the input graph. The
value T(i,j) is 1 if there is a path from node i to node j in the input graph, and 0
otherwise.
Step 6: Stop the process.

PROGRAM :-
#include<stdio.h>
#include<conio.h>
#include<math.h>
int max(int, int);
void warshal(int p[10][10], int n) {
int i, j, k;
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
p[i][j] = max(p[i][j], p[i][k] && p[k][j]);
}
int max(int a, int b) {
;
if (a > b)
return (a);
else
return (b);
}
void main() {
int p[10][10] = { 0 }, n, e, u, v, i, j;
printf("\n Enter the number of vertices:");
scanf("%d", &n);

42
 printf("\n Enter the number of edges:");
scanf("%d", &e);
for (i = 1; i <= e; i++) {
//printf("\n Enter the end vertices of edge %d:", i);
scanf("%d%d", &u, &v);
p[u][v] = 1;
}
printf("\n Matrix of input data: \n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
printf("%d\t", p[i][j]);
printf("\n");
}
warshal(p, n);
printf("\n Transitive closure: \n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
printf("%d\t", p[i][j]);
printf("\n");
}
getch();
}

43
OUTPUT:-

Enter the number of vertices: 5

Enter the number of edges: 11
Enter the end vertices of edge 1: 1 1
Enter the end vertices of edge 2: 1 4
Enter the end vertices of edge 3: 3 2
Enter the end vertices of edge 4: 3 3
Enter the end vertices of edge 5: 3 4
Enter the end vertices of edge 6: 4 2
Enter the end vertices of edge 7: 4 4
Enter the end vertices of edge 8: 5 2
Enter the end vertices of edge 9: 5 3
Enter the end vertices of edge 10: 5 4
Enter the end vertices of edge 11: 5 5

Matrix of input data:

1 0 0 1 0
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 1
Particulars Marks Marks
Transitive closure: Allocated Obtained
Performance 50
1 1 0 1 0
0 0 0 0 0 Viva-Voce 10
0 1 1 1 0
0 1 0 1 0 Record 15
0 1 1 1 1
Total 75

RESULT:

44
 EX NO : 11
Develop a program to find out the maximum and minimum numbers in a
given list of n numbers using the divide and conquer techniques.
Date:

AIM :
To write a C program to implement divide and conquer techniques.

ALGORITHM :

Step 1 : Start the program

Step 2 : Divide the list into two halves, left and right, with roughly equal numbers of
elements.
Step 3: Recursively find the maximum and minimum values in the left and right
halves of
the list.
Step 4:Compare the maximum value found in the left half with the maximum value
found
in the right half, and select the greater of the two as the overall maximum for
the
entire list.
Step 5 : Compare the minimum value found in the left half with the minimum value
found in the right half, and select the lesser of the two as the overall minimum
for
the entire list.
Step 6: Return the maximum and minimum values found in steps 3 and 4.
Step 7: Stop the program

PROGRAM :

/* structure is used to return two values from minMax() */

#include <stdio.h>

struct pair {

int min;

int max;

};

struct pair getMinMax(int arr[], int low, int high)

struct pair minmax, mml, mmr;

45
int mid;

// If there is only one element

if (low == high) {

minmax.max = arr[low];

minmax.min = arr[low];

return minmax;

/* If there are two elements */

if (high == low + 1) {

if (arr[low] > arr[high]) {

minmax.max = arr[low];

minmax.min = arr[high];

else {

minmax.max = arr[high];

minmax.min = arr[low];

return minmax;

/* If there are more than 2 elements */

mid = (low + high) / 2;

mml = getMinMax(arr, low, mid);

46
 mmr = getMinMax(arr, mid + 1, high);

/* compare minimums of two parts*/

if (mml.min < mmr.min)

minmax.min = mml.min;

else

minmax.min = mmr.min;

/* compare maximums of two parts*/

if (mml.max > mmr.max)

minmax.max = mml.max;

else

minmax.max = mmr.max;

return minmax;

/* Driver program to test above function */

int main()

int arr[] = { 1000, 11, 445, 1, 330, 3000 };

int arr_size = 6;

struct pair minmax = getMinMax(arr, 0, arr_size - 1);

printf("nMinimum element is %d", minmax.min);

printf("nMaximum element is %d", minmax.max);

47
 getchar();

OUTPUT :

Minimum element is 1
Maximum element is 3000

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

48
 Implement Merge sort and Quick sort methods to sort an array of elements
EX NO : 12
and determine the time required to sort. Repeat the experiment for different
values of n, the number of elements in the list to be sorted and plot a graph of
Date:
the time taken versus n.

AIM :
To write a C program to implement the Merge sort and Quick sort methods.

ALGORITHM :
Merge Sort
Step 1 : Start the program.
Step 2 : Suppose we have a given array, then first we need to divide the array into sub
array. Each sub array can store 5 elements.
Step 3: Here we gave the first sub array name as A1 and divide into next two subarray as
B1 and B2.
Step 4:Similarly, the right sub array name as A2 and divide it into next two sub array as
B3 and B4.
Step 5: This process is repeated continuously until the sub array is divided into a single
element and no more partitions may be possible.
Step 6: After that, compare each element with the corresponding one and then start the
process of merging to arrange each element in such a way that they are placed in
ascending order.
Step 7: The merging process continues until all the elements are merged in ascending
order
Step 8 : Stop the program

PROGRAM :
Merge Sort
#include <stdio.h>
//#include <conio.h>
#include <stdlib.h>

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

{
int i, j, k;
int a1 = m - l + 1;
int a2 = end - m;

// create temp subarray

int sub1[a1], sub2[a2];

// Store data to temp subarray subArr1[] and subArr2[]

for (i = 0; i < a1; i++)
sub1[i] = arr[l + i];
for (j = 0; j < a2; j++)
sub2[j] = arr[m + 1 + j];

// Merge the temp array into the original array arr[]

49
 i = 0;
j = 0;
k = l;
while (i < a1 && j < a2)
{
if (sub1[i] <= sub2[j])
{
arr[k] = sub1[i];
i++;
}
else
{
arr[k] = sub2[j];
j++;
}
k++;
}

// copry the rest element of subArr1[], if some element is left;

while (i < a1)
{
arr[k] = sub1[i];
i++;
k++;
}

// copry the rest element of subArr2[], if some element is left;

while (j < a2)
{
arr[k] = sub2[j];
j++;
k++;
}
}

/* st represents the first index and end represents the right index of the subarray of arr[] to be
sorted using merge sort. */
void mergeSort(int arr[], int l, int end)
{
if (l < end)
{
int m = l + (end - l) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, end);

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

50
// Function to print the merge sort.
void mergePrint(int Ar[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d \t", Ar[i]);
printf("\n");
}

int main()
{
int arr[] = { 70, 80, 40, 50, 60, 11, 35, 85, 2 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf(" Predefined Array is \n");

mergePrint(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\n Sorted array using the Merge Sort algorithm \n");

mergePrint(arr, arr_size);
return 0;
}
OUTPUT :

Predefined Array is
70 80 40 50 60 11 35 85 2

Sorted array using the Merge Sort algorithm

2 11 35 40 50 60 70 80 85

Quick Sort
Algorithm:
Quick Sort
Step 1 : Start the program.
Step 2 : Consider the first element of the list as pivot.
Step 3: Define two variables i and j. Set i and j to first and last elements of the list
respectively.
Step 4: Increment i until list[i] > pivot then stop..
Step 5: Decrement j until list[j] < pivot then stop..
Step 6 If i < j then exchange list[i] and list[j]..
Step 7: Repeat steps 3,4 & 5 until i > j.
Step 8: Exchange the pivot element with list[j] element.
Step 9 : Stop the program

Program:
#include<stdio.h>
#include<conio.h>

51
void quickSort(int [10],int,int);

void main(){
int list[20],size,i;

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

scanf("%d",&size);

printf("Enter %d integer values: ",size);

for(i = 0; i < size; i++)
scanf("%d",&list[i]);

quickSort(list,0,size-1);

printf("List after sorting is: ");

for(i = 0; i < size; i++)
printf(" %d",list[i]);

getch();
}

void quickSort(int list[10],int first,int last){

int pivot,i,j,temp;

if(first < last){

pivot = first;
i = first;
j = last;

while(i < j){

while(list[i] <= list[pivot] && i < last)
i++;
while(list[j] > list[pivot])
j--;
if(i <j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}

temp = list[pivot];
list[pivot] = list[j];
list[j] = temp;
quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}

52
OUTPUT:

Enter size of the List: 8

Enter 8 integer values: 5 3 8 1 4 6 2 7
List after sorting is: 1 2 3 4 5 6 7 8

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

53
EX NO : 13
Implement N Queens problem using Backtracking
Date:

AIM :

To write a C program to Implement N Queens problem using Backtracking

ALGORITHM :
Step 1 : Start the program
Step 2 : Initialize an empty chessboard of size NxN.
Step 3 : Start with the leftmost column and place a queen in the first row of that
column
Step 4 : Move to the next column and place a queen in the first row of that column.
Step 5 : Repeat step 3 until either all N queens have been placed or it is impossible to
place a queen in the current column without violating the rules of the
problem.
Step 6 : If all N queens have been placed, print the solution.
Step 7: If it is not possible to place a queen in the current column without violating
the
rules of the problem, backtrack to the previous column.
Step 8: Remove the queen from the previous column and move it down one row.
Step 9: Repeat steps 4-7 until all possible configurations have been tried.
Step 10:Stop the program.

PROGRAM :

/* C program to solve N Queen Problem using

backtracking */
#define N 4
#include <stdbool.h>
#include <stdio.h>

/* A utility function to print solution */

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

/* A utility function to check if a queen can

be placed on board[row][col]. Note that this
function is called when "col" queens are
already placed in columns from 0 to col -1.
So we need to check only left side for
attacking queens */

54
bool isSafe(int board[N][N], int row, int col)
{
int i, j;

/* Check this row on left side */

for (i = 0; i < col; i++)
if (board[row][i])
return false;

/* Check upper diagonal on left side */

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

/* Check lower diagonal on left side */

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

return true;
}

/* A recursive utility function to solve N

Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
/* base case: If all queens are placed
then return true */
if (col >= N)
return true;

/* Consider this column and try placing

this queen in all rows one by one */
for (int i = 0; i < N; i++) {
/* Check if the queen can be placed on
board[i][col] */
if (isSafe(board, i, col)) {
/* Place this queen in board[i][col] */
board[i][col] = 1;

/* recur to place rest of the queens */

if (solveNQUtil(board, col + 1))
return true;

/* If placing queen in board[i][col]

doesn't lead to a solution, then
remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}

55
 /* If the queen cannot be placed in any row in
this column col then return false */
return false;
}
bool solveNQ()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };

if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return false;
}

printSolution(board);
return true;
}

// driver program to test above function

int main()
{
solveNQ();
return 0;
}
OUTPUT :

..Q.
Q...
...Q
.Q..
Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

56
EX NO : 14 Implement any scheme to find the optimal solution for the Traveling
Salesperson problem and then solve the same problem instance using any
Date: approximation algorithm and determine the error in the approximation.

AIM :
To Write a C program to Implement any scheme to find the optimal solution for the
Traveling Salesperson problem and then solve the same problem instance
using any approximation algorithm and determine the error in the approximation.
ALGORITHM :
Step 1 : Start the program
Step 2 : Start on an arbitrary vertex as current vertex.
Step 3 : Find out the shortest edge connecting current vertex and an unvisited vertex V.
Step 4 : Set current vertex to V.
Step 5 : Mark V as visited.
Step 6: If all the vertices in domain are visited, then terminate.
Step 7 : Go to step 2.
Step 8: The sequence of the visited vertices is the output of the algorithm.
Step 9:Stop the program.

PROGRAM :

#include<stdio.h>

int a[10][10],n,visit[10];

int cost_opt=0,cost_apr=0;

int least_apr(int c);

int least_opt(int c);

void mincost_opt(int city)

int i,ncity;

visit[city]=1;

printf("%d-->",city);

ncity=least_opt(city);

if(ncity==999)

57
 ncity=1;

printf("%d",ncity);

cost_opt+=a[city][ncity];

return;

mincost_opt(ncity);

void mincost_apr(int city)

int i,ncity;

visit[city]=1;

printf("%d-->",city);

ncity=least_apr(city);

if(ncity==999)

ncity=1;

printf("%d",ncity);

cost_apr+=a[city][ncity];

return;

mincost_apr(ncity);

int least_opt(int c)

58
 int i,nc=999;

int min=999,kmin=999;

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

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

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

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

kmin=a[c][i];

nc=i;

if(min!=999)

cost_opt+=kmin;

return nc;

int least_apr(int c)

int i,nc=999;

int min=999,kmin=999;

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

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

if(a[c][i]<kmin)

59
 {

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

kmin=a[c][i];

nc=i;

if(min!=999)

cost_apr+=kmin;

return nc;

void main()

int i,j;

printf("Enter No. of cities:\n");

scanf("%d",&n);

printf("Enter the cost matrix\n");

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

printf("Enter elements of row:%d\n",i );

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

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

visit[i]=0;

printf("The cost list is \n");

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

printf("\n\n");

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

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

printf("\n\n Optimal Solution :\n");

printf("\n The path is :\n");

mincost_opt(1);

printf("\n Minimum cost:");

printf("%d",cost_opt);

printf("\n\n Approximated Solution :\n");

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

visit[i]=0;

printf("\n The path is :\n");

mincost_apr(1);

printf("\nMinimum cost:");

printf("%d",cost_apr);

printf("\n\nError in approximation is approximated solution/optimal solution=%f",

(float)cost_apr/cost_opt);

61
OUTPUT :

Enter No. of cities:

4
Enter the cost matrix
Enter elements of row:1
0136
Enter elements of row:2
1023
Enter elements of row:3
3201
Enter elements of row:4
6310

The cost list is

0 1 3 6

1 0 2 3

3 2 0 1

6 3 1 0

Optimal Solution :

The path is :
1-->2-->4-->3-->1
Minimum cost:8

Approximated Solution :

The path is :
1-->2-->3-->4-->1
Minimum cost:10

Error in approximation is approximated solution/optimal solution=1.250000

62
 Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

63
EX NO : 15
Implement randomized algorithms for finding the kth smallest number. The
programs can be implemented in C/C++/JAVA/ Python.
Date:

AIM :
To Write a C program to implement randomized algorithms for finding the kth smallest
number.

ALGORITHM :

Step 1 : Start the program.

Step 2 : Choose a pivot element randomly from the array.
Step 3: Partition the array around the pivot element, so that all elements smaller than the
pivot are on the left, and all elements larger than the pivot are on the right. Let i
be the index of the pivot after partitioning.
Step 4 : If i = k, we have found the kth smallest element and can return it
Step 5 : If i < k, the kth smallest element must be in the right partition, so we recurse on
the right partition.
Step 6 : If i > k, the kth smallest element must be in the left partition, so we recurse on
the left partition.
Step 7 : Stop the program

PROGRAM :

// C program to find K'th smallest element

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

// Compare function for qsort

int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}

// Function to return K'th smallest

// element in a given array
int kthSmallest(int arr[], int N, int K)
{
// Sort the given array
qsort(arr, N, sizeof(int), cmpfunc);

// Return k'th element in the sorted array

return arr[K - 1];
}

// Driver's code
int main()
{

64
 int arr[] = { 12, 3, 5, 7, 19 };
int N = sizeof(arr) / sizeof(arr[0]), K = 2;

// Function call
printf("K'th smallest element is %d",
kthSmallest(arr, N, K));
return 0;
}

OUTPUT:

K'th smallest element is 5

Particulars Marks Allocated Marks Obtained

Performance 50
Viva-Voce 10
Record 15
Total 75

RESULT:

65