Daa
Example heading with h2 size
Example heading with h3 size
Following is sample java code.
int i = 10;
if(i>0){
System.out.println('positive');
}
```C Code Solutions for CS-554-MJP Lab Course
Savitribai Phule University
M.Sc. (Computer Science) Sem-II
Practical Examination (Design and Analysis of Algorithms)
Date: April 15, 2025
---
1. Selection Sort (Slip 1, Q1)
Problem: 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.
Code:
#include <stdio.h>
#include <time.h>
void selectionSort(int arr[], int n) {
int i, j, min_idx, temp;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements: ", n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
clock_t start = clock();
selectionSort(arr, n);
clock_t end = clock();
printf("Sorted array: ");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\nTime taken: %f seconds\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}
Explanation:
- Algorithm: Selection sort finds the minimum element in the unsorted portion and swaps it with the first element of the unsorted portion.
- Time Complexity: O(n²).
- Time Measurement: Uses clock() to measure execution time.
- Input: User provides the number of elements and the elements themselves.
---
2. Quick Sort (Slip 1, Q2)
Problem: 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 for different values of n, with elements read from a file or generated randomly.
Code:
#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, j;
for (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);
}
}
int main() {
int n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
// Generate random elements
srand(time(0));
for (i = 0; i < n; i++)
arr[i] = rand() % 1000; // Random numbers between 0 and 999
printf("Original array: ");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
clock_t start = clock();
quickSort(arr, 0, n - 1);
clock_t end = clock();
printf("Sorted array: ");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\nTime taken: %f seconds\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}
Explanation:
- Algorithm: Quick sort selects a pivot, partitions the array around it, and recursively sorts the subarrays.
- Time Complexity: Average O(n log n), worst O(n²).
- Random Input: Uses rand() to generate random numbers.
- Time Measurement: Uses clock() for timing.
- Note: To read from a file, replace the random generation with file input using fscanf().
---
3. Prim’s Algorithm (Slip 6, Q1)
Problem: Write a program for the implementation of Prim’s algorithm to find the minimum cost spanning tree.
Code:
#include <stdio.h>
#include <limits.h>
#define V 5 // Number of vertices
int minKey(int key[], int mstSet[], int n) {
int min = INT_MAX, min_index, v;
for (v = 0; v < n; v++)
if (mstSet[v] == 0 && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
void primMST(int graph[V][V]) {
int parent[V], key[V], mstSet[V], i, v, u;
for (i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = 0;
key[0] = 0;
parent[0] = -1;
for (i = 0; i < V - 1; i++) {
u = minKey(key, mstSet, V);
mstSet[u] = 1;
for (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];
}
printf("Edge \tWeight\n");
int total = 0;
for (i = 1; i < V; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
total += graph[i][parent[i]];
}
printf("Total MST weight: %d\n", total);
}
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;
}
Explanation:
- Algorithm: Prim’s algorithm builds a minimum spanning tree by selecting the smallest edge connecting a vertex in the MST to a vertex outside it.
- Time Complexity: O(V²) with adjacency matrix.
- Input: Hardcoded 5x5 adjacency matrix; 0 indicates no edge.
- Output: Prints edges and weights of the MST and total weight.
---
4. N-Queens Problem (Slip 17, Q1)
Problem: Write a program to implement the N-Queens problem using backtracking.
Code:
#include <stdio.h>
#include <stdbool.h>
#define N 4 // Board size (4x4 for 4-Queens)
void printSolution(int board[N][N]) {
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
printf("%d ", board[i][j]);
printf("\n");
}
printf("\n");
}
bool isSafe(int board[N][N], int row, int col) {
int i, j;
// Check row on left
for (i = 0; i < col; i++)
if (board[row][i])
return false;
// Check upper diagonal on left
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
// Check lower diagonal on left
for (i = row, j = col; i < N && j >= 0; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQueensUtil(int board[N][N], int col) {
if (col >= N)
return true;
int i;
for (i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueensUtil(board, col + 1))
return true;
board[i][col] = 0; // Backtrack
}
}
return false;
}
void solveNQueens() {
int board[N][N] = {0};
if (solveNQueensUtil(board, 0))
printSolution(board);
else
printf("Solution does not exist\n");
}
int main() {
solveNQueens();
return 0;
}
Explanation:
- Algorithm: Backtracking places queens column by column, ensuring no two queens threaten each other (same row, column, or diagonal).
- Time Complexity: O(N!) in worst case.
- Output: Prints one valid board configuration (1 for queen, 0 for empty).
- Note: Set N to desired board size (e.g., 8 for 8-Queens).
---
Notes:
- Each program includes the time complexity in the explanation.
- For programs requiring time measurement (e.g., sorting), clock() is used.
- Input handling is kept simple; user input or hardcoded data is used.
- For additional solutions or specific slips, contact the creator.