Untitled

/* 1 */

#include <stdio.h>

int main() {
    int arr1[] = {1, 3, 5, 7};
    int arr2[] = {2, 4, 6, 8};

    int size1 = 4, size2 = 4;
    int merged[8];

    int *p1 = arr1;
    int *p2 = arr2;
    int *p3 = merged;

    int *end1 = arr1 + size1;
    int *end2 = arr2 + size2;

    while (p1 < end1 && p2 < end2) {
        if (*p1 < *p2) {
            *p3 = *p1;
            p1++;
        } else {
            *p3 = *p2;
            p2++;
        }
        p3++;
    }

    while (p1 < end1) {
        *p3 = *p1;
        p1++;
        p3++;
    }

    while (p2 < end2) {
        *p3 = *p2;
        p2++;
        p3++;
    }

    printf("Merged Sorted Array:\n");

    int *ptr = merged;
    int *largest = merged;

    while (ptr < merged + size1 + size2) {
        printf("%d ", *ptr);

        if (*ptr > *largest) {
            largest = ptr;
        }

        ptr++;
    }

    printf("\n\nLargest Element = %d", *largest);
    printf("\nAddress of Largest Element = %p\n", (void*)largest);

    return 0;
}

/* 2 */

#include <stdio.h>
#include <math.h>

#define MAX 100

struct Stack {
    int top;
    char items[MAX];
};

void push(struct Stack *s, char value) {
    s->items[++(s->top)] = value;
}

char pop(struct Stack *s) {
    return s->items[(s->top)--];
}

void moveDisk(char from, char to, int disk) {
    printf("Move Disk %d from %c to %c\n", disk, from, to);
}

int main() {
    int N;

    printf("Enter number of disks: ");
    scanf("%d", &N);

    int totalMoves = pow(2, N) - 1;

    struct Stack A, B, C;

    A.top = B.top = C.top = -1;

    for (int i = N; i >= 1; i--) {
        push(&A, i);
    }

    char source = 'A', auxiliary = 'B', destination = 'C';

    if (N % 2 == 0) {
        char temp = destination;
        destination = auxiliary;
        auxiliary = temp;
    }

    for (int i = 1; i <= totalMoves; i++) {

        if (i % 3 == 1) {

            int s = (A.top == -1) ? 999 : A.items[A.top];
            int d = (C.top == -1) ? 999 : C.items[C.top];

            if (s < d) {
                int disk = pop(&A);
                push(&C, disk);
                moveDisk(source, destination, disk);
            } else {
                int disk = pop(&C);
                push(&A, disk);
                moveDisk(destination, source, disk);
            }
        }

        else if (i % 3 == 2) {

            int s = (A.top == -1) ? 999 : A.items[A.top];
            int a = (B.top == -1) ? 999 : B.items[B.top];

            if (s < a) {
                int disk = pop(&A);
                push(&B, disk);
                moveDisk(source, auxiliary, disk);
            } else {
                int disk = pop(&B);
                push(&A, disk);
                moveDisk(auxiliary, source, disk);
            }
        }

        else if (i % 3 == 0) {

            int a = (B.top == -1) ? 999 : B.items[B.top];
            int d = (C.top == -1) ? 999 : C.items[C.top];

            if (a < d) {
                int disk = pop(&B);
                push(&C, disk);
                moveDisk(auxiliary, destination, disk);
            } else {
                int disk = pop(&C);
                push(&B, disk);
                moveDisk(destination, auxiliary, disk);
            }
        }
    }

    printf("\nTotal Moves = %d\n", totalMoves);

    return 0;
}



/* 3 */

#include <stdio.h>

int main() {

    char arr1[] = {'k', 'd', 'a', 'm', 'b'};
    char arr2[] = {'c', 'e', 'f', 'z'};

    int n1 = 5, n2 = 4;
    int swapCount = 0;

    for (int i = 0; i < n1 - 1; i++) {
        int min = i;

        for (int j = i + 1; j < n1; j++) {
            if (arr1[j] < arr1[min]) {
                min = j;
            }
        }

        if (min != i) {
            char temp = arr1[i];
            arr1[i] = arr1[min];
            arr1[min] = temp;

            swapCount++;
        }
    }

    char merged[20];

    int i = 0, j = 0, k = 0;

    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            merged[k++] = arr1[i++];
        } else {
            merged[k++] = arr2[j++];
        }
    }

    while (i < n1) {
        merged[k++] = arr1[i++];
    }

    while (j < n2) {
        merged[k++] = arr2[j++];
    }

    printf("Sorted First Array:\n");
    for (i = 0; i < n1; i++) {
        printf("%c ", arr1[i]);
    }

    printf("\n\nSecond Sorted Array:\n");
    for (i = 0; i < n2; i++) {
        printf("%c ", arr2[i]);
    }

    printf("\n\nMerged Sorted Array:\n");
    for (i = 0; i < n1 + n2; i++) {
        printf("%c ", merged[i]);
    }

    printf("\n\nTotal Swaps in Selection Sort = %d\n", swapCount);

    return 0;
}

/* 4 */

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->next = NULL;

    return newNode;
}

void insert(struct Node** head, int value) {
    struct Node* newNode = createNode(value);

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* temp = *head;

    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = newNode;
}

void display(struct Node* head) {
    struct Node* temp = head;

    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }

    printf("NULL\n");
}

struct Node* mergeLists(struct Node* head1, struct Node* head2) {

    if (head1 == NULL)
        return head2;

    struct Node* temp = head1;

    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = head2;

    return head1;
}

void removeDuplicates(struct Node* head) {

    struct Node *ptr1, *ptr2, *dup;

    ptr1 = head;

    while (ptr1 != NULL && ptr1->next != NULL) {

        ptr2 = ptr1;

        while (ptr2->next != NULL) {

            if (ptr1->data == ptr2->next->data) {

                dup = ptr2->next;
                ptr2->next = ptr2->next->next;

                free(dup);
            }
            else {
                ptr2 = ptr2->next;
            }
        }

        ptr1 = ptr1->next;
    }
}

int main() {

    struct Node* list1 = NULL;
    struct Node* list2 = NULL;
    struct Node* mergedList = NULL;

    insert(&list1, 10);
    insert(&list1, 20);
    insert(&list1, 30);
    insert(&list1, 40);

    insert(&list2, 20);
    insert(&list2, 40);
    insert(&list2, 50);
    insert(&list2, 60);

    printf("First Linked List:\n");
    display(list1);

    printf("\nSecond Linked List:\n");
    display(list2);

    mergedList = mergeLists(list1, list2);

    printf("\nMerged Linked List:\n");
    display(mergedList);

    removeDuplicates(mergedList);

    printf("\nLinked List After Removing Duplicates:\n");
    display(mergedList);

    return 0;
}

/* 5 */

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

#define MAX 100

struct Node {
    int data;
    struct Node *left, *right;
};

struct Stack {
    struct Node* items[MAX];
    int top;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

void push(struct Stack* s, struct Node* node) {
    s->items[++(s->top)] = node;
}

struct Node* pop(struct Stack* s) {
    return s->items[(s->top)--];
}

int isEmpty(struct Stack* s) {
    return s->top == -1;
}

void inorderIterative(struct Node* root) {

    struct Stack s;
    s.top = -1;

    struct Node* current = root;

    printf("Inorder Traversal:\n");

    while (current != NULL || !isEmpty(&s)) {

        while (current != NULL) {
            push(&s, current);
            current = current->left;
        }

        current = pop(&s);

        printf("%d ", current->data);

        current = current->right;
    }

    printf("\n");
}

void postorderIterative(struct Node* root) {

    if (root == NULL)
        return;

    struct Stack s1, s2;
    s1.top = -1;
    s2.top = -1;

    push(&s1, root);

    while (!isEmpty(&s1)) {

        struct Node* temp = pop(&s1);
        push(&s2, temp);

        if (temp->left != NULL)
            push(&s1, temp->left);

        if (temp->right != NULL)
            push(&s1, temp->right);
    }

    printf("Postorder Traversal:\n");

    while (!isEmpty(&s2)) {
        struct Node* temp = pop(&s2);
        printf("%d ", temp->data);
    }

    printf("\n");
}

int height(struct Node* root) {

    if (root == NULL)
        return 0;

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    if (leftHeight > rightHeight)
        return leftHeight + 1;
    else
        return rightHeight + 1;
}

int main() {

    struct Node* root = createNode(1);

    root->left = createNode(2);
    root->right = createNode(3);

    root->left->left = createNode(4);
    root->left->right = createNode(5);

    root->right->left = createNode(6);
    root->right->right = createNode(7);

    root->left->left->left = createNode(8);
    root->left->left->right = createNode(9);

    root->right->right->left = createNode(10);

    inorderIterative(root);

    printf("\n");

    postorderIterative(root);

    printf("\nHeight of Tree = %d\n", height(root));

    return 0;
}

/* 6 */

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

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct Node* insert(struct Node* root, int value) {

    if (root == NULL)
        return createNode(value);

    if (value < root->data)
        root->left = insert(root->left, value);

    else
        root->right = insert(root->right, value);

    return root;
}

int isBST(struct Node* root, int min, int max) {

    if (root == NULL)
        return 1;

    if (root->data <= min || root->data >= max)
        return 0;

    return isBST(root->left, min, root->data) &&
           isBST(root->right, root->data, max);
}

void longestPath(struct Node* root, int path[], int level,
                 int longest[], int *maxLevel) {

    if (root == NULL)
        return;

    path[level] = root->data;

    if (root->left == NULL && root->right == NULL) {

        if (level + 1 > *maxLevel) {

            *maxLevel = level + 1;

            for (int i = 0; i <= level; i++) {
                longest[i] = path[i];
            }
        }
    }

    longestPath(root->left, path, level + 1,
                longest, maxLevel);

    longestPath(root->right, path, level + 1,
                longest, maxLevel);
}

void kthSmallest(struct Node* root, int k,
                 int *count, int *result) {

    if (root == NULL || *count >= k)
        return;

    kthSmallest(root->left, k, count, result);

    (*count)++;

    if (*count == k) {
        *result = root->data;
        return;
    }

    kthSmallest(root->right, k, count, result);
}

void inorder(struct Node* root) {

    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {

    struct Node* root = NULL;

    int values[] = {50, 30, 70, 20, 40,
                    60, 80, 10, 25, 90};

    int n = 10;

    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }

    printf("Inorder Traversal of BST:\n");
    inorder(root);

    if (isBST(root, INT_MIN, INT_MAX))
        printf("\n\nTree is a Valid BST\n");
    else
        printf("\n\nTree is NOT a Valid BST\n");

    int path[100], longest[100];
    int maxLevel = 0;

    longestPath(root, path, 0, longest, &maxLevel);

    printf("\nLongest Path from Root to Leaf:\n");

    for (int i = 0; i < maxLevel; i++) {
        printf("%d ", longest[i]);
    }

    int k;

    printf("\n\nEnter value of k: ");
    scanf("%d", &k);

    int count = 0, result = -1;

    kthSmallest(root, k, &count, &result);

    if (result != -1)
        printf("The %dth Smallest Element = %d\n", k, result);
    else
        printf("Invalid value of k\n");

    return 0;
}

/* 7 */

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

#define SIZE 6

struct Node {
    int data;
    struct Node* next;
};

struct Queue {
    struct Node *front, *rear;
};

void initQueue(struct Queue* q) {
    q->front = q->rear = NULL;
}

void enqueue(struct Queue* q, int value) {

    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

    temp->data = value;
    temp->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }

    q->rear->next = temp;
    q->rear = temp;
}

int dequeue(struct Queue* q) {

    if (q->front == NULL)
        return -1;

    struct Node* temp = q->front;

    int value = temp->data;

    q->front = q->front->next;

    if (q->front == NULL)
        q->rear = NULL;

    free(temp);

    return value;
}

int isEmpty(struct Queue* q) {
    return q->front == NULL;
}

void BFS(int graph[SIZE][SIZE], int start,
         struct Queue* bfsQueue) {

    int visited[SIZE] = {0};

    struct Queue q;
    initQueue(&q);

    visited[start] = 1;
    enqueue(&q, start);

    printf("BFS Traversal:\n");

    while (!isEmpty(&q)) {

        int node = dequeue(&q);

        printf("%d ", node);

        enqueue(bfsQueue, node);

        for (int i = 0; i < SIZE; i++) {

            if (graph[node][i] == 1 && !visited[i]) {

                visited[i] = 1;
                enqueue(&q, i);
            }
        }
    }

    printf("\n");
}

int isPalindrome(struct Queue* q) {

    int arr[100];
    int n = 0;

    struct Node* temp = q->front;

    while (temp != NULL) {
        arr[n++] = temp->data;
        temp = temp->next;
    }

    for (int i = 0; i < n / 2; i++) {

        if (arr[i] != arr[n - i - 1])
            return 0;
    }

    return 1;
}

int main() {

    int graph[SIZE][SIZE] = {

        {0,1,1,0,0,0},
        {1,0,0,1,1,0},
        {1,0,0,0,1,0},
        {0,1,0,0,0,1},
        {0,1,1,0,0,1},
        {0,0,0,1,1,0}
    };

    struct Queue bfsQueue;
    initQueue(&bfsQueue);

    BFS(graph, 0, &bfsQueue);

    printf("\nBFS Order Stored in Queue:\n");

    struct Node* temp = bfsQueue.front;

    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    if (isPalindrome(&bfsQueue))
        printf("\n\nBFS Traversal is a Palindrome\n");
    else
        printf("\n\nBFS Traversal is NOT a Palindrome\n");

    return 0;
}

/* 8 */

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

struct CharStack {
    char items[MAX];
    int top;
};

struct IntStack {
    int items[MAX];
    int top;
};

void pushChar(struct CharStack *s, char value) {
    s->items[++(s->top)] = value;
}

char popChar(struct CharStack *s) {
    return s->items[(s->top)--];
}

void pushInt(struct IntStack *s, int value) {
    s->items[++(s->top)] = value;
}

int popInt(struct IntStack *s) {
    return s->items[(s->top)--];
}

int precedence(char op) {

    if (op == '+' || op == '-')
        return 1;

    if (op == '*' || op == '/')
        return 2;

    return 0;
}

void infixToPostfix(char infix[], char postfix[]) {

    struct CharStack s;
    s.top = -1;

    int j = 0;

    for (int i = 0; infix[i] != '\0'; i++) {

        char ch = infix[i];

        if (isdigit(ch)) {
            postfix[j++] = ch;
        }

        else if (ch == '(') {
            pushChar(&s, ch);
        }

        else if (ch == ')') {

            while (s.items[s.top] != '(') {
                postfix[j++] = popChar(&s);
            }

            popChar(&s);
        }

        else {

            while (s.top != -1 &&
                   precedence(s.items[s.top]) >= precedence(ch)) {

                postfix[j++] = popChar(&s);
            }

            pushChar(&s, ch);
        }
    }

    while (s.top != -1) {
        postfix[j++] = popChar(&s);
    }

    postfix[j] = '\0';
}

int evaluatePostfix(char postfix[]) {

    struct IntStack s;
    s.top = -1;

    for (int i = 0; postfix[i] != '\0'; i++) {

        char ch = postfix[i];

        if (isdigit(ch)) {
            pushInt(&s, ch - '0');
        }

        else {

            int b = popInt(&s);
            int a = popInt(&s);

            switch (ch) {

                case '+':
                    pushInt(&s, a + b);
                    break;

                case '-':
                    pushInt(&s, a - b);
                    break;

                case '*':
                    pushInt(&s, a * b);
                    break;

                case '/':
                    pushInt(&s, a / b);
                    break;
            }
        }
    }

    return popInt(&s);
}

struct IntStack stack1, stack2;

void enqueue(int value) {
    pushInt(&stack1, value);
}

int dequeue() {

    if (stack2.top == -1) {

        while (stack1.top != -1) {
            pushInt(&stack2, popInt(&stack1));
        }
    }

    return popInt(&stack2);
}

int main() {

    char infix[MAX], postfix[MAX];

    printf("Enter Infix Expression: ");
    scanf("%s", infix);

    infixToPostfix(infix, postfix);

    printf("\nPostfix Expression: %s\n", postfix);

    int result = evaluatePostfix(postfix);

    printf("Evaluated Result: %d\n", result);

    stack1.top = -1;
    stack2.top = -1;

    char resultStr[20];
    sprintf(resultStr, "%d", result);

    for (int i = 0; resultStr[i] != '\0'; i++) {
        enqueue(resultStr[i] - '0');
    }

    printf("\nDigits Dequeued from Queue:\n");

    while (stack1.top != -1 || stack2.top != -1) {
        printf("%d ", dequeue());
    }

    printf("\n");

    return 0;
}