Dynamic Memory Management in C: Linked Lists and Sparse Matrices
Mark and Sweep The Mark Sweep algorithm is as straightforward as its name suggests. It consists of two phases: a mark phase and a sweep phase. The collector crawls across all the roots (global variables, local variables, stack frames, virtual and hardware registers, and so on) and marks every item it meets by setting a bit anywhere around that object during the mark phase. It also walks across the heap during the sweep phase, reclaiming memory from all the unmarked items.
Sweep() is a simple function with a straightforward implementation. It linearly traverses the heap, freeing any objects that aren’t tagged. Our heap layout does face parseability restrictions as a result of this. The next object(address) implementation must be able to return the heap’s next object. In most cases, the heap just has to be parseable in one way. In most GC-enabled language runtimes, an object’s data is often tagged with an object header. The header provides details about the item, such as type, size, hashcode, mark bits, sync block, etc.
Garbage collection: Garbage collection (GC) is a dynamic technique for memory management and heap allocation that examines and identifies dead memory blocks before reallocating storage for reuse. Garbage collection’s primary goal is to reduce memory leaks. Garbage collection frees the programmer from having to deallocate and return objects to the memory system manually. Garbage collection can account for a considerable amount of a program’s total processing time, and as a result, can have a significant impact on performance. Stack allocation, region inference, memory ownership, and combinations of various techniques are examples of related techniques. Garbage collection’s dynamic approach to automatic heap allocation addresses common and costly faults that, if left undiscovered, can lead to real-world programmer problems. Allocation errors are costly because they are difficult to detect and correct. As a result, many programmers regard garbage collection as an essential language feature that simplifies the programmer’s job by reducing manual heap allocation management.
Linked list If arrays accommodate similar types of data types, linked lists consist of elements with different data types that are also arranged sequentially. But how are these linked lists created? A linked list is a collection of “nodes” connected together via links. These nodes consist of the data to be stored and a pointer to the address of the next node within the linked list. In the case of arrays, the size is limited to the definition, but in linked lists, there is no defined size. Any amount of data can be stored in it and can be deleted from it. There are three types of linked lists − • Singly Linked List − The nodes only point to the address of the next node in the list. • Doubly Linked List − The nodes point to the addresses of both previous and next nodes. • Circular Linked List − The last node in the list will point to the first node in the list. It can either be singly linked or doubly linked. Linked List Representation Linked list can be visualized as a chain of nodes, where every node points to the next node.
Singly Linked Lists Singly linked lists contain two “buckets” in one node; one bucket holds the data and the other bucket holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.
Doubly Linked Lists Doubly Linked Lists contain three “buckets” in one node; one bucket holds the data and the other buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.
Circular Linked Lists Circular linked lists can exist in both singly linked list and doubly linked list. Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.
Basic Operations in the Linked Lists The basic operations in the linked lists are insertion, deletion, searching, display, and deleting an element at a given key. These operations are performed on Singly Linked Lists as given below − • Insertion − Adds an element at the beginning of the list. • Deletion − Deletes an element at the beginning of the list. • Display − Displays the complete list. • Search − Searches an element using the given key. • Delete − Deletes an element using the given key. Basic Operations in the Linked Lists The basic operations in the linked lists are insertion, deletion,
Circular linked list: The circular linked list is a linked list where all nodes are connected to form a circle. In a circular linked list, the first node and the last node are connected to each other which forms a circle. There is no NULL at the end. There are generally two types of circular linked lists: • Circular singly linked list: In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. We traverse the circular singly linked list until we reach the same node where we started. The circular singly linked list has no beginning or end. No null value is present in the next part of any of the nodes. Representation of Circular singly linked list • Circular Doubly linked list: Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by the previous and next pointer and the last node points to the first node by the next pointer and also the first node points to the last node by the previous pointer. Representation of circular doubly linked list
Stack: In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure – elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.
Queue: An excellent example of a queue is a line of students in the food court of the UC. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access. 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.
FIFO & LILO and LIFO & FILO Queue: First In First Out (FIFO): The first object into a queue is the first object to leave the queue, used by a queue. Stack: Last In First Out (LIFO): The last object into a stack is the first object to leave the stack, used by a stack OR Stack: First In Last Out (FILO): The first object or item in a stack is the last object or item to leave the stack. Queue: Last In Last Out (LILO): The last object or item in a queue is the last object or item to leave the queue.
Stack and queue as ADT: Stacks and queues are two types of abstract data types that you can use to store and retrieve data in different ways. Stacks have a last-in-first-out mechanism (LIFO), while Queues have a first-in-first-out mechanism (FIFO). But what does this mean? Stacks (LIFO) Stacks can be compared to piles of plates. When you have a whole pile of plates, you can only add a new plate on top of the pile, aka the top of the stack. The last plate you put on top is also the same plate that first gets out, hence the LIFO (last-in-first-out) mechanism. The 2 most important methods in a stack are push() and pop(). Push() adds a new item to the top of the stack, and pop() removes the item at the top of the stack. Just like a stack of plates, you can only add — push() — and remove — pop() — from the top of the stack. Aka, adding or removing from the “last” plate. Stack Implementation All stacks require only one pointer looking to the end of the stack. Whenever a push() or pop() operation is performed, the pointer should always increment/decrement to the “top” of the stack. A common data structure used to implement stack is an array. For push(), the stack pointer will always increment to the index of the new element being “pushed.” For pop(), the stack pointer will always decrement to the index of the element before the element being “popped.”
Infix to Prefix Algorithm for Infix to Prefix Conversion: Step 1: Insert “)” onto stack, and add “(” to end of the A . Step 2: Scan A from right to left and repeat Step 3 to 6 for each element of A until the stack is empty . Step 3: If an operand is encountered, add it to B . Step 4: If a right parenthesis is encountered, insert it onto stack . Step 5: If an operator is encountered then, a. Delete from stack and add to B (each operator on the top of stack) which has same or higher precedence than the operator. b. Add operator to stack. Step 6: If left parenthesis is encountered then , a. Delete from the stack and add to B (each operator on top of stack until a left parenthesis is encountered). b. Remove the left parenthesis. Step 7: Exit 3. Postfix to Infix Following is an algorithm for Postfix to Infix conversion: Step 1: While there are input symbol left. Step 2: Read the next symbol from input. Step 3: If the symbol is an operand, insert it onto the stack. Step 4: Otherwise, the symbol is an operator. Step 5: If there are fewer than 2 values on the stack, show error /* input not sufficient values in the expression */ Step 6: Else, a. Delete the top 2 values from the stack. b. Put the operator, with the values as arguments and form a string. c. Encapsulate the resulted string with parenthesis. d. Insert the resulted string back to stack. Step 7: If there is only one value in the stack, that value in the stack is the desired infix string. Step 8: If there are more values in the stack, show error /* The user input has too many values */ Example: Suppose we are converting efg-+he-sh-o+/* expression into Infix.
1. Conversion of Infix to Postfix Algorithm for Infix to Postfix Step 1: Consider the next element in the input. Step 2: If it is operand, display it. Step 3: If it is opening parenthesis, insert it on stack. Step 4: If it is an operator, then • If stack is empty, insert operator on stack. • If the top of stack is opening parenthesis, insert the operator on stack • If it has higher priority than the top of stack, insert the operator on stack. • Else, delete the operator from the stack and display it, repeat Step 4. Step 5: If it is a closing parenthesis, delete the operator from stack and display them until an opening parenthesis is encountered. Delete and discard the opening parenthesis. Step 6: If there is more input, go to Step 1. Step 7: If there is no more input, delete the remaining operators to output. Example: Suppose we are converting 3*3/(4-1)+6*2 expression into postfix form.
priority queue: Priority Queue is an abstract data type that performs operations on data elements per their priority. To understand it better, first analyze the real-life scenario of a priority queue. The hospital emergency queue is an ideal real-life example of a priority queue. In this queue of patients, the patient with the most critical situation is the first in a queue, and the patient who doesn’t need immediate medical attention will be the last. In this queue, the priority depends on the medical condition of the patients.
Priority Queue in Data Structure: Implementation, Types, and More The priority queue in a data structure is used in Google Maps for searching the optimal path to reach any destination. Dijkstra’s Shortest Path algorithm utilizes a min priority queue to store all possible paths to reach the destination, considering distance as a parameter for priority assignment. In the end, it will return the element with the highest priority as the optimal route. So, in this tutorial, you will discover priority queue in data structure to understand their functionalities and applications. Introduction to Priority Queue in Data Structure Priority Queue is an abstract data type that performs operations on data elements per their priority.
Characteristics of Priority Queue Priority queue in a data structure is an extension of a linear queue that possesses the following properties: • Every element has a certain priority assigned to it. • Every element of this queue must be comparable. • It will delete the element with higher priority before the element with lower priority. • If multiple elements have the same priority, it does their removal from the queue according to the FCFS principle. • Now, understand these properties with the help of an example. Consider you have to insert 7, 2, 45, 32, and 12 in a priority queue. The element with the
Representation of Priority Queue You can also implement a priority queue using arrays, however, if you consider array implementation of the priority queue, then inserting elements into the sorted array will cost you O(n). In general, processing each element will further cost you O(n^2). Because of this complexity, implementing a priority queue using arrays is not an ideal approach. Hence, you will only learn about the representation of the priority queueusing a li
What are binary trees? If you have worked on normal trees before or even know about their basics, you would know that there are no restrictions when it comes to the number of children that different nodes are allowed to have in these trees. Binary trees are a little different in this sense. Every parent or node in binary trees can have a maximum of only two children.
A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.
What is data structure? Why to study data structure? Enlist the five areas of computer science in which data structure is used Answer: Data Structures: Organizing, managing and storing data is important as it enables easier access and efficient modifications. Data structure allows us to organize in a way that it enables to store collection of data, relate them and perform operations on them accordingly Why to Study Data Structure: As we Know data structure often used to access, store, manage and manipulate large amount of data in the minimum time. So it often used 1. To store data efficiently. 2. It does certain operations on them like searching, sorting etc in the least possible time. Areas of Computer Science in which Data Structure is used: * Used in any program or software. * Compiler Design *Operating System *DBMS * Simulation * Numerical Analysis « Artificial Intelligence B) What is garbage collection? Who will run garbage collection program? When it will be run? Answer Garbage Collection: Garbage collection is a technique of collecting all the deleted spaces or unused spaces in memory. The OS of a computer may periodically collect all the deleted space onto the free-storage list. Garbage collection may take place when there is only some minimum amount of space or no space is left in free storage list. Garbage collection collects all nodes which are allocated but no longer in use Who will run garbage collection program: The OS of a computer or a application software may periodically run the garbage collection program When it will be run?: 1. No free storage left 2. Periodically 3. Free storage reach a threshold 4. System is idle
What is primitive data structure? Enlist the differences between primitive and non Answer: Data structures are classified into two types: Primitive data structure Non primitive data structure primitive data structures DS THEORY Page 1 Non primitive data structure Primitive data structure: primitive data structure is the fundamental data structure, which stores the values of only one data type for example: A variable with the data type integer can allow storing the values of integer type only, a variable with the float data type can allow storing the values of float data type. Basically, the primitive data structure consists of fundamental data types like float, character, integer, etc. The classification of data structure is as follows:
Difference between primitive and non-primitive data structures: Primitive data structure is a kind of data structure that stores the data of one type Primitive data structure : Non – primitive data structure Non-primitive data structure is a type of data structure that can store the data of more than one type. Examples of primitive data structure are integer, character, float. Examples of non-primitive data structure are Array, Linked list, stack. Primitive data structure will contain some value, i.e., it cannot be NULL. The size depends on the type of the data structure Non-primitive data structure can consist of a NULL value. In case of non-primitive data structure, size is not fixed It starts with a lowercase character. It starts with an uppercase character. Primitive data structure can be used to call the methods Non-primitive data structure cannot be used to call the methods.
A binary tree is a data structure where each node has at most two children, which are referred to as the left child and the right child. Each node in a binary tree can have up to two children, but it can also have zero or one child if it is a leaf node or a parent node with only one child. Inorder and postorder traversals are two methods used to traverse a binary tree. Inorder traversal of a binary tree means visiting all the nodes in the tree in the order of left subtree, root, and right subtree. In other words, we first visit the left subtree, then the root, and finally the right subtree.
What is an algorithm? Write an algorithm to find Greatest common divisor (GCD). ANSWER: An algorithm is a set of instructions or a step-by-step procedure for solving a problem or performing a task. It is a sequence of computational steps that transform the input into the desired output. Here is an algorithm to find the Greatest Common Divisor (GCD) of two numbers: Algorithm: GCD(a, b) Set c = a mod b (where mod is the modulo operator) If c is zero, return b as the GCD Otherwise, set a = b, b = c, and go to step 1 The above algorithm uses the Euclidean algorithm to find the GCD of two numbers a and b. The algorithm works by iteratively reducing the problem of finding the GCD of a and b to the problem of finding the GCD of b and c, where c is the remainder when a is divided by b. The algorithm continues this process until the remainder c is zero, at which point b is the GCD of the original numbers a and b. Here is an example of how to use the algorithm to find the GCD of 12 and 18: GCD(12, 18) Step 1: 18 mod 12 = 6, set a = 12, b = 6 Step 2: 12 mod 6 = 0, return 6 as the GCD Therefore, the GCD of 12 and 18 is 6.
Using linear probing insert the following values in hash table of size 10. Elements are 28, 55, 71, 67, 11, 10, 90, 44,
ANSWER: Assuming the hash function is simply the modulo operator % with a table size of 10, and linear probing is used to handle collisions, here is how the values can be inserted into the hash table: Initial state: Initial state: Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | | | | | | | | | | | Insert 28 Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | 28| | | | | | | | | | Insert 55: Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | 28|55 | | | | | | | | | Insert 71: Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | 28|55 |71 | | | | | | | | Insert 67: Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | 28|55 |71 |67 | | | | | | | Insert 11: Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | 28|55 |71 |67 |11 | | | | | | Insert 10: Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | 28|55 |71 |67 |11 |10 | | | | | Insert 90: Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | 28|55 |71 |67 |11 |10 |90 | | | | Insert 44: Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Element | 28|55 |71 |67 |11 |10 |90 |44 | |
Explain sequential search, Write an algorithm for sequential search. ANSWER: Sequential search, also known as linear search, is a method for finding a particular element in a list by examining each element in order, starting from the beginning of the list until the target element is found or the end of the list is reached. The algorithm works by comparing each element of the list with the target element until a match is found. If a match is found, the algorithm returns the index of the element in the list. If no match is found after examining all elements in the list, the algorithm returns a value indicating that the target element is not in the list. The algorithm for sequential search is as follows: Set a variable found to false Set a variable index to 0 While found is false and index is less than the length of the list: a. If the item at the current index is equal to the target item: i. Set found to true b. Else, increment index by 1 If found is true, return the index of the target item If found is false, return -1 to indicate that the target item was not found. Sequential search has a time complexity of O(n), where n is the length of the list, because in the worst case scenario, the algorithm must examine every element in the list before determining that the target element is not present. Despite its simplicity, sequential search can be useful for small lists or lists that are not sorted. However, for large lists or lists that are sorted, more efficient search algorithms such as binary search or hash tables may be more appropriate.
Convert the A*B+C/D expression into postfix using stack. ANSWER: To convert the infix expression A*B+C/D to postfix using a stack, we can follow the following steps: Create an empty stack and an empty output string. Create an empty stack and an empty output string. Iterate through each symbol in the infix expression from left to right. If the symbol is an operand (i.e., a letter or a number), add it to the output string. If the symbol is an operator (+, -, *, /), pop all operators from the stack that have higher or equal precedence than the current operator, and append them to the output string. Then push the current operator onto the stack. If the symbol is an opening parenthesis, push it onto the stack. If the symbol is a closing parenthesis, pop operators from the stack and append them to the output string until an opening parenthesis is encountered. Discard the opening and closing parentheses. After all symbols have
What is skip list? Give its representation. Write an algorithm to insert new item (k,e) in the skip list S ANSWER: A skip list is a probabilistic data structure that allows for efficient searching, insertion, and deletion operations. It consists of a sorted linked list with additional linked lists called “skip lists” that allow for faster search operations. The skip list is represented by a series of layers, with the bottom layer being an ordinary linked list containing all the elements in sorted order. Each layer above the bottom layer is a sub-list of the previous layer, and each element in a higher layer appears in that layer with a certain probability. The highest layer contains only a single element, which is a sentinel node that marks the end of the list. Each element in a skip list contains two fields: a key field that holds the value of the element, and a pointer field that points to the next element in the list. In addition, each element in a higher layer also has a pointer field that points to the next element in the higher layer. To insert a new item (k,e) into a skip list S, we can use the following algorithm: Traverse the skip list from the highest layer to the bottom layer, searching for the appropriate location to insert the new item. During this traversal, maintain an array “update” that contains the nodes that need to be updated when the new item is inserted. Once the appropriate location has been found, check if the node at that location already contains the key “k”. If it does, then update the value of that node to “e”. Otherwise, proceed to step 3. Generate a random number between 0 and 1. If the number is less than or equal to a pre-determined probability p, then insert a new node with key “k” and value “e” at each layer up to a new random layer. Otherwise, only insert the new node at the bottom layer. Update the pointers of the nodes in the “update” array to point to the new node at each layer where the new node was inserted. By using skip lists, we can achieve logarithmic time complexity for searching, insertion, and deletion operations on average. The probability p can be adjusted to balance the trade-off between space and time complexity
Construction algorithm for following operations on a Doubly linked List (1) CREATE AT END (2) DELETE AT START (3) TRAVERSE
ANSWER: Here is a construction algorithm for the following operations on a doubly linked list:
(1) CREATE AT END: Initialize a new node with the given data and pointers to the previous and next nodes, setting both to NULL. If the list is empty (i.e. head is NULL), set the head to the new node. Otherwise, traverse the list to find the last node and set its next pointer to the new node, and set the new node’s prev pointer to the last node. Display a message indicating that the node has been created.
(2) DELETE AT START: If the list is empty (i.e. head is NULL), display a message indicating that the list is empty and return. Otherwise, set a temporary node pointer to the head of the list. If the list contains only one node, set the head to NULL. Otherwise, set the next pointer of the second node to NULL, and set the head to point to the second node. Free the memory allocated for the temporary node pointer. Display a message indicating that the node has been deleted.
(3) TRAVERSE: If the list is empty (i.e. head is NULL), display a message indicating that the list is empty and return. Otherwise, set a temporary node pointer to the head of the list. Traverse the list, displaying the data of each node and setting the temporary node pointer to the next node. Repeat step 3 until the temporary node pointer is NULL.
been processed, pop any remaining operators from the stack and append them to the output string. Using this algorithm, we can convert the infix expression A*B+C/D to the postfix expression AB*CD/+. Here is a step-by-step explanation of the conversion proccess Therefore, the postfix expression of A*B+C/D is AB*C+D/ (not for this)
With the help of suitable example, explain following operation, Enqueue and Dequeue and traverse operation of circular queue. ANSWER: DS THEORY Page 12 A circular queue is a data structure that behaves like a regular queue, except that the rear end of the queue is connected to the front end, forming a circle. This allows elements to be efficiently inserted and removed from the queue in a circular manner. The enqueue and dequeue operations work similarly to those of a regular queue, with the exception that the queue is circular. Let’s consider an example of a circular queue of size 5. Initially, the queue is empty and all pointers point to -1. Front = -1, Rear = -1 Enqueue: We add elements to the queue by incrementing the rear pointer and adding the element to that index. Suppose we want to add the elements 10, 20, 30, 40, and 50 in that order. 10 | – | – | – | – | Front = 0, Rear = 0 10 | 20 | – | – | – | Front = 0, Rear = 1 10 | 20 | 30 | – | – | Front = 0, Rear = 2 10 | 20 | 30 | 40 | – | Front = 0, Rear = 3 10 | 20 | 30 | 40 | 50 | Front = 0, Rear = 4 Dequeue: We remove elements from the queue by incrementing the front pointer and returning the element at that index. Suppose we dequeue two elements.- | 20 | 30 | 40 | 50 | Front = 1, Rear = 4- | – | 30 | 40 | 50 | Front = 2, Rear = 4 Traverse: To traverse the circular queue, we can start from the front index and iterate through the elements until we reach the rear index. For example, if we want to print the elements of the queue in order,
we can do the following:
for (int i = front; i
printf(“%d “, queue[i]);
}
This will output: 30 40 50
Explain breadth first search technique for graph traversal. ANSWER: Breadth-First Search (BFS) is a graph traversal technique that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the vertices at the next level. The algorithm starts at a source vertex and explores all the vertices at the same level before moving on to the next level. To achieve this, BFS uses a queue to store the vertices that have been visited but whose neighbors have not been explored yet. Here is the step-by-step process for BFS: Initialize a queue and add the source vertex to it. Mark the source vertex as visited. • While the queue is not empty, do the following: Dequeue the next vertex from the queue. Visit the vertex. • • For each neighbor of the vertex, if it has not been visited yet, mark it as visited and enqueue it. Repeat step 3 until the queue is empty. The BFS algorithm visits all the vertices of the graph in the order of their distance from the source vertex. That is, it visits all the vertices at a distance of 1 from the source vertex first, then all the vertices at a distance of 2, and so on. BFS can be used to find the shortest path between two vertices in an unweighted graph, as the algorithm guarantees that it visits all the vertices at a certain distance from the source vertex before moving on to the vertices at the next distance level. For example, consider the following undirected graph: 1–2–3 / | 4 | 5–6 Starting from vertex 1, the BFS algorithm will visit the vertices in the following order: 1, 2, 4, 3, 5, 6. The queue will contain the following vertices at each step:
Step 1: queue = [1]
Step 2: queue = [2, 4]
Step 3: queue = [4, 3, 5] 
Step 4: queue = [3, 5, 6]
Step 5: queue = [5, 6]
Step 6: queue = [6] Therefore, the BFS algorithm will visit all the vertices of the graph in breadth-first order, starting from vertex 1.
What is Binary Tree. Explain inorder and postorder traversals with example. ANSWER: A binary tree is a data structure where each node has at most two children, which are referred to as the left child and the right child. Each node in a binary tree can have up to two children, but it can also have zero or one child if it is a leaf node or a parent node with only one child. Inorder and postorder traversals are two methods used to traverse a binary tree. Inorder traversal of a binary tree means visiting all the nodes in the tree in the order of left subtree, root, and right subtree. In other words, we first visit the left subtree, then the root, and finally the right subtree. Here is an example of inorder traversal of a binary tree: 1 / \ 2 3 / \ / \ 4 5 6 7 The inorder traversal of this binary tree is: 4, 2, 5, 1, 6, 3, 7. Postorder traversal of a binary tree means visiting all the nodes in the tree in the order of left subtree, right subtree, and root. In other words, we first visit the left subtree, then the right subtree, and finally the root. Here is an example of postorder traversal of a binary tree: 1 / \ 2 3 / \ / \ 4 5 6 7 The postorder traversal of this binary tree is: 4, 5, 2, 6, 7, 3, 1. In inorder traversal, we visit the left subtree first, so we visit the leftmost node in the tree, which is 4. Then we visit its parent node, which is 2, and then we visit the right child of 2, which is 5. After that, we visit the root node, which is 1, and then we visit its right child, which is 3. Finally, we visit the rightmost subtree, which is rooted at 7. In postorder traversal, we visit the left subtree first, so we visit the leftmost node in the tree, which is 4. Then we visit its right sibling, which is 5, and then we visit their parent node, which is 2. After that, we visit the left child of 2, which is 6, and then we visit its right sibling, which is 7. Finally, we visit the root node, which is 1. 
What is an Abstract Data type (ADT)? Explain, why queue is called ADT?
ANSWER: An Abstract Data Type (ADT) is a high-level description of a data structure that specifies the operations that can be performed on that structure and the constraints that apply to those operations. An ADT provides a conceptual view of the data structure, independent of its implementation details. A queue is a classic example of an ADT. It is a collection of elements that are arranged in a specific order, where the order of elements is determined by the order in which they were added to the queue. A queue supports two primary operations: enqueue, which adds an element to the back of the queue, and dequeue, which removes and returns the element at the front of the queue. The reason why a queue is considered an ADT is that it specifies a set of operations that must be supported by any implementation of a queue. The ADT does not specify how the queue should be implemented; it only specifies the behavior that the queue must exhibit. For example, the ADT does not specify whether the queue should be implemented as a linked list or as an array. By defining the behavior of a data structure in this way, an ADT enables developers to create code that is independent of the underlying implementation of the data structure. This makes it possible to switch to a different implementation of the data structure without affecting the code that uses it. In other words, an ADT provides a layer of abstraction that helps to decouple the implementation details from the application logic
The malloc() function is used to dynamically allocate memory at runtime. It takes a single argument, which is the number of bytes to be allocated. It returns a pointer to the beginning of the allocated memory block, or NULL if the allocation failed. calloc(): The calloc() function is used to dynamically allocate and initialize memory at runtime. It takes two arguments, the number of elements to be allocated and the size of each element. It returns a pointer to the beginning of the allocated memory block, or NULL if the allocation failed. realloc(): The realloc() function is used to dynamically resize a previously allocated memory block. It takes two arguments, a pointer to the previously allocated memory block and the new size in bytes. It returns a pointer to the beginning of the resized memory block, or NULL if the allocation failed. free(): The free() function is used to deallocate memory that was previously allocated with malloc(), calloc(), or realloc(). It takes a single argument, which is a pointer to the beginning of the memory block to be deallocated.
Explain the following graph terminology with figure i) Undirected graph ii) Total degree of vertex iii) Simple path iv) Cycle ANSWER: i) Undirected graph: An undirected graph is a type of graph in which edges do not have a direction, meaning that they can be traversed in both directions. In other words, an undirected graph is a set of vertices connected by edges where the order of vertices does not matter. Example of an undirected graph: A —– B | | | | C —– D DS THEORY Page 21 C —–D ii) Total degree of vertex: The total degree of a vertex in a graph is the sum of the degrees of all edges connected to that vertex. The degree of a vertex is the number of edges that are connected to it. Example of total degree of vertex: In the following undirected graph, the vertex A has a total degree of 3 since it is connected to three edges (B, C, and D). A —–B | | | | C —–D iii) Simple path: A simple path is a path in a graph that does not visit any vertex more than once. In other words, a simple path is a path that does not have any repeated vertices. Example of a simple path: In the following undirected graph, the path (A, C, E) is a simple path since it does not visit any vertex more than once. B / \ / \ A —C —E \ / \/ D iv) Cycle: A cycle is a path in a graph that starts and ends at the same vertex. In other words, a cycle is a path that starts and ends at the same vertex, and contains at least one other vertex. Example of a cycle: In the following undirected graph, the path (C, E, F, C) is a cycle since it starts and ends at the vertex C, and contains other vertices. A / \ / \ B C —E / \ / \ F D
What is queue? Write an algorithm to implement insert item into queue using singly linked list. ANSWER: A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In a queue, the elements are added at the back and removed from the front. The element that is added first is the first one to be removed. The operations that can be performed on a queue are: Enqueue: Adds an element to the back of the queue. Dequeue: Removes an element from the front of the queue. Peek: Returns the element at the front of the queue without removing it. IsEmpty: Checks if the queue is empty or not. Enqueue operation: a. Create a new node with the given data. b. If the queue is empty, make the new node the front and rear of the queue. c. Otherwise, make the new node the next of the current rear and update rear to point to the new node. Dequeue operation: a. If the queue is empty, return null. b. Store the data of the front node. c. Update the front to point to the next node. d. If the front becomes null, update rear to null as well. e. Return the stored data. Peek operation: a. If the queue is empty, return null. b. Return the data of the front node. IsEmpty operation: a. Return true if front is null, false otherwise. algorithm to insert an item into a queue using a singly linked list: Create a new node for the item to be inserted. If the queue is empty (i.e., the head is null), set the head of the queue to the new node and return. Otherwise, traverse the linked list from the head node to the last node. Set the next pointer of the last node to the new node. Set the tail of the queue to the new node. Return. In summary, a queue is a linear data structure that follows the FIFO principle, and it can be implemented using a singly linked list. The insert item operation is implemented using the Enqueue operation, which adds an element to the back of the queue
Write a short note on dynamic storage management. Explain how it is done in C. ANSWER: Dynamic storage management refers to the process of allocating and deallocating memory during program execution. It allows programs to request memory from the operating system as needed, and release it when it is no longer needed. This is in contrast to static storage management, where memory is allocated at compile time and remains fixed throughout the program’s execution. In C, dynamic storage management is done using the functions malloc(), calloc(), realloc(), and free(). These functions are defined in the stdlib.h header file. malloc():
Store elements of the given below binary tree using i) One dimensional array ii) Linked list A / \ B C / \ D E \ F
ANSWER: To store the elements of the given binary tree using a one-dimensional array, we need to use a technique called “level order traversal”. This traversal visits each level of the tree from top to bottom, starting from the root. Within each level, it visits the nodes from left to right. We can use a queue to implement this traversal. Here is the algorithm to store the elements of the binary tree using a one-dimensional array: Create a queue and an empty array. Enqueue the root node of the binary tree to the queue. While the queue is not empty: a. Dequeue the first node from the queue. b. Append the value of the dequeued node to the array. c. If the dequeued node has a left child, enqueue the left child to the queue. d. If the dequeued node has a right child, enqueue the right child to the queue. queue. Return the array. Using this algorithm with the given binary tree, we get the following one-dimensional array: [A, B, C, D, E, F] To store the elements of the binary tree using a linked list, we need to define a structure for a node that contains a value and pointers to its left and right children. We can then use these nodes to build a linked list that represents the binary tree. Here is the algorithm to store the elements of the binary tree using a linked list: Define a structure for a node that contains a value and pointers to its left and right children. Create a root node and assign the value of the root of the binary tree to it. For each non-leaf node in the binary tree: a. Create a new node and assign its value to the value of the non-leaf node. b. Set the left child of the new node to a new node with the value of the left child of the non-leaf node. c. Set the right child of the new node to a new node with the value of the right child of the non-leaf node. Return the root node of the linked list.
Write an algorithm to evaluate postfix expression using stack and execute your algorithm with postfix expression 10, 5, 6, * , +, 8, /. Show intermediate stack content after each operation. show intermediate stack content after each operation.
ANSWER: Here’s the algorithm to evaluate postfix expression using a stack: Create an empty stack. Read the postfix expression from left to right. If the current element is a number, push it onto the stack. If the current element is an operator, pop the top two elements from the stack and perform the operation. Push the result back onto the stack. Continue until the end of the postfix expression is reached. Pop the final result from the stack. Now let’s execute this algorithm with the postfix expression 10, 5, 6, *, +, 8, / and show the intermediate stack content after each operation:
Step 1: Create an empty stack.
Step 2: Read the postfix expression from left to right.
Current element: 10 Action: Push 10 onto the stack Stack content: [10]
Current element: 5 Action: Push 5 onto the stack Stack content: [10, 5]
Current element: 6 Action: Push 6 onto the stack Stack content: [10, 5, 6]
Current element: * Action: Pop 6 and 5 from the stack, perform 6 * 5 = 30, and push the result (30) back onto the stack Stack content: [10, 30]
Current element: + Action: Pop 30 and 10 from the stack, perform 30 + 10 = 40, and push the result (40) back onto the stack Stack content: [40]
Current element: 8 Action: Push 8 onto the stack Stack content: [40, 8]
Current element: / Action: Pop 8 and 40 from the stack, perform 40 / 8 = 5, and push the result (5) back onto the stack Stack content: [5]
Step 6: Pop the final result from the stack, which is 5
What is header linked list? Use header linked list to store the following A) polynomial. p(x) = 2x^8 — ANSWER: 5x^7 + 3x^2 + 4 A header linked list is a variation of a singly linked list where an additional node, known as the header node, is used to store metadata about the list. The header node contains information such as the length of the list, pointers to the first and last nodes in the list, and any other information that may be useful for efficiently manipulating the list. To use a header linked list to store the polynomial p(x) = 2x^8 – 5x^7 + 3x^2 + 4, we can represent each term of the polynomial as a node in the linked list. Each node will contain two fields: the coefficient of the term and the exponent of the variable x. Here is the header linked list representation of the polynomial:
Header Node:
Length = 4
First = 0x12345678
Last = 0x87654321
Data Nodes:
Coeff: 2, Exp: 8 -> Next: 0x23456789
Coeff: -5, Exp: 7 -> Next: 0x3456789A
Coeff: 3, Exp: 2 -> Next: 0x456789AB
Coeff: 4, Exp: 0 -> Next: NULL
In this representation, the header node contains information about the list: the length of the list (4), the address of the first node (0x12345678), and the address of the last node (0x87654321). The data nodes represent each term of the polynomial in the order they appear. For example, the first node has a coefficient of 2 and an exponent of 8, representing the term 2x^8 in the polynomial. The last node has a coefficient of 4 and an exponent of 0, representing the constant term 4 in the polynomial. The “Next” field of each node contains the address of the next node in the list. With this representation, we can easily traverse the list to perform operations on the polynomial, such as adding or multiplying it with another polynomial. The header node also allows us to quickly retrieve metadata about the list without having to traverse the entire list
What is sparse matrix ? Convert the following sparse matrix into non-A) sparse matrix. 1 0 0 0, 0 -2 11 0 ,0 0 0 0 ,0 6 0 5, ANSWER: A sparse matrix is a matrix in which most of the elements are zero. In contrast, a dense matrix is a matrix in which most of the elements are non-zero. In many real-world applications, such as scientific simulations, data analysis, and machine learning, matrices can be very large and sparse. Storing and processing such matrices can be computationally expensive and memory intensive. Sparse matrix techniques provide a way to represent and manipulate large sparse matrices efficiently. There are several ways to represent a sparse matrix. One common approach is the compressed sparse row (CSR) format, also known as the row-oriented format. In the CSR format, the non-zero elements of the matrix are stored in three arrays: the values array, the DS NUMERICALS Page 9 format, the non-zero elements of the matrix are stored in three arrays: the values array, the column indices array, and the row pointers array. The values array stores the non-zero values of the matrix in row-major order, the column indices array stores the corresponding column indices of the non-zero values, and the row pointers array stores the indices in the values and column indices arrays where each row of the matrix starts. For example, consider the following sparse matrix: 0 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 0 4 0 5 6 0 0 In the CSR format, the values array would be: 2 3 4 5 6 This format can greatly reduce the memory required to store a sparse matrix, as only the non-zero elements are stored explicitly. Sparse matrix techniques are also used in many algorithms that operate on matrices, such as matrix multiplication, eigenvalue decomposition, and linear solvers. To convert the given sparse matrix into a non-sparse matrix, we simply need to fill in the zero entries with their corresponding values. The resulting non-sparse matrix would be:
1 0 0 0
0 -2 11 0
0 0 0 0
0 6 0 5
Consider the following specification of a graph G=(V, E). v = {1, 2, 3, 4} E= {(1,2) (1,3) (3,3) (3,4) (4,1)} i) Draw an undirected graph. ii) Represent graph G using adjacency matrix. iii) Represent graph G using adjacency linked list.
ANSWER: i) The undirected graph corresponding to the given specification is:
1 —2
/ \
/ \
3 —4
ii) The adjacency matrix representation of the graph G is:
| 1 2 3 4
1 | 0 1 1 0
2 | 1 0 0 0
3 | 0 0 1 1
4 | 1 0 0 0
The rows and columns of the matrix represent the vertices of the graph, and the entries indicate whether there is an edge between the corresponding vertices. For example, the entry in the first row and second column is 1, indicating that there is an edge between vertices 1 and 2.
iii) The adjacency linked list representation of the graph G is:
1: 2 -> 3 -> NULL
2: 1 -> NULL
3: 3 -> 4 -> NULL
4: 1 -> NULL
Each vertex of the graph is represented by a linked list, and the nodes in the linked list represent the adjacent vertices. For example, the linked list for vertex 1 is 2 -> 3 -> NULL, indicating that vertex 1 is adjacent to vertices 2 and 3.
Write a program in C to create a singly linked list and perform the following operations (1) Insert into list (2) search for data Delete from list.
ANSWER: #include
struct Node {
int data; struct Node* next;
};
struct Node* head = NULL;
// Insert a new node at the beginning of the list
void insert(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = head; head =
new_node; printf(“%d inserted into list.\n”, data); }
// Search for a node with the given data
void search(int data) {
struct Node* current = head;
while (current != NULL) {
if (current->data == data) {
printf(“%d found in list.\n”, data);
return;
} current = current->next;
} printf(“%d not found in list.\n”, data);
}
// Delete the first occurrence of a node with the given data
void delete(int data) {
struct Node* current = head;
struct Node* prev = NULL;
while (current != NULL) {
if (current->data == data) {
if (prev == NULL) {
// Node to be deleted is the first node
head = current->next;
}
else {
// Node to be deleted is not the first node
prev->next = current->next;
} free(current);
printf(“%d deleted from list.\n”, data);
return;
} prev = current; current = current->next;
} printf(“%d not found in list.\n”, data);
} int main() { int choice, data;
while (1) {
printf(“1. Insert into list\n”);
printf(“2. Search for data\n”);
printf(“3. Delete from list\n”);
printf(“4. Exit\n”);
printf(“Enter your choice: “);
scanf(“%d”, &choice);
switch (choice) {
case 1:
printf(“Enter data to insert: “);
scanf(“%d”, &data);
insert(data);
break;
case 2:
printf(“Enter data to search: “);
scanf(“%d”, &data);
search(data);
break;
Write a “C” code to find the transpose of a sparse matrix stored in this way. ANSWER:
#include
void transpose(int row, int col, int num, int A[num][3], int B[num][3])
{
int count[col], index[col];
int i, j, k;
// Initialize count array with zeros
for (i = 0; i
count[i] = 0; // Count the number of non-zero elements in each column
for (i = 0; i
count[A[i][1]]++; // Compute the starting index of each column in the transpose matrix
index[0] = 0; for (i = 1; i
// Compute the transpose matrix
for (i = 0; i
{
j = A[i][1]; // column of A[i]
k = index[j]; // starting index of column j in B
B[k][0] = A[i][1]; // row of B[k]
B[k][1] = A[i][0]; // column of B[k]
B[k][2] = A[i][2]; // value of B[k]
index[j]++; // increment index for next element in column j
} }
int main() {
int row, col, num, i, j;
printf(“Enter the number of rows: “);
scanf(“%d”, &row);
printf(“Enter the number of columns: “);
scanf(“%d”, &col);
printf(“Enter the number of non-zero elements: “);
scanf(“%d”, &num); int A[num][3], B[num][3];
printf(“Enter the matrix in compressed row format (row, column, value):\n”);
for (i = 0; i
scanf(“%d %d %d”, &A[i][0], &A[i][1], &A[i][2]);
transpose(row, col, num, A, B); printf(“The transpose of the matrix in compressed row format (row, column, value) is:\n”);
for (i = 0; i
printf(“%d %d %d\n”, B[i][0], B[i][1], B[i][2]);
return 0;
}
2nd prog
case 3:
printf(“Enter data to delete: “);
scanf(“%d”, &data);
delete(data);
break;
case 4:
exit(0);
default:
printf(“Invalid choice.\n”);
}
}
return 0;
}