## If you are looking for MCS-208 IGNOU Solved Assignment solution for the subject Data Structures and Algorithms, you have come to the right place. MCS-208 solution on this page applies to 2022-23 session students studying in PGDCA_NEW, PGDCA courses of IGNOU.

# MCS-208 Solved Assignment Solution by Gyaniversity

**Assignment Code: **MCS-208/Assign/2022-23

**Course Code: **MCS-208

**Assignment Name: **Data Structures and Algorithms

**Year: **2022-2023

**Verification Status: **Verified by Professor

**Question 1: (20 Marks)**

**What are Sparse Matrices? Explain with example(s)**

**Ans**) Sparse matrices are those that have a significant proportion of zero elements.

Take into consideration the following matrices:

A square matrix that has all of its entries either above or below the major diagonal is referred to as a triangular matrix. Sparse matrices include triangular matrices. A tridiagonal matrix is a square matrix with zero diagonals on the immediate upper and lower sides and the main diagonal as the only other element. Sparse matrices also include tridiagonal matrices.

Let's look at a sparse matrix from the perspective of storage. Assume that the sparse matrix is stored in its entirety. The matrix is then stored in a sizeable portion of zeroes in memory. Memory is being wasted in this manner. Such waste could amount to megabytes in real-world applications. Therefore, it is necessary to investigate an effective way to store sparse matrices.

The order 7 by 6 sparse matrix as follows:

The 3-tuple form is a popular approach to express non-zero members in a sparse matrix. The number of rows, columns, and non-zero items are always specified in the first row of a sparse matrix. The total number of rows in the sparse matrix is seven. Similar to this, the matrix's total number of columns is represented by the number 6. The total number of non-zero matrix elements is 8, which is represented by the number. Every non-zero element from the second row is stored, with the first and second elements of the row designating the row and column in the original matrix, respectively, in which the element is present. The actual value of the non-zero element is stored in this row's third element.

For instance, the following is the 3-tuple form of the matrix from the previous matrix:

7, 7, 5

0, 3, 5

1, 1, 4

2, 4, 9

3, 1, 3

3, 3, 2

4, 2, 2

6, 2, 8

The sparse matrix can be entered into the programme 1.1, which outputs the matching 3-tuple representations.

**Program 1.1**

/* The program accepts a matrix as input and prints the 3-tuple representation

of it*/

#include<stdio.h>

void main()

{

int a[5][5],rows,columns,i,j;

printf("enter the order of the matrix. The order should be less than 5 × 5:\n");

scanf("%d %d",&rows,&columns);

printf("Enter the elements of the matrix:\n");

for(i=0;i<rows;i++)

for(j=0;j<columns;j++)

{ scanf("%d",&a[i][j]);

}

printf(“The 3-tuple representation of the matrix is:\n”);

for(i=0;i<rows;i++)

for(j=0;j<columns;j++)

{

if (a[i][j]!=0)

{

printf("%d %d %d\n", (i+1),(j+1),a[i][j]);

}

}

}

**Output**

The 3-tuple representation of the matrix is:

The program initially prompted for the order of the input matrix with a warning that the order should not be greater than 5 × 5. After accepting the order, it prompts for the elements of the matrix. After accepting the matrix, it checks each element of the matrix for a non zero. If the element is non zero, then it prints the row number and column number of that element along with its value.

**Question 2: (20 Marks)**

**How many different traversals of a Binary Tree are possible? Explain them with example(s).**

**Ans**) Preorder, inorder, and postorder are the three methods that can be used to traverse a binary tree. The following binary tree's inorder binary tree traversal is:

Starting from the root, we should first visit the node's left subtree, followed by the node itself and its right subtree. Here, the left sub-tree of root is rooted at +. Consequently, we shift to + and look for its left sub-tree (we are suppose repaeat this for every node). Once more, + has a left sub-tree with a root at 4. As a result, we must now look for node 4's left sub-tree, but since node 4 doesn't have a left sub-tree, we will visit node 4 first (in our example, print) and look for its right sub-tree. Since no right sub-tree exists at node 4, we will return to + and search for its right sub-tree. We go to number 5 because it has a right sub-tree anchored there. Well, there isn't a left or right sub-tree in 5. Therefore, we only go to 5 (print 5) and then go back to +. We return to * since we have already been to +. Due to the fact that we have not yet visited the node itself, we visit * before looking for the appropriate sub-tree of *, which is 3. We go to 3 since it lacks left and right sub-trees. So, the inorder traversal results in 4 + 5 * 3

The traversals of the preorder and postorder are comparable to those of a common binary tree. All of these tree traversals have one thing in common: their traversal method is fundamentally recursive.

**Recursive Implementation of Binary Tree Traversals**

There are three traditional methods for iteratively scanning a binary tree. The left and right subtrees in each of these are iteratively examined, while the element in the root is visited or processed just once in each case.

struct NODE

{

struct NODE *left;

int value; /* can be of any type */

struct NODE *right;

};

inorder(struct NODE *curr)

{

if(curr->left != NULL) inorder(curr->left);

printf("%d", curr->value);

if(curr->right != NULL) inorder(curr->right);

}

**Program**: Inorder traversal of a binary tree

struct NODE

{

struct NODE *left;

int value; /* can be of any type */

struct NODE *right;

};

preorder(struct NODE *curr)

{

printf("%d", curr->value);

if(curr->left != NULL) preorder(curr->left);

if(curr->right != NULL) preorder(curr->right);

}

**Program 6.3 **: Preorder traversal of a binary tree

struct NODE

{

struct NODE *left;

int value; /* can be of any type */

struct NODE *right;

};

postorder(struct NODE *curr)

{

if(curr->left != NULL) postorder(curr->left);

if(curr->right != NULL) postorder(curr->right);

printf("%d", curr->value);

}

**Program **: Postorder traversal of a binary tree

The left and right subtrees are travelled through first (pre), then. The left sub-tree is visited first in a postorder traversal, then the right sub-tree, and finally the root. In an inorder traversal, the left subtree, root, and right subtree are all traversed in that order.

Non-recursive implementation of binary tree traversals

The implementation was straightforward through a recursive process because the traversal techniques were by their very nature recursive. In contrast, a non-recursive traversal method must be iterative in order to be applied to all nodes in the tree. This means that all steps for traversing a node must be contained within a loop.

**Algorithm **: Non-recursive preorder binary tree traversal

Stack S

push root onto S

repeat until S is empty

{

v = pop S

if v is not NULL

visit v

push v’s right child onto S

push v’s left child onto S

}

The programme section for the implementation of nonrecursive preorder traversal is shown in the above programme.

/* preorder traversal of a binary tree, implemented using a stack */

void preorder(binary_tree_type *tree)

{

stack_type *stack;

stack = create_stack();

push(tree, stack); /* push the first element of the tree to the stack */

while (!empty(stack))

{

tree = pop(stack);

visit(tree);

push(tree->right, stack); /* push right child to the stack */

push(tree->left, stack); /* push left child to the stack */

}

}

Preorder traversal is implemented non-recursively in the programme.

Preorder traversal's worst-case scenario will cause the stack to swell to size n/2, where n is the number of nodes in the tree. Pointers to the parent node are needed for a different non-recursive binary tree traversal technique that does not use stack (called threaded binary tree).

Every node that does not have a right child has a THREAD (a third connection) to its INORDER successor in a threaded binary tree. By using threading, we may avoid the memory- and time-intensive recursive tree traversal approach and stack usage.

A threaded binary node structure is:

A threaded binary tree's node structure varies slightly and looks something like this:

struct NODE

{

struct NODE *leftchild;

int node_value;

struct NODE *rightchild;

struct NODE *thread; /* third pointer to it’s inorder successor */

}

**Question 3: (20 Marks)**

**What are AVL trees? How do they differ from Splay trees.**

**Ans**) An AVL tree is a type of binary search tree. Named after it's inventors Adelson, Velskii, and Landis, AVL trees have the property of dynamic self-balancing in addition to all the other properties exhibited by binary search trees.

A BST is a data structure composed of nodes. It has the following guarantees:

Each tree has a root node (at the top)

The root node has zero, one, or two child nodes

Each child node has zero, one, or two child nodes

Each node has up to two children

For each node, its left descendants are less than the current node, which is less than the right descendants

The difference between the depth of right and left sub-trees cannot be more than one. This difference is called the balance factor.

In order to maintain this guarantee, an implementation of an AVL will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee

AVL trees have a worst case lookup, insert, and delete time of O(log n), where n is the number of nodes in the tree. The worst case space complexity is O(n).

**AVL Insertion Process**

Insertion in an AVL tree is similar to insertion in a binary search tree. But after inserting and element, you need to fix the AVL properties using left or right rotations:

If there is an imbalance in the left child's right sub-tree, perform a left-right rotation

If there is an imbalance in the left child's left sub-tree, perform a right rotation

If there is an imbalance in the right child's right sub-tree, perform a left rotation

If there is an imbalance in the right child's left sub-tree, perform a right-left rotation

**AVL Tree Rotations**

In AVL trees, after each operation like insertion and deletion, the balance factor of every node needs to be checked. If every node satisfies the balance factor condition, then the operation can be concluded. Otherwise, the tree needs to be rebalanced using rotation operations.

There are four rotations and they are classified into two types:

**Left-Right Rotation (LR Rotation)**

Left-right rotations are a combination of a single left rotation followed by a single right rotation.

First, every node moves one position to the left, then one position to the right from the current position.

**Right-Left Rotation (RL Rotation)**

Right-left rotations are a combination of a single right rotation followed by a single left rotation.

First, every node moves one position to the right then, then one position to the left from the current position.

**Application of AVL Trees**

AVL trees are beneficial in cases like a database where insertions and deletions are not that frequent, but you frequently check for entries.

Difference between AVL trees and Splay trees

AVL Tree has a guaranteed fast runtime ( O(log n) ) on every lookup, insert and deletion

Splay tree is faster for repeated lookup

For real-time applications, AVL Tree is better than Splay tree

For non real time applications, Splay tree has better average running time

Splay tree is more efficient in tree merging and splitting

Splay tree is more memory efficient than AVL tree because it does not need to store balance information in the nodes

AVL Tree supports multi-threading and parallel lookup while Splay tree cannot because it reshapes it on every lookup

Splay tree is a better choice if only small number of nodes will be accessed or some nodes are accessed more than others

Splay tree is easier to implement because the rotation logic is simpler

For splay tree, any long sequence operations will take at most O(n log n) time and individual operation could take O(n) time.

**Question 4: (20 Marks)**

**What are Tries? How do they differ from Binary Tries?**

**Ans**) Tries are a type of tree-based data structure that find string-based keys in a given set. The edges connecting the tree's nodes are represented by individual characters in a string. The following are the main traits of tries:

A node's children are connected by a shared prefix.

The location of the node indicates the key.

The depth-first search method can be used for string searches.

The usage of integer-based information retrieval is widespread in the real world. For instance, integer-based lookup is required for account number-based search and ID number-based information retrieval. Bitwise attempts can be used in many usage cases to speed up information retrieval. For text search use cases, tries are also employed in web search engines. The trie data structure's average time complexity for search, insert, and delete operations is O (n).

A sample Tries

**Binary tries**: Bits are used in binary attempts to represent integers as keys. We can traverse the binary tries by using the bit representation of each individual character in a string. Only the leaf node of a binary trie contains the key. To identify the key, we compare the tree's component parts.

The steps for finding a key in a binary trie are as follows:

Begin your search with the root node.

Compare the ith bit of the key after setting i=0.

Check the left node if the key bit value is 0, else, search the right node.

Return success if the current node is a leaf and all of the key's bits match the path; otherwise, return failure.

Increase the counter I and repeat steps 3 through 5 if the current node is not a leaf.

Tries and binary tries differ in the following ways:

Attempts to use tree-based data structures Bits are used in binary attempts to represent integers as keys.

Tries uses bit representations of each letter in a string to connect the tree's nodes and Individual characters from a string are employed as edges in binary tries to navigate the system. Only the leaf node of a binary trie contains the key.

##

###

####

##### 100% Verified solved assignments from ₹ 40 written in our own words so that you get the best marks!

####

Don't have time to write your assignment neatly? Get it written by experts and get free home delivery

####

Get Guidebooks and Help books to pass your exams easily. Get home delivery or download instantly!

####

Download IGNOU's official study material combined into a single PDF file absolutely free!

####

Download latest Assignment Question Papers for free in PDF format at the click of a button!

####

Download Previous year Question Papers for reference and Exam Preparation for free!