12.
Design and implement C/C++ Program for N Queen's problem using
Backtracking.
#include <stdio.h>
int is_attack(int i, int j, int board[5][5], int N) {
int k, l;
// checking for column j
for(k=1; k<=i-1; k++) {
if(board[k][j] == 1)
return 1;
}
// checking upper right diagonal
k = i-1;
l = j+1;
while (k>=1 && l<=N) {
if (board[k][l] == 1)
return 1;
k=k+1;
l=l+1;
}
// checking upper left diagonal
k = i-1;
l = j-1;
while (k>=1 && l>=1) {
if (board[k][l] == 1)
return 1;
k=k-1;
l=l-1;
}
return 0;
}
int n_queen(int row, int n, int N, int board[5][5]) {
if (n==0)
return 1;
int j;
for (j=1; j<=N; j++) {
if(!is_attack(row, j, board, N)) {
board[row][j] = 1;
if (n_queen(row+1, n-1, N, board))
return 1;
board[row][j] = 0; //backtracking
}
}
return 0;
}
int main() {
int board[5][5];
int i, j;
for(i=0;i<=4;i++) {
for(j=0;j<=4;j++)
board[i][j] = 0;
}
n_queen(1, 4, 4, board);
//printing the matix
for(i=1;i<=4;i++) {
for(j=1;j<=4;j++)
{
if(board[i][j])
printf("Q");
else
printf(".");
}
printf("\n");
}
return 0;
}
8. Design and implement C/C++ Program to find a subset of a given set S =
{sl , s2,.....,sn} of n positive integers whose sum is equal to a given positive
integer d.
#include <stdio.h>
int s[10], d, n, set[10], count = 0;
int flag = 0;
void display(int count);
void subset(int sum, int i);
void main() {
int i;
printf("ENTER THE NUMBER OF THE ELEMENTS IN THE SET: ");
scanf("%d", &n);
printf("ENTER THE SET OF VALUES: ");
for(i = 0; i < n; i++) # loop to read `n` values into the array `s`.
scanf("%d", &s[i]);
printf("ENTER THE SUM: ");
scanf("%d", &d);
printf("THE PROGRAM OUTPUT IS: ");
subset(0, 0);
if(flag == 0)
printf("There is no solution\n");
}
void subset(int sum, int i) {
if(sum == d) {
flag = 1;
display(count);
return ;
}
if(sum > d || i >= n) # current sum exceeds the desired sum or if the index
`i` is out of bounds.
return ;
else {
set[count++] = s[i];
subset(sum + s[i], i + 1);
count--;
subset(sum, i + 1);
}
}
void display(int count) {
int i;
printf("\t{");
for(i = 0; i < count; i++)
printf("%d%s", set[i], (i < count - 1) ? "," : "");
printf("}\n");
}
9. Design and implement C/C++ Program to sort a given set of n integer
elements using Selection Sort method and compute its time complexity. Run the
program for varied values of n> 5000 and record the time taken to sort. Plot a
graph of the time taken versus n. 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>
// Function to perform Selection Sort
void selectionSort(int arr[], int n)
{
for (int i = 0; i < n - 1; ++i)
{
int minIndex = i;
for (int j = i + 1; j < n; ++j)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
int main()
{
// Open file to store time complexity data
FILE *timeData;
timeData = fopen("time_complexity_data.txt", "w");
if (timeData == NULL) {
printf("Error opening file.\n");
return 1;
}
// Varying values of n
int nValues[] = {1000, 2000, 3000, 4000, 5000};
int numNValues = sizeof(nValues) / sizeof(nValues[0]);
// Perform sorting and compute time complexity for each n
for (int i = 0; i < numNValues; ++i)
{
int n = nValues[i];
int arr[n];
// Generate random integers
srand(time(NULL));
for (int j = 0; j < n; ++j)
{
arr[j] = rand() % 1000; // Range of random numbers: 0 to 999
}
// Record start time
clock_t start = clock();
// Perform selection sort
selectionSort(arr, n);
// Record end time
clock_t end = clock();
// Calculate time taken for sorting
double timeTaken = ((double) (end - start)) / CLOCKS_PER_SEC;
// Print time taken and write to file
printf("Time taken to sort for n = %d: %.6f seconds\n", n, timeTaken);
fprintf(timeData, "%d %.6f\n", n, timeTaken); }
// Close file
fclose(timeData);
return 0;
}
11. Design and implement C/C++ Program to sort a given set of n integer
elements using Merge Sort method and compute its time complexity. Run the
program for varied values of n> 5000, and record the time taken to sort. Plot a
graph of the time taken versus n. 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>
// Function to merge two subarrays
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int 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++;
}
}
// Function to perform Merge Sort
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()
{
// Open file to store time complexity data
FILE *timeData;
timeData = fopen("time_complexity_data.txt", "w");
if (timeData == NULL) {
printf("Error opening file.\n");
return 1;
}
// Varying values of n
int nValues[] = {1000, 2000, 3000, 4000, 5000};
int numNValues = sizeof(nValues) / sizeof(nValues[0]);
// Perform sorting and compute time complexity for each n
for (int i = 0; i < numNValues; ++i)
{
int n = nValues[i];
int arr[n];
// Generate random integer srand(time(NULL));
for (int j = 0; j < n; ++j)
{
arr[j] = rand() % 1000; // Range of random numbers: 0 to
999
}
// Record start time
clock_t start = clock();
// Perform Merge Sort
mergeSort(arr, 0, n - 1);
// Record end time
clock_t end = clock();
// Calculate time taken for sorting
double timeTaken = ((double) (end - start)) / CLOCKS_PER_SEC;
// Print time taken and write to file
printf("Time taken to sort for n = %d: %.6f seconds\n", n,
timeTaken);
fprintf(timeData, "%d %.6f\n", n, timeTaken);
}
// Close file
fclose(timeData);
return 0;
}
