Design & Analysis of Algorithm Practical Slips Programs
Design & Analysis of Algorithm Practical Slips Programs
Slip 1
Write a program to sort a list of n numbers in ascending order using selection sort and determine the time required to sort the elements.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap arr[minIndex] and arr[i]
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
int main() {
int n, i;
clock_t start, end;
double cpu_time_used;
printf("Enter the number of elements: ");
scanf("%d", &n);
int *arr = (int *)malloc(n * sizeof(int));
printf("Enter %d integers:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
start = clock();
selectionSort(arr, n);
end = clock();
printf("Sorted list in ascending order:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nTime taken to sort: %lf seconds\n", cpu_time_used);
free(arr); // Free dynamically allocated memory
return 0;
}
Write a program to sort a given set of elements using the Quick sort method 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. The elements can be read from a file or can be generated using the random number generator
#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 - 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() {
FILE *file;
file = fopen("numbers.txt", "w");
if (file == NULL) {
printf("Error opening file.\n");
return 1;
}
// Generate random numbers and write to file
srand(time(NULL));
int n_values[] = {10, 100, 1000, 10000}; // Different values of n
for (int k = 0; k < sizeof(n_values) / sizeof(n_values[0]); k++) {
int n = n_values[k];
fprintf(file, "n = %d\n", n);
for (int i = 0; i < n; i++) {
fprintf(file, "%d ", rand() % 1000);
}
fprintf(file, "\n");
}
fclose(file);
// Read numbers from file and sort using quick sort
file = fopen("numbers.txt", "r");
if (file == NULL) {
printf("Error opening file.\n");
return 1;
}
int num, n;
clock_t start, end;
double cpu_time_used;
while (fscanf(file, "n = %d", &n) == 1) {
int arr[n];
for (int i = 0; i < n; i++) {
fscanf(file, "%d", &arr[i]);
}
start = clock();
quickSort(arr, 0, n - 1);
end = clock();
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken to sort %d elements using Quick sort: %lf seconds\n", n, cpu_time_used);
}
fclose(file);
return 0;
}
Slip 2
Write a program to sort n randomly generated elements using Heapsort method
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int n;
clock_t start, end;
double cpu_time_used;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
// Generate random numbers and store them in arr
srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 1000; // Generating numbers between 0 and 999
}
printf("Unsorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
start = clock();
heapSort(arr, n);
end = clock();
printf("Sorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken to sort: %lf seconds\n", cpu_time_used);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
// Function to add two matrices
void add(int n, int A[][n], int B[][n], int C[][n]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
}
// Function to subtract two matrices
void subtract(int n, int A[][n], int B[][n], int C[][n]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = A[i][j] - B[i][j];
}
}
}
// Function to multiply two matrices using Strassen's algorithm
void strassen(int n, int A[][n], int B[][n], int C[][n]) {
if (n == 1) {
C[0][0] = A[0][0] * B[0][0];
return;
}
int newSize = n / 2;
int A11[newSize][newSize], A12[newSize][newSize], A21[newSize][newSize], A22[newSize][newSize];
int B11[newSize][newSize], B12[newSize][newSize], B21[newSize][newSize], B22[newSize][newSize];
int C11[newSize][newSize], C12[newSize][newSize], C21[newSize][newSize], C22[newSize][newSize];
int M1[newSize][newSize], M2[newSize][newSize], M3[newSize][newSize], M4[newSize][newSize], M5[newSize][newSize], M6[newSize][newSize], M7[newSize][newSize];
int temp1[newSize][newSize], temp2[newSize][newSize];
// Divide matrices A and B into 4 submatrices each
for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + newSize];
A21[i][j] = A[i + newSize][j];
A22[i][j] = A[i + newSize][j + newSize];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j + newSize];
B21[i][j] = B[i + newSize][j];
B22[i][j] = B[i + newSize][j + newSize];
}
}
// Calculate M1 to M7 matrices
add(newSize, A11, A22, temp1);
add(newSize, B11, B22, temp2);
strassen(newSize, temp1, temp2, M1);
add(newSize, A21, A22, temp1);
strassen(newSize, temp1, B11, M2);
subtract(newSize, B12, B22, temp1);
strassen(newSize, A11, temp1, M3);
subtract(newSize, B21, B11, temp1);
strassen(newSize, A22, temp1, M4);
add(newSize, A11, A12, temp1);
strassen(newSize, temp1, B22, M5);
subtract(newSize, A21, A11, temp1);
add(newSize, B11, B12, temp2);
strassen(newSize, temp1, temp2, M6);
subtract(newSize, A12, A22, temp1);
add(newSize, B21, B22, temp2);
strassen(newSize, temp1, temp2, M7);
// Calculate C matrices
add(newSize, M1, M4, temp1);
subtract(newSize, temp1, M5, temp2);
add(newSize, temp2, M7, C11);
add(newSize, M3, M5, C12);
add(newSize, M2, M4, C21);
add(newSize, M1, M3, temp1);
subtract(newSize, temp1, M2, temp2);
add(newSize, temp2, M6, C22);
// Combine C matrices into one result matrix C
for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
C[i][j] = C11[i][j];
C[i][j + newSize] = C12[i][j];
C[i + newSize][j] = C21[i][j];
C[i + newSize][j + newSize] = C22[i][j];
}
}
}
// Function to print a matrix
void printMatrix(int n, int A[][n]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d\t", A[i][j]);
}
printf("\n");
}
}
int main() {
int n;
printf("Enter the size of square matrices: ");
scanf("%d", &n);
if (n <= 0) {
printf("Invalid matrix size.\n");
return 1;
}
if (n & (n - 1)) {
printf("Matrix size must be a power of 2.\n");
return 1;
}
int A[n][n], B[n][n], C[n][n];
printf("Enter elements of matrix A:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &A[i][j]);
}
}
printf("Enter elements of matrix B:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &B[i][j]);
}
}
strassen(n, A, B, C);
printf("Resultant matrix C:\n");
printMatrix(n, C);
return 0;
}
Slip 3
Write a program to sort a given set of elements using the Quick sort method and determine the time required to sort the elements
#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 - 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 n;
clock_t start, end;
double cpu_time_used;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
start = clock();
quickSort(arr, 0, n - 1);
end = clock();
printf("Sorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken to sort: %lf seconds\n", cpu_time_used);
return 0;
}
Slip 4
Write a program to implement a Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Merge two subarrays of arr[].
// First subarray is arr[l..m].
// Second subarray is arr[m+1..r].
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temporary arrays back into arr[l..r]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// l is for left index and r is right index of the sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// Same as (l+r)/2, but avoids overflow for large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
int main() {
int n;
clock_t start, end;
double cpu_time_used;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
start = clock();
mergeSort(arr, 0, n - 1);
end = clock();
printf("Sorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken to sort: %lf seconds\n", cpu_time_used);
return 0;
}
Slip 5
Write a program for the Implementation of Kruskal’s algorithm to find minimum cost spanning tree
#include <stdio.h>
#include <stdlib.h>
// Structure to represent an edge in the graph
struct Edge {
int src, dest, weight;
};
// Structure to represent a subset for union-find
struct Subset {
int parent;
int rank;
};
// Function to find set of an element i
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// Function that does union of two sets of x and y
void Union(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high rank tree
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// Comparator function for sorting edges based on their weights
int compare(const void *a, const void *b) {
struct Edge *a1 = (struct Edge *)a;
struct Edge *b1 = (struct Edge *)b;
return a1->weight - b1->weight;
}
// Function to find the Minimum Cost Spanning Tree using Kruskal's algorithm
void KruskalMST(struct Edge edges[], int V, int E) {
struct Edge result[V]; // This will store the resultant MST
int e = 0; // Index variable for result[]
// Sort all the edges in non-decreasing order of their weight
qsort(edges, E, sizeof(edges[0]), compare);
// Allocate memory for creating V subsets
struct Subset *subsets = (struct Subset *)malloc(V * sizeof(struct Subset));
// Create V subsets with single elements
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Number of edges to be taken is equal to V-1
while (e < V - 1 && E > 0) {
// Pick the smallest edge. Increment the index for the next iteration
struct Edge next_edge = edges[E - 1];
E--;
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge does't cause cycle, include it in result and increment the index
if (x != y) {
result[e] = next_edge;
e++;
Union(subsets, x, y);
}
}
// Print the Minimum Cost Spanning Tree
printf("Edges in the Minimum Cost Spanning Tree:\n");
for (int i = 0; i < e; i++) {
printf("%d - %d : %d\n", result[i].src, result[i].dest, result[i].weight);
}
free(subsets);
}
int main() {
int V, E;
printf("Enter the number of vertices and edges: ");
scanf("%d %d", &V, &E);
struct Edge edges[E];
printf("Enter the source, destination, and weight of each edge:\n");
for (int i = 0; i < E; i++) {
printf("Edge %d: ", i + 1);
scanf("%d %d %d", &edges[i].src, &edges[i].dest, &edges[i].weight);
}
KruskalMST(edges, V, E);
return 0;
}
Slip 6
Write a program for the Implementation of Prim’s algorithm to find minimum cost spanning tree.
#include <stdio.h>
#include <limits.h>
#define V 5 // Number of vertices in the graph
// Function to find the vertex with minimum key value, from the set of vertices not yet included in MST
int minKey(int key[], int mstSet[]) {
int min = INT_MAX, min_index;
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 constructed MST stored in parent[]
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 construct and print MST for a graph represented using adjacency matrix representation
void primMST(int graph[V][V]) {
int parent[V]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge in cut
int mstSet[V]; // To represent set of vertices not yet included in MST
// Initialize all keys as INFINITE
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++) {
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() {
// Example graph represented using adjacency matrix
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 MST
printf("Minimum Spanning Tree using Prim's algorithm:\n");
primMST(graph);
return 0;
}
Slip 7
Write a program for the Implementation of Dijkstra’s algorithm to find shortest path to other vertices
#include <stdio.h>
#include <limits.h>
#define V 9 // Number of vertices in the graph
// Function to find the vertex with minimum distance value, from the set of vertices not yet included in shortest path tree
int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == 0 && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// Function to print the constructed distance array
void printSolution(int dist[]) {
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
}
// Function that implements Dijkstra's single source shortest path algorithm for a graph represented using adjacency matrix
void dijkstra(int graph[V][V], int src) {
int dist[V]; // The output array. dist[i] will hold the shortest distance from src to i
int sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and sptSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = 0;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed. u is always equal to src in the first iteration
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = 1;
// Update dist value of the adjacent vertices of the picked vertex
for (int v = 0; v < V; v++)
// Update dist[v] only if it's not in sptSet, there's an edge from u to v, and the total weight of path from src to v through u is smaller than current value of dist[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];
}
// Print the constructed distance array
printSolution(dist);
}
int main() {
// Example graph represented using adjacency matrix
int graph[V][V] = {
{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}
};
dijkstra(graph, 0);
return 0;
}
Slip 8
Write a program to implement Fractional Knapsack problems using Greedy Method
#include <stdio.h>
#include <stdlib.h>
// Structure to represent an item
struct Item {
int value;
int weight;
double ratio; // Value-to-weight ratio
};
// Comparator function for sorting items based on value-to-weight ratio in non-increasing order
int compare(const void *a, const void *b) {
double ratioA = ((struct Item *)a)->ratio;
double ratioB = ((struct Item *)b)->ratio;
return (ratioB > ratioA) ? 1 : -1;
}
// Function to solve fractional knapsack problem using greedy method
void fractionalKnapsack(struct Item items[], int n, int capacity) {
// Sort items based on value-to-weight ratio in non-increasing order
qsort(items, n, sizeof(items[0]), compare);
int currentWeight = 0; // Current weight in knapsack
double finalValue = 0.0; // Final value of items taken
printf("Items selected:\n");
// Loop through sorted items and add them to knapsack greedily
for (int i = 0; i < n; i++) {
// If adding the entire item doesn't exceed the capacity, add it fully
if (currentWeight + items[i].weight <= capacity) {
currentWeight += items[i].weight;
finalValue += items[i].value;
printf("Item with value %d and weight %d\n", items[i].value, items[i].weight);
} else {
// Otherwise, take a fraction of the item to fill the knapsack
int remainingWeight = capacity - currentWeight;
finalValue += items[i].value * ((double)remainingWeight / items[i].weight);
printf("Item with value %d and weight %d (fraction %.2lf)\n", items[i].value, items[i].weight, ((double)remainingWeight / items[i].weight));
break; // Knapsack is full
}
}
printf("Total value obtained: %.2lf\n", finalValue);
}
int main() {
int n, capacity;
printf("Enter the number of items: ");
scanf("%d", &n);
struct Item items[n];
printf("Enter the value and weight of each item:\n");
for (int i = 0; i < n; i++) {
printf("Item %d: ", i + 1);
scanf("%d %d", &items[i].value, &items[i].weight);
items[i].ratio = (double)items[i].value / items[i].weight;
}
printf("Enter the capacity of the knapsack: ");
scanf("%d", &capacity);
fractionalKnapsack(items, n, capacity);
return 0;
}
Slip 9
Write a program to implement optimal binary search tree and also calculate the best-case complexity
#include <stdio.h>
#include <limits.h>
#define MAX_KEYS 10
// Function to find the minimum of two values
int min(int a, int b) {
return (a < b) ? a : b;
}
// Function to construct optimal binary search tree
void constructOBST(int keys[], int freq[], int n) {
int cost[n][n];
// cost[i][j] will store the cost of the optimal binary search tree with keys[i] to keys[j]
// Initialize cost[i][i] to the frequency of the single key at i
for (int i = 0; i < n; i++)
cost[i][i] = freq[i];
// For chains of length 2 to n
for (int chainLen = 2; chainLen <= n; chainLen++) {
// For each chain starting at i
for (int i = 0; i <= n - chainLen + 1; i++) {
// Get the end of the chain
int j = i + chainLen - 1;
cost[i][j] = INT_MAX;
// Try making each key in the chain the root
for (int k = i; k <= j; k++) {
// Cost when keys[k] is root
int rootCost = ((k > i) ? cost[i][k - 1] : 0) +
((k < j) ? cost[k + 1][j] : 0) +
freq[k];
cost[i][j] = min(cost[i][j], rootCost);
}
}
}
printf("Cost of optimal binary search tree is: %d\n", cost[0][n - 1]);
}
int main() {
int keys[MAX_KEYS] = {10, 20, 30, 40, 50};
int freq[MAX_KEYS] = {4, 2, 6, 3, 1};
int n = sizeof(keys) / sizeof(keys[0]);
constructOBST(keys, freq, n);
return 0;
}
Slip 11
) Write a programs to implement DFS (Depth First Search) and determine the time complexity for the same
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// Structure for an adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Structure for an adjacency list
struct AdjList {
struct AdjListNode* head;
};
// Structure for a graph
struct Graph {
int V;
struct AdjList* array;
};
// Function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// Function to create a graph with V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Function to add an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// Function to perform DFS recursively
void DFSUtil(struct Graph* graph, int v, bool visited[]) {
visited[v] = true;
printf("%d ", v);
struct AdjListNode* temp = graph->array[v].head;
while (temp) {
if (!visited[temp->dest])
DFSUtil(graph, temp->dest, visited);
temp = temp->next;
}
}
// Function to perform Depth First Search traversal
void DFS(struct Graph* graph, int startVertex) {
bool* visited = (bool*)malloc(graph->V * sizeof(bool));
for (int i = 0; i < graph->V; i++)
visited[i] = false;
DFSUtil(graph, startVertex, visited);
free(visited);
}
int main() {
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printf("DFS traversal starting from vertex 0: ");
DFS(graph, 0);
printf("\n");
return 0;
}
Slip 12
Write a program to implement BFS (Breadth First Search) and determine the time complexity for the same
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// Structure for an adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Structure for an adjacency list
struct AdjList {
struct AdjListNode* head;
};
// Structure for a graph
struct Graph {
int V;
struct AdjList* array;
};
// Structure for a queue node used in BFS
struct QueueNode {
int data;
struct QueueNode* next;
};
// Structure for a queue used in BFS
struct Queue {
struct QueueNode *front, *rear;
};
// Function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// Function to create a graph with V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Function to add an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// Function to create a new queue node
struct QueueNode* newQueueNode(int data) {
struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to create a queue
struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
// Function to enqueue an element into the queue
void enqueue(struct Queue* q, int data) {
struct QueueNode* newNode = newQueueNode(data);
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
// Function to dequeue an element from the queue
int dequeue(struct Queue* q) {
if (q->front == NULL)
return -1;
struct QueueNode* temp = q->front;
int data = temp->data;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
free(temp);
return data;
}
// Function to perform Breadth First Search traversal
void BFS(struct Graph* graph, int startVertex) {
bool* visited = (bool*)malloc(graph->V * sizeof(bool));
for (int i = 0; i < graph->V; i++)
visited[i] = false;
struct Queue* queue = createQueue();
visited[startVertex] = true;
enqueue(queue, startVertex);
while (queue->front != NULL) {
int currentVertex = dequeue(queue);
printf("%d ", currentVertex);
struct AdjListNode* temp = graph->array[currentVertex].head;
while (temp) {
int adjVertex = temp->dest;
if (!visited[adjVertex]) {
visited[adjVertex] = true;
enqueue(queue, adjVertex);
}
temp = temp->next;
}
}
}
int main() {
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printf("BFS traversal starting from vertex 0: ");
BFS(graph, 0);
printf("\n");
return 0;
}
Slip 13
Write a program to find minimum number of multiplications in Matrix Chain Multiplication
#include <stdio.h>
#include <limits.h>
// Function to find the minimum number of multiplications in matrix chain multiplication
int matrixChainOrder(int p[], int n) {
int m[n][n];
// cost is zero when multiplying one matrix.
for (int i = 1; i < n; i++)
m[i][i] = 0;
// L is chain length.
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
int j = i + L - 1;
m[i][j] = INT_MAX;
for (int k = i; k <= j - 1; k++) {
int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
int main() {
int arr[] = {10, 30, 5, 60};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications is %d\n", matrixChainOrder(arr, size));
return 0;
}
Slip 14
Write a program to sort a list of n numbers in ascending order using Insertion sort and determine the time required to sort the elements.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to perform 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;
}
}
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
// Measure the time taken to perform insertion sort
clock_t start_time = clock();
insertionSort(arr, n);
clock_t end_time = clock();
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
// Calculate the time taken in seconds
double time_taken = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;
printf("Time taken to sort the elements: %f seconds\n", time_taken);
return 0;
}
Slip 15
Write a program to implement to find out solution for 0/1 knapsack problem using LCBB (Least Cost Branch and Bound)
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a node in the priority queue
struct Node {
int level;
int profit;
int weight;
float bound;
};
// Function to swap two nodes
void swap(struct Node* a, struct Node* b) {
struct Node t = *a;
*a = *b;
*b = t;
}
// Function to perform min-heapify operation
void minHeapify(struct Node* heap, int i, int size) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && heap[left].bound < heap[smallest].bound)
smallest = left;
if (right < size && heap[right].bound < heap[smallest].bound)
smallest = right;
if (smallest != i) {
swap(&heap[i], &heap[smallest]);
minHeapify(heap, smallest, size);
}
}
// Function to build a min-heap
void buildMinHeap(struct Node* heap, int size) {
for (int i = size / 2 - 1; i >= 0; i--)
minHeapify(heap, i, size);
}
// Function to extract the minimum node from the priority queue
struct Node extractMin(struct Node* heap, int* size) {
struct Node minNode = heap[0];
heap[0] = heap[*size - 1];
(*size)--;
minHeapify(heap, 0, *size);
return minNode;
}
// Function to calculate the bound of a node
float calculateBound(struct Node u, int n, int W, int* wt, int* val) {
if (u.weight >= W)
return 0;
float bound = u.profit;
int j = u.level + 1;
int totalWeight = u.weight;
while (j < n && totalWeight + wt[j] <= W) {
bound += val[j];
totalWeight += wt[j];
j++;
}
if (j < n)
bound += (W - totalWeight) * ((float)val[j] / wt[j]);
return bound;
}
// Function to solve the 0/1 Knapsack Problem using LCBB
int knapsack(int W, int wt[], int val[], int n) {
struct Node* heap = (struct Node*)malloc(sizeof(struct Node) * (n + 1));
int heapSize = 0;
struct Node u, v;
u.level = -1;
u.profit = u.weight = 0;
u.bound = calculateBound(u, n, W, wt, val);
heap[heapSize++] = u;
int maxProfit = 0;
while (heapSize > 0) {
u = extractMin(heap, &heapSize);
if (u.bound > maxProfit) {
v.level = u.level + 1;
v.weight = u.weight + wt[v.level];
v.profit = u.profit + val[v.level];
if (v.weight <= W && v.profit > maxProfit)
maxProfit = v.profit;
v.bound = calculateBound(v, n, W, wt, val);
if (v.bound > maxProfit)
heap[heapSize++] = v;
v.weight = u.weight;
v.profit = u.profit;
v.bound = calculateBound(v, n, W, wt, val);
if (v.bound > maxProfit)
heap[heapSize++] = v;
}
}
free(heap);
return maxProfit;
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printf("Maximum value that can be obtained is %d\n", knapsack(W, wt, val, n));
return 0;
}
Slip 16
Write a program to implement to find out solution for 0/1 knapsack problem using dynamic programming.
#include <stdio.h>
// Function to find the maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// Function to solve the 0/1 Knapsack problem using dynamic programming
int knapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
// Build table K[][] in bottom-up manner
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printf("Maximum value that can be obtained is %d\n", knapSack(W, wt, val, n));
return 0;
}
Write a program to determine if a given graph is a Hamiltonian cycle or not.
#include <stdio.h>
#include <stdbool.h>
#define V 5 // Number of vertices in the graph
// Function to check if the vertex v can be added at index pos in the Hamiltonian Cycle
bool isSafe(int v, bool graph[V][V], int path[], int pos) {
// Check if this vertex is an adjacent vertex of the previously added vertex
if (!graph[path[pos - 1]][v])
return false;
// Check if the vertex has already been included
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
// Function to recursively solve the Hamiltonian Cycle problem
bool hamCycleUtil(bool graph[V][V], int path[], int pos) {
// Base case: if all vertices are included in the path
if (pos == V) {
// And if there is an edge from the last included vertex to the first vertex
if (graph[path[pos - 1]][path[0]])
return true;
else
return false;
}
// Try different vertices as the next candidate in the path
for (int v = 1; v < V; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1) == true)
return true;
path[pos] = -1;
}
}
// If no vertex can be added to the path
return false;
}
// Function to solve the Hamiltonian Cycle problem
bool hamCycle(bool graph[V][V]) {
int path[V];
for (int i = 0; i < V; i++)
path[i] = -1;
// Start from the first vertex (vertex 0) as the first vertex in the path
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false) {
printf("Solution does not exist\n");
return false;
}
// Print the solution
printf("Solution exists: Following is one Hamiltonian cycle\n");
for (int i = 0; i < V; i++)
printf("%d ", path[i]);
printf("%d ", path[0]); // Include the first vertex again to form a cycle
printf("\n");
return true;
}
int main() {
bool graph[V][V] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0}
};
hamCycle(graph);
return 0;
}
Slip 17
Write a program to implement solve ‘N’ Queens Problem using Backtracking
#include <stdio.h>
#include <stdbool.h>
#define N 4 // Number of queens
// Function to print the solution matrix
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");
}
}
// Function to check if a queen can be placed on board[row][col]
bool isSafe(int board[N][N], int row, int col) {
int i, j;
// Check this row on the 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;
}
// Recursive function to solve N Queens problem
bool solveNQUtil(int board[N][N], int col) {
// Base case: If all queens are placed, 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 it
board[i][col] = 0;
}
}
// If the queen can't be placed in any row in this column, return false
return false;
}
// Function to solve the N Queens problem
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\n");
return false;
}
printSolution(board);
return true;
}
int main() {
solveNQ();
return 0;
}
Slip 18
Write a program to implement Graph Coloring Algorithm
#include <stdio.h>
#include <stdbool.h>
#define V 4 // Number of vertices in the graph
// Function to check if it is safe to assign color c to vertex v
bool isSafe(int v, bool graph[V][V], int color[], int c) {
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;
return true;
}
// Function to recursively solve graph coloring problem
bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) {
// Base case: If all vertices are assigned a color
if (v == V)
return true;
// Consider this vertex v and try different colors
for (int c = 1; c <= m; c++) {
// Check if assignment of color c to v is possible
if (isSafe(v, graph, color, c)) {
color[v] = c;
// Recur to assign colors to rest of the vertices
if (graphColoringUtil(graph, m, color, v + 1))
return true;
// If assigning color c doesn't lead to a solution, then remove it
color[v] = 0;
}
}
// If no color can be assigned to this vertex
return false;
}
// Function to solve graph coloring problem
bool graphColoring(bool graph[V][V], int m) {
int color[V];
for (int i = 0; i < V; i++)
color[i] = 0;
if (!graphColoringUtil(graph, m, color, 0)) {
printf("Solution does not exist\n");
return false;
}
// Print the solution
printf("Solution exists: Following are the assigned colors\n");
for (int i = 0; i < V; i++)
printf("Vertex %d --> Color %d\n", i, color[i]);
return true;
}
int main() {
bool graph[V][V] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
int m = 3; // Number of colors
graphColoring(graph, m);
return 0;
}
Slip 19
Write a program to determine if a given graph is a Hamiltonian cycle or not.
#include <stdio.h>
#include <stdbool.h>
#define V 5 // Number of vertices in the graph
// Function to check if the vertex v can be added at index pos in the Hamiltonian Cycle
bool isSafe(int v, bool graph[V][V], int path[], int pos) {
// Check if this vertex is an adjacent vertex of the previously added vertex
if (!graph[path[pos - 1]][v])
return false;
// Check if the vertex has already been included
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
// Function to recursively solve the Hamiltonian Cycle problem
bool hamCycleUtil(bool graph[V][V], int path[], int pos) {
// Base case: if all vertices are included in the path
if (pos == V) {
// And if there is an edge from the last included vertex to the first vertex
if (graph[path[pos - 1]][path[0]])
return true;
else
return false;
}
// Try different vertices as the next candidate in the path
for (int v = 1; v < V; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1) == true)
return true;
path[pos] = -1;
}
}
// If no vertex can be added to the path
return false;
}
// Function to solve the Hamiltonian Cycle problem
bool hamCycle(bool graph[V][V]) {
int path[V];
for (int i = 0; i < V; i++)
path[i] = -1;
// Start from the first vertex (vertex 0) as the first vertex in the path
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false) {
printf("Solution does not exist\n");
return false;
}
// Print the solution
printf("Solution exists: Following is one Hamiltonian cycle\n");
for (int i = 0; i < V; i++)
printf("%d ", path[i]);
printf("%d ", path[0]); // Include the first vertex again to form a cycle
printf("\n");
return true;
}
int main() {
bool graph[V][V] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0}
};
hamCycle(graph);
return 0;
}
Write a program to show board configuration of 4 queens’ problem.
#include <stdio.h>
#define N 4
// Function to print the board configuration
void printBoard(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");
}
}
int main() {
// Initial board configuration with no queens
int board[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0} };
// Placing queens on the board
// In this example, we'll place one queen in each row
board[0][1] = 1; // Placing queen at (0, 1)
board[1][3] = 1; // Placing queen at (1, 3)
board[2][0] = 1; // Placing queen at (2, 0)
board[3][2] = 1; // Placing queen at (3, 2)
// Print the board configuration
printf("Board Configuration:\n");
printBoard(board);
return 0;
}
Slip 20
Write a program to implement for finding Topological sorting and determine the time complexity for the same
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define V 6 // Number of vertices
// Structure to represent a node in the adjacency list
struct Node {
int vertex;
struct Node* next;
};
// Structure to represent the adjacency list
struct Graph {
struct Node** adjList;
bool* visited;
};
// Function to create a new node
struct Node* createNode(int v) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Function to create a graph with V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->adjList = (struct Node**)malloc(V * sizeof(struct Node*));
graph->visited = (bool*)malloc(V * sizeof(bool));
for (int i = 0; i < V; i++) {
graph->adjList[i] = NULL;
graph->visited[i] = false;
}
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
// Add an edge from src to dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
}
// Function to perform Depth First Search (DFS) and store the topological order
void topologicalSortUtil(struct Graph* graph, int v, bool visited[], int* stackIndex, int* stack) {
visited[v] = true;
struct Node* temp = graph->adjList[v];
while (temp != NULL) {
if (!visited[temp->vertex])
topologicalSortUtil(graph, temp->vertex, visited, stackIndex, stack);
temp = temp->next;
}
stack[(*stackIndex)++] = v;
}
// Function to perform topological sorting
void topologicalSort(struct Graph* graph) {
int stack[V];
int stackIndex = 0;
bool* visited = (bool*)malloc(V * sizeof(bool));
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(graph, i, visited, &stackIndex, stack);
}
// Print the topological order
printf("Topological Sorting: ");
for (int i = V - 1; i >= 0; i--)
printf("%d ", stack[i]);
printf("\n");
free(visited);
}
int main() {
struct Graph* graph = createGraph(V);
addEdge(graph, 5, 2);
addEdge(graph, 5, 0);
addEdge(graph, 4, 0);
addEdge(graph, 4, 1);
addEdge(graph, 2, 3);
addEdge(graph, 3, 1);
topologicalSort(graph);
return 0;
}
End
Comments
Post a Comment
hey