1.

Aim:

develop a program and measure the running time for binary search with divide and conquer

program:

#include <stdio.h>

#include <time.h>

Int binary_search(int arr[], int low, int high, int key)

if (high >= low) {

int mid = low + (high - low) / 2;

if (arr[mid] == key) {

return mid;

if (arr[mid] > key) {

return binary_search(arr, low, mid - 1, key);

return binary_search(arr, mid + 1, high, key);

return -1; // Key not found

int main()

int arr[] = {2, 3, 4, 10, 40};

int n = sizeof(arr) / sizeof(arr[0]);

int key = 10;

clock_t start = clock();

int result = binary_search(arr, 0, n - 1, key);

 clock_t end = clock();

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

if (result == -1) {

printf("Element is not present in array\n");

} else {

printf("Element is present at index %d\n", result);

printf("Time taken: %f seconds\n", time_taken);

return 0;

Output:

Element is present at index 3

Time taken: 0.000001 seconds

2. develop a program and measure the running time for merge sort with divide and conquer
using c

Program:

#include <stdio.h>
#include <time.h>

void merge(int arr[], int left, int mid, int right) {

int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

int L[n1], R[n2];

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

L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

i = 0;
j = 0;
k = left;
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 left, int right) {

if (left < right) {
int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

}
}

int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

clock_t start, end;

double time_taken;

start = clock();
mergeSort(arr, 0, n - 1);
end = clock();

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

 printf("Sorted array: \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);

printf("\nTime taken: %f seconds\n", time_taken);

return 0;
}
Output:

Sorted array:

11 12 22 25 34 64 90

Time taken: 0.000002 seconds

3. develop a program and measure the running time for Quick sort with divide and conquer
using c

Program:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

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

{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; 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);
}
}

void printArray(int arr[], int size)

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

int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
clock_t start, end;
double cpu_time_used;
start = clock(); // Start time measurement
quickSort(arr, 0, n - 1);
end = clock(); // End time measurement
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Sorted array: \n");
printArray(arr, n);
printf("\nTime taken: %f seconds\n", cpu_time_used);
return 0;
}
Output:
Sorted array:
1 5 7 8 9 10
Time taken: 0.000001 seconds
4. Develop a program and measure the running time for estimating minimum cost
spanning tree with greedy method using java.
Program:
import java.util.ArrayList;
import java.util.PriorityQueue;
class Graph {
int V;
ArrayList<ArrayList<Node>> adjList;
public Graph(int V)
{
this.V = V;
adjList = new ArrayList<>();
for (int i = 0; i < V; i++) {
adjList.add(new ArrayList<>());
}
}
 public void addEdge(int u, int v, int weight) {
adjList.get(u).add(new Node(v, weight));
adjList.get(v).add(new Node(u, weight));
}
public void primMST() {
PriorityQueue<Node> pq = new PriorityQueue<>();
boolean[] visited = new boolean[V];
pq.add(new Node(0, 0)); // Add the starting vertex with weight 0
int cost = 0;
while (!pq.isEmpty()) {
Node node = pq.poll();
int u = node.vertex;
if (visited[u]) continue;
visited[u] = true;
cost += node.weight;
for (Node neighbor : adjList.get(u)) {
if (!visited[neighbor.vertex]) {
pq.add(neighbor);
}
}
}

System.out.println("Total cost of MST: " + cost);

}

public static void main(String[] args)

{
// Create a sample graph
Graph g = new Graph(5);
g.addEdge(0, 1, 2);
g.addEdge(0, 3, 6);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 8);
g.addEdge(1, 4, 5);
g.addEdge(2, 4, 7);
g.addEdge(3, 4, 9);
long startTime = System.nanoTime();
g.primMST();
long endTime = System.nanoTime();
double runningTime = (endTime - startTime) / 1e9;
System.out.println("Running time: " + runningTime + " seconds");
}
static class Node implements Comparable<Node>
{
int vertex;
int weight;
public Node(int vertex, int weight) {
this.vertex = vertex;
 this.weight = weight;
}
@Override
public int compareTo(Node other) {
return this.weight - other.weight;
}
}
}
Output:
Total cost of MST: 16
Running time: 0.10363484 seconds

7. develop a program and measure the running time for identifying solution for traveling salesperson
problem with dynamic programming using c
Program:

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#include <time.h>

#define MAX_N 10

int n;

int graph[MAX_N][MAX_N];

int memo[MAX_N][1 << MAX_N]; // Memoization table for dynamic programming

// Function to find the minimum cost Hamiltonian cycle using dynamic programming

int tsp(int current, int mask) {

if (mask == (1 << n) - 1) {

return graph[current][0]; // Return to the starting city

if (memo[current][mask] != -1) {

return memo[current][mask];

int minCost = INT_MAX;

 for (int next = 0; next < n; next++) {

if ((mask & (1 << next)) == 0) {

int cost = graph[current][next] + tsp(next, mask | (1 << next));

minCost = (cost < minCost) ? cost : minCost;

memo[current][mask] = minCost;

return minCost;

int main() {

printf("Enter the number of cities (maximum %d): ", MAX_N);

scanf("%d", &n);

printf("Enter the cost matrix (0 for unreachable cities):\n");

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

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

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

// Initialize memoization table with -1

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

for (int j = 0; j < (1 << MAX_N); j++) {

memo[i][j] = -1;

clock_t start_time = clock();

 int minCost = tsp(0, 1); // Start from city 0 with mask representing only city 0 visited

clock_t end_time = clock();

printf("Minimum cost of the Hamiltonian cycle: %d\n", minCost);

double elapsed_time = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;

printf("Running time: %f seconds\n", elapsed_time);

return 0;

Output:

/tmp/b47SILh8lX.o

Enter the number of cities (maximum 10): 4

Enter the cost matrix (0 for unreachable cities):

0 10 15 20

10 0 35 25

15 35 0 30

20 25 30 0

Minimum cost of the Hamiltonian cycle: 80

Running time: 0.000002 seconds

5. develop a program and measure the running time for estimating single
source shortest paths with greedy method

Program:

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#include <stdbool.h>

#include <time.h>
#define MAX_VERTICES 100

// Structure to represent a weighted directed graph

struct Graph {

int vertices;

int** adjMatrix;

};

// Function to create a new graph with the given number of vertices

struct Graph* createGraph(int vertices) {

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

graph->vertices = vertices;

// Allocate memory for the adjacency matrix

graph->adjMatrix = (int**)malloc(vertices * sizeof(int*));

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

graph->adjMatrix[i] = (int*)malloc(vertices * sizeof(int));

for (int j = 0; j < vertices; j++) {

graph->adjMatrix[i][j] = 0;

return graph;

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest, int weight) {

graph->adjMatrix[src][dest] = weight;

}
// Function to find the vertex with the minimum distance value

int minDistance(int distance[], bool visited[], int vertices) {

int min = INT_MAX, minIndex;

for (int v = 0; v < vertices; v++) {

if (!visited[v] && distance[v] <= min) {

min = distance[v];

minIndex = v;

return minIndex;

// Function to print the solution (shortest distances from the source)

void printSolution(int distance[], int vertices) {

printf("Vertex Distance from Source\n");

for (int i = 0; i < vertices; i++)

printf("%d \t\t %d\n", i, distance[i]);

// Function to perform Dijkstra's algorithm

void dijkstra(struct Graph* graph, int src) {

int vertices = graph->vertices;

int distance[MAX_VERTICES];

bool visited[MAX_VERTICES];

// Initialize distances and visited array

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

 distance[i] = INT_MAX;

visited[i] = false;

distance[src] = 0;

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

int u = minDistance(distance, visited, vertices);

visited[u] = true;

for (int v = 0; v < vertices; v++) {

if (!visited[v] && graph->adjMatrix[u][v] && distance[u] != INT_MAX &&

distance[u] + graph->adjMatrix[u][v] < distance[v]) {

distance[v] = distance[u] + graph->adjMatrix[u][v];

printSolution(distance, vertices);

int main() {

int vertices, edges;

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

scanf("%d", &vertices);

struct Graph* graph = createGraph(vertices);

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

scanf("%d", &edges);

printf("Enter edges (source destination weight):\n");

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

 int src, dest, weight;

scanf("%d %d %d", &src, &dest, &weight);

addEdge(graph, src, dest, weight);

int source;

printf("Enter the source vertex: ");

scanf("%d", &source);

clock_t start_time = clock();

dijkstra(graph, source);

clock_t end_time = clock();

double elapsed_time = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;

printf("Running time: %f seconds\n", elapsed_time);

return 0;

Output:

Enter the number of vertices:

6. develop a program and measure the running time for optimal binary search
tree with dynamic programming using java

Program:

import java.util.Scanner;

public class OptimalBinarySearchTree {

// Function to calculate the sum of probabilities from i to j

private static float sumOfProbabilities(float probabilities[], int i, int j) {

 float sum = 0;

for (int k = i; k <= j; k++) {

sum += probabilities[k];

return sum;

// Function to construct the optimal binary search tree

private static void optimalBST(float probabilities[]) {

int n = probabilities.length;

float cost[][] = new float[n + 1][n + 1];

float sumProbabilities[][] = new float[n + 1][n + 1];

// Calculate the sum of probabilities for all subproblems

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

sumProbabilities[i][i] = probabilities[i];

for (int j = i + 1; j < n; j++) {

sumProbabilities[i][j] = sumProbabilities[i][j - 1] + probabilities[j];

// Initialize the cost matrix

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

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

cost[i][j] = 0;

// Build the cost matrix

for (int len = 1; len <= n; len++) {

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

 int j = i + len - 1;

cost[i][j] = Float.MAX_VALUE;

for (int r = i; r <= j; r++) {

float c = ((r > i) ? cost[i][r - 1] : 0) +

((r < j) ? cost[r + 1][j] : 0) +

sumOfProbabilities(probabilities, i, j);

cost[i][j] = Math.min(c, cost[i][j]);

System.out.println("Minimum cost of optimal binary search tree: " + cost[0][n - 1]);

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("Enter the number of keys: ");

int n = scanner.nextInt();

float probabilities[] = new float[n];

System.out.println("Enter the probabilities for each key:");

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

probabilities[i] = scanner.nextFloat();

long startTime = System.currentTimeMillis();

optimalBST(probabilities);

long endTime = System.currentTimeMillis();

double elapsedTime = (endTime - startTime) / 1000.0;

System.out.println("Running time: " + elapsedTime + " seconds");

scanner.close();
 }

Output:

Enter the number of keys: 5

Enter the probabilities for each key:

Minimum cost of optimal binary search tree: 35.0Running time: 0.016 seconds