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

Popular posts from this blog

RUINS TOP-UP

The Runawayz: Encounter