Free Solved Question Paper of MCS021 - Data and File Structure for June 2023

1. (a) Write an algorithm for multiplication of two n × n matrices. Calculate both time and space complexity for this algorithm. [10 marks]

Answer :

Algorithm for Multiplication of Two n × n Matrices:
Step 1: Initialize an empty matrix C of size n × n to store the result.
Step 2: For each element c_ij in matrix C, do the following:

→ Step 2.1: Set c_ij to 0.
→ Step 2.2: For each k from 0 to n-1, add the product of the elements from matrices A and B to c_ij:

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        C[i][j] = 0;
        for (k = 0; k < n; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}
        

Explanation:
The above algorithm uses three nested loops to perform the matrix multiplication:
→ The outer loop iterates over the rows of the resultant matrix C.
→ The middle loop iterates over the columns of the resultant matrix C.
→ The innermost loop calculates the dot product of the corresponding row from matrix A and the column from matrix B.

For each element c_ij in the resultant matrix C, the innermost loop performs the sum of products:
c_ij = Σ ( A_ik * B_kj ) for k from 0 to n-1.

Time Complexity:
The time complexity of this algorithm is O(n³). This is because the algorithm contains three nested loops, each iterating n times. Thus, the total number of operations is proportional to n × n × n or O(n³).

Space Complexity:
The space complexity of this algorithm is O(n²). This is due to the storage required for the resultant matrix C, which is of size n × n. The input matrices A and B are also of size n × n, but since they are provided as input, they do not contribute to the additional space complexity.

1. (b) What is a sparse matrix? Write an algorithm that accepts a 6 × 5 sparse matrix and output 3-tuple representation of the matrix. [10 marks]

Answer :

Sparse Matrix:
A sparse matrix is a matrix in which most of the elements are zero. Typically, a matrix is considered sparse when the number of non-zero elements is less than 10% of the total elements in the matrix.

Algorithm for 3-tuple representation of a 6 × 5 sparse matrix:

→ Step 1: Initialize a counter count to 0 for non-zero elements.
→ Step 2: Create a 2D array tuple to store the 3-tuple representation.
→ Step 3: Traverse the sparse matrix and for each non-zero element:
→ → Step 3.1: Increment count.
→ → Step 3.2: Add a new row to tuple with [row_index, column_index, value].
→ Step 4: Set the first row of tuple as [row_count, column_count, count].
→ Step 5: Output the tuple array.

Implementation in C-like pseudocode:

void sparse_to_3tuple(int matrix[6][5], int tuple[][3]) {
    int count = 0;
    
    // Count non-zero elements
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 5; j++) {
            if (matrix[i][j] != 0) {
                count++;
            }
        }
    }
    
    // Set first row of tuple
    tuple[0][0] = 6;  // Number of rows
    tuple[0][1] = 5;  // Number of columns
    tuple[0][2] = count;  // Number of non-zero elements
    
    // Fill the tuple array
    int k = 1;
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 5; j++) {
            if (matrix[i][j] != 0) {
                tuple[k][0] = i;
                tuple[k][1] = j;
                tuple[k][2] = matrix[i][j];
                k++;
            }
        }
    }
}

Explanation:
The algorithm first counts the number of non-zero elements in the matrix. It then creates a 3-tuple representation where:
→ The first row contains: [number of rows, number of columns, number of non-zero elements]
→ Each subsequent row represents a non-zero element as: [row index, column index, value]

Time Complexity: O(m × n), where m is the number of rows (6) and n is the number of columns (5).
Space Complexity: O(k), where k is the number of non-zero elements plus one (for the first row).

This 3-tuple representation is an efficient way to store sparse matrices, as it only stores information about non-zero elements, significantly reducing memory usage for matrices with many zero elements.

1. (c) Write an algorithm for array implementation of linked list. [10 marks]

Answer :

Array Implementation of Linked List:
An array implementation of a linked list uses an array to store the elements and another array to store the "next" pointers. This approach is also known as a "static linked list".

Algorithm for Array Implementation of Linked List:

1. Initialization:
→ Create an array data[] to store the elements.
→ Create an array next[] to store the indices of the next elements.
→ Initialize a variable head to -1 (indicating an empty list).
→ Initialize a variable availablePos to 0 (first available position in the array).

2. Insertion Algorithm:

→ Check if availablePos is greater than or equal to the maximum size of the array.
 → If yes, return "List is full".
→ Store the element at data[availablePos].
→ Update the next[availablePos] to head.
→ Update head to availablePos.
→ Increment availablePos by 1.

3. Deletion Algorithm (deleting the first element):

→ Check if head is -1.
 → If yes, return "List is empty".
→ Store the element to be deleted from data[head].
→ Move head to the next element indicated by next[head].
→ Return the deleted element.

4. Traversal Algorithm:

→ Initialize current to head.
→ While current is not -1, do the following:
 → Print the element at data[current].
 → Move current to the next element indicated by next[current].

Advantages:
→ Constant time insertion at the beginning of the list.
→ No dynamic memory allocation required.
→ Better cache performance due to contiguous memory allocation.

Disadvantages:
→ Fixed size, cannot grow beyond the initial array size.
→ Inefficient for large lists with many insertions and deletions.
→ Does not support efficient insertion at arbitrary positions.

Time Complexity:
→ Insertion at the beginning: O(1)
→ Deletion from the beginning: O(1)
→ Traversal: O(n), where n is the number of elements

Space Complexity: O(n), where n is the maximum number of elements that can be stored.

1. (d) What is a binary search? Write an algorithm for binary search and find its complexity. [10 marks]

Answer :

Binary Search:
Binary search is an efficient algorithm for searching an element in a sorted array by repeatedly dividing the search interval in half. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half until the target is found or it is clear the target is not in the array.

Algorithm for Binary Search:

binarySearch(arr, target, low, high):
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  // Target found
        elif arr[mid] < target:
            low = mid + 1  // Target is in the upper half
        else:
            high = mid - 1  // Target is in the lower half
    return -1  // Target not found

Explanation of the Algorithm:
→ Initialize two pointers: low at the start of the array and high at the end.
→ While low is less than or equal to high:
→ → Calculate the middle index mid.
→ → If the middle element is the target, return its index.
→ → If the target is greater than the middle element, search the upper half.
→ → If the target is less than the middle element, search the lower half.
→ If the loop ends without finding the target, return -1.

Complexity Analysis:
Time Complexity: O(log n)
→ In each step, the algorithm divides the search interval in half.
→ The number of steps required is logarithmic in the size of the input array.
→ Worst and average case: O(log n)
→ Best case (when the middle element is the target): O(1)

Space Complexity: O(1)
→ The algorithm uses a constant amount of extra space regardless of the input size.
→ It only requires a few variables (low, high, mid) to keep track of the search interval.

Advantages of Binary Search:
→ Very efficient for large sorted datasets.
→ Significantly faster than linear search for large arrays.
→ Useful in many algorithms and data structures (e.g., binary search trees).

Limitations:
→ Requires the array to be sorted beforehand.
→ Not efficient for small arrays or frequently changing datasets where sorting overhead is significant.

2. (a) What is a Splay Tree? Explain how it is different from a binary tree. [10 marks]

Answer :

Splay Tree:
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, search and deletion in O(log n) amortized time.

Key Features of Splay Trees:
→ Self-adjusting: After an access, the tree is restructured using a splay operation.
→ Splay operation: Moves the accessed node to the root through a series of rotations.
→ Amortized efficiency: While individual operations can be O(n), the average over a sequence of operations is O(log n).

Differences from a Regular Binary Tree:

1. Structure Modification:
→ Binary Tree: Structure remains static after insertion unless explicitly balanced.
→ Splay Tree: Structure changes with each access, bringing the accessed node to the root.

2. Balance:
→ Binary Tree: Can become highly unbalanced, leading to O(n) operations in worst case.
→ Splay Tree: Maintains a rough balance through splaying, ensuring amortized O(log n) operations.

3. Access Patterns:
→ Binary Tree: Performance doesn't adapt to access patterns.
→ Splay Tree: Automatically brings frequently accessed items closer to the root, improving future access times.

4. Complexity:
→ Binary Tree: Operations have O(h) worst-case time, where h is the height of the tree.
→ Splay Tree: Operations have O(log n) amortized time, regardless of the tree's current shape.

5. Implementation:
→ Binary Tree: Simpler implementation with straightforward insert, delete, and search operations.
→ Splay Tree: More complex implementation due to the splay operation and various rotation cases.

6. Memory Usage:
→ Binary Tree: Consistent memory usage.
→ Splay Tree: May require more memory operations due to frequent restructuring.

7. Use Cases:
→ Binary Tree: General-purpose tree structure, good for stable datasets.
→ Splay Tree: Excellent for applications with locality of reference or where recent items are likely to be accessed again.

Conclusion:
While both are binary search trees, splay trees offer a unique self-adjusting property that can provide significant performance benefits in certain scenarios, especially when access patterns exhibit temporal locality. However, this comes at the cost of more complex implementation and potentially more frequent tree restructuring operations.

2. (b) Traverse the following binary tree in Pre-order and In-order: [10 marks]

Answer :

Pre-order Traversal:

In pre-order traversal, we visit the root node first, then the left subtree, and finally the right subtree. The process is as follows:

A → B → C → D → E → G → F

Explanation of Pre-order traversal:

1. Start at root A and visit it
2. Move to left child B and visit it
3. Move to B's left child C and visit it
4. Return to A and move to right child D, visit it
5. Move to D's left child E and visit it
6. Move to E's left child G and visit it
7. Return to D and visit its right child F

In-order Traversal:

In in-order traversal, we visit the left subtree first, then the root node, and finally the right subtree. The process is as follows:

C → B → A → G → E → D → F

Explanation of In-order traversal:

1. Start at the leftmost node C and visit it
2. Move up to parent B and visit it
3. Move up to root A and visit it
4. Move to A's right subtree, then to the leftmost node G and visit it
5. Move up to parent E and visit it
6. Move up to D and visit it
7. Finally, visit D's right child F

Key Points:

→ Pre-order traversal is useful for creating a copy of the tree or prefix expression of an expression tree.
→ In-order traversal of a binary search tree gives nodes in non-decreasing order.
→ These traversals are fundamental in many tree-based algorithms and operations.

3. (a) Explain Quick sort algorithm. Sort the following set of data using this algorithm. Show intermediate steps of sorting: 20, 6, 8, 19, 36, 4, 28, 50 [10 marks]

Answer :

Quick Sort Algorithm:
Quick sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Steps of Quick Sort:
1. Choose a pivot element from the array.
2. Partition the array around the pivot, such that:
→ Elements smaller than the pivot are on the left.
→ Elements greater than the pivot are on the right.
3. Recursively apply steps 1-2 to the sub-array of elements with smaller values and the sub-array of elements with greater values.

Sorting the given data: 20, 6, 8, 19, 36, 4, 28, 50

Step 1 (First partition):
Choose 20 as pivot:
[6, 8, 19, 4, 20, 36, 28, 50]

Step 2 (Recursion on left sub-array):
[6, 8, 19, 4] - Choose 6 as pivot:
[4, 6, 8, 19] - Left side sorted

Step 3 (Recursion on right sub-array):
[36, 28, 50] - Choose 36 as pivot:
[28, 36, 50] - Right side sorted

Final sorted array:
[4, 6, 8, 19, 20, 28, 36, 50]

Time Complexity:
→ Average case: O(n log n)
→ Worst case: O(n²) - occurs when the pivot is always the smallest or largest element
→ Best case: O(n log n) - occurs when the pivot always divides the array in half

Space Complexity: O(log n) due to the recursive call stack

Advantages of Quick Sort:
→ In-place sorting (requires little additional memory)
→ Very efficient for large datasets
→ Good cache performance

Disadvantages:
→ Unstable sort (doesn't preserve the relative order of equal elements)
→ Worst-case time complexity of O(n²)

3. (b) What is an Indexed Sequential File Organization? How is it different from direct file organization? Explain. [10 marks]

Answer :

Indexed Sequential File Organization:
Indexed Sequential File Organization is a method of organizing and accessing data in a file that combines features of both sequential and indexed file organizations. It allows both sequential access and direct access to records.

Key Features of Indexed Sequential File Organization:
→ Records are stored in sequential order based on a key field.
→ An index is maintained to allow direct access to records.
→ Supports both sequential and random access to records.

Differences from Direct File Organization:

1. Record Organization:
→ Indexed Sequential: Records are stored in a sorted order based on a key field.
→ Direct: Records are stored at locations determined by a hashing function applied to the key.

2. Access Method:
→ Indexed Sequential: Supports both sequential and direct access.
→ Direct: Primarily supports direct access to records.

3. Index Structure:
→ Indexed Sequential: Uses a multi-level index structure (cylinder index, track index, etc.).
→ Direct: Typically doesn't use an index structure; relies on the hashing function.

4. Search Efficiency:
→ Indexed Sequential: Efficient for both range queries and individual record retrieval.
→ Direct: Very efficient for individual record retrieval, less so for range queries.

5. Space Utilization:
→ Indexed Sequential: May have some unused space due to the need for sequential ordering.
→ Direct: Can have better space utilization but may suffer from collisions.

6. Insertion and Deletion:
→ Indexed Sequential: Insertions and deletions can be complex, often requiring reorganization.
→ Direct: Insertions and deletions are generally simpler and don't require reorganization.

7. Suitability:
→ Indexed Sequential: Suited for applications requiring both sequential processing and random access.
→ Direct: Best for applications requiring frequent, rapid access to individual records.

Conclusion:
Indexed Sequential File Organization offers a balance between the efficiency of direct access and the flexibility of sequential access. It's particularly useful in scenarios where both types of access are required, such as in database management systems. Direct File Organization, on the other hand, excels in situations where rapid access to individual records is the primary requirement, but it lacks the sequential access capabilities of Indexed Sequential organization.

4. (a) What is a spanning tree? What are its applications? Write Kruskal's algorithm to find minimum cost spanning tree and explain it in terms of its complexity. [10 marks]

Answer :

Spanning Tree:
A spanning tree of an undirected graph is a subgraph that includes all the vertices of the graph and is a tree (i.e., it has no cycles). A minimum spanning tree (MST) is a spanning tree with weight less than or equal to the weight of every other spanning tree.

Applications of Spanning Trees:
→ Network design (e.g., computer networks, telecommunications)
→ Circuit design in electrical engineering
→ Transportation networks and civil engineering
→ Clustering and classification in data analysis
→ Image processing and computer vision

Kruskal's Algorithm for Minimum Spanning Tree:

KruskalMST(Graph G):
    A = ∅ (A will contain the edges of the MST)
    Sort all edges of G in non-decreasing order of weight
    Create a disjoint set for each vertex
    For each edge (u,v) in the sorted edge list:
        If Find(u) ≠ Find(v):
            Add edge (u,v) to A
            Union(u,v)
    Return A

Explanation of Kruskal's Algorithm:
1. Start with an empty set A to store MST edges.
2. Sort all edges in non-decreasing order of weight.
3. For each edge, check if it forms a cycle with the spanning tree formed so far:
→ If no cycle is formed, add the edge to A.
→ If a cycle is formed, discard the edge.
4. Repeat step 3 until (n-1) edges are added to A, where n is the number of vertices.

Complexity Analysis:
Time Complexity: O(E log E) or O(E log V)
→ Sorting edges: O(E log E)
→ Find and Union operations: O(log V) each
→ Total: O(E log E) + O(E log V) = O(E log E) (since E ≤ V²)

Space Complexity: O(E + V)
→ O(E) for sorting edges
→ O(V) for disjoint set data structure

Optimizations:
→ Using efficient disjoint set data structures (e.g., union by rank, path compression) can improve the time complexity to nearly O(E).
→ For dense graphs, Prim's algorithm might be more efficient.

Advantages of Kruskal's Algorithm:
→ Simple to implement
→ Works well for sparse graphs
→ Can be easily adapted for distributed systems

Limitations:
→ Not as efficient for dense graphs compared to Prim's algorithm
→ Requires sorting of all edges, which can be memory-intensive for large graphs

4. (b) Define AVL tree. Write any two applications of AVL tree. [10 marks]

Answer :

AVL Tree:
An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. This balance is maintained through rotation operations performed after insertions and deletions.

Key Properties:
→ Balance Factor: For each node, the height difference between left and right subtrees is at most 1.
→ Self-Balancing: Automatically rebalances after insertions and deletions.
→ Height: The height of an AVL tree is always O(log n), where n is the number of nodes.

Two Applications of AVL Trees:

1. Database Indexing:
→ AVL trees are used in database systems to create and maintain indices.
→ Ensures fast data retrieval, insertion, and deletion operations.
→ Maintains balance even with frequent updates, ensuring consistent performance.

2. In-memory Sorting and Searching:
→ Used in memory management systems for efficient allocation and deallocation.
→ Provides fast in-memory sorting and searching capabilities.
→ Useful in applications requiring frequent lookups and modifications, such as spell checkers or symbol tables in compilers.

Advantages of AVL Trees:
→ Guaranteed O(log n) time complexity for search, insert, and delete operations.
→ Automatic balancing ensures consistent performance regardless of input order.
→ Efficient for applications with frequent lookups and less frequent modifications.

Limitations:
→ More complex implementation compared to simple binary search trees.
→ Higher memory overhead due to balance factor storage and more frequent rotations.
→ May be overkill for small datasets or applications with infrequent updates.

5. (a) Write algorithms for the following:
(i) To create doubly linked list.
(ii) To delete an element from a doubly linked list. [10 marks]

Answer :

(i) Algorithm to Create a Doubly Linked List:

CreateDoublyLinkedList():
    head = null
    tail = null

InsertNode(data):
    newNode = new Node(data)
    if head is null:
        head = newNode
        tail = newNode
    else:
        tail.next = newNode
        newNode.prev = tail
        tail = newNode

Explanation:
→ Initialize empty list with head and tail as null.
→ For each insertion, create a new node.
→ If list is empty, set both head and tail to the new node.
→ Otherwise, add the new node at the end and update pointers.

(ii) Algorithm to Delete an Element from a Doubly Linked List:

DeleteNode(key):
    if head is null:
        return  // List is empty

    current = head
    while current is not null and current.data != key:
        current = current.next

    if current is null:
        return  // Key not found

    if current == head:
        head = current.next
    else:
        current.prev.next = current.next

    if current == tail:
        tail = current.prev
    else:
        current.next.prev = current.prev

    delete current

Explanation:
→ Traverse the list to find the node with the given key.
→ If found, update the pointers of adjacent nodes.
→ Handle special cases: deleting head, tail, or the only node.
→ Free the memory of the deleted node.

Time Complexity:
→ Creation (inserting n elements): O(n)
→ Deletion: O(n) in worst case (searching for the element)

Space Complexity:
→ O(1) for both operations (excluding the space for the list itself)

5. (b) What is a stack? Explain PUSH and POP operations of stack with the help of algorithms for each operation. [10 marks]

Answer :

Stack:
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Elements can be added or removed only from one end, called the top of the stack.

Key Characteristics:
→ LIFO (Last In First Out) ordering
→ Operations are performed at one end only (top)
→ Main operations: PUSH (insert) and POP (remove)

1. PUSH Operation:
PUSH adds an element to the top of the stack.

PUSH(stack, max_size, element):
    if top >= max_size - 1:
        return "Stack Overflow"
    top = top + 1
    stack[top] = element

Explanation of PUSH:
→ Check if stack is full (top == max_size - 1).
→ If not full, increment top.
→ Add the new element at the top position.

2. POP Operation:
POP removes and returns the top element from the stack.

POP(stack):
    if top < 0:
        return "Stack Underflow"
    element = stack[top]
    top = top - 1
    return element

Explanation of POP:
→ Check if stack is empty (top < 0).
→ If not empty, store the top element.
→ Decrement top.
→ Return the stored element.

Time Complexity:
→ PUSH: O(1)
→ POP: O(1)

Space Complexity:
→ O(1) for both operations

Applications of Stack:
→ Function call management (Call Stack)
→ Expression evaluation and syntax parsing
→ Undo mechanisms in text editors
→ Backtracking algorithms
→ Browser history (back button functionality)

Advantages of Stack:
→ Simple and efficient implementation
→ Fast access to the most recently added element
→ Useful for algorithms that need to backtrack or undo operations

Limitations:
→ Limited access (only top element is directly accessible)
→ Fixed size in array implementation (can lead to stack overflow)
→ Not suitable for problems requiring random access to elements