IGNOU MCS-208 Solved Question Paper PDF Download

IGNOU MCS-208 Previous Year Solved Question Paper in Hindi

IGNOU MCS-208 Previous Year Solved Question Paper in English

Q1. (a) What is an algorithm ? What are its properties ? Explain tradeoff between space and time complexity of algorithms. Explain time complexity of linear search algorithm. (b) What is Stack ? Implement stack using array. (c) Write preorder and postorder traversals of the following tree: [Image of a tree] (d) What is Link List ? Write algorithms for inserting and deleting element in link list.

Ans. (a) Algorithm and its Complexity Algorithm: An algorithm is a finite set of well-defined, step-by-step instructions to solve a problem or perform a computation. It is like a recipe that specifies exactly what to do to complete a specific task. Properties of an Algorithm:

• Finiteness: An algorithm must always terminate after a finite number of steps.
• Definiteness: Each step of the algorithm must be precise and unambiguous.
• Input: An algorithm may have zero or more well-defined inputs.
• Output: An algorithm must have one or more well-defined outputs, which are related to the input.
• Effectiveness: Every instruction must be basic enough to be carried out, in principle, by a person using only paper and pencil.

Space-Time Tradeoff:

This is a fundamental concept in computer science. It means that often, one has to use more memory (space) to make an algorithm faster (reduce time), or conversely, make it run for a longer time to reduce memory usage. For example, storing pre-computed data in a lookup table (more space) can speed up processing (time) compared to calculating it on the fly.

Time Complexity of Linear Search:

Linear search is a simple method for finding an item in an array. It starts from the beginning of the array and checks each element sequentially until the desired element is found or the end of the array is reached.

• Best Case Complexity: O(1) – This occurs when the element being searched for is the very first element of the array.
• Worst Case Complexity: O(n) – This occurs when the element is the last element of the array or is not present in the array at all. In this case, all ‘n’ elements must be checked.
• Average Case Complexity: O(n) – On average, the algorithm has to scan half of the array to find the element.

Thus, the overall time complexity of a linear search is considered to be

O(n)

.

(b) Stack and its Array Implementation

Stack:

A stack is a linear data structure that follows the

LIFO (Last-In, First-Out)

principle. This means the element that is added last is the one to be removed first. It works like a stack of plates.

The main operations are:

• Push: Adding an element to the top of the stack.
• Pop: Removing an element from the top of the stack.
• Peek (or Top): Viewing the top element without removing it.

Implementation using Array:

We can implement a stack using an array and a variable called `top` that tracks the top element of the stack.

#define MAX_SIZE 100int stack[MAX_SIZE];int top = -1;
// Function to check for overflowint isFull() { return top == MAX_SIZE - 1;}
// Function to check for underflowint isEmpty() { return top == -1;}
// Algorithm to push an element into the stackvoid push(int item) { if (isFull()) { printf("Stack Overflow\n"); return; } top = top + 1; stack[top] = item;}
// Algorithm to pop an element from the stackint pop() { if (isEmpty()) { printf("Stack Underflow\n"); return -1; // Error value } int item = stack[top]; top = top - 1; return item;}

(c) Tree Traversal

For the given tree (using standard labeling A, B, C…), the traversals are as follows:

(Assumed tree: Root A; B and C are children of A; D and F are children of B; G is child of C; E is child of D; H and I are children of E)

Preorder Traversal (Root, Left, Right):

In this traversal, we first visit the root node, then recursively traverse the left subtree, and finally recursively traverse the right subtree.

Order: A → B → D → E → H → I → F → C → G

Postorder Traversal (Left, Right, Root):

In this traversal, we first recursively traverse the left subtree, then recursively traverse the right subtree, and finally visit the root node.

Order: H → I → E → D → F → B → G → C → A

(d) Linked List

Linked List:

A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element is a ‘node’ that contains two parts: the

data

and a

pointer (or link)

to the next node in the sequence. This allows for dynamic memory allocation.

Algorithm for Inserting Element (at the beginning):

1. Allocate memory for a new node called `newNode`.

2. Set the data part of the `newNode` to the value.

3. Point the `next` pointer of the `newNode` to the current `head` node.

4. Update the `head` to point to the `newNode`.

void insertAtBeginning(int data) { // Node structure: struct Node { int data; struct Node* next; }; // head is a global pointer struct Node newNode = (struct Node)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = head; head = newNode;}

Algorithm for Deleting Element (from the beginning): 1. Check if the list is empty (`head` is NULL). If so, exit. 2. Create a temporary pointer `temp` and point it to the `head`. 3. Move the `head` to the next node (`head = head->next`). 4. Free the memory pointed to by `temp`.

void deleteFromBeginning() { if (head == NULL) { printf("List is empty.\n"); return; } struct Node* temp = head; head = head->next; free(temp);}

Q2. (a) What is a binary tree ? What are its properties ? Explain how to create a binary tree with the help of a suitable code. (b) What is queue data structure ? What are its properties ? Implement queue using linked list. Make necessary assumptions.

Ans. (a) Binary Tree Binary Tree: A binary tree is a hierarchical data structure in which each node can have at most two children, referred to as the left child and the right child . The topmost node is called the root . Nodes that have no children are called leaf nodes . Properties of a Binary Tree:

• The maximum number of nodes in a binary tree of height ‘h’ (root at 0) is 2 ^h+1 – 1 .
• The maximum number of nodes at level ‘l’ is 2 ^l .
• The minimum possible height for a binary tree with ‘N’ nodes is log₂(N+1) – 1 .
• In a non-empty binary tree, if n₀ is the number of leaf nodes and n₂ is the number of nodes with two children, then n₀ = n₂ + 1 .

Creating a Binary Tree:

To create a binary tree, we first define a node structure. Then, we use a function to create nodes and link them together.

#include <stdio.h>#include <stdlib.h>
// Structure of a binary tree nodestruct Node { int data; struct Node* left; struct Node* right;};
// A helper function to create a new nodestruct Node* createNode(int data) { struct Node newNode = (struct Node)malloc(sizeof(struct Node)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode;}
int main() { // Create the tree // Root node struct Node* root = createNode(1); /* 1 / \ NULL NULL */
 // Add children root->left = createNode(2); root->right = createNode(3);
 /* 1 / \ 2 3 */
 // Add another child to the left child root->left->left = createNode(4); /* 1 / \ 2 3 / 4 */
 printf("Binary tree created successfully.\n"); printf("Value of root node: %d\n", root->data); printf("Value of root's left child: %d\n", root->left->data); return 0;}

(b) Queue and its Linked List Implementation

Queue Data Structure:

A queue is a linear data structure that operates on a

FIFO (First-In, First-Out)

principle. This means the first element inserted is the first one to be removed. It is like people standing in a queue (line).

Properties of a Queue:

• It has two ends: Front and Rear .
• Elements are inserted at the Rear end (this operation is called Enqueue ).
• Elements are removed from the Front end (this operation is called Dequeue ).
• If the queue is empty, both Front and Rear are NULL.

Implementation using Linked List:

A linked list is ideal for a queue as it can grow and shrink dynamically. We will use two pointers, `front` and `rear`.

#include <stdio.h>#include <stdlib.h>
// Structure of a nodestruct Node { int data; struct Node* next;};
// Front and Rear pointers of the queuestruct Node *front = NULL;struct Node *rear = NULL;
// To add an element to the queue (Enqueue)void enqueue(int value) { struct Node newNode = (struct Node)malloc(sizeof(struct Node)); newNode->data = value; newNode->next = NULL;
 // If queue is empty, new node is both front and rear if (rear == NULL) { front = rear = newNode; return; }
 // Add the new node at the end of the existing rear node rear->next = newNode; rear = newNode;}
// To remove an element from the queue (Dequeue)int dequeue() { // If queue is empty, it's an underflow if (front == NULL) { printf("Queue Underflow\n"); return -1; }
 // Store front node and move front to the next struct Node* temp = front; int item = temp->data; front = front->next;
 // If front becomes NULL, also make rear NULL if (front == NULL) { rear = NULL; }
 free(temp); // free the old front node return item;}

Q3. (a) What is array ? Explain row major and column major representations of array with examples. (b) What is need of file organisation ? What are key drivers for file organization ? Explain indexed sequential file organization.

Ans. (a) Array and its Memory Representation Array: An array is a linear data structure that is a collection of data items of the same type stored in contiguous memory locations . Each item can be accessed using an index number. It allows storing multiple variables under a single name. There are two main ways to map multi-dimensional arrays, like 2D arrays, into linear memory: 1. Row-Major Representation: In this method, the elements of a 2D array are stored row by row. All elements of the first row are stored first, followed by all elements of the second row, and so on. Languages like ‘C’, ‘C++’, and ‘Python’ use row-major order. The address of an element `A[i][j]` for an `m x n` array `A` can be calculated using the formula: Address(A[i][j]) = BaseAddress + (i n + j) size where `BaseAddress` is the initial address of the array, `i` is the row index, `j` is the column index, `n` is the total number of columns, and `size` is the size of each element. Example: A 3×3 array `int A[3][3]` would look like this in memory: A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2], A[2][0], A[2][1], A[2][2] 2. Column-Major Representation: In this method, the elements of a 2D array are stored column by column. All elements of the first column are stored first, followed by all elements of the second column, and so on. Languages like ‘Fortran’ and ‘MATLAB’ use column-major order. The address of the element `A[i][j]` can be calculated using the formula: Address(A[i][j]) = BaseAddress + (j m + i) size where `m` is the total number of rows. Example: The same 3×3 array `int A[3][3]` would look like this in memory: A[0][0], A[1][0], A[2][0], A[0][1], A[1][1], A[2][1], A[0][2], A[1][2], A[2][2] (b) File Organization Need for File Organization: File organization refers to the way records (data) are stored on secondary storage devices like disks. Efficient file organization is needed for:

• Fast Data Access: To reduce the time it takes to find and retrieve records quickly.
• Efficient Storage: To make optimal use of storage space and reduce wastage.
• Easy Updates: To allow for easy insertion, deletion, and modification of records.
• Data Integrity: To ensure that the data stored is consistent and accurate.
• Safety and Security: To protect data from unauthorized access and system failures.

Key Drivers:

The choice of file organization depends on several factors, known as key drivers:

• Access Pattern: Will the data be accessed sequentially (one after another) or randomly (in any order)?
• Update Frequency: How often is the data modified?
• Response Time: How quickly do users need the data?
• Storage Cost: The cost and capacity of the available storage.

Indexed Sequential File Organization:

This method combines the benefits of both sequential file organization and direct (or random) file organization. It is also known as

ISAM (Indexed Sequential Access Method)

.

• Structure: Records are stored physically in a sequential order based on a key field (e.g., employee ID).
• Index: An index is created to provide faster access to records. The index contains entries of key values and their corresponding addresses of the records on the disk. To find a record, the system first searches the index to find the approximate location of the block containing the record, and then searches that block sequentially.
• Advantages: It is efficient for both sequential processing (like payroll) and random processing (like retrieving a specific customer’s record).
• Disadvantages: It requires extra space for maintaining the index. Performance can degrade when many records are inserted or deleted, requiring frequent reorganization of the file.

Q4. (a) Sort the following lists using Bubble Sort Algorithm. Showing intermediate steps: 25 8 22 90 80 60 0 (b) What is graph ? Write adjacency matrix representation of the following graph : [Image of a graph] (c) What are B-trees ? What are its applications ?

Ans. (a) Bubble Sort Algorithm Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. Original List: [25, 8, 22, 90, 80, 60, 0] Intermediate Steps: Pass 1: [ 8, 25 , 22, 90, 80, 60, 0] (25 > 8, swap) [8, 22, 25 , 90, 80, 60, 0] (25 > 22, swap) [8, 22, 25, 80, 90 , 60, 0] (90 > 80, swap) [8, 22, 25, 80, 60, 90 , 0] (90 > 60, swap) [8, 22, 25, 80, 60, 0, 90 ] (90 > 0, swap) After Pass 1: [8, 22, 25, 80, 60, 0, 90 ] Pass 2: [8, 22, 25, 60, 80 , 0, 90] (80 > 60, swap) [8, 22, 25, 60, 0, 80 , 90] (80 > 0, swap) After Pass 2: [8, 22, 25, 60, 0, 80, 90 ] Pass 3: [8, 22, 25, 0, 60 , 80, 90] (60 > 0, swap) After Pass 3: [8, 22, 25, 0, 60, 80, 90 ] Pass 4: [8, 22, 0, 25 , 60, 80, 90] (25 > 0, swap) After Pass 4: [8, 22, 0, 25, 60, 80, 90 ] Pass 5: [8, 0, 22 , 25, 60, 80, 90] (22 > 0, swap) After Pass 5: [8, 0, 22, 25, 60, 80, 90 ] Pass 6: [ 0, 8 , 22, 25, 60, 80, 90] (8 > 0, swap) After Pass 6: [0, 8, 22, 25, 60, 80, 90] Sorted List: [0, 8, 22, 25, 60, 80, 90] (b) Graph and Adjacency Matrix Graph: A graph is a non-linear data structure consisting of a set of vertices (or nodes) and a set of edges (or arcs) that connect these vertices. A graph G is represented as G = (V, E), where V is the set of vertices and E is the set of edges. Graphs are used to model networks, circuits, and various relationships. Adjacency Matrix Representation: This is a way of representing a graph using a 2D matrix `A`, where the value of `A[i][j]` indicates whether there is an edge between vertex `i` and vertex `j`.

• If there is an edge between vertex `i` and `j`, then `A[i][j] = 1`.
• Otherwise, `A[i][j] = 0`.

For the given graph (a complete graph K₄), which has 4 vertices (let’s assume 1, 2, 3, 4), and every vertex is connected to every other vertex.

Adjacency Matrix:

 1 2 3 4 1[0 1 1 1] 2[1 0 1 1] 3[1 1 0 1] 4[1 1 1 0]

This matrix is symmetric because the graph is undirected. (c) B-Trees B-Tree: A B-tree is a self-balancing search tree designed to minimize search times for data stored on secondary storage devices like disks. Unlike binary search trees, nodes of a B-tree can have more than two children. Properties of a B-Tree:

• All leaf nodes are at the same level.
• A B-tree is defined by a minimum degree ‘t’ (t ≥ 2).
• Every node except the root must have at least `t-1` keys. The root may have at least 1 key.
• Every node can have at most `2t-1` keys.
• An internal node has one more child than its number of keys.

These properties ensure that the tree remains balanced and relatively shallow, thus reducing the number of disk accesses. Applications of B-Trees: B-trees are widely used in systems that need to read and write large amounts of data.

• Database Systems: Almost all modern databases (e.g., Oracle, MySQL, PostgreSQL) use B-trees or their variants (like B+ trees) to implement indexes on tables for fast data retrieval.
• File Systems: Many file systems (e.g., NTFS, HFS+, JFS) use B-trees to efficiently manage and locate files and directories.
• Searching in Large Datasets: In any application where data resides on disk and needs to be searched quickly, B-trees are a suitable choice.

Q5. (a) What is AVL tree ? Explain insertion of a node into an AVL tree. (b) Write binary search algorithm. (c) What is spanning tree ? Write and explain Prim’s algorithm to find minimum cost spanning tree. Also, write the applications of spanning tree.

Ans. (a) AVL Tree AVL Tree: An AVL tree (named after its inventors Adelson-Velsky and Landis) is a self-balancing Binary Search Tree (BST) . In it, for any node, the difference between the heights of the left and right subtrees cannot be more than 1. This property is measured by the Balance Factor . Balance Factor = height(left subtree) – height(right subtree) Every node in an AVL tree must have a balance factor of -1, 0, or 1. Insertion of a Node into an AVL Tree: The process of inserting a node into an AVL tree involves two stages: 1. Standard BST Insertion: First, the new node is inserted in the same way as in a standard Binary Search Tree. 2. Rebalancing: After insertion, we trace the path back from the inserted node to the root. For each node on this path, we check its balance factor. If a node becomes unbalanced (balance factor is not -1, 0, or 1), a rotation is performed to rebalance the tree. There are four types of imbalances and corresponding rotations:

• Left-Left (LL) Case: The new node is inserted into the left subtree of the left child of the unbalanced node ‘z’. This is fixed by a single Right Rotation .
• Right-Right (RR) Case: The new node is inserted into the right subtree of the right child of ‘z’. This is fixed by a single Left Rotation .
• Left-Right (LR) Case: The new node is inserted into the right subtree of the left child of ‘z’. This is fixed by a Left Rotation followed by a Right Rotation (a double rotation ).
• Right-Left (RL) Case: The new node is inserted into the left subtree of the right child of ‘z’. This is fixed by a Right Rotation followed by a Left Rotation (a double rotation ).

These rotations rebalance the tree’s height while preserving the BST property.

(b) Binary Search Algorithm

Binary search is an efficient algorithm for finding a value in a

sorted array

. It works by repeatedly dividing the search interval in half.

Algorithm:

1. Compare the target value with the middle element of the array.

2. If the target value matches the middle element, return its index.

3. If the target value is less than the middle element, continue the search in the lower half (to the left).

4. If the target value is greater than the middle element, continue the search in the upper half (to the right).

5. This process is repeated until the value is found or the interval is empty.

Iterative Algorithm in C-like language:

int binarySearch(int arr[], int size, int key) { int left = 0; int right = size - 1;
 while (left <= right) { // Calculate mid to avoid overflow int mid = left + (right - left) / 2;
 // Check if key is present at mid if (arr[mid] == key) { return mid; // Element found }
 // If key is greater, ignore left half if (arr[mid] < key) { left = mid + 1; }  // If key is smaller, ignore right half else { right = mid - 1; } }
 // If we reach here, then element was not present return -1;}

The time complexity of binary search is

O(log n)

, making it very fast for large datasets.

(c) Spanning Tree and Prim’s Algorithm

Spanning Tree:

A spanning tree of a connected, undirected graph G is a subgraph that is a tree and includes all the vertices of G. It has the minimum possible number of edges that connect all vertices, meaning it has no cycles.

Minimum Cost Spanning Tree (MST):

For a weighted graph, a Minimum Cost Spanning Tree (MST) is a spanning tree whose total weight (the sum of the weights of all its edges) is less than or equal to the weight of every other spanning tree.

Prim’s Algorithm:

Prim’s algorithm is a greedy algorithm for finding an MST. It grows the tree starting from one vertex, and at each step, it adds the cheapest possible edge that connects a vertex already in the tree to one that is not yet in the tree.

Steps of the Algorithm:

1. Create an MST set that is initially empty.

2. Create a `key` array to assign to all vertices, storing the weight of the edge that connects the vertex to the MST. Initialize all keys to infinity and the key of the first vertex to 0.

3. Create a `parent` array that will construct the MST.

4. While not all vertices are included in the MST set:

a. Pick a vertex `u` not in the MST set that has the minimum key value.

b. Add `u` to the MST set.

c. For all adjacent vertices `v` of `u`, if the weight of edge `(u, v)` is less than the current key of `v`, update the key of `v` to the weight of edge `(u, v)` and set the parent of `v` as `u`.

Applications of Spanning Tree:

• Network Design: In designing computer and telecommunication networks, such as connecting cities with cables, fiber optics, or roads with minimum cost.
• Cluster Analysis: For grouping data points into clusters.
• Circuit Design: For connecting pins on a circuit board with the minimum length of wire.
• Approximation Algorithms: In finding approximate solutions for NP-hard problems like the Traveling Salesman Problem.