DSA Unit 2 2024 Past Paper PDF

Data structures and their applications Unit - II Compiled by M S Anand Department of Computer Science Data Structures and their applications Introduction Text Book(s): 1. "Data Structures using C / C++", Langsum Yedidyah, Moshe J Augenstein, Aaron M Tenenbaum Pearson...

Data structures and their applications Unit - II Compiled by M S Anand Department of Computer Science Data Structures and their applications Introduction Text Book(s): 1. "Data Structures using C / C++", Langsum Yedidyah, Moshe J Augenstein, Aaron M Tenenbaum Pearson Education Inc, 2nd edition, 2015. Reference Book(s): 1. "Data Structures and Program Design in C", Robert Kruse, Bruce Leung, C.L Tondo, Shashi Mogalla, Pearson, 2nd Edition, 2019 17/09/2024 Data structures and their applications Queue Queues. A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer who came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. 17/09/2024 Data structures and their applications Queue. 17/09/2024 Data structures and their applications Queue Basic operations on a queue. Enqueue() - Insertion of elements to the queue at the rear end. Dequeue() - Removal of elements from the queue (from the head). Peek() - Acquires the data element available at the front node of the queue without deleting it. isFull() - Checks if the queue is full. isNull() - Checks if the queue is empty. 17/09/2024 Data structures and their applications Queue Enqueue() Operation. The following steps should be followed to insert (enqueue) data element into a queue - Step 1: Check if the queue is full. Step 2: If the queue is full, Overflow error. Step 3: If the queue is not full, increment the rear pointer to point to the next available empty space. Step 4: Add the data element to the queue location where the rear is pointing. 17/09/2024 Data structures and their applications Queue Dequeue operation. Step 1: Check if the queue is empty. Step 2: If the queue is empty, Underflow error. Step 3: If the queue is not empty, access the data where the front pointer is pointing. Step 4: Increment front pointer to point to the next available data element. 17/09/2024 Data structures and their applications Queue Peek () operation. Step 1: Check if the queue is empty. Step 2: If the queue is empty, print “Queue is Empty.” Step 3: If the queue is not empty, access the data where the front pointer is pointing. Step 4: Return data. 17/09/2024 Data structures and their applications Queue isFull() Operation. This function checks if the queue has the maximum allowed number of elements. The following steps are performed in the isFull() operation - Step 1: Check if rear == MAXSIZE - 1. Step 2: If they are equal, return “Queue is Full.” Step 3: If they are not equal, return “Queue is not Full.” 17/09/2024 Data structures and their applications Queue isEmpty() Operation. The algorithm of the isEmptyl() operation is as follows - Step 1: Check if the rear and front are pointing to null memory space. Step 2: If they are pointing to NULL, return “Queue is empty.” Step 3: If they are not equal, return “Queue is not empty.” 17/09/2024 Data structures and their applications Queue Implementation. using arrays QueuewithAMain.c QueuewithArrays.c QueueArray.h Implementation using linked lists QueuewithListMain.c QueuewithList.c QueList.h 17/09/2024 Data structures and their applications Circular queue A circular queue is a linear queue that behaves as if the end position. the queue is connected to the start position, forming a circular ring. of It is also known as a Ring Buffer. In array-based implementation, the circular behavior is achieved by manipulating the queue pointers. 17/09/2024 Data structures and their applications Circular Queue … The queue pointers (Front (front) pointer and Rear (rear) pointer) will. start moving from 0 to N-1 (Maximum size of Queue = N) and after reaching N-1, they come back to 0, again they start from 0,1.., up to N-1 and they continue moving around the Queue. The variable rear points to the next free position in the buffer; front points to the first full position in the buffer. 17/09/2024 Data structures and their applications Circular Queue … When is the buffer empty? When is it full?. The buffer is empty when rear== front; The buffer is full when ((rear+ 1)% BUFFER_SIZE) == front. Implementation of a circular queue using arrays: CircularQMain.c CircularQueue.c CircularQ.h 17/09/2024 Data structures and their applications Deque A deque is a linear data structure, which stands for Double Ended. Queue. Unlike queue, where the data can be only inserted from one end and deleted from another, in a deque, the data can be inserted and deleted from both front and rear ends. Hence Deque inherits the properties of both queues and stacks. Additionally, the implementation of this data structure requires constant time, i.e., time complexity = O(1). This means you can use deque to your advantage to implement both the queue and stack The insertion and deletion in deque can be limited to one node. When you do that, the deque becomes a stack. As deque can operate on both ends, you can extract queue properties by limiting insertion at the front node and removal at the rear node. Doing this will allow deque to act as a linear queue. 17/09/2024 Data structures and their applications Deque Types of Deque in Data Structure. There are two types of deque which are created by restricting certain operations. Input-Restricted Deque: It is a deque with some limitations while performing insertion operations. In the Input-Restricted Deque, it will perform the deletion at both ends, whereas it performs the insertion at only one end. The image below shows how input restricted deque limits insertion at one end. 17/09/2024 Data structures and their applications Deque Output-Restricted Deque: It. is a deque with some limitations while performing deletion operations. In the Output-Restricted Deque, it will perform the insertion at both ends, whereas it performs the deletion of elements at only one end. The image below shows how output restricted deque limits removal at one end. 17/09/2024 Data structures and their applications Deque Operations on Deque. Four basic operations are performed on deque, they are as follows: 1. Insertion at Rear 2. Insertion at Front 3. Deletion at Front 4. Deletion at Rear Along with these primary operations, you can also perform isEmpty(), isFull() and Peek() operations. These operations are called supportive queue operations. The time required to implement all these functions must be constant, i.e., time-complexity = O(1). Implementation using arrays: DequeMain.c DequeFunctions.c DequeFunctions.h Using Lists: DequeListMain.c DequeList.c DequeList.h 17/09/2024 Data structures and their applications Priority Queue What is Priority Queue?. priority queue serves as a specialized data structure where A elements are organized based on their priority values, ensuring that higher-priority items are processed before lower-priority ones. This organization enables efficient retrieval of the most critical elements. Priority is a number. We can define the order the way we like it: For example: Lower this number, higher the priority Higher the value of this number, higher is the priority Sample implementation: priorityqMain.c priorityq.c priorityq.h 17/09/2024 Data structures and their applications Applications of queues Some of the common application of queue in data structure:. Queues can be used to schedule jobs and ensure that they are executed in the correct order. to manage the order in which print jobs are sent to the printer. to implement the breadth-first search algorithm. to manage incoming calls and ensure that they are handled in the correct order. to manage the order in which processes are executed on the CPU. for buffering data while it is being transferred between two systems. When data is received, it is added to the back of the queue, and when data is sent, it is removed from the front of the queue. 17/09/2024 Data structures and their applications Josephus problem and solution Josephus Problem : Postulates a group of soldiers surrounded by an. overwhelming enemy force. There is no hope of victory without reinforcements. There is one horse available for escape The soldiers agree to a pact to determine which of them is to escape and seek help. The soldiers form a circle and a number n is picked from a hat. One of the names is also picked from the hat. Beginning with the soldier whose name is picked , they begin to count clockwise around the circle. when the count reaches n, that soldier is removed from the circle and the count begins with the next soldier. The process continues so that each time the count reaches n, another soldier is removed from the circle. Any soldier removed from the circle is no longer counted. The last soldier remaining is to take the horse and escape. 17/09/2024 Data structures and their applications Josephus problem and solution Problem Statement:. There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and the kth person is killed in a circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. 17/09/2024 Data structures and their applications Josephus problem Example Now starting from 1st.Initially, 5 people are position, we will skip k- standing in the circle as 1 people and kill the kth follows: person. k in the example is 3 so the person to be killed is 3rd person. 17/09/2024 Data structures and their applications Josephus problem Next, our current becomes Now the current is 2nd.the 4th person in the circle, person, we don’t consider we go from 4 to 5 and back 3rd person as he is already to 1 which is kth person to killed. The next person is be killed. 4th and 5th person is killed. 17/09/2024 Data structures and their applications Josephus problem Again the current is 2nd person and we go to 4th person and back.to 2nd person. Thus, 2nd person is killed in this step. So, the only one who doesn’t get killed is the 4th one. 17/09/2024 Data structures and their applications Josephus problem. 17/09/2024 Data structures and their applications Josephus problem - Solution Implementation using an array. JoseArray.c Implementation using recursion JoseRecursive.c 17/09/2024 Data structures and their applications Josephus problem - Solution ▪ The input to the program is the number n and list of names, which. is the clockwise ordering of the circle, beginning with the soldier from whom the count is to start. ▪ The program should print the names in the order that they are eliminated and the name of soldier who escapes. ▪ For example if n=3 and that there are five solders named A,B,C,D and E. We count three soldiers starting at A, so that C is eliminated first. ▪ We then begin at D and count D E and back to A. A is eliminated. Then we count B D and E, E is eliminated. And finally B D and B is eliminated. ▪ D is the one who escapes 17/09/2024 Data structures and their applications Josephus problem - Solution Pseudo code of implementation using circular list. read(n) read(name) while(all the names are read) { insert name on the circular list read(name) } while(there is more than one node on the list) { count through n-1 nodes on the list print name in the nth node delete the nth node } print the name of the only node on the list 17/09/2024 Data structures and their applications Josephus problem - Solution Implementation using linked list. JosephusList.c 17/09/2024 Data structures and their applications Process scheduling First Come First Served (FCFS) – Implemented using a Queue. Shortest Job First (SJF) – Priority based. The burst tie is used to prioritize and schedule a job/process. The running process may be pre-empted to make way for a shorter job. Shortest Job First (Non pre-emptive) – Jobs are placed in a queue such that the shortest job takes highest priority. But, the running job is not pre- empted. Longest Job First (Pre-emptive) Longest Job First (Non pre-emptive) Pre-emptive priority based scheduling Round Robin scheduling If more than one process has the same priority, then FCFS amongst them 17/09/2024 Data structures and their applications Tree There are many basic data structures that can be used to solve. application problems. Comparison of Array and a Linked List Array is a good static data structure that can be accessed randomly and is fairly easy to implement. Linked List on the other hand is dynamic and is ideal for application that requires frequent operations such as add, delete, and update. One drawback of linked list is that data access is sequential. Then there are other specialized data structures like, stacks and queues that allows us to solve complicated problems using these restricted data structures. 17/09/2024 Data structures and their applications Tree … We can extend the concept of linked data structure (linked list,. stack, queue) to a structure that may have multiple relations among its nodes. Such a structure is called a tree. A tree is a collection of nodes connected by directed (or undirected) edges. A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees. A tree has following general properties: One node is distinguished as a root; Every node (exclude a root) is connected by a directed edge from exactly one other node; A direction is: parent -> children 17/09/2024 Data structures and their applications Tree …. A is a parent of B, C, D, B is called a child of A. On the other hand, B is a parent of E, F, K In the picture, the root has 3 subtrees. 17/09/2024 Data structures and their applications Tree … Terminology. Each node can have arbitrary number of children. Nodes with no children are called leaves, or external nodes. In the picture (previous slide), C, E, F, L, G are leaves. Nodes, which are not leaves, are called internal nodes. Internal nodes have at least one child. Nodes with the same parent are called siblings. In the picture, B, C, D are called siblings. The depth of a node is the number of edges from the root to the node. The depth of K is 2. The height of a node is the number of edges from the node to the deepest leaf. The height of B is 2. The height of a tree is the height of root. 17/09/2024 Data structures and their applications Tree … General Tree. A general tree is a tree where each node may have zero or more children. General trees are used to model applications such as file systems. 17/09/2024 Data structures and their applications Binary Tree A binary tree is a specialized version of the General tree. A binary tree is.a tree in which each node can have at most two nodes. The node at the top of the hierarchy of a tree is called the root node. 17/09/2024 Data structures and their applications Binary Tree … Each node in a binary tree has these three elements –.▪ Data item that is the data stored in the node ▪ Address of the left child ▪ Address of the right child 17/09/2024 Data structures and their applications Binary Tree … Terminology in Binary Tree.Nodes – Nodes are the building blocks of any data structure. They majorly contain some data and link to the next/previous nodes. In the case of binary trees, they contain the address of the left and the right child respectively. Root – The topmost node in a tree is known as the root node. A tree can have at most one root node. Parent Node – A node (except the root) that has a succeeding node is known as a parent node. Child Node – A node that has a preceding node is known as a child node. A node can be both parent and child depending on the node that is in context. Leaf Node – A node with no children. Internal Node – A node that has at least one child node is known as an internal node. Depth of a Binary Tree – The number of edges from a node in the tree to the root node. Height of a Binary Tree – The number of edges from the deepest node in the tree to the root node. 17/09/2024 Data structures and their applications Binary Tree … Level of a node.Level of a node represents the number of connections between the node and the root. It represents generation of a node. If the root node is at level 0, its next node is at level 1, its grand child is at level 2 and so on. Levels of a node can be shown as follows: 17/09/2024 Data structures and their applications Binary Tree … Degree of Node.Degree of a node represents a number of children of a node. Edge Edge is a connection between one node to another. It is a line between two nodes or a node and a leaf. Path Path is a number of successive edges from source node to destination node 17/09/2024 Data structures and their applications Binary Tree …. 17/09/2024 Data structures and their applications Types of Binary Tree Full Binary Tree.A full binary tree, also known as a proper binary tree, is a tree in which each internal node has either zero or two children nodes. In other words, if in a binary tree a node contains only one child node, it is not a full binary tree. In a full binary tree, if there are n number of total nodes – The number of internal nodes is given by (n-1)/2 The number of leaf nodes is given by (n+1)/2 17/09/2024 Data structures and their applications Types of Binary Tree … Complete Binary Tree. A complete binary tree is a binary tree in which all the elements are arranged without missing any sequence. In a complete binary tree – All the levels are completely filled except the last level that may or may not be completely filled. Elements are filled from left to right. The trees shown in the next slide are complete binary trees since they have no empty spaces in them. 17/09/2024 Data structures and their applications Types of Binary Tree …. 17/09/2024 Data structures and their applications Types of Binary Tree … Perfect Binary Trees.If in a tree all the internal nodes have exactly two children nodes, it is known as a perfect binary tree. In a perfect binary tree, all the leaf nodes are on the same level. Consider a perfect binary tree with height h, the total number of nodes in this case is given by 2h – 1. 17/09/2024 Data structures and their applications Types of Binary Tree … Balanced Binary Trees.A binary tree is said to be balanced if the height of the left and the right subtrees differ by 0 or 1. In a balanced binary tree, both the left and right trees are also balanced. The following diagram shows a balanced binary tree – 17/09/2024 Data structures and their applications Types of Binary Tree … Notice that in the first image, the right subtree is at the height of 3, and the.left subtree is at 2. The difference between the heights of the left and the right subtree is therefore 1. Therefore, the given tree is a balanced binary tree. In the second image, the right subtree is at the height of 3, whereas the left subtree is at 1. The difference between the heights of the left and the right subtrees is 2. It violates the condition of a balanced binary tree. Hence, the given tree is not a balanced binary tree. 17/09/2024 Data structures and their applications Representation of binary tree in C A binary tree can be represented using a linked list and also using. an array. How do you represent this tree using arrays? 17/09/2024 Data structures and their applications Representation of binary tree in C Array Representation :. The binary tree can be represented using an array of size 2n+1 if the depth of the binary tree is n. If the parent element is at the index p, then the left child will be stored at the index (2p)+1 , and the right child will be stored at the index (2p)+2. The array representation of the above binary tree is : A, the root node will be stored in the 0th index. The left child of A will be stored in the 2(0)+1 equal to the 1st location. B is stored in index 1. And similarly, the right child of A will be stored in the 2(0)+2 index. For every node, the left and right child will be stored accordingly. 17/09/2024 Data structures and their applications Representation of binary tree in C Linked List Representation :. For the linked list representation, we will use the doubly linked list, which has two pointers so that we can point to the left and right children of a binary tree node. NULL is given to the pointer as the address when no child is connected. 17/09/2024 Data structures and their applications Representation of binary tree in C The linked list representation for the given tree is as shown below:. 17/09/2024 Data structures and their applications Tree traversal Traversal of a Binary Tree. We can traverse the element tree and can display these elements in three formats/methods : In every traversal method of the binary tree, we need to visit the left node, the right node, and the data of the present/current node(root). There are three methods which have these three actions in a different order. 17/09/2024 Data structures and their applications Tree traversal Pre-Order :. In this type of traversal, first, we will take the value of the current node(present node), then we will go to the left node, and after that, we will go to the right node. 17/09/2024 Data structures and their applications Tree traversal … In-Order :. In this type of traversal, first, we'll go to the left node, then we'll take the value of the current node, and then we will go to the right node. 17/09/2024 Data structures and their applications Tree traversal … Post-Order :. In this type of traversal, first, we'll go to the left node, then to the right node, and at last, we will take the current node's value. 17/09/2024 Data structures and their applications Tree traversal … A sample implementation of a Binary Tree including all three. modes of traversal is here: BinaryTree.c Ordered tree An ordered tree is a rooted tree in which the set of children of each vertex is assigned a total order. In a drawing of an ordered rooted tree, with the root shown at the top, the children of a vertex are shown from left to right. We can call b as the first or the oldest child of a and d as the last or the youngest child of a. 17/09/2024 Data structures and their applications Tree traversal … Unordered tree. A tree in which nodes are not in any particular order is called an unordered tree 17/09/2024 Data structures and their applications N-ary tree An n-ary tree is a tree data structure where each node can have at. most n children. Unlike binary trees, which have at most two children per node, n- ary trees allow for a variable number of children. They are used in scenarios where each node may have multiple possible paths or branches, such as in hierarchical data structures or decision trees. 17/09/2024 Data structures and their applications N-ary tree …. In the above figure, we can see that there is one root node with some children. Here we have decided to keep our n value as 3. So, the number of children each node has is less than or equal to 3. This tree can also be called a 3-Ary tree. 17/09/2024 Data structures and their applications N-ary tree … Representation in C. First representation struct node { int info; struct node *child [MAX]; }; Each node can have a maximum of MAX children. 17/09/2024 Data structures and their applications N-ary tree … Alternate representation. struct node { int n; int numKids; struct node **kids; }; 17/09/2024 Data structures and their applications N-ary tree … Another representation. struct node { int n; struct node *kids; struct node *siblings; }; From any single node you can only directly access its first kid, through the kids pointer. You access the second kid through kids->siblings, the third kid through kids->siblings->siblings, and so on. In other words, instead of storing a node’s kids in an array, you store them in a list; it just so happens that this list can be embedded 17/09/2024elegantly in the nodes themselves. Data structures and their applications n-ary tree traversal. 17/09/2024 Data structures and their applications n-ary tree traversal Pre. order Traversal In an N-ary tree, preorder means visit the root node first and then traverse the subtree rooted at its children one by one. For instance, the preorder of the 3-ary tree above is: A->B->C->E->F->D->G. Post order Traversal In an N-ary tree, postorder means traverse the subtree rooted at its children first and then visit the root node itself. For instance, the postorder of the 3-ary tree above is: B->E->F->C->G->D->A. Level-order Traversal Level-order traversal in an N-ary tree is the same with a binary tree. Typically, when we do breadth-first search in a tree, we will traverse the tree in level order. For instance, the level-order of the 3-ary tree above is: A->B->C->D->E->F->G. 17/09/2024 Data structures and their applications n-ary tree traversal. 17/09/2024 Data structures and their applications n-ary tree traversal Using the following representation of the tree:. struct node { int data; struct node *kids; struct node *siblings; }; pre order traversal void preorder (NODE *root) { if (root != NULL) { printf (“Data is %d\n”, root->data); preorder (root->kids); preorder (root->siblings); } } 17/09/2024 Data structures and their applications n-ary tree traversal … in order traversal.void inorder (NODE *root) { if (root != NULL) { inorder (root->kids); printf (“Data is %d\n”, root->data); inorder (root->siblings); } } post order traversal void postorder (NODE *root) { if (root != NULL) { postorder (root->kids); postorder (root->siblings); printf (“Data is %d\n”, root->data); } } 17/09/2024 Data structures and their applications Conversion of an n-ary tree to a binary tree Following are the rules to convert a Generic (N-array Tree) to a.Binary Tree: The root of the Binary Tree is the Root of the Generic Tree. The left child of a node in the Generic Tree is the Left child of that node in the Binary Tree. The right sibling of any node in the Generic Tree is the Right child of that node in the Binary Tree. 17/09/2024 Data structures and their applications Conversion of an n-ary tree to a binary tree Convert the following general tree to a binary tree.. 17/09/2024 Data structures and their applications Conversion of an n-ary tree to a binary tree. Note: If the parent node has only the right child in the general tree then it becomes the rightmost child node of the last node following the parent node in the binary tree. In this example, if node B has the right child node L then in binary tree representation L would be the right child of node D. 17/09/2024 Data structures and their applications Conversion of an n-ary tree to a binary tree The steps:.✓ As per the rules mentioned above, the root node of general tree A is the root node of the binary tree. ✓ The leftmost child node of the root node in the general tree is B and it is the leftmost child node of the binary tree. ✓ As B has E as its leftmost child node, it is its leftmost child node in the binary tree whereas it has C as its rightmost sibling node so it is its right child node in the binary tree. ✓ C has F as its leftmost child node and D as its rightmost sibling node, so they are its left and right child node in the binary tree respectively. ✓ D has I as its leftmost child node which is its left child node in the binary tree but doesn’t have any rightmost sibling node, so doesn’t have any right child in the binary tree. ✓ For I, J is its rightmost sibling node and so it is its right child node in the binary tree. ✓ Similarly, for J, K is its leftmost child node and thus it is its left child node in the binary tree. ✓ For C, F is its leftmost child node, which has G as its rightmost sibling node, which has H as its just right sibling node and thus they form their left, right, and right child node respectively. 17/09/2024 Data structures and their applications Conversion of an n-ary tree to a binary tree The procedure. 1. For a given node, draw edges connecting all siblings. 2. Remove the edges from all the siblings to the parent node except the leftmost sibling. 3. This will end up in a binary tree which will not have a right subtree. 17/09/2024 Data structures and their applications Forest … A forest is a group of randomly placed trees. A forest, as opposed. to a single tree, consists of various tree structures, each with its own root node and hierarchy. The following are the fundamental traits of forests: ▪ Multiple Trees: Two or more distinct tree structures make up a forest. The root nodes and hierarchies of these trees may differ. ▪ Disconnected Trees: A forest does not contain a single root node that connects all of its parts, unlike a single tree. As an alternative, no two trees in the forest are interdependent. ▪ No Cycles Within Trees: While individual trees in a forest may go through cycles, there aren't any cycles that connect different trees in the forest. 17/09/2024 Data structures and their applications Creating a Forest from a collection of trees. Straighten the leftmost branch of each tree including the root node. 17/09/2024 Data structures and their applications Creating a Forest from a collection of trees. Whichever node has lost the connection to its parent, connect that node to its neighbour. Connect all the roots also. 17/09/2024 Data structures and their applications Creating a Forest from a collection of trees. Rotate the whole figure by 45 degrees to the right. 17/09/2024 Data structures and their applications Creating a Forest from a collection of trees. 17/09/2024 THANK YOU M S Anand Department of Computer Science Engineering [email protected]