program



Practical no 10

#include <stdio.h> #include <string.h> #define MAX_LENGTH 100000 // Function to calculate the number of substrings with X and Y on endpoints int calculateSubstringCount(char* str, int length, char X, char Y) { int count = 0; int prefixCount[MAX_LENGTH] = {0}; for (int i = 0; i < length; i++) { if (str[i] == Y) { prefixCount[i + 1] = prefixCount[i] + 1; } else { prefixCount[i + 1] = prefixCount[i]; } } for (int i = 0; i < length; i++) { if (str[i] == X) { count += prefixCount[length] - prefixCount[i + 1]; } } return count; } int main() { char str[MAX_LENGTH]; printf("Enter the string: "); scanf("%s", str); int length = strlen(str); int Q; printf("Enter the number of queries: "); scanf("%d", &Q); printf("Enter the queries (X Y):\n"); for (int i = 0; i < Q; i++) { char X, Y; scanf(" %c %c", &X, &Y); int count = calculateSubstringCount(str, length, X, Y); printf("Number of substrings with '%c' and '%c' on endpoints: %d\n", X, Y, count); } return 0; }



Practical no 09

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an order
typedef struct {
    int orderNumber;
    int time;
    int duration;
} Order;

// Comparison function for sorting orders
int compareOrders(const void* a, const void* b) {
    Order* orderA = (Order*)a;
    Order* orderB = (Order*)b;

    if (orderA->time != orderB->time) {
        return orderA->time - orderB->time;
    } else {
        return orderA->orderNumber - orderB->orderNumber;
    }
}

// Function to print the order sequence
void printOrderSequence(Order* orders, int n) {
    qsort(orders, n, sizeof(Order), compareOrders);

    printf("Order sequence:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", orders[i].orderNumber);
    }
    printf("\n");
}

int main() {
    int n;
    printf("Enter the number of orders: ");
    scanf("%d", &n);

    Order orders[n];

    printf("Enter the order details (order number, time, duration):\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &orders[i].orderNumber, &orders[i].time, &orders[i].duration);
    }

    printOrderSequence(orders, n);

    return 0;
}





PR no 8 

WAP  in c to implement Binary search on 1D array of Employee structure (contains employee_name,
emp_no, emp_salary), with key as emp_no. And count the number of comparison happened. 

#include <stdio.h> #include <stdlib.h> struct Employee { char name[100]; int emp_no; double emp_salary; }; int binarySearch(struct Employee *arr, int n, int key) { int low = 0; int high = n - 1; int mid; int count = 0; while (low <= high) { mid = (low + high) / 2; count++; if (arr[mid].emp_no == key) { return mid; } else if (arr[mid].emp_no < key) { low = mid + 1; } else { high = mid - 1; } } return -1; } int main() { struct Employee arr[] = { {"Lokesh", 1, 50000.00}, {"Sweety", 2, 60000.00}, {"Rushi", 3, 80000.00}, {"aman", 4, 70000.00}, {"Jay", 5, 100000.00}, {"Ratan", 6, 20000.00}, }; int n = sizeof(arr) / sizeof(arr[0]); int key; int index; int count = 0; printf("Enter the employee number to search for: "); scanf("%d", &key); index = binarySearch(arr, n, key); if (index == -1) { printf("Employee number not found.\n"); } else { printf("Employee number %d found at index %d.\n", key, index); printf("Number of comparisons: %d\n", count); printf("name:%s\n",arr[index].name); printf("roll no:%d\n",arr[index].emp_no); printf("Salary:%lf\n",arr[index].emp_salary); } return 0; }


Quick sort
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Define the structure for student
struct Student {
    char student_name[50];
    int student_roll_no;
    float total_marks;
};

// Function to swap two students
void swap(struct Student* a, struct Student* b) {
    struct Student temp = *a;
    *a = *b;
    *b = temp;
}

// Function to partition the array
int partition(struct Student arr[], int low, int high, int* swap_count) {
    int pivot = arr[high].student_roll_no;
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j].student_roll_no < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
            (*swap_count)++;
        }
    }

    swap(&arr[i + 1], &arr[high]);
    (*swap_count)++;
    return (i + 1);
}

// Function to perform Quick Sort
void quickSort(struct Student arr[], int low, int high, int* swap_count) {
    if (low < high) {
        int pi = partition(arr, low, high, swap_count);

        quickSort(arr, low, pi - 1, swap_count);
        quickSort(arr, pi + 1, high, swap_count);
    }
}

int main() {
    int n;
    printf("Enter the number of students: ");
    scanf("%d", &n);

    // Allocate memory for the array of students
    struct Student* students = (struct Student*)malloc(n * sizeof(struct Student));

    // Input the data for each student
    printf("Enter the data for each student:\n");
    for (int i = 0; i < n; i++) {
        printf("Student %d\n", i + 1);
        printf("Name: ");
        scanf("%s", students[i].student_name);
        printf("Roll No.: ");
        scanf("%d", &students[i].student_roll_no);
        printf("Total Marks: ");
        scanf("%f", &students[i].total_marks);
    }

    int swap_count = 0;

    // Perform Quick Sort on the array of students
    quickSort(students, 0, n - 1, &swap_count);

    // Print the sorted array of students
    printf("\nSorted array of students:\n");
    for (int i = 0; i < n; i++) {
        printf("Name: %s\tRoll No.: %d\tTotal Marks: %.2f\n", students[i].student_name, students[i].student_roll_no, students[i].total_marks);
    }

    // Print the number of swaps performed
    printf("\nNumber of swaps performed: %d\n", swap_count);

    // Free the allocated memory
    free(students);

    return 0;
}





Prims algo


#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define V 6

int minKey(int key[], bool mstSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}

int printMST(int parent[], int graph[V][V])
{
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d \t%d \n", parent[i], i,
            graph[i][parent[i]]);
}


void primMST(int graph[V][V])                                                                                              
{

    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;


    key[0] = 0;

    parent[0] = -1;

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

        int u = minKey(key, mstSet);


        mstSet[u] = true;
        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == false
                && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }


    printMST(parent, graph);
}


int main()
{
    int graph[V][V] = { { 0, 7, 8, 0, 0, 0},
                        { 7, 0, 3, 6, 0, 0},
                        { 8, 3, 0, 4, 3, 0},
                        { 0, 6, 4, 0, 2, 5},
                        { 0, 0, 3, 2, 0, 2},
                        { 0, 0, 0, 5, 2, 0}
                        };

    // Print the solution
    primMST(graph);

    return 0;
}



GRAPH PR 5

#include <stdio.h>
#include <limits.h>

#define V 5

int minDistance(int dist[], int visited[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (visited[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void printSolution(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int visited[V];

    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);
        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];
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = { {0, 10, 20, 0, 0},
                        {10, 0, 5, 6, 0},
                        {20, 5, 0, 15, 30},
                        {0, 6, 15, 0, 8},
                        {0, 0, 30, 8, 0} };

    dijkstra(graph, 0);

    return 0;
}




OP:



https://programs.programmingoneonone.com/2021/07/hackerrank-dijkstra-shortest-reach-2-problem-solution.html



Graph 

#include <stdio.h>
#include <limits.h>

#define MAX_NODES 10000

int graph[MAX_NODES][MAX_NODES];
int dist[MAX_NODES];
int visited[MAX_NODES];

int find_min_distance(int n)
{
    int min_dist = INT_MAX;
    int min_index = -1;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i] && dist[i] < min_dist)
        {
            min_dist = dist[i];
            min_index = i;
        }
    }
    return min_index;
}

void dijkstra(int start_node, int n)
{
    for (int i = 0; i < n; i++)
    {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[start_node] = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int u = find_min_distance(n);
        visited[u] = 1;
        for (int v = 0; v < n; v++)
        {
            if (graph[u][v] && !visited[v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

int main()
{
    int n, m; // n: number of nodes, m: number of edges
    printf("Enter the number of nodes and edges: ");
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int u, v, w; // u and v are nodes, w is weight of edge (u, v)
        printf("Enter edge %d (u v w): ", i + 1);
        scanf("%d%d%d", &u, &v, &w);
        graph[u - 1][v - 1] = w;
        graph[v - 1][u - 1] = w;
    }
    int start_node;
    printf("Enter the starting node: ");
    scanf("%d", &start_node);
    dijkstra(start_node - 1, n);
    printf("Shortest paths from node %d:\n", start_node);
    for (int i = 0; i < n; i++)
    {
        if (dist[i] == INT_MAX)
        {
            printf("Node %d: -1\n", i + 1);
        }
        else
        {
            printf("Node %d: %d\n", i + 1, dist[i]);
        }
    }
    return 0;
}


AVL TREE 


#include <stdio.h>
#include <stdlib.h>

struct AVLNode {
    int key;
    int height;
    int balanceFactor;
    struct AVLNode *left;
    struct AVLNode *right;
};

int getHeight(struct AVLNode *node) {
    if(node == NULL) {
        return 0;
    }
    return node->height;
}

int getBalanceFactor(struct AVLNode *node) {
    if(node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

struct AVLNode *createNode(int key) {
    struct AVLNode *newNode = (struct AVLNode*)malloc(sizeof(struct AVLNode));
    newNode->key = key;
    newNode->height = 1;
    newNode->balanceFactor = 0;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct AVLNode *rightRotate(struct AVLNode *y) {
    struct AVLNode *x = y->left;
    struct AVLNode *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    y->balanceFactor = getBalanceFactor(y);
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    x->balanceFactor = getBalanceFactor(x);

    return x;
}


struct AVLNode *leftRotate(struct AVLNode *x) {
    struct AVLNode *y = x->right;
    struct AVLNode *T2 = y->left;


    y->left = x;
    x->right = T2;


    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    x->balanceFactor = getBalanceFactor(x);
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    y->balanceFactor = getBalanceFactor(y);

    return y;
}


struct AVLNode *insert(struct AVLNode *node, int key) {

    if(node == NULL) {
        return createNode(key);
    }
    if(key < node->key) {
        node->left = insert(node->left, key);
    }
    else if(key > node->key) {
        node->right = insert(node->right, key);
    }
    else {
        return node; 
    }


    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    node->balanceFactor = getBalanceFactor(node);

    
    int balance = node->balanceFactor;


    if(balance > 1 && key < node->left->key) {
        return rightRotate(node);
}

if(balance < -1 && key > node->right->key) {
    return leftRotate(node);
}

if(balance > 1 && key > node->left->key) {
    node->left = leftRotate(node->left);
    return rightRotate(node);
}


if(balance < -1 && key < node->right->key) {
    node->right = rightRotate(node->right);
    return leftRotate(node);
}


return node;
}


void printPreorder(struct AVLNode *node) {
if(node != NULL) {
printf("%d (%d)\n", node->key, node->balanceFactor);
printPreorder(node->left);
printPreorder(node->right);
}
}

int main() {
struct AVLNode *root = NULL;
int n, key;
printf("Enter number of keys to insert: ");
scanf("%d", &n);
printf("Enter keys to insert:\n");
for(int i = 0; i < n; i++) {
scanf("%d", &key);
root = insert(root, key);
}
printf("Preorder traversal of AVL tree:\n");
printPreorder(root);
return 0;
}





HEAP TREE


#include <stdio.h>

void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}

void heapify(int arr[], int N, int i)
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;

if (l < N && arr[l] > arr[largest])
largest = l;

if (r < N && arr[r] > arr[largest])
largest = r;

if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, N, largest);
}
}

void buildHeap(int arr[], int N)
{
int startIdx = (N / 2) - 1;

for (int i = startIdx; i >= 0; i--) {
heapify(arr, N, i);
}
}

void printHeap(int arr[], int N)
{
printf("Array representation of Heap is:\n");

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

int main()
{
int arr[11] = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17};
int N = sizeof(arr) / sizeof(arr[0]);
    printf("Given elements :");
    for(int i = 0; i < 11;i++)
    {
        printf("%d",arr[i]);
    }
    printf("\n");
buildHeap(arr, N);
printHeap(arr, N);

return 0;
}


PR2 BST


#include <stdio.h>
#include <stdlib.h>

struct BST
{
    int data;
    struct BST *left;
    struct BST *right;
};

typedef struct BST NODE;
NODE *node;
NODE *createtree(NODE *node, int data)
{
    if (node == NULL)
    {
        NODE *temp;
        temp = (NODE *)malloc(sizeof(NODE));
        temp->data = data;
        temp->left = temp->right = NULL;
        return temp;
    }
    if (data < (node->data))
    {
        node->left = createtree(node->left, data);
    }
    else if (data > node->data)
    {
        node->right = createtree(node->right, data);
    }
    return node;
}

NODE *search(NODE *node, int data)
{
    if (node == NULL)
        printf("\nElement not found");
    else if (data < node->data)
    {
        node->left = search(node->left, data);
    }
    else if (data > node->data)
    {
        node->right = search(node->right, data);
    }
    else

        printf("\nElement found is: %d", node->data);

    return node;
}

void inorder(NODE *node)

{

    if (node != NULL)

    {

        inorder(node->left);

        printf("%d\t", node->data);

        inorder(node->right);
    }
}

NODE *findMin(NODE *node)
{
    if (node == NULL)
    {
        return NULL;
    }
    if (node->left)
        return findMin(node->left);
    else
        return node;
}

NODE *del(NODE *node, int data)
{
    NODE *temp;
    if (node == NULL)
    {
        printf("\nElement not found");
    }
    else if (data < node->data)
    {
        node->left = del(node->left, data);
    }
    else if (data > node->data)
    {
        node->right = del(node->right, data);
    }
    else
    { /* Now We can delete this node and replace with either minimum element in the right sub tree or maximum element in the left subtree */
        if (node->right && node->left)
        { /* Here we will replace with minimum element in the right sub tree */
            temp = findMin(node->right);
            node->data = temp->data;
            /* As we replaced it with some other node, we have to delete that node */
            node->right = del(node->right, temp->data);
        }
        else
        {
            /* If there is only one or zero children then we can directly remove it from the tree and connect its parent to its child */
            temp = node;
            if (node->left == NULL)
                node = node->right;
            else if (node->right == NULL)
                node = node->left;
            free(temp); /* temp is longer required */
        }
    }
    return node;
}

void main()
{
    int data, ch, i, n;
    NODE *root = NULL;
    while (1)
    {
        printf("\n1.Insertion ");
        printf("\n2.Search ");
        printf("\n3.Delete ");
        printf("\n4.Inorder\n5.Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1:
            printf("\nEnter N value: ");
            scanf("%d", &n);
            printf("\nEnter the values to create BST \n");
            for (i = 0; i < n; i++)
            {
                scanf("%d", &data);
                root = createtree(root, data);
            }
            break;
        case 2:
            printf("\nEnter the element to search: ");
            scanf("%d", &data);
            root = search(root, data);
            break;
        case 3:
            printf("\nEnter the element to delete: ");
            scanf("%d", &data);
            root = del(root, data);
            break;

        case 4:
            printf("\nInorder Traversal: \n");
            inorder(root);
            break;

        case 5:
            exit(0);

        default:
            printf("\nWrong option");
            break;
        }
    }
}


Pr 1 inorder Preorder Postorder


// Tree traversal in C

#include <stdio.h>
#include <stdlib.h>

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Inorder traversal
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ", root->item);
  inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// Postorder traversal
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ", root->item);
}

// Create a new Node
struct node* create(int value) {
  struct node* newNode = (struct node*) malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
  root->left = create(value);
  return root->left;
}

// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
  root->right = create(value);
  return root->right;
}

int main() {
  struct node* root = create(1);
  insertLeft(root, 10);
  insertRight(root, 20);
  insertLeft(root->left, 30);
  insertRight(root->left, 40);
  insertLeft(root->right, 50);
  insertRight(root->right, 60);

  printf("Traversal of the inserted binary tree \n");
  printf("Inorder traversal \n");
  inorderTraversal(root);

  printf("\nPreorder traversal \n");
  preorderTraversal(root);


  printf("\nPostorder traversal \n");
  postorderTraversal(root);

}





OS FCFS

#include <stdio.h>

int main() {
   int n, bt[20], wt[20], tat[20], avg_wt = 0, avg_tat = 0, i, j;
 
   printf("Enter the number of processes: ");
   scanf("%d", &n);
 
   printf("\nEnter the burst time of the processes:\n");
   for(i = 0; i < n; i++) {
      printf("P[%d]: ", i+1);
      scanf("%d", &bt[i]);
   }
 
   wt[0] = 0;    // Waiting time for first process is 0
 
   // Calculating waiting time
   for(i = 1; i < n; i++) {
      wt[i] = 0;
      for(j = 0; j < i; j++)
         wt[i] += bt[j];
   }
 
   printf("\nProcess\tBurst Time\tWaiting Time\tTurnaround Time");
 
   // Calculating turnaround time
   for(i = 0; i < n; i++) {
      tat[i] = bt[i] + wt[i];
      avg_wt += wt[i];
      avg_tat += tat[i];
      printf("\nP[%d]\t\t%d\t\t%d\t\t%d", i+1, bt[i], wt[i], tat[i]);
   }
 
   avg_wt /= i;
   avg_tat /= i;
   printf("\n\nAverage Waiting Time: %d", avg_wt);
   printf("\nAverage Turnaround Time: %d\n", avg_tat);
 
   return 0;
}

OS practical 
FIRST FIT PROGRAM IN C

#include<stdio.h>
void main()
{
int bsize[10], psize[10], bno, pno, flags[10], allocation[10], i, j;
for(i = 0; i < 10; i++)
{
flags[i] = 0;
allocation[i] = -1;
}
printf("Enter no. of blocks: ");
scanf("%d", &bno);
printf("\nEnter size of each block: ");
for(i = 0; i < bno; i++)
scanf("%d", &bsize[i]);
printf("\nEnter no. of processes: ");
scanf("%d", &pno);
printf("\nEnter size of each process: ");
for(i = 0; i < pno; i++)
scanf("%d", &psize[i]);
for(i = 0; i < pno; i++)         //allocation as per first fit
for(j = 0; j < bno; j++)
if(flags[j] == 0 && bsize[j] >= psize[i])
{
allocation[j] = i;
flags[j] = 1;
break;
}
//display allocation details
printf("\nBlock no.\tsize\t\tprocess no.\t\tsize");
for(i = 0; i < bno; i++)
{
printf("\n%d\t\t%d\t\t", i+1, bsize[i]);
if(flags[i] == 1)
printf("%d\t\t\t%d",allocation[i]+1,psize[allocation[i]]);
else
printf("Not allocated");
}
}



Comments

Post a Comment

Popular posts from this blog

Free Fire City Open : Official Trailer

Image
 Free Fire City Open : Official Trailer The Free Fire City Open is all set to kick off! Are you ready to represent your city and grab the lion's share of INR 60 Lacs prize pool? The FFC Mode Qualifiers has begun! Head to Free Fire Esports India YouTube channel and catch the action live! Track: Unknown Brain & Hoober - Phenomenon (ft. Dax & VinDon) [NCS Release] Music provided by NoCopyrightSounds. Watch: https://youtu.be/LO9vChXMBp8​
Read more

New 11th Elite pass

Image
Elite pass  The new elite pass, sandstorm worriors, will be making its presence felt soon. For now, take a look at some of the elite passpool. The elite pass preorder will commerce soon. So hurry and collect the badget to complete the primal hunter mission. Got your water element bundle for the supermarket 2.0? The only thing that's missing is a matching weapon skin. You're in luck because the aqua scar skin is now available in weapon royale. Spin for a chance to own the alluring aqua scar and pow pow to victory. Super sale is back! Pick up your shopping bags and push your carts because we arr going on a shopping sprre! From today until the 1st of August, Pickup your desitred items from the supermarket and get them.
Read more