Ex.

No:1
Date: Linear Search

Aim:
To perform a linear search on a given list of integers and find the position of a given
element in the list.

Algorithm:
1. Start
2. Declare a list of integers.
3. Take input from the user for the element to be searched.
4. Set a flag variable to 0.
5. Traverse through each element in the list and check if it matches the search element.
6. If a match is found, set the flag variable to 1 and break out of the loop.
7. If the flag variable is 1, print the position of the search element in the list.
8. If the flag variable is 0, print "Element not found in the list."
9. Stop.

Program:
#include <stdio.h>
int main()
{
int arr[10] = {2, 5, 3, 8, 6, 1, 10, 7, 9, 4};
int search_element, flag=0;
printf("Enter the element to be searched: ");
scanf("%d", &search_element);
for(int i=0; i<10; i++)
{
if(arr[i] == search_element)
{
flag = 1;
printf("%d found at position %d.\n", search_element, i+1);
break;
}
}
if(flag == 0)
printf("Element not found in the list.\n");
return 0;
}

Output:
Enter the element to be searched: 7
7 found at position 8.
Result:
The program successfully performs a linear search on the given list of integers and
finds the position of the given search element. If the element is not found in the list, it
displays an appropriate message.
[Link] Binary Search
Date:

Aim:
To perform a binary search on a given list of integers and find the position of a given
element in the list.

Algorithm:
1. Start
2. Declare a list of integers and sort it in ascending order.
3. Take input from the user for the element to be searched.
4. Set two pointers, low and high, to the beginning and end of the list respectively.
5. While low is less than or equal to high, repeat steps 6 to 8.
6. Set mid to the middle index between low and high.
7. If the element at the middle index matches the search element, print the position of the
search element in the list and stop.
8. If the element at the middle index is less than the search element, set low to mid+1.
9. If the element at the middle index is greater than the search element, set high to mid-
1.
10. If the search element is not found in the list, print "Element not found in the list."
11. Stop

Program:
#include <stdio.h>
int main()
{
int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int search_element, low=0, high=9, mid;
printf("Enter the element to be searched: ");
scanf("%d", &search_element);
while(low <= high)
{
mid = (low + high) / 2;

if(arr[mid] == search_element)
{
printf("%d found at position %d.\n", search_element, mid+1);
break;
}
else if(arr[mid] < search_element)
low = mid + 1;
else
high = mid - 1;
}
if(low > high)
printf("Element not found in the list.\n");
 return 0;
}

Output:
Enter the element to be searched: 7
7 found at position 8.

Result:
The program successfully performs a binary search on the given list of integers and
finds the position of the given search element. If the element is not found in the list, it
displays an appropriate message
[Link] Pattern Matching Algorithm(Naïve String matching algorithm)
Date:

Aim:
To find all occurrences of a pattern in a given text using the Naive String algorithm.

Algorithm:
1. Calculate the lengths of the pattern and the text.
2. Iterate through the text using a loop, with the loop variable i ranging from 0 to n - m,
where n is the length of the text and m is the length of the pattern.
3. For each i, compare the substring of length m starting at position i with the pattern
character by character.
4. If the substring matches the pattern, print the index i.
5. Repeat steps 2-4 until all occurrences of the pattern in the text have been found.

Program:
#include <stdio.h>
#include <string.h>
void search(char pat[], char txt[]) {
int m = strlen(pat); // length of pattern
int n = strlen(txt); // length of text

// iterate through the text

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

// check if the current substring matches the pattern

for (j = 0; j < m; j++) {
if (txt[i+j] != pat[j])
break;
}
// if the pattern is found, print the index
if (j == m) {
printf("Pattern found at index %d\n", i);
}
}
}
int main() {
char txt[] = "abracadabra";
char pat[] = "cad";
// call the search function
search(pat, txt);
return 0;}

Output:
Pattern found at index 4
Result:
The Naive String algorithm is a simple yet effective algorithm for finding all
occurrences of a pattern in a given text. It has a time complexity of O(nm), where n is the
length of the text and m is the length of the pattern. In this experiment, we successfully
implemented the Naive String algorithm in C and used it to find all occurrences of the pattern
"cad" in the text "abracadabra". The output showed that the pattern was found at index 4,
which is the expected result.
[Link] Insertion and Heap sort
Date:

Aim:
To sort a given set of elements using the Insertion sort and Heap sort methods and
plot a graph of the time taken versus n.

Algorithm:
Insertion sort:
1. Iterate through the list from the second element to the last.
2. For each element, compare it with the elements before it and insert it in the correct
position.
Heap sort:
1. Build a max heap from the list.
2. Swap the root element (which is the largest element) with the last element in the heap
and remove the last element from the heap.
3. Maintain the max heap property by heapifying the remaining elements.
4. Repeat steps 2-3 until all elements have been removed from the heap

Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function to print an array

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

// Function to perform insertion sort

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

while (j >= 0 && arr[j] > key) {

arr[j+1] = arr[j];
j--;
}

arr[j+1] = key;
}
}
// Function to perform heap sort
void heap_sort(int arr[], int n) {
// Build max heap
for (int i = n/2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}

// Extract elements from heap

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

// Maintain max heap property

heapify(arr, i, 0);
}
}

// Function to heapify a subtree rooted with node i

void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2*i + 1; // Left child
int r = 2*i + 2; // Right child

// 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) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);
}
}
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}

printf("Unsorted array: ");

print_array(arr, n);

clock_t t;

// Insertion sort
t = clock();

Result:
Thus the program to sort a given set of elements using the Insertion sort and Heap sort
methods and plot a graph of the time taken versus n has been done successfully.
[Link] Breadth First Search
Date:

Aim:
The aim of this program is to implement Breadth First Search (BFS) traversal on a
graph.

Algorithm:
1. Create a queue data structure and initialize it with the starting vertex of the graph.
2. Create a visited array to keep track of the vertices that have been visited and initialize
it to all false.
3. Mark the starting vertex as visited and enqueue it in the queue.
4. While the queue is not empty, do the following: a. Dequeue a vertex from the queue.
b. Visit the dequeued vertex and print it. c. For each adjacent vertex of the dequeued
vertex, if it has not been visited yet, mark it as visited and enqueue it in the queue.
5. Repeat step 4 until the queue is empty.

Program:
from collections import deque
class Graph:
def __init__(self, adj_list):
self.adj_list = adj_list

def bfs(self, start):

visited = [False] * len(self.adj_list)
queue = deque([start])

while queue:
vertex = [Link]()
visited[vertex] = True
print(vertex, end=" ")

for neighbor in self.adj_list[vertex]:

if not visited[neighbor]:
visited[neighbor] = True
[Link](neighbor)

# Example usage
adj_list = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
g = Graph(adj_list)
[Link](2)

Output:
2031
Result:
The above program implements the BFS traversal algorithm on a graph using Python.
By following the BFS algorithm, it ensures that all vertices of the graph are visited in a
systematic way, starting from the given vertex. The output of the program shows the order in
which the vertices are visited.
[Link] Depth First Search
Date:

Aim:
The aim of this program is to implement graph traversal using Depth First Search
(DFS) algorithm.

Algorithm: The DFS algorithm starts at the root node of a graph and explores as far as
possible along each branch before backtracking. It maintains a stack to keep track of nodes to
be visited. The algorithm works as follows:
1. Create a stack to keep track of nodes to be visited.
2. Push the root node onto the stack.
3. While the stack is not empty, do the following: a. Pop a node from the stack. b. If the
node has not been visited, mark it as visited and print its value. c. Push all of the
node's unvisited neighbors onto the stack

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

#define MAX_NODES 100

// structure to represent a graph

struct Graph {
int num_nodes;
int adj_matrix[MAX_NODES][MAX_NODES];
};

// initialize graph
void init_graph(struct Graph* G, int num_nodes) {
G->num_nodes = num_nodes;

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

for (int j = 0; j < num_nodes; j++) {
G->adj_matrix[i][j] = 0;
}
}
}

// add edge to graph

void add_edge(struct Graph* G, int u, int v) {
G->adj_matrix[u][v] = 1;
}

// depth-first search traversal of graph

void dfs(struct Graph* G, int start, int visited[]) {
visited[start] = 1;
printf("%d ", start);

for (int i = 0; i < G->num_nodes; i++) {

if (G->adj_matrix[start][i] == 1 && visited[i] == 0) {
dfs(G, i, visited);
}
}
}

// Example usage
int main() {
struct Graph G;
int num_nodes = 4;
init_graph(&G, num_nodes);

add_edge(&G, 0, 1);
add_edge(&G, 0, 2);
add_edge(&G, 1, 2);
add_edge(&G, 2, 0);
add_edge(&G, 2, 3);
add_edge(&G, 3, 3);

int visited[MAX_NODES] = {0};

printf("Depth First Traversal (starting from vertex 2): ");
dfs(&G, 2, visited);

return 0;
}

Output:
Depth First Traversal (starting from vertex 2): 2 0 1 3

Result:
The program successfully implemented the Depth First Search (DFS) algorithm to
traverse a graph starting from a given vertex. The output shows the nodes visited in the order
they were visited during the traversal
[Link] Dijkstra’s Algorithm
Date:

Aim:
To implement Dijkstra's algorithm to find the shortest path between two nodes in a
weighted graph.

Algorithm:
1. Initialize the distance array with infinity except the source vertex, which is 0.
2. Initialize a set of unvisited vertices.
3. Set the current vertex as the source vertex and mark it as visited.
4. For each unvisited neighbor of the current vertex, calculate the tentative distance from
the source vertex to that neighbor through the current vertex.
5. If the tentative distance is less than the current distance, update the distance array with
the tentative distance.
6. Select the unvisited vertex with the smallest tentative distance and mark it as visited.
7. Repeat steps 4-6 until the destination vertex is marked as visited or there are no more
unvisited vertices.
8. The shortest path from the source vertex to the destination vertex is the sum of
distances along the path between these vertices.

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

#define V 6 // Number of vertices

int minDistance(int dist[], bool visited[]) {

int min = INT_MAX, min_index;
for (int i = 0; i < V; i++) {
if (!visited[i] && dist[i] <= min) {
min = dist[i];
min_index = i;
}
}
return min_index;
}

void dijkstra(int graph[V][V], int src, int dest) {

int dist[V];
bool visited[V];
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = false;
}
dist[src] = 0;
 for (int i = 0; i < V - 1; i++) {
int u = minDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printf("Shortest path from %d to %d: %d\n", src, dest, dist[dest]);
}

int main() {
int graph[V][V] = {{0, 2, 0, 6, 0, 0},
{2, 0, 3, 8, 5, 0},
{0, 3, 0, 0, 7, 0},
{6, 8, 0, 0, 9, 10},
{0, 5, 7, 9, 0, 1},
{0, 0, 0, 10, 1, 0}};
int src = 0, dest = 5;
dijkstra(graph, src, dest);
return 0;
}

Output:
Shortest path from 0 to 5: 14

Result:
The above program implements Dijkstra's algorithm to find the shortest path between
two nodes in a weighted graph. The program takes an adjacency matrix as input and outputs
the shortest path between the source and destination vertices. The result obtained from the
sample graph is that the shortest path from node 0 to node 5 is of length 14.
[Link] Prim’s Algorithm
Date:

Aim:
To implement Prim's algorithm to find the minimum spanning tree of a weighted
graph.

Algorithm:
1. Create a set of visited vertices and initialize it to empty.
2. Create a set of unvisited vertices and initialize it to all vertices in the graph.
3. Select any vertex from the unvisited set and add it to the visited set.
4. While the unvisited set is not empty, do the following: a. Find the minimum weight
edge that connects a visited vertex to an unvisited vertex. b. Add the unvisited vertex
to the visited set and remove it from the unvisited set. c. Add the minimum weight
edge to the minimum spanning tree.
5. The minimum spanning tree is the set of edges added in step 4.

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

#define V 5 // Number of vertices

int minKey(int key[], bool visited[]) {

int min = INT_MAX, min_index;
for (int i = 0; i < V; i++) {
if (!visited[i] && key[i] < min) {
min = key[i];
min_index = i;
}
}
return min_index;
}

void prim(int graph[V][V]) {

int parent[V];
int key[V];
bool visited[V];
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
visited[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int i = 0; i < V - 1; i++) {
int u = minKey(key, visited);
 visited[u] = true;
for (int v = 0; v < V; v++) {
if (graph[u][v] && !visited[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printf("Minimum spanning tree:\n");
for (int i = 1; i < V; i++) {
printf("%d - %d\n", parent[i], i);
}
}

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}};
prim(graph);
return 0;
}

Output:
Minimum spanning tree:
0-1
1-2
0-3
1-4

Result:
The above program implements Prim's algorithm to find the minimum spanning tree
of a weighted graph. The program takes an adjacency matrix as input and outputs the edges in
the minimum spanning tree. The result obtained from the sample graph is that the minimum
spanning tree consists of edges (0,1), (1,2), (0,3), and (1,4), with a total weight of 16.
[Link] Floyd’s Algorithm
Date:

Aim:
To implement Floyd's algorithm to find the shortest path between all pairs of vertices
in a weighted graph.

Algorithm:
1. Create a distance matrix dist[][], where dist[i][j] stores the shortest distance between
vertices i and j.
2. Initialize dist[][] to the weight of the edges between adjacent vertices and INT_MAX
for non-adjacent vertices.
3. For each vertex v, set dist[v][v] to 0.
4. For each intermediate vertex k from 0 to V-1, do the following: a. For each pair of
vertices i and j, if the distance from i to j through k is less than the current distance
between i and j, update the distance to the new value.
5. The resulting dist[][] matrix contains the shortest path between all pairs of vertices.

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

#define V 4 // Number of vertices

void floyd(int graph[][V]) {

int dist[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] <
dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
printf("Shortest distance matrix:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INT_MAX) {
printf("INF ");
 } else {
printf("%d ", dist[i][j]);
}
}
printf("\n");
}
}

int main() {
int graph[V][V] = {{0, 5, INT_MAX, 10},
{INT_MAX, 0, 3, INT_MAX},
{INT_MAX, INT_MAX, 0, 1},
{INT_MAX, INT_MAX, INT_MAX, 0}};
floyd(graph);
return 0;
}

Output:
Shortest distance matrix:
0589
INF 0 3 4
INF INF 0 1
INF INF INF 0

Result:
The above program implements Floyd's algorithm to find the shortest path between all
pairs of vertices in a weighted graph. The program takes an adjacency matrix as input and
outputs the resulting distance matrix. The result obtained from the sample graph is that the
shortest distance matrix is as shown above.
[Link] Warshall’s Algorithm
Date:

Aim:
To implement Warshall's algorithm to find the transitive closure of a given directed
graph.

Algorithm:
1. Create a matrix closure[][] of size VxV, where V is the number of vertices in the
graph.
2. Initialize closure[][] to the adjacency matrix of the graph.
3. For each intermediate vertex k from 0 to V-1, do the following: a. For each pair of
vertices i and j, if there is a path from i to k and from k to j, mark closure[i][j] as true.
4. The resulting closure[][] matrix contains the transitive closure of the graph.

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

#define V 4 // Number of vertices

void warshall(int graph[][V]) {

bool closure[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
closure[i][j] = graph[i][j];
}
}
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
closure[i][j] = closure[i][j] || (closure[i][k] && closure[k][j]);
}
}
}
printf("Transitive closure matrix:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf("%d ", closure[i][j]);
}
printf("\n");
}
}

int main() {
int graph[V][V] = {{1, 1, 0, 1},
 {0, 1, 1, 0},
{0, 0, 1, 1},
{0, 0, 0, 1}};
warshall(graph);
return 0;
}

Output:
Transitive closure matrix:
1111
0110
0011
0001

Result:
The above program implements Warshall's algorithm to find the transitive closure of
a given directed graph. The program takes an adjacency matrix as input and outputs the
resulting closure matrix. The result obtained from the sample graph is that the transitive
closure matrix is as shown above.
[Link] Minimum and maximum using divide and conquer
Date:

Aim:
To implement the divide and conquer method to find the minimum and maximum
elements in an array.

Algorithm:
1. If the array has only one element, return that element as both the minimum and
maximum.
2. If the array has two elements, compare the two elements and return the smaller one as
the minimum and the larger one as the maximum.
3. If the array has more than two elements, divide the array into two halves.
4. Recursively find the minimum and maximum of each half.
5. Compare the minimums of the two halves and return the smaller one as the overall
minimum.
6. Compare the maximums of the two halves and return the larger one as the overall
maximum

Program:
#include <stdio.h>

void findMinMax(int arr[], int low, int high, int* min, int* max) {
int mid, min1, max1, min2, max2;
if (low == high) { // Case 1: Only one element in the array
*min = arr[low];
*max = arr[low];
return;
} else if (high == low + 1) { // Case 2: Two elements in the array
if (arr[low] > arr[high]) {
*min = arr[high];
*max = arr[low];
} else {
*min = arr[low];
*max = arr[high];
}
return;
} else { // Case 3: More than two elements in the array
mid = (low + high) / 2;
findMinMax(arr, low, mid, &min1, &max1);
findMinMax(arr, mid+1, high, &min2, &max2);
if (min1 < min2) {
*min = min1;
} else {
*min = min2;
}
 if (max1 > max2) {
*max = max1;
} else {
*max = max2;
}
}
}

int main() {
int arr[] = {2, 8, 1, 6, 5, 3, 7, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int min, max;
findMinMax(arr, 0, n-1, &min, &max);
printf("Minimum element = %d\n", min);
printf("Maximum element = %d\n", max);
return 0;
}

Output:
Minimum element = 1
Maximum element = 8

Result:
The above program implements the divide and conquer method to find the minimum
and maximum elements in an array. The program takes an array as input and outputs the
minimum and maximum elements in the array. The result obtained from the sample array is
that the minimum element is 1 and the maximum element is 8.
[Link] Merge Sort and Quick Sort
Date:

Aim:
To implement the Merge Sort algorithm to sort an array of integers.

Algorithm:
1. Divide the array into two halves, left and right.
2. Recursively sort the left and right halves.
3. Merge the sorted left and right halves into a single sorted array.

Program:
#include <stdio.h>
#include <stdlib.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);
}
}

int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
mergeSort(arr, 0, n - 1);
printf("\nAfter sorting: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

Output:
Before sorting: 38 27 43 3 9 82 10
After sorting: 3 9 10 27 38 43 82

Result:
The above program implements the Merge Sort algorithm to sort an array of integers.
The program takes an array as input and outputs the sorted array. The result obtained from
the sample array is 3 9 10 27 38 43 82
[Link]: 12 Quick Sort
Date:

Aim:
To implement the Quick Sort algorithm to sort an array of integers.

Algorithm:
1. Choose an element from the array, called the pivot.
2. Partition the array into two sub-arrays: elements less than or equal to the pivot, and
elements greater than the pivot.
3. Recursively apply the Quick Sort algorithm to the two sub-arrays

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

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

int t = *a;
*a = *b;
*b = t;
}

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

int pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

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

if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
 int n = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
quickSort(arr, 0, n - 1);
printf("\nAfter sorting: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

Output:
Before sorting: 38 27 43 3 9 82 10
After sorting: 3 9 10 27 38 43 82

Result:
The above program implements the Quick Sort algorithm to sort an array of integers. The
program takes an array as input and outputs the sorted array. The result obtained from the
sample array is 3 9 10 27 38 43 82.
[Link] N Queens Problem
Date:

Aim:
To implement the N Queens problem to place N queens on an NxN chessboard
without any two queens attacking each other.

Algorithm:
1. Place the first queen in the first column.
2. Move to the next column and place the next queen in a row such that it cannot attack
the first queen.
3. Repeat step 2 until all N queens have been placed.
4. If a solution has been found, output the positions of the queens.
5. If a solution has not been found, backtrack to the last queen placement and try a
different row in the current column.

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

#define N 8

int board[N][N];

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

int isSafe(int row, int col) {

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

int solveNQueens(int col) {

if (col == N) {
return 1;
}
for (int i = 0; i < N; i++) {
if (isSafe(i, col)) {
board[i][col] = 1;
if (solveNQueens(col + 1)) {
return 1;
}
board[i][col] = 0;
}
}
return 0;
}

int main() {
if (solveNQueens(0)) {
printf("Solution exists.\n");
printBoard();
}
else {
printf("Solution does not exist.");
}
return 0;
}

Output:
Solution exists.
00001000
00000001
00010000
00000010
10000000
00000000
00000100
01000000
Result:
The above program implements the N Queens problem to place N queens on an NxN
chessboard without any two queens attacking each other. The program outputs the positions
of the queens if a solution exists, otherwise, it outputs "Solution does not exist." The result
obtained from the sample problem is shown above.
[Link] Traveling Sales Person
Date:

Aim:
To implement Traveling Sales Person(TSP) problem using C programming.

Algorithm:
1. Travelling salesman problem takes a graph G {V, E} as an input and declare another
graph as the output (say G’) which will record the path the salesman is going to take
from one node to another.
2. The algorithm begins by sorting all the edges in the input graph G from the least
distance to the largest distance.
3. The first edge selected is the edge with least distance, and one of the two vertices (say
A and B) being the origin node (say A).
4. Then among the adjacent edges of the node other than the origin node (B), find the
least cost edge and add it onto the output graph.
5. Continue the process with further nodes making sure there are no cycles in the output
graph and the path reaches back to the origin node A.
6. However, if the origin is mentioned in the given problem, then the solution must
always start from that node only. Let us look at some example problems to understand
this better.

Program:
#include <stdio.h>
int tsp_g[10][10] = {
{12, 30, 33, 10, 45},
{56, 22, 9, 15, 18},
{29, 13, 8, 5, 12},
{33, 28, 16, 10, 3},
{1, 4, 30, 24, 20}
};
int visited[10], n, cost = 0;

/* creating a function to generate t

he shortest path */
void travellingsalesman(int c){
int k, adj_vertex = 999;
int min = 999;

/* marking the vertices visited in an assigned array */

visited[c] = 1;

/* displaying the shortest path */

printf("%d ", c + 1);
 /* checking the minimum cost edge in the graph */
for(k = 0; k < n; k++) {
if((tsp_g[c][k] != 0) && (visited[k] == 0)) {
if(tsp_g[c][k] < min) {
min = tsp_g[c][k];
}
adj_vertex = k;
}
}
if(min != 999) {
cost = cost + min;
}
if(adj_vertex == 999) {
adj_vertex = 0;
printf("%d", adj_vertex + 1);
cost = cost + tsp_g[c][adj_vertex];
return;
}
travellingsalesman(adj_vertex);
}

/* main function */
int main(){
int i, j;
n = 5;
for(i = 0; i < n; i++) {
visited[i] = 0;
}
printf("\n\nShortest Path:\t");
travellingsalesman(0);
printf("\n\nMinimum Cost: \t");
printf("%d\n", cost);
return 0;
}

Output:
Shortest Path: 1 5 4 3 2 1
Minimum Cost: 99

Result:
Thus the travelling sales person algorithm has been implemented and output verified
successfully.
[Link] Randomized algorithm for finding kth smallest number
Date:

Aim:
Toimplement randomized algorithms for finding the kth smallest number.

Algorithm:
1. Select a random element from a array as a pivot.
2. Then partition to the array around the pivot, its help to all the smaller element were
placed before in the pivot and all greater element are placed after the pivot.
3. then Check the position of the pivot. If it is the kth element then return it.
4. If it is the less than the kth element then repeat the process of the subarray.
5. If it is the greater then the kth element then repeat the process of the left subarray.

Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function prototypes
int kthSmallest(int arr[], int l, int r, int k);
int randomPartition(int arr[], int l, int r);
int partition(int arr[], int l, int r);
void swap(int arr[], int a, int b);

// Function to swap two elements in the array

void swap(int arr[], int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}

// Standard partition process of QuickSort()

int partition(int arr[], int l, int r) {
int x = arr[r];
int i = l;
for (int j = l; j < r; j++) {
if (arr[j] <= x) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, r);
return i;
}
// Picks a random pivot element between l and r
// and partitions arr[l..r] around the randomly
// picked element using partition()
int randomPartition(int arr[], int l, int r) {
int n = r - l + 1;
int pivot = rand() % n;
swap(arr, l + pivot, r);
return partition(arr, l, r);
}

// This function returns k'th smallest element

// in arr[l..r] using QuickSort based method.
int kthSmallest(int arr[], int l, int r, int k) {
if (k > 0 && k <= r - l + 1) {
int pos = randomPartition(arr, l, r);

if (pos - l == k - 1)
return arr[pos];
if (pos - l > k - 1)
return kthSmallest(arr, l, pos - 1, k);
return kthSmallest(arr, pos + 1, r, k - pos + l - 1);
}
return 999999999;
}

int main() {
int arr[] = { 12, 3, 5, 7, 4, 19, 26 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
srand(time(NULL));
printf("K'th smallest element is %d\n", kthSmallest(arr, 0, n - 1, k));
return 0;
}

Output:
K'th smallest element is 5

Result:Thusthe implementation of randomized algorithms for finding the kth smallest

number has been done and output verified successfully.