DAA Lab
Tue Dec 03 2024 18:54:42 GMT+0000 (Coordinated Universal Time)
Saved by @student
ite a recursive function factorial that accepts an integer
n
as a parameter and returns the factorial of
n
, or
#include <stdio.h>
int factorial(int n)
{
if(n==0 || n==1){
return 1;
}
return n*factorial(n-1);
}
int main()
{
int T, no;
scanf("%d",&T);
while(T--)
{
scanf("%d",&no);
printf("%d\n",factorial(no));
}
return 0;
}
Write a C program to calculate the factorial of small positive integers using non recursive approach
#include <stdio.h>
int main() {
int N;
unsigned long long factorial = 1;
// Read the integer N
scanf("%d", &N);
// Ensure the input is a non-negative integer
if (N < 0) {
printf("Factorial is not defined for negative numbers.\n");
} else {
// Calculate factorial using a loop
for (int i = 1; i <= N; ++i) {
factorial *= i;
}
// Print the result
printf("%llu",factorial);
}
return 0;
}
Write a program to implement a Naive string-matching algorithm
#include <stdio.h>
#include <string.h>
/*
int main()
{ char txt[50], pat[50];
scanf("%s", txt);
scanf("%s", pat);
search(pat, txt);
return 0;
}
*/
// Function to perform the Naive string-matching algorithm
void search(char pat[], char txt[]) {
int M = strlen(pat); // Length of the pattern
int N = strlen(txt); // Length of the text
int found = 0;
// Slide the pattern over the text one by one
for (int i = 0; i <= N - M; i++) {
int j;
// For current position i, check the pattern matches
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j]) {
break;
}
}
// If the pattern is found at index i
if (j == M) {
printf("Pattern found at index %d\n", i);
found = 1;
}
}
// If the pattern is not found in the text
if (!found) {
printf("Not Found\n");
}
}
int main() {
char txt[50], pat[50];
// Read the text and pattern strings
scanf("%s", txt);
scanf("%s", pat);
// Call the search function
search(pat, txt);
return 0;
}
You are developing a program for a digital library to manage its collection of e-books. Each e-book is identified by a unique Book ID. To optimize the process of listing e-books, you need to implement a sorting algorithm that arranges the e-books based on their Book ID's.
#include <stdio.h>
#include <stdlib.h>
// Quicksort partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Pivot element
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to the pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap the pivot element with the element at index (i+1)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
// Quicksort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is the partitioning index, arr[pi] is now at the right place
int pi = partition(arr, low, high);
// Recursively sort elements before partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}
int main() {
int n;
printf("no of e-books: ");
scanf("%d", &n);
int BID[n];
printf("Book ID's of e-books: ");
for (int i = 0; i < n; i++) {
scanf("%d", &BID[i]);
}
printf("Original Book ID's: ");
printArray(BID, n);
printf("\n");
// Sort the e-books based on their BIDs using quicksort
quickSort(BID, 0, n - 1);
printf("Sorted Book ID's: ");
printArray(BID, n);
printf("\n");
return 0;
}
You are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Note that we have only one quantity of each item.
#include <stdio.h>
// Function to return the maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// Function to solve the 0-1 Knapsack problem
int knapsack(int W, int wt[], int val[], int N) {
int dp[N+1][W+1];
// Building the DP table
for (int i = 0; i <= N; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (wt[i-1] <= w) {
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
} else {
dp[i][w] = dp[i-1][w];
}
}
}
// The maximum value that can be achieved with the given constraints
return dp[N][W];
}
int main() {
int N, W;
// Read the number of items
scanf("%d", &N);
// Read the knapsack capacity
scanf("%d", &W);
int val[N], wt[N];
// Read the values of the items
for (int i = 0; i < N; i++) {
scanf("%d", &val[i]);
}
// Read the weights of the items
for (int i = 0; i < N; i++) {
scanf("%d", &wt[i]);
}
// Calculate the maximum value that can be achieved
int maxValue = knapsack(W, wt, val, N);
// Print the result
printf("%d\n", maxValue);
return 0;
}
1.1.6. Dijkstra’s Shortest Path Algorithm
You're a transportation engineer at a city planning department tasked with optimizing public transportation routes for a growing urban population. Your team is exploring graph-based algorithms to find the shortest routes between key locations in the city. Your manager, Alex, provides the context:
As our city's population continues to grow, it's crucial to optimize our public transportation routes to ensure efficient and reliable travel for residents. One approach is to model our transportation network as a graph, where each vertex represents a key location in the city, and edges represent the transportation connections between locations. We need to find the shortest routes between a source vertex, such as a major transit hub, and each vertex in the graph to improve commuter accessibility and reduce travel times.
#include <stdio.h>
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited, V);
visited[u] = 1;
for (int v = 0; v < V; 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];
}
}
}
printDistances(dist, V);
}
int main() {
int V;
printf("");
scanf("%d", &V);
if (V > MAX_VERTICES) {
printf("The number of vertices exceeds the maximum allowed limit (%d).\n", MAX_VERTICES);
return 1;
}
int graph[MAX_VERTICES] [MAX_VERTICES];
printf("");
for (int i = 0; i< V; i++) {
for (int j = 0; j < V; j++) {
scanf("%d", &graph [i][j]);
}
}
int src = 0;
dijkstra(graph, src, V);
return 0;
}
1.1.7. Huffman Encoding
09:42
Given a string S of distinct character of size N and their corresponding frequency f[] i.e. character S[i] has f[i] frequency. Your task is to build the Huffman tree and print all the Huffman codes in the preorder traversal of the tree.
Note: While merging if two nodes have the same value, then the node that occurs at first will be taken on the left of Binary Tree and the other one to the right, otherwise Node with less value will be taken to the left of the subtree and other one to the right.
#include <stdio.h>
// Build the Huffman Tree
struct Node* buildHuffmanTree(char* S, int* freq, int n) {
struct Node* left, *right, *top;
struct Node** heapArray = (struct Node**)malloc(n * sizeof(struct Node*));
int heapSize = 0;
// Step 1: Build a min heap
for (int i = 0; i < n; ++i)
heapArray[i] = createNode(S[i], freq[i]);
heapSize = n;
for (int i = (heapSize - 1) / 2; i >= 0; i--)
heapify(heapArray, heapSize, i);
// Step 2: Extract two minimum nodes and merge them until heap contains only one node
while (heapSize > 1) {
left = extractMin(heapArray, &heapSize);
right = extractMin(heapArray, &heapSize);
top = createNode('#', left->freq + right->freq);
top->left = left;
top->right = right;
insertHeap(heapArray, &heapSize, top);
}
return extractMin(heapArray, &heapSize);
}
// Function to print the Huffman codes using preorder traversal
void printCodes(struct Node* root, int arr[], int top) {
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (!root->left && !root->right) {
for (int i = 0; i < top; i++)
printf("%d", arr[i]);
printf(" ");
}
}
int main() {
char S[27];
int freq[26], n;
// Input the string and frequency array
scanf("%s", S);
n = strlen(S);
for (int i = 0; i < n; i++)
scanf("%d", &freq[i]);
// Build Huffman Tree
struct Node* root = buildHuffmanTree(S, freq, n);
// Print Huffman codes in preorder traversal
int arr[100], top = 0;
printCodes(root, arr, top);
printf("\n");
return 0;
}
N-Queens using Backtracking:
You're a software developer at a chess club you have been tasked to design and implement an algorithm to solve the N-Queens problem using backtracking, providing a step-by-step explanation of how the algorithm works and how it ensures that no queens attack each other on the chessboard.
#include <stdio.h>
// Function to print the board
void printBoard(int board[], int N) {
solutionCount++;
printf("Solution #%d:\n", solutionCount);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i] == j) {
printf("Q ");
} else {
printf("* ");
}
}
printf("\n");
}
}
// Function to check if a queen can be placed on the board at row 'row' and column 'col'
bool isSafe(int board[], int row, int col, int N) {
for (int i = 0; i < row; i++) {
// Check the same column and the two diagonals
if (board[i] == col || (board[i] - i == col - row) || (board[i] + i == col + row)) {
return false;
}
}
return true;
}
// Backtracking function to solve the N-Queens problem
int solveNQueens(int board[], int N, int row) {
if (row == N) {
printBoard(board, N); // Print the solution
return 1; // A solution is found
}
int solutions = 0;
for (int col = 0; col < N; col++) {
if (isSafe(board, row, col, N)) {
board[row] = col; // Place the queen
solutions += solveNQueens(board, N, row + 1); // Recur to place the next queen
board[row] = -1; // Backtrack
}
}
return solutions; // Return the total number of solutions found
}
int main() {
int N;
scanf("%d", &N);
if (N < 1 || N > MAX) {
printf("N must be between 1 and 6.\n");
return 1;
}
int board[N];
for (int i = 0; i < N; i++) {
board[i] = -1; // Initialize the board with -1 indicating no queen placed in that row
}
int totalSolutions = solveNQueens(board, N, 0); // Start solving from the first row
printf("Total solutions:%d\n", totalSolutions);
return 0;
}
1.1.9. Job assignment
41:10
Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.
#include <stdio.h>
// write the code..
int* assignedJobs=(int*)malloc(N * sizeof(int));
int* jobAssigned=(int*)calloc(N, sizeof(int));
int minCost=INT_MAX;
int* optimalAssignment=(int*)malloc(N* sizeof(int));
minCost=findMinCostRec(costMatrix, N, assignedJobs, 0, jobAssigned, 0, minCost, optimalAssignment);
for(int i=0;i<N;i++){
printf("Worker %c - Job %d\n", 'A' + i, optimalAssignment[i]);
}
free(assignedJobs);
free(jobAssigned);
free(optimalAssignment);
return minCost;
}
int findMinCostRec(int** costMatrix, int N,int* assignedJobs, int level,int* jobAssigned, int currentCost,int minCost, int* optimalAssignment) {
if(level==N){
if(currentCost < minCost){
minCost = currentCost;
for(int i=0;i<N;i++){
optimalAssignment[i]=assignedJobs[i];
}
}
return minCost;
}
for(int job=0;job<N;job++){
if(!jobAssigned[job]){
jobAssigned[job]=1;
assignedJobs[level]=job;
int newCost=currentCost+costMatrix[level][job];
if(newCost < minCost){
minCost=findMinCostRec(costMatrix, N, assignedJobs,level+1,jobAssigned, newCost, minCost,optimalAssignment);
}
jobAssigned[job]=0;
}
}
return minCost;
}
// Driver code
int main() {
int N;
scanf("%d", &N);
int** costMatrix = (int**)malloc(N * sizeof(int*));
for (int i = 0; i < N; i++) {
costMatrix[i] = (int*)malloc(N * sizeof(int));
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &costMatrix[i][j]);
}
}
printf("Optimal Cost:%d\n", findMinCost(costMatrix, N));
// Free dynamically allocated memory
for (int i = 0; i < N; i++) {
free(costMatrix[i]);
}
free(costMatrix);
return 0;
}
1.1.10. Travelling Salesman Problem
04:49
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
#include <stdio.h>
}
totalCost += costMatrix[fromCity][toCity];
}
// Add the cost of returning to the start city
if (costMatrix[tour[n - 1]][tour[0]] == -1) { // No direct connection
return INF;
}
totalCost += costMatrix[tour[n - 1]][tour[0]];
return totalCost;
}
// Function to generate permutations and solve TSP
void solveTSP(int n, int costMatrix[][100]) {
int cities[100];
for (int i = 0; i < n; i++) {
cities[i] = i;
}
int minCost = INF;
// Generate all permutations using next_permutation-like logic
do {
int currentCost = calculateTourCost(costMatrix, cities, n);
if (currentCost < minCost) {
minCost = currentCost;
}
// Generate the next permutation
int i = n - 1;
while (i > 0 && cities[i - 1] >= cities[i]) i--;
if (i == 0) break;
int j = n - 1;
while (cities[j] <= cities[i - 1]) j--;
int temp = cities[i - 1];
cities[i - 1] = cities[j];
cities[j] = temp;
for (int k = i, l = n - 1; k < l; k++, l--) {
temp = cities[k];
cities[k] = cities[l];
cities[l] = temp;
}
} while (true);
printf("%d\n", minCost);
}
int main() {
int n;
scanf("%d", &n);
int costMatrix[100][100];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &costMatrix[i][j]);
}
}
solveTSP(n, costMatrix);
return 0;
}
1.1.11. Graph Colouring
05:13
Given an undirected graph G with n vertices and e edges, the goal is to assign colors to the vertices such that no two adjacent vertices (vertices connected by an edge) have the same color, using the minimum number of colors possible.
#include <stdio.h>
available[result[adj]] = true;
}
}
// Find the first available color
int color = 0;
while (color < n && available[color]) {
color++;
}
// Assign the found color to the vertex u
result[u] = color;
// Reset the availability of colors for the next iteration
for (int i = 0; i < degrees[u]; i++) {
int adj = edges[u][i];
if (result[adj] != -1) {
available[result[adj]] = false;
}
}
}
// The chromatic number is the maximum color used + 1
int chromatic_number = 0;
for (int i = 0; i < n; i++) {
if (result[i] > chromatic_number) {
chromatic_number = result[i];
}
}
return chromatic_number + 1;
}
int main() {
// Input number of vertices and edges
int n, e;
scanf("%d", &n);
scanf("%d", &e);
// Create an adjacency list for the graph
int* degrees = (int*)malloc(n * sizeof(int));
int** edges = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
degrees[i] = 0;
edges[i] = (int*)malloc(n * sizeof(int)); // Maximum possible degree is n-1
}
// Input the edges
int u, v;
for (int i = 0; i < e; i++) {
scanf("%d %d", &u, &v);
edges[u][degrees[u]++] = v;
edges[v][degrees[v]++] = u;
}
// Get the chromatic number using the greedy coloring method
int chromatic_number = greedy_coloring(n, edges, degrees);
// Output the result
printf("%d\n", chromatic_number);
// Free dynamically allocated memory
for (int i = 0; i < n; i++) {
free(edges[i]);
}
free(edges);
free(degrees);
return 0;
}
Comments