Algorithm Programs
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.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int linear_search(int arr[], int n, int x) {
// Linear search function to find the index of an element in an array.
// Returns the index if found, else returns -1.
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
return -1;
double time_linear_search(int arr[], int n, int x) {
// Function to measure the time taken for linear search on an array of length n.
// Returns the time taken.
clock_t start, end;
double cpu_time_used;
start = clock();
linear_search(arr, n, x);
Algorithm Programs
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
return cpu_time_used;
int main() {
int sizes[] = {1000, 2000, 3000, 4000, 5000}; // Different values of n
int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
// Repeat the experiment for different values of n
for (int i = 0; i < num_sizes; i++) {
int n = sizes[i];
int arr[n];
// Initialize the array with random values
srand(time(0));
for (int j = 0; j < n; j++) {
arr[j] = rand() % 1000;
// Choose a random element to search for
int x = arr[rand() % n];
// Measure the time taken for linear search
double time_taken = time_linear_search(arr, n, x);
Algorithm Programs
// Print the time taken for each value of n
printf("Time taken for n = %d: %lf seconds\n", n, time_taken);
return 0;
Output:
Time taken for n = 1000: 0.000002 seconds
Time taken for n = 2000: 0.000001 seconds
Time taken for n = 3000: 0.000004 seconds
Time taken for n = 4000: 0.000001 seconds
Time taken for n = 5000: 0.000003 seconds
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.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int binary_search_recursive(int arr[], int low, int high, int x) {
// Recursive binary search function to find the index of an element in a sorted
array.
// Returns the index if found, else returns -1.
if (low <= high) {
Algorithm Programs
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
return binary_search_recursive(arr, mid + 1, high, x);
} else {
return binary_search_recursive(arr, low, mid - 1, x);
return -1;
double time_binary_search(int arr[], int n, int x) {
// Function to measure the time taken for binary search on a sorted array of
length n.
// Returns the time taken.
clock_t start, end;
double cpu_time_used;
start = clock();
binary_search_recursive(arr, 0, n - 1, x);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
Algorithm Programs
return cpu_time_used;
int main() {
int sizes[] = {1000, 2000, 3000, 4000, 5000}; // Different values of n
int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
// Repeat the experiment for different values of n
for (int i = 0; i < num_sizes; i++) {
int n = sizes[i];
int arr[n];
// Initialize the array with sorted values
for (int j = 0; j < n; j++) {
arr[j] = j;
// Choose a random element to search for
int x = rand() % n;
// Measure the time taken for binary search
double time_taken = time_binary_search(arr, n, x);
// Print the time taken for each value of n
printf("Time taken for n = %d: %lf seconds\n", n, time_taken);
Algorithm Programs
return 0;
Output:
Time taken for n = 1000: 0.000002 seconds
Time taken for n = 2000: 0.000000 seconds
Time taken for n = 3000: 0.000001 seconds
Time taken for n = 4000: 0.000001 seconds
Time taken for n = 5000: 0.000001 seconds
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.
#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 for pattern match starting at position i
Algorithm Programs
for (j = 0; j < m; j++) {
if (txt[i + j] != pat[j])
break;
// If pattern is found starting at position i
if (j == m)
printf("Pattern found at index %d\n", i);
int main() {
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
search(pat, txt);
return 0;
Output:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
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
Algorithm Programs
number of elements in the list to be sorted and plot a graph of the
time taken versus n.
Output:
Graph Algorithms
1. Develop a program to implement graph traversal using
Breadth First Search.
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 100
typedef struct {
int front, rear;
int array[MAX_NODES];
} Queue;
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = -1;
return q;
}
Algorithm Programs
void enqueue(Queue* q, int value) {
if (q->rear == MAX_NODES - 1)
return;
if (q->front == -1)
q->front = 0;
q->array[++q->rear] = value;
int dequeue(Queue* q) {
if (q->front == -1)
return -1;
int item = q->array[q->front];
if (q->front == q->rear)
q->front = q->rear = -1;
else
q->front++;
return item;
void BFS(int graph[][MAX_NODES], int start, int num_nodes) {
Queue* q = createQueue();
int visited[MAX_NODES] = {0};
visited[start] = 1;
enqueue(q, start);
Algorithm Programs
while (q->front != -1) {
int current = dequeue(q);
printf("%d ", current);
for (int i = 0; i < num_nodes; i++) {
if (graph[current][i] && !visited[i]) {
visited[i] = 1;
enqueue(q, i);
printf("\n");
int main() {
int graph[MAX_NODES][MAX_NODES] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 0, 0, 0}
};
int num_nodes = 5;
Algorithm Programs
printf("BFS traversal starting from node 0: ");
BFS(graph, 0, num_nodes);
return 0;
Output:
BFS traversal starting from node 0: 0 1 2 3 4
2. Develop a program to implement graph traversal using Depth
First Search.
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 100
void DFS(int graph[][MAX_NODES], int start, int num_nodes, int visited[]) {
printf("%d ", start);
visited[start] = 1;
for (int i = 0; i < num_nodes; i++) {
if (graph[start][i] && !visited[i]) {
DFS(graph, i, num_nodes, visited);
}
Algorithm Programs
int main() {
int graph[MAX_NODES][MAX_NODES] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 0, 0, 0}
};
int num_nodes = 5;
int visited[MAX_NODES] = {0};
printf("DFS traversal starting from node 0: ");
DFS(graph, 0, num_nodes, visited);
return 0;
Ouput:
DFS traversal starting from node 0: 0 1 3 4 2
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.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
Algorithm Programs
#define MAX_NODES 100
// Function to find the vertex with the minimum distance value
int minDistance(int dist[], int visited[], int num_nodes) {
int min = INT_MAX, min_index;
for (int v = 0; v < num_nodes; v++) {
if (visited[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
return min_index;
// Function to print the shortest paths from the source vertex
void printShortestPaths(int dist[], int num_nodes) {
printf("Vertex Distance from Source\n");
for (int i = 0; i < num_nodes; i++)
printf("%d \t\t %d\n", i, dist[i]);
// Function to implement Dijkstra's algorithm
Algorithm Programs
void dijkstra(int graph[MAX_NODES][MAX_NODES], int src, int
num_nodes) {
int dist[MAX_NODES]; // Array to store the shortest distances from the
source
int visited[MAX_NODES]; // Array to keep track of visited vertices
// Initialize distances and visited array
for (int i = 0; i < num_nodes; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
dist[src] = 0; // Distance from source vertex to itself is always 0
// Find shortest paths for all vertices
for (int count = 0; count < num_nodes - 1; count++) {
int u = minDistance(dist, visited, num_nodes);
visited[u] = 1; // Mark the selected vertex as visited
// Update distance values of adjacent vertices
for (int v = 0; v < num_nodes; 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];
Algorithm Programs
// Print the shortest paths
printShortestPaths(dist, num_nodes);
int main() {
int graph[MAX_NODES][MAX_NODES] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
int num_nodes = 9; // Number of vertices in the graph
int source = 0; // Source vertex
dijkstra(graph, source, num_nodes);
Algorithm Programs
return 0;
Output:
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
4. Find the minimum cost spanning tree of a given undirected
graph using Prim’s algorithm.
#include <stdio.h>
#include <limits.h>
#define V 5 // Number of vertices in the graph
// Function to find the vertex with the minimum key value
int minKey(int key[], int mstSet[]) {
int min = INT_MAX, min_index;
Algorithm Programs
for (int v = 0; v < V; v++) {
if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
min_index = v;
return min_index;
// Function to print the minimum spanning tree
void printMST(int parent[], int graph[V][V]) {
printf("Edge Weight\n");
for (int i = 1; i < V; i++)
printf("%d - %d %d \n", parent[i], i, graph[i][parent[i]]);
// Function to implement Prim's algorithm for minimum spanning tree
void primMST(int graph[V][V]) {
int parent[V]; // Array to store constructed minimum spanning tree
int key[V]; // Key values used to pick minimum weight edge in cut
int mstSet[V]; // Array to represent set of vertices included in MST
// Initialize all keys as INFINITE and mstSet[] as false
Algorithm Programs
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = 0;
// Always include first vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
parent[0] = -1; // First node is always root of MST
// 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] = 1;
// 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]
Algorithm Programs
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
// Print the constructed MST
printMST(parent, graph);
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}
};
primMST(graph);
return 0;
}
Algorithm Programs
Output:
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
5. Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths
problem.
#include <stdio.h>
#include <limits.h>
#define V 4 // Number of vertices in the graph
// Function to print the solution matrix
void printSolution(int dist[][V]) {
printf("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] == INT_MAX)
printf("INF\t");
else
printf("%d\t", dist[i][j]);
printf("\n");
}
Algorithm Programs
// Function to implement Floyd's algorithm
void floydWarshall(int graph[][V]) {
int dist[V][V]; // Initialize the solution matrix
// Initialize the solution matrix same as the input graph matrix
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
// Update dist[][] to store the shortest path distances between every pair of
vertices
for (int k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (int i = 0; i < V; i++) {
// Pick all vertices as destination for the above picked source
for (int 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] != 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];
}
Algorithm Programs
// Print the shortest path matrix
printSolution(dist);
int main() {
// Example graph represented as an adjacency matrix
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}
};
// Call the function to find shortest paths between all pairs of vertices
floydWarshall(graph);
return 0;
Output:
Shortest distances between every pair of vertices:
0 5 8 9
INF 0 3 4
Algorithm Programs
INF INF 0 1
INF INF INF 0
6. Compute the transitive closure of a given directed graph using
Warshall's algorithm.
#include <stdio.h>
#define V 4 // Number of vertices in the graph
// Function to print the transitive closure matrix
void printTransitiveClosure(int tc[][V]) {
printf("Transitive Closure of the given graph:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf("%d ", tc[i][j]);
printf("\n");
// Function to compute the transitive closure using Warshall's algorithm
void transitiveClosure(int graph[][V]) {
int tc[V][V]; // Initialize the transitive closure matrix
// Initialize the transitive closure matrix same as the input graph matrix
for (int i = 0; i < V; i++)
Algorithm Programs
for (int j = 0; j < V; j++)
tc[i][j] = graph[i][j];
// Compute transitive closure matrix using Warshall's algorithm
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
tc[i][j] = tc[i][j] || (tc[i][k] && tc[k][j]);
// Print the transitive closure matrix
printTransitiveClosure(tc);
int main() {
// Example graph represented as an adjacency matrix
int graph[V][V] = {
{1, 1, 0, 1},
{0, 1, 1, 0},
{0, 0, 1, 1},
{0, 0, 0, 1}
};
Algorithm Programs
// Call the function to compute the transitive closure
transitiveClosure(graph);
return 0;
Output:
Transitive Closure of the given graph:
1111
0111
0011
0001
