DS Midsem Prep

This is a live document. Expect changes frequently. I am parsing through PYQs during free time. You can expect it to conclude in a week's time.

Given the following function in C:

void func() {
    int i = 1, j;
    while(i <= n) {
        for(j = 1; j * j <= n; j++)
            printf("Data Structure...\n");
        ++i;
    }
}

Determine the time complexity of the function.

Answer

Time Complexity Analysis:

Outer while loop:
- The loop runs from i = 1 to i = n, so it iterates n times.
Inner for loop:
- The loop runs from j = 1 to j * j <= n, which implies that j runs approximately up to $\sqrt{n}$.

Therefore, the inner loop runs approximately $\sqrt{n}$ times for each iteration of the outer loop.

Total Time Complexity:
- Since the outer loop runs n times and for each iteration of the outer loop, the inner loop runs $\sqrt{n}$ times, the total time complexity is:

$$\text{Time Complexity} = O(n \times \sqrt{n}) = O(n^{3/2})$$

Consider a 2-D array arr[6][7] (with 6 rows and 7 columns). Each element of the array requires 4 bytes of memory space. If the array is stored in row-major order with a base address of 1001, what will be the address of the array element arr[5][3]?

Answer

To calculate the address of a specific element in a 2D array stored in row-major order, we use the following formula:

$$\text{Address} = \text{Base Address} + \text{Element Size} \times \left[\text{Number of Columns} \times i + j\right]$$

Where:

Base Address = 1001
Element Size = 4 bytes
Number of Columns = 7
i and j are the row and column indices, respectively.

For the element arr[5][3]:

i = 5
j = 3

Substitute the values into the formula, the address of the array element arr[5][3] is 1153.

If the node of a doubly linked list is declared in C as:

struct node {
    int data;
    struct node *prev;
    struct node *next;
};

and ptr is a pointer pointing to one of the internal nodes of a doubly linked list, then write the required statements to delete the node to which ptr is pointing without using any other pointer variable.

Answer

To delete the node pointed to by ptr in a doubly linked list without using any other pointer variable, you can use the following statements:

ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
free(ptr);

Explanation:

ptr->prev->next = ptr->next;
- This statement updates the next pointer of the previous node to point to the next node, effectively bypassing the node pointed to by ptr.
ptr->next->prev = ptr->prev;
- This statement updates the prev pointer of the next node to point to the previous node, completing the bypass.
free(ptr);
- Finally, the ptr node is freed from memory.

These operations effectively remove the node from the doubly linked list and free the memory occupied by it without requiring any additional pointer variables.

How can a singly linked list be used to represent the following polynomial?

$$P(x) = 2xy^2z^3 + 3x^2yz - 4xy^3z + 5x^2y^2 + 7xy^2z^5 + 11$$

Answer

To represent the polynomial using a singly linked list, each node of the list will represent a term in the polynomial. The structure of the node will contain:

The coefficient of the term.
The powers of the variables (x), (y), and (z).
A pointer to the next node.

Here is how you can define the structure in C:

struct Node {
    int coefficient;
    int power_x;
    int power_y;
    int power_z;
    struct Node* next;
};

Each node will store the coefficient and powers corresponding to one term of the polynomial. The linked list will be created with each node representing a term in the polynomial in descending order of the degree (or any other specific order).

For example:

The first node might represent (2xy^2z^3) with coefficient = 2, power_x = 1, power_y = 2, and power_z = 3.
The second node might represent (3x^2yz) with coefficient = 3, power_x = 2, power_y = 1, and power_z = 1.
And so on for the rest of the terms.

A stack is implemented using an array declared in C: st[N] and an integer variable pos. The pseudo code for the push() and pop() operations of the stack are as follows:

push(x) {
    st[pos] = x;
    pos = pos - 1;
}

pop() {
    pos = pos + 1;
    return(st[pos]);
}

Find the initialization of the integer variable pos for an empty stack with a maximum capacity of N elements for the above implementation.

Answer

The stack is implemented using an array st[N], and pos is used to track the position of the stack's top element.

Initialization of pos:
- Since the push() operation first assigns x to st[pos] and then decrements pos, it suggests that pos starts at the topmost position of the stack.
- After a push, pos is decremented, and after a pop, pos is incremented.

For an empty stack:

The stack should be considered empty when pos is just below the first index of the array (which would be pos = N - 1 if using a 0-based index for a maximum capacity of N elements).

Thus, pos should be initialized to N - 1 for an empty stack.

Create a two-dimensional array of size M×N dynamically containing English alphabets (capital letters) except ‘X’. Write a C program to delete ALL the vowels present in the matrix. Once any vowel is found in a row and deleted, the elements will be shifted from the same row as well as the next rows to fill the deleted element. The empty space at the end will be replaced by the alphabet ‘X’.

Example:

For the deletion of the first vowel (U):

Before:
```
 A S D U C J
 P R I J K L
 M N T W O Y
 Q S F D B L
```
After:
```
 A S D C J P
 R I J K L M
 N T W O Y Q
 S F D B L X
```
For the deletion of the second vowel (I):

Before:
```
 A S D C J P
 R I J K L M
 N T W O Y Q
 S F D B L X
```
After:
```
 A S D C J P
 R J K L M N
 T W O Y Q S
 F D B L X X
```
Answer

Since 2D arrays in C are stored in row-major order, we can directly use a pointer to the start of the 2D array and manipulate it as if it were a 1D array. This allows us to treat the matrix as a single contiguous block of memory.
1. Direct Pointer Usage: Instead of copying the matrix data, directly assign a pointer to the beginning of the 2D array (&example[0][0]). This pointer will be used to traverse and manipulate the matrix.
2. Vowel Detection and Shifting:
  - Traverse the matrix using the pointer.
  - When a vowel is detected, shift all subsequent elements to the left to fill the gap.
3. Replacement with 'X':
  - After all vowels have been deleted, fill the remaining positions at the end of the array with 'X'.
4. Use of Original Array: The operations modify the original array (example), and the changes are reflected in the same array.

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

    // Function to check if a character is a vowel
    bool isVowel(char c) {
        return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }

    // Function to delete vowels from the matrix and shift elements
    void deleteVowels(char* matrix, int size) {
        int writeIndex = 0;  // Pointer to track the next write position

        // Traverse through the matrix as a linear 1D array
        for (int readIndex = 0; readIndex < size; readIndex++) {
            if (!isVowel(matrix[readIndex])) {
                matrix[writeIndex++] = matrix[readIndex];  // Copy non-vowel characters
            }
        }

        // Fill the remaining positions with 'X'
        for (int i = writeIndex; i < size; i++) {
            matrix[i] = 'X';
        }
    }

    int main() {
        int M = 4, N = 6;  // Dimensions of the matrix
        int size = M * N;  // Total number of elements in the matrix

        // Example matrix (declared as a 2D array)
        char example[4][6] = {
            {'A', 'S', 'D', 'U', 'C', 'J'},
            {'P', 'R', 'I', 'J', 'K', 'L'},
            {'M', 'N', 'T', 'W', 'O', 'Y'},
            {'Q', 'S', 'F', 'D', 'B', 'L'}
        };

        // Use a pointer to the start of the example matrix
        char* matrix = &example[0][0];

        // Print the initial matrix
        printf("Initial Matrix:\n");
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                printf("%c ", example[i][j]);  // Using the original array 'example' to print
            }
            printf("\n");
        }

        // Delete vowels and shift elements
        deleteVowels(matrix, size);

        // Print the modified matrix
        printf("\nModified Matrix:\n");
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                printf("%c ", example[i][j]);  // Changes are reflected in the original 'example' array
            }
            printf("\n");
        }

        return 0;
    }

Explanation

Direct Pointer Usage: The pointer matrix is initialized to point to the start of the 2D array example (char* matrix = &example[0][0];). This allows the program to treat the 2D array as a linear block of memory and perform operations as if it were a 1D array.
Efficient Vowel Deletion and Element Shifting:
- The deleteVowels function processes the array using the pointer (matrix). It identifies vowels and shifts non-vowel elements to the left in the array, directly modifying the original 2D array.
Reflecting Changes in the Original Array: The printing of the matrix before and after the operation is done using the example array. This demonstrates that the operations performed through the pointer matrix are directly modifying the original 2D array example.
Memory Efficiency: By directly manipulating the original array without copying, the program is efficient in both time and space, ensuring all operations are done in-place.

The table below is a representation of a doubly linked list where the nodes are declared in C as:

struct node {
    int data;
    struct node *prev;
    struct node *next;
};

The nodes are connected as per the data shown in the table. Draw the linked list. Also, write C-like statements to replace the values of Node-III and Node-IV by adding the value of Node-I to these node values and replace the value of Node-II by subtracting the value of Node-I from it. Consider the base pointer ptr, which holds the address of Node-I. Do not use any other pointer variable.

Node	Data	Prev Address	Next Address	Node Address
I	10	2001	3001	1001
II	15	NULL	NULL	2001
III	-5	NULL	4001	3001
IV	25	NULL	NULL	4001

Answer

Drawing the Linked List:

Node-II (2001) <- Node-I (1001) -> Node-III (3001) -> Node-IV (4001)

C-like Statements:

Assuming ptr is pointing to Node-I:

// Replace Node-III data with Node-III data + Node-I data
ptr->next->data = ptr->next->data + ptr->data;

// Replace Node-IV data with Node-IV data + Node-I data
ptr->next->next->data = ptr->next->next->data + ptr->data;

// Replace Node-II data with Node-II data - Node-I data
ptr->prev->data = ptr->prev->data - ptr->data;

The following data are stored in a singly linked list in the order shown below:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

Write a pseudo code or C-function to delete all odd numbers from the list.

Answer

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

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

// Function to delete all odd numbers from the list
void deleteOdds(struct Node** head) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    while (temp != NULL) {
        if (temp->data % 2 != 0) {
            if (prev == NULL) {
                // Head node is odd
                *head = temp->next;
                free(temp);
                temp = *head;
            } else {
                // Middle or last node is odd
                prev->next = temp->next;
                free(temp);
                temp = prev->next;
            }
        } else {
            prev = temp;
            temp = temp->next;
        }
    }
}

// Function to print the list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

// Main function for testing
int main() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->next->data = 4;
    head->next->next->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->next->next->data = 5;
    head->next->next->next->next->next = NULL;

    printf("Original List:\n");
    printList(head);

    deleteOdds(&head);

    printf("List after deleting odd numbers:\n");
    printList(head);

    return 0;
}

Explain a sparse matrix and its representations. Write a pseudo code or C-function to display the triplet of a transpose of a sparse matrix with a suitable example.

Answer

Let's use a struct to represent the triplet form of a sparse matrix. Each triplet will store the row index, column index, and value of a non-zero element. The sparse matrix will be an array of these triplet structures.

To represent a sparse matrix using structs in C:

Define a struct to hold each non-zero element's row index, column index, and value.
Use an array of this struct to represent the entire sparse matrix.

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

// Define a struct for the triplet representation
struct Triplet {
    int row;
    int col;
    int value;
};

// Function to display the triplet representation
void displayTriplets(struct Triplet* spMatrix, int nonZeroCount) {
    printf("Row Column Value\n");
    for (int i = 0; i < nonZeroCount; i++) {
        printf("%d    %d     %d\n", spMatrix[i].row, spMatrix[i].col, spMatrix[i].value);
    }
}

// Function to compute and display the transpose of the sparse matrix in triplet form
void transposeSparseMatrix(struct Triplet* spMatrix, int nonZeroCount) {
    struct Triplet* transposeMatrix = (struct Triplet*)malloc(nonZeroCount * sizeof(struct Triplet));

    for (int i = 0; i < nonZeroCount; i++) {
        transposeMatrix[i].row = spMatrix[i].col;
        transposeMatrix[i].col = spMatrix[i].row;
        transposeMatrix[i].value = spMatrix[i].value;
    }

    printf("\nTranspose in Triplet Form:\n");
    displayTriplets(transposeMatrix, nonZeroCount);

    free(transposeMatrix);
}

int main() {
    // Initialize the sparse matrix with non-zero elements
    struct Triplet spMatrix[] = {
        {0, 2, 3},
        {1, 0, 4},
        {2, 1, 5},
        {2, 3, 7}
    };

    int nonZeroCount = sizeof(spMatrix) / sizeof(spMatrix[0]);

    printf("Original Matrix in Triplet Form:\n");
    displayTriplets(spMatrix, nonZeroCount);

    // Compute and display the transpose
    transposeSparseMatrix(spMatrix, nonZeroCount);

    return 0;
}

Output

Original Matrix in Triplet Form:
Row Column Value
0    2     3
1    0     4
2    1     5
2    3     7

Transpose in Triplet Form:
Row Column Value
2    0     3
0    1     4
1    2     5
3    2     7

Explanation:

Struct Definition (Triplet):
- Defines a structure to store the row index, column index, and value of each non-zero element in the sparse matrix.
Array of Structs (spMatrix):
- Represents the sparse matrix as an array of Triplet structs, where each struct contains the row, column, and value of a non-zero element.
Function displayTriplets():
- Takes the array of triplets and the count of non-zero elements and prints the triplet form of the matrix.
Function transposeSparseMatrix():
- Computes the transpose of the sparse matrix by swapping the row and column indices for each triplet.
- Uses dynamic memory allocation to create an array for the transpose matrix and frees the memory after use.
Main Function (main()):
- Initializes the sparse matrix in triplet form, displays it, computes the transpose, and then displays the transpose matrix.
Write an algorithm, pseudo code, or C-function to convert an expression in infix notation to its equivalent prefix expression. Convert the infix expression: (A+B)+C-(D-E)^F to prefix equivalent mentioning each step of the algorithm.

Answer

Infix Expression

(A+B)+C-(D-E)^F

Steps to Convert Infix to Prefix

Reverse the Infix Expression:
- Reverse the expression.
- Swap '(' with ')' and vice versa.

Reversed Infix:
F^(E-D)-C+(B+A)

Convert the Reversed Infix to Postfix:
- Initialize an empty stack for operators and an empty output list.
- Read the reversed infix expression from left to right.
- Process each character using the stack rules:

Step-by-Step Process:

F: Operand → Add to output: Postfix: F
^: Operator → Push to stack: Stack: ^
(: Right parenthesis after reversing (treated as left) → Push to stack: Stack: ^ (
E: Operand → Add to output: Postfix: FE
-: Operator → Push to stack: Stack: ^ ( -
D: Operand → Add to output: Postfix: FED
): Left parenthesis after reversing (treated as right) → Pop from stack to output until '(' is found. Postfix: FED- Stack: ^
-: Operator → Compare precedence with ^, pop ^ and push -: Postfix: FED-^ Stack: -
C: Operand → Add to output: Postfix: FED-^C
+: Operator → Push to stack: Stack: - +
(: Right parenthesis after reversing (treated as left) → Push to stack: Stack: - + (
B: Operand → Add to output: Postfix: FED-^CB
+: Operator → Push to stack: Stack: - + ( +
A: Operand → Add to output: Postfix: FED-^CBA
): Left parenthesis after reversing (treated as right) → Pop from stack to output until ( is found. Postfix: FED-^CBA+ Stack: - +
Pop remaining operators from stack to output:
Postfix: FED-^CBA+-

Reverse the Postfix Expression to Get Prefix:

Reversed Postfix:
-+ABC^-DEF

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

#define MAX 100

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

// Initialize the stack
void initialize(Stack* stack) {
    stack->top = -1;
}

// Check if the stack is empty
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// Push element onto the stack
void push(Stack* stack, char c) {
    if (stack->top == MAX - 1) return;
    stack->items[++(stack->top)] = c;
}

// Pop element from the stack
char pop(Stack* stack) {
    if (isEmpty(stack)) return '\0';
    return stack->items[(stack->top)--];
}

// Peek at the top element of the stack
char peek(Stack* stack) {
    if (isEmpty(stack)) return '\0';
    return stack->items[stack->top];
}

// Determine precedence of operators
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '^') return 3;
    return 0;
}

// Check if character is an operator
int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

// Function to reverse a string
void reverseString(char* str) {
    int length = strlen(str);
    for (int i = 0; i < length / 2; i++) {
        char temp = str[i];
        str[i] = str[length - i - 1];
        str[length - i - 1] = temp;
    }
}

// Convert infix expression to prefix
void infixToPrefix(char* infix) {
    Stack s;
    initialize(&s);
    int length = strlen(infix);
    char postfix[MAX];
    int k = 0;

    // Reverse the infix expression
    reverseString(infix);

    // Swap '(' with ')' and vice versa
    for (int i = 0; i < length; i++) {
        if (infix[i] == '(') {
            infix[i] = ')';
        } else if (infix[i] == ')') {
            infix[i] = '(';
        }
    }

    // Process the reversed infix expression to get postfix
    for (int i = 0; i < length; i++) {
        char c = infix[i];

        if (isalnum(c)) {
            postfix[k++] = c;
        } else if (c == '(') {
            push(&s, c);
        } else if (c == ')') {
            while (peek(&s) != '(') {
                postfix[k++] = pop(&s);
            }
            pop(&s); // Remove '(' from the stack
        } else if (isOperator(c)) {
            while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(c)) {
                postfix[k++] = pop(&s);
            }
            push(&s, c);
        }
    }

    while (!isEmpty(&s)) {
        postfix[k++] = pop(&s);
    }

    postfix[k] = '\0';

    // Reverse the postfix expression to get the prefix expression
    reverseString(postfix);

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

int main() {
    char infix[MAX] = "(A+B)+C-(D-E)^F";
    infixToPrefix(infix);
    return 0;
}

Explanation:

Stack Operations: Basic stack operations (push, pop, peek) are used to manage the operators.
Reverse the Infix Expression: The expression is reversed, and parentheses are swapped to ensure the correct processing order.
Convert Reversed Infix to Postfix: The reversed expression is processed as a postfix conversion, respecting operator precedence and associativity.
Reverse the Postfix to Get Prefix: Finally, reverse the postfix result to get the prefix expression.

Output

Prefix Expression: -+ABC^-DEF

Create a function that searches for an integer num in a doubly linked list and displays the content (info/data) of its left node and right node. In case of unavailability, the content should be displayed as -1.

Answer

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

// Define the structure for a doubly linked list node
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// Function to search for a number and display adjacent node data
void searchAndDisplay(struct Node* head, int num) {
    struct Node* temp = head;

    while (temp != NULL) {
        if (temp->data == num) {
            int leftData = (temp->prev != NULL) ? temp->prev->data : -1;
            int rightData = (temp->next != NULL) ? temp->next->data : -1;

            printf("Left Node Data: %d\n", leftData);
            printf("Right Node Data: %d\n", rightData);
            return;
        }
        temp = temp->next;
    }

    printf("Number not found. Left Node Data: -1, Right Node Data: -1\n");
}

// Helper function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Example usage
int main() {
    // Creating a doubly linked list for demonstration
    struct Node* head = createNode(10);
    head->next = createNode(20);
    head->next->prev = head;
    head->next->next = createNode(30);
    head->next->next->prev = head->next;
    head->next->next->next = createNode(40);
    head->next->next->next->prev = head->next->next;

    int num = 20;
    searchAndDisplay(head, num);

    return 0;
}

Evaluate the following postfix expression where a=10, b=2, c=3, d=5, e=4:
```
a b / c - d e * + a c * -
```
Answer
To evaluate the postfix expression, follow these steps:
1. Substitute the values: 10 2 / 3 - 5 4 * + 10 3 * -
2. Process using a stack:
  - Push 10, 2
  - / operator: 10 / 2 = 5
  - Push 3
  - - operator: 5 - 3 = 2
  - Push 5, 4
  - * operator: 5 * 4 = 20
  - + operator: 2 + 20 = 22
  - Push 10, 3
  - * operator: 10 * 3 = 30
  - - operator: 22 - 30 = -8

Result: -8

The seven elements A, B, C, D, E, F, and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times, and each element is inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Finally, one element is popped from the stack. Stepwise show the content of both stack and queue.

Answer
- Initial Stack (after pushing G to A in reverse):
  Stack: G, F, E, D, C, B, A
- Pop 5 elements and insert them into the queue:
  Stack: G, F
  Queue: A, B, C, D, E
- Delete 2 elements from the queue and push onto the stack:
  Stack: G, F, A, B
  Queue: C, D, E
- Pop 1 element from the stack:
  Stack: G, F, A
  Queue: C, D, E

Write a function that concatenates two circular linked lists into one circular linked list.
Answer

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

// Define the structure for a circular linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to concatenate two circular linked lists
void concatenate(struct Node** head1, struct Node** head2) {
    if (*head1 == NULL) {
        *head1 = *head2;
        return;
    }
    if (*head2 == NULL) {
        return;
    }

    struct Node* temp1 = *head1;
    while (temp1->next != *head1) {
        temp1 = temp1->next;
    }

    struct Node* temp2 = *head2;
    while (temp2->next != *head2) {
        temp2 = temp2->next;
    }

    temp1->next = *head2;
    temp2->next = *head1;
}

// Helper function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = newNode;  // Points to itself to form a circular list
    return newNode;
}

// Example usage
int main() {
    // Creating two circular linked lists for demonstration
    struct Node* head1 = createNode(1);
    head1->next = createNode(2);
    head1->next->next = createNode(3);
    head1->next->next->next = head1;  // Making it circular

    struct Node* head2 = createNode(4);
    head2->next = createNode(5);
    head2->next->next = head2;  // Making it circular

    concatenate(&head1, &head2);

    // Printing the concatenated circular linked list
    struct Node* temp = head1;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head1);
    printf("\n");

    return 0;
}

Write insertion and deletion functions to implement an output-restricted double-ended queue (deque).
Answer
An output-restricted double-ended queue (deque) is a type of double-ended queue where insertion operations can be performed at both the front and rear ends, but deletion operations are restricted to only one end (usually the front).

This kind of deque allows for more flexible insertion while still maintaining the constraint of a traditional queue with respect to deletion. This structure is useful in scenarios where elements need to be added from both ends but only removed from one end, such as in certain scheduling or buffering algorithms.

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

#define MAX 100

// Define the structure for an output-restricted deque
struct Deque {
    int arr[MAX];
    int front, rear;
};

// Function to initialize deque
void initDeque(struct Deque* deque) {
    deque->front = -1;
    deque->rear = -1;
}

// Function to insert at the front of the deque
void insertFront(struct Deque* deque, int item) {
    if ((deque->front == 0 && deque->rear == MAX - 1) || (deque->front == deque->rear + 1)) {
        printf("Deque is full\n");
        return;
    }

    if (deque->front == -1) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->front == 0) {
        deque->front = MAX - 1;
    } else {
        deque->front = deque->front - 1;
    }

    deque->arr[deque->front] = item;
}

// Function to insert at the rear of the deque
void insertRear(struct Deque* deque, int item) {
    if ((deque->front == 0 && deque->rear == MAX - 1) || (deque->front == deque->rear + 1)) {
        printf("Deque is full\n");
        return;
    }

    if (deque->front == -1) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->rear == MAX - 1) {
        deque->rear = 0;
    } else {
        deque->rear = deque->rear + 1;
    }

    deque->arr[deque->rear] = item;
}

// Function to delete from the front of the deque
int deleteFront(struct Deque* deque) {
    if (deque->front == -1) {
        printf("Deque is empty\n");
        return -1;
    }

    int item = deque->arr[deque->front];
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->front == MAX - 1) {
        deque->front = 0;
    } else {
        deque->front = deque->front + 1;
    }

    return item;
}

// Example usage
int main() {
    struct Deque deque;
    initDeque(&deque);

    // Inserting elements into the deque
    insertRear(&deque, 10);
    insertRear(&deque, 20);
    insertFront(&deque, 5);
    insertRear(&deque, 30);

    // Deleting elements from the front
    printf("Deleted from front: %d\n", deleteFront(&deque));
    printf("Deleted from front: %d\n", deleteFront(&deque));
    printf("Deleted from front: %d\n", deleteFront(&deque));

    // Attempt to delete from an empty deque
    printf("Deleted from front: %d\n", deleteFront(&deque));

    return 0;
}

Explanation of the Code

Initialization (initDeque): Initializes the deque by setting both front and rear pointers to -1, indicating that the deque is empty.
Insertion at the Front (insertFront): Adds an element to the front of the deque. It adjusts the front pointer accordingly and handles cases where the deque is either full or empty.
Insertion at the Rear (insertRear): Adds an element to the rear of the deque. Similar to insertFront, it adjusts the rear pointer and checks for full or empty conditions.
Deletion from the Front (deleteFront): Removes an element from the front of the deque and returns it. If the deque becomes empty after the deletion, both front and rear pointers are reset to -1.
Output-Restricted Nature: The deletion operation is restricted to only the front of the deque, which is the defining characteristic of an output-restricted deque.

Given two singly linked lists, write the code to merge their nodes to make one list, taking nodes alternately between the two lists. If either list runs out, all the nodes should be taken from the other list.

Answer:

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

// Define the structure for a singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to merge two lists alternately
struct Node* mergeAlternately(struct Node* list1, struct Node* list2) {
    if (!list1) return list2;
    if (!list2) return list1;

    struct Node* head = list1;
    struct Node* temp1 = list1->next;
    struct Node* temp2 = list2;
    struct Node* current = head;

    int toggle = 0; // To switch between lists

    while (temp1 && temp2) {
        if (toggle == 0) {
            current->next = temp2;
            temp2 = temp2->next;
            toggle = 1;
        } else {
            current->next = temp1;
            temp1 = temp1->next;
            toggle = 0;
        }
        current = current->next;
    }

    // Append the remaining nodes of either list
    current->next = (temp1) ? temp1 : temp2;

    return head;
}

// Helper function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Helper function to print the list
void printList(struct Node* head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Example usage
int main() {
    // Creating two lists for demonstration
    struct Node* list1 = createNode(1);
    list1->next = createNode(2);
    list1->next->next = createNode(3);

    struct Node* list2 = createNode(7);
    list2->next = createNode(13);
    list2->next->next = createNode(1);

    struct Node* mergedList = mergeAlternately(list1, list2);
    printList(mergedList);

    return 0;
}

Represent the following sparse matrix in the triplet form using the data structure array and linked list. Write the C-code or pseudo-code to add two sparse matrices using any of the representations.

Sparse Matrix:

Answer

Triplet Representation

The triplet form of a sparse matrix stores only the non-zero elements along with their row and column indices. This can be represented using an array or a linked list.

Triplet Array Representation: Each non-zero element is stored as a triplet (row, column, value).

For the given matrix, the triplet representation would be:

Adding Two Sparse Matrices

Assume we have two matrices A and B in triplet form. The addition involves merging these two lists by adding values with the same row and column indices.

// Node structure for linked list representation
struct Node {
    int row, col, value;
    struct Node* next;
};

// Function to add two sparse matrices
struct Node* addSparseMatrices(struct Node* head1, struct Node* head2) {
    struct Node* head3 = NULL;
    struct Node* temp1 = head1;
    struct Node* temp2 = head2;
    struct Node* temp3 = NULL;

    while (temp1 != NULL && temp2 != NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->next = NULL;

        if (temp1->row < temp2->row || (temp1->row == temp2->row && temp1->col < temp2->col)) {
            newNode->row = temp1->row;
            newNode->col = temp1->col;
            newNode->value = temp1->value;
            temp1 = temp1->next;
        } else if (temp2->row < temp1->row || (temp1->row == temp2->row && temp2->col < temp1->col)) {
            newNode->row = temp2->row;
            newNode->col = temp2->col;
            newNode->value = temp2->value;
            temp2 = temp2->next;
        } else {
            newNode->row = temp1->row;
            newNode->col = temp1->col;
            newNode->value = temp1->value + temp2->value;
            temp1 = temp1->next;
            temp2 = temp2->next;
        }

        if (head3 == NULL) {
            head3 = newNode;
            temp3 = head3;
        } else {
            temp3->next = newNode;
            temp3 = temp3->next;
        }
    }

    while (temp1 != NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->row = temp1->row;
        newNode->col = temp1->col;
        newNode->value = temp1->value;
        newNode->next = NULL;
        temp3->next = newNode;
        temp3 = temp3->next;
        temp1 = temp1->next;
    }

    while (temp2 != NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->row = temp2->row;
        newNode->col = temp2->col;
        newNode->value = temp2->value;
        newNode->next = NULL;
        temp3->next = newNode;
        temp3 = temp3->next;
        temp2 = temp2->next;
    }

    return head3;
}

Write a program to insert n records (nodes) of student profiles in a double linked list such that the records or nodes will be present in ascending order of the student's CGPA. The student profile consists of roll number (int), name (string), and CGPA (float).
Answer

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

// Structure to hold student profile
struct Student {
    int rollNumber;
    char name[50];
    float cgpa;
    struct Student* prev;
    struct Student* next;
};

// Function to create a new node
struct Student* createStudent(int rollNumber, char* name, float cgpa) {
    struct Student* newStudent = (struct Student*)malloc(sizeof(struct Student));
    newStudent->rollNumber = rollNumber;
    strcpy(newStudent->name, name);
    newStudent->cgpa = cgpa;
    newStudent->prev = newStudent->next = NULL;
    return newStudent;
}

// Function to insert student in sorted order by CGPA
void insertStudent(struct Student** head, int rollNumber, char* name, float cgpa) {
    struct Student* newStudent = createStudent(rollNumber, name, cgpa);
    if (*head == NULL) {
        *head = newStudent;
        return;
    }

    struct Student* current = *head;

    while (current != NULL && current->cgpa < cgpa) {
        current = current->next;
    }

    if (current == NULL) {
        // Insert at the end
        struct Student* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newStudent;
        newStudent->prev = temp;
    } else {
        // Insert before the current node
        newStudent->next = current;
        newStudent->prev = current->prev;
        if (current->prev != NULL) {
            current->prev->next = newStudent;
        } else {
            *head = newStudent; // Update head if inserted at the beginning
        }
        current->prev = newStudent;
    }
}

// Function to display the list
void displayList(struct Student* head) {
    while (head != NULL) {
        printf("Roll Number: %d, Name: %s, CGPA: %.2f\n", head->rollNumber, head->name, head->cgpa);
        head = head->next;
    }
}

// Example usage
int main() {
    struct Student* head = NULL;
    insertStudent(&head, 101, "Alice", 8.5);
    insertStudent(&head, 102, "Bob", 7.8);
    insertStudent(&head, 103, "Charlie", 9.1);
    insertStudent(&head, 104, "David", 8.0);

    printf("Students in ascending order of CGPA:\n");
    displayList(head);

    return 0;
}

Write a C-code or pseudo-code that will create a new linked list by removing alternative nodes from the given linear linked list. Display the resultant two linked lists (old and new).

Input Example:
2 -> 5 -> 3 -> 7 -> 8
Output:
Old List: 5 -> 7
New List: 2 -> 3 -> 8

Answer

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

// Define the structure for a linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to split the list into two lists by removing alternate nodes
void splitAlternateNodes(struct Node* head, struct Node** newList) {
    struct Node* current = head;
    *newList = head;  // Initialize new list with the head

    while (current != NULL && current->next != NULL) {
        struct Node* temp = current->next;
        current->next = temp->next;
        current = current->next;
        temp->next = NULL;  // Isolate the removed node
    }
}

// Function to print a linked list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Example usage
int main() {
    // Creating a linked list for demonstration
    struct Node* head = createNode(2);
    head->next = createNode(5);
    head->next->next = createNode(3);
    head->next->next->next = createNode(7);
    head->next->next->next->next = createNode(8);

    printf("Original List:\n");
    printList(head);

    struct Node* newList = NULL;
    splitAlternateNodes(head, &newList);

    printf("Old List after removal of alternate nodes:\n");
    printList(head);

    printf("New List with removed nodes:\n");
    printList(newList);

    return 0;
}

What is the time complexity of the function func()?

    void func(int arr[], int n) {
        int i, j = 0;
        for (i = 0; i < n; i++) {
            while (j < n && arr[i] < arr[j]) {
                j++;
            }
        }
    }

Answer

The time complexity is O(n). This is because the outer loop runs n times, and the inner loop's total number of executions across all iterations of the outer loop is also at most n.

A matrix M[1...n, 1...n] is initialized as: M[i][j] = i - j for all i, j, 1 ≤ i ≤ n; 1 ≤ j ≤ n. Write a code for initializing M and find the sum of all the elements of the matrix M. If the value of n is 100, then what is the sum of all the elements of the matrix M?

Answer

    #include <stdio.h>

    int main() {
        int n = 100;
        int M[100][100];
        int sum = 0;

        // Initialize the matrix and compute the sum
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                M[i][j] = i - j;
                sum += M[i][j];
            }
        }

        printf("Sum of all elements in the matrix M: %d\n", sum);
        return 0;
    }

For n = 100, the sum is 0.

Let a doubly linked list consist of 20 elements. If a pointer called ptr is pointing to the 5th node of the list, then write a code to swap the 5th and 6th nodes of the list without using any additional pointer variable and without changing the ptr's position.
Define data structure and Abstract Data Type. Implement PUSH and POP operations of STACK ADT.

Answer

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

    #define MAX 100

    typedef struct Stack {
        int arr[MAX];
        int top;
    } Stack;

    // Initialize stack
    void initialize(Stack* stack) {
        stack->top = -1;
    }

    // Check if stack is empty
    int isEmpty(Stack* stack) {
        return stack->top == -1;
    }

    // Check if stack is full
    int isFull(Stack* stack) {
        return stack->top == MAX - 1;
    }

    // Push operation
    void push(Stack* stack, int value) {
        if (isFull(stack)) {
            printf("Stack Overflow\n");
            return;
        }
        stack->arr[++stack->top] = value;
    }

    // Pop operation
    int pop(Stack* stack) {
        if (isEmpty(stack)) {
            printf("Stack Underflow\n");
            return -1;
        }
        return stack->arr[stack->top--];
    }

    // Example usage
    int main() {
        Stack stack;
        initialize(&stack);
        push(&stack, 10);
        push(&stack, 20);
        printf("Popped: %d\n", pop(&stack));
        printf("Popped: %d\n", pop(&stack));
        return 0;
    }

What does the following function do for the linked list: 10 -> 20 -> 30 -> 40 -> 50?

    void func(struct Node* start) {
        if (start == NULL) return;
        func(start->next);
        printf("%d ", start->data);
        func(start->next);
    }

25. Design a suitable data structure to efficiently represent a sparse matrix? Write an algorithm to add the original sparse matrix with the transpose of the same matrix.

Answer
To efficiently represent a sparse matrix using the triplet form, we can design a data structure that uses an array of struct Triplet. Each Triplet will store the row index, column index, and value of a non-zero element. To add the original sparse matrix with its transpose, we will use this data structure to perform matrix operations.

Define a struct to hold each non-zero element's row index, column index, and value.
Use an array of this struct to represent the entire sparse matrix.

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

    // Define a struct for the triplet representation
    struct Triplet {
        int row;
        int col;
        int value;
    };

    // Function to display the triplet representation
    void displayTriplets(struct Triplet* spMatrix, int nonZeroCount) {
        printf("Row Column Value\n");
        for (int i = 0; i < nonZeroCount; i++) {
            printf("%d    %d     %d\n", spMatrix[i].row, spMatrix[i].col, spMatrix[i].value);
        }
    }

    // Function to transpose a sparse matrix
    void transposeSparseMatrix(struct Triplet* spMatrix, struct Triplet* transposeMatrix, int nonZeroCount) {
        for (int i = 0; i < nonZeroCount; i++) {
            transposeMatrix[i].row = spMatrix[i].col;
            transposeMatrix[i].col = spMatrix[i].row;
            transposeMatrix[i].value = spMatrix[i].value;
        }
    }

    // Function to add two sparse matrices
    void addSparseMatrices(struct Triplet* spMatrix, struct Triplet* transposeMatrix, struct Triplet* resultMatrix, int nonZeroCount, int* resultCount) {
        int i = 0, j = 0, k = 0;

        while (i < nonZeroCount && j < nonZeroCount) {
            if (spMatrix[i].row < transposeMatrix[j].row || 
               (spMatrix[i].row == transposeMatrix[j].row && spMatrix[i].col < transposeMatrix[j].col)) {
                resultMatrix[k++] = spMatrix[i++];
            } else if (transposeMatrix[j].row < spMatrix[i].row || 
                      (transposeMatrix[j].row == spMatrix[i].row && transposeMatrix[j].col < spMatrix[i].col)) {
                resultMatrix[k++] = transposeMatrix[j++];
            } else {
                resultMatrix[k].row = spMatrix[i].row;
                resultMatrix[k].col = spMatrix[i].col;
                resultMatrix[k].value = spMatrix[i].value + transposeMatrix[j].value;
                i++; j++; k++;
            }
        }

        // Add remaining elements
        while (i < nonZeroCount) {
            resultMatrix[k++] = spMatrix[i++];
        }

        while (j < nonZeroCount) {
            resultMatrix[k++] = transposeMatrix[j++];
        }

        *resultCount = k; // Update the count of non-zero elements in the result
    }

    int main() {
        // Example sparse matrix in triplet form
        struct Triplet spMatrix[] = {
            {0, 2, 3},
            {1, 0, 4},
            {2, 1, 5},
            {2, 3, 7}
        };

        int nonZeroCount = sizeof(spMatrix) / sizeof(spMatrix[0]);

        printf("Original Matrix in Triplet Form:\n");
        displayTriplets(spMatrix, nonZeroCount);

        // Array to store the transpose matrix
        struct Triplet transposeMatrix[nonZeroCount];
        transposeSparseMatrix(spMatrix, transposeMatrix, nonZeroCount);

        printf("\nTranspose Matrix in Triplet Form:\n");
        displayTriplets(transposeMatrix, nonZeroCount);

        // Array to store the result of addition
        struct Triplet resultMatrix[2 * nonZeroCount]; // In worst case, result can have at most 2 * nonZeroCount elements
        int resultCount = 0;

        // Add the original matrix and its transpose
        addSparseMatrices(spMatrix, transposeMatrix, resultMatrix, nonZeroCount, &resultCount);

        printf("\nResultant Matrix after Adding Original and Transpose:\n");
        displayTriplets(resultMatrix, resultCount);

        return 0;
    }

Explanation:

Struct Definition (Triplet):
- Defines a structure to store the row index, column index, and value of each non-zero element in the sparse matrix.
Array of Structs (spMatrix):
- Represents the sparse matrix as an array of Triplet structs, where each struct contains the row, column, and value of a non-zero element.
Function displayTriplets():
- Takes the array of triplets and the count of non-zero elements and prints the triplet form of the matrix.
Function transposeSparseMatrix():
- Computes the transpose of the sparse matrix by swapping the row and column indices for each triplet.
Function addSparseMatrices():
- Adds the original sparse matrix and its transpose by comparing the row and column indices of each element.
- Merges the two arrays in sorted order based on row and column indices.
Main Function (main()):
- Initializes the sparse matrix in triplet form, displays it, computes the transpose, adds the original matrix with its transpose, and then displays the result.

Write a pseudo code/function to reverse only even position nodes' values in a Singly Linked List.

Answer

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

// Define the structure for a singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to find the length of the list
int getLength(struct Node* head) {
    int length = 0;
    struct Node* current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

// Function to reverse values at even positions
void reverseEvenPositionValues(struct Node* head) {
    int length = getLength(head);
    if (length < 2) return; // No even positions to reverse

    struct Node *left = head, *right = head;
    int leftIndex = 2, rightIndex = length - (length % 2);

    // Move right pointer to the last even position
    for (int i = 1; i < rightIndex; i++) {
        right = right->next;
    }

    while (leftIndex < rightIndex) {
        struct Node* tempLeft = left;
        struct Node* tempRight = right;

        // Move left pointer to the next even position
        for (int j = 1; j < leftIndex; j++) {
            tempLeft = tempLeft->next;
        }

        // Move right pointer to the previous even position
        for (int j = length; j > rightIndex; j--) {
            tempRight = tempRight->next;
        }

        // Swap the values
        int temp = tempLeft->data;
        tempLeft->data = tempRight->data;
        tempRight->data = temp;

        // Update indices for next even positions
        leftIndex += 2;
        rightIndex -= 2;
    }
}

// Function to print the linked list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Example usage
int main() {
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);
    head->next->next->next->next->next = createNode(6);

    printf("Original List:\n");
    printList(head);

    reverseEvenPositionValues(head);

    printf("\nList after reversing even position nodes' values:\n");
    printList(head);

    return 0;
}

DS Midsem Prep

Comments (1)

More from this blog

Computer Arithmetic: From Fast Adders to Floating-Point

The Complete Memory Hierarchy: From Semiconductor RAM to Virtual Memory

The Ultimate Spring Boot Guide: From Fundamentals to Production-Ready REST APIs

Understanding Functions, Memory, and Pointers in C: A Complete Guide

Datapath and Control

Drawing the Linked List:

C-like Statements:

Infix Expression

Steps to Convert Infix to Prefix

Answer

Adding Two Sparse Matrices

Command Palette

Comments (1)

More from this blog

Drawing the Linked List:

C-like Statements:

Infix Expression

Steps to Convert Infix to Prefix

Answer

Adding Two Sparse Matrices