{"pinia":{"ui":{"prefs":{"theme":"system","textScale":"md","fontFamily":"sans","reducedMotion":false,"highContrast":false}},"academy":{"universities":[],"universitySummaries":[{"slug":"rtu","name":"RTU","fullName":"Rajasthan Technical University","branches":[{"slug":"first-year-common","name":"First Year (Common)"},{"slug":"computer-science","name":"Computer Science"},{"slug":"mechanical","name":"Mechanical"},{"slug":"civil","name":"Civil"},{"slug":"ai-data-science","name":"AI & Data Science"},{"slug":"ee-ec-eee","name":"EE / EC / EEE"}]},{"slug":"aktu","name":"AKTU","fullName":"Dr. A. P. J. Abdul Kalam Technical University","branches":[{"slug":"first-year-common","name":"First Year (Common)"},{"slug":"computer-science","name":"Computer Science"}]}],"activePapers":[{"id":"rtu-cs-y2-s3-data-structures-paper-2024","title":"Data Structures and Algorithms — Semester 3 (2024)","subjectSlug":"data-structures","subjectName":"Data Structures","universitySlug":"rtu","branchSlug":"computer-science","year":2,"semester":3,"examYear":2024,"paperCode":"3E1202","questions":[{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q1","number":1,"marks":2,"tags":["basics"],"text":[{"type":"paragraph","content":"What is Data structure?"}],"answer":{"summary":"A data structure provides a specific format for organizing, storing, and accessing data efficiently in memory.","explanation":[{"type":"paragraph","content":"A data structure is a specialized, systematic format used in computer science for organizing, processing, retrieving, and storing data in memory. It rigorously defines not only the logical relationship between individual data elements but also the specific algorithms and operational constraints that can be efficiently performed on them, such as arrays, linked lists, or trees."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q2","number":2,"marks":2,"tags":["complexity","asymptotic-notations"],"text":[{"type":"paragraph","content":"Explain Asymptotic Notations?"}],"answer":{"summary":"Asymptotic notations mathematically describe algorithm complexity limits regarding execution time and memory space.","explanation":[{"type":"paragraph","content":"Asymptotic notations are formal mathematical tools utilized extensively to describe the limiting behavior and inherent complexity of an algorithm as the input size progressively approaches infinity. The three primary notations are Big O ($O$) for the worst-case upper bound, Omega ($\\Omega$) for the best-case lower bound, and Theta ($\\Theta$) for the tight, average-case bound."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q3","number":3,"marks":2,"tags":["classification"],"text":[{"type":"paragraph","content":"What are linear and non-linear data structural?"}],"answer":{"summary":"Linear structures arrange data sequentially, while non-linear structures connect data hierarchically.","explanation":[{"type":"paragraph","content":"Linear data structures arrange their constituent elements in a strict, sequential, one-dimensional order where every element logically connects to its immediate predecessor and successor (e.g., Arrays, Stacks, Linked Lists). Conversely, non-linear data structures organize elements hierarchically or interconnectedly, allowing a single element to connect to multiple other elements simultaneously, establishing complex relationships (e.g., Trees, Graphs)."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q4","number":4,"marks":2,"tags":["linked-list"],"text":[{"type":"paragraph","content":"What is linked list? What are its types?"}],"answer":{"summary":"A linked list is a sequential collection of nodes containing data and pointers. Types include singly, doubly, and circular.","explanation":[{"type":"paragraph","content":"A linked list is a dynamic, linear data structure consisting of discrete elements called nodes. Each node physically encapsulates two parts: the actual data and a referential pointer linking to the memory address of the subsequent node. The primary classifications encompass Singly Linked Lists (forward traversal only), Doubly Linked Lists (bidirectional traversal), and Circular Linked Lists (continuous looping)."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q5","number":5,"marks":2,"tags":["stack"],"text":[{"type":"paragraph","content":"Write applications of stacks."}],"answer":{"summary":"Stacks are vital for managing function calls, evaluating expressions, and executing backtracking algorithms.","explanation":[{"type":"paragraph","content":"Stacks operate strictly on a Last-In-First-Out (LIFO) architectural principle, making them indispensable for various system-level operations. Critical applications include meticulously managing nested function call memory (the Call Stack), parsing and evaluating complex mathematical expressions (infix to postfix conversion), implementing undo/redo state mechanisms in software, and executing algorithmic backtracking in graph traversals (like Depth First Search)."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q6","number":6,"marks":2,"tags":["tree","binary-tree"],"text":[{"type":"paragraph","content":"Define complete Binary Tree?"}],"answer":{"summary":"A complete binary tree fills every hierarchical level entirely, with the lowest level filling strictly from left to right.","explanation":[{"type":"paragraph","content":"A complete binary tree is a highly structured binary tree variant strictly mandated to have all its hierarchical levels completely filled with nodes, with the possible sole exception of the deepest, final level. Furthermore, any nodes located on this final terminal level must be densely populated as far left as physically possible, without any spatial gaps."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q7","number":7,"marks":2,"tags":["memory-management"],"text":[{"type":"paragraph","content":"Differentiate between static and Dynamic memory allocation."}],"answer":{"summary":"Static allocation occurs during compilation with fixed sizes, whereas dynamic allocation occurs at runtime with adaptable sizes.","explanation":[{"type":"paragraph","content":"Static memory allocation strictly occurs during the software compilation phase, permanently reserving a rigidly fixed block of memory that cannot be subsequently resized (e.g., standard arrays). Dynamic memory allocation occurs flexibly during runtime execution, allowing software to dynamically request, resize, and explicitly free memory blocks on the heap as operational demands fluctuate (e.g., using `malloc()` or `new`)."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q8","number":8,"marks":2,"tags":["graph","mst"],"text":[{"type":"paragraph","content":"What is the concept of minimum spanning Tree?"}],"answer":{"summary":"An MST connects all graph vertices without cycles using the absolute minimum cumulative edge weight.","explanation":[{"type":"paragraph","content":"Within a weighted, undirected graph, a Minimum Spanning Tree (MST) is a mathematically derived subset of interconnecting edges that successfully spans and links all constituent vertices together without forming any closed cyclic loops. Crucially, the aggregate sum of the numerical weights of all edges comprising this specific tree is the absolute minimum mathematically possible for that graph."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q9","number":9,"marks":2,"tags":["adt"],"text":[{"type":"paragraph","content":"What is meant by abstract data type?"}],"answer":{"summary":"An ADT defines data behavior and operational constraints without specifying underlying implementation details.","explanation":[{"type":"paragraph","content":"An Abstract Data Type (ADT) serves as a conceptual, mathematical blueprint or model for a data structure. It rigorously specifies the logical behavior, allowable data values, and permitted operational methods from a strict user perspective, while purposefully omitting all concrete details regarding algorithmic implementation or underlying physical memory management (e.g., defining a Queue's enqueue/dequeue actions without specifying arrays or linked lists)."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q10","number":10,"marks":2,"tags":["tree","graph"],"text":[{"type":"paragraph","content":"Compare tree and graph."}],"answer":{"summary":"Trees enforce a strict hierarchical root structure without loops, while graphs allow complex, cyclic networks without roots.","explanation":[{"type":"paragraph","content":"A tree is a specialized, strictly hierarchical non-linear data structure originating from a singular root node, mathematically enforcing a rule where exactly one unique path exists between any two discrete nodes, strictly forbidding cyclic loops. A graph is a generalized network data structure consisting of freely interconnected vertices and edges, readily permitting multiple diverse paths, closed cyclic loops, and possessing no mandatory root node."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q11","number":11,"marks":4,"tags":["recursion","tower-of-hanoi"],"text":[{"type":"paragraph","content":"Explain tower of Hanoi problem in detail and write algorithm for that."}],"answer":{"summary":"A comprehensive explanation of the Tower of Hanoi recursive algorithm, detailing the mathematical rules, operational logic, and C++ algorithmic implementation.","explanation":[{"type":"heading","content":"The Tower of Hanoi Algorithmic Puzzle"},{"type":"paragraph","content":"The Tower of Hanoi is a classic, fundamental mathematical puzzle that serves as the quintessential educational example for teaching the paradigm of recursive algorithmic design. The puzzle setup consists of three vertical pegs (or rods) and a specified number of perforated disks of differing, incrementally increasing radii. Initially, all disks are neatly stacked on the first originating peg in a perfectly conical shape, ordered strictly by size with the largest disk resting at the very bottom."},{"type":"subheading","content":"Operational Constraints and Rules"},{"type":"paragraph","content":"The overarching objective of the algorithm is to successfully transport the entire stacked tower from the initial source peg to a designated destination peg, utilizing the third remaining peg as an auxiliary workspace. This physical transfer must strictly adhere to three non-negotiable operational constraints: First, only one single disk may be manipulated and moved at any given time. Second, a valid move strictly consists of removing the topmost exposed disk from one peg and sliding it onto another peg. Third, and most crucially, a larger, heavier disk can never, under any circumstances, be placed on top of a smaller, lighter disk."},{"type":"subheading","content":"Recursive Algorithmic Logic"},{"type":"paragraph","content":"The problem can be elegantly deconstructed using a recursive mathematical methodology. To move a tower of height $n$ from the Source peg to the Destination peg, the algorithm implicitly assumes the capability to move a smaller tower of height $n-1$. The logical sequence is threefold: \n1. Recursively move the top $n-1$ disks from the Source peg to the Auxiliary peg. \n2. Physically move the largest, remaining $n$-th disk directly from the Source peg to the Destination peg. \n3. Recursively move the $n-1$ disks from the Auxiliary peg to the final Destination peg, resting them on top of the largest disk. \nThis recursive breakdown continues down to the trivial base case where $n=1$, requiring only a single direct move."},{"type":"subheading","content":"C++ Algorithmic Implementation"},{"type":"code","language":"cpp","code":"void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {\n // Base Condition: Only 1 disk left to move\n if (n == 1) {\n cout << \"Move disk 1 from rod \" << from_rod << \" to rod \" << to_rod << endl;\n return;\n }\n // Step 1: Move top n-1 disks from Source to Auxiliary\n towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);\n \n // Step 2: Move the largest nth disk from Source to Destination\n cout << \"Move disk \" << n << \" from rod \" << from_rod << \" to rod \" << to_rod << endl;\n \n // Step 3: Move the n-1 disks from Auxiliary to Destination\n towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);\n}"}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q12","number":12,"marks":4,"tags":["array","address-calculation"],"text":[{"type":"paragraph","content":"Calculate the address of the element A[15,25] using row major order and column major order for an array A[-15...10, 15...40] of elements. It is stored at location 100 and the size of each element is 4 bytes."}],"answer":{"summary":"A detailed mathematical calculation of absolute memory addresses in a two-dimensional array using both Row-Major and Column-Major ordering formulas.","explanation":[{"type":"heading","content":"2D Array Memory Address Calculation"},{"type":"paragraph","content":"Two-dimensional arrays, despite their conceptual matrix-like grid structure, must ultimately be stored linearly within a computer's one-dimensional memory space. This linear flattening is typically achieved via two standard memory mapping algorithms: Row-Major Order (storing data row by sequential row) and Column-Major Order (storing data column by sequential column). Calculating the exact physical memory address of a specific element requires applying defined mathematical formulas utilizing the array's declared bounds, the base memory address, and the byte size of a single element."},{"type":"subheading","content":"Extracting Matrix Parameters"},{"type":"paragraph","content":"The problem explicitly defines a 2D array structurally bounded as $A[L1\\dots U1, L2\\dots U2] = A[-15\\dots 10, 15\\dots 40]$. \nFrom this declaration, we systematically extract the critical operational parameters: \n- Row Lower Bound ($L1$) = -15 \n- Row Upper Bound ($U1$) = 10 \n- Column Lower Bound ($L2$) = 15 \n- Column Upper Bound ($U2$) = 40 \n- Base Starting Memory Address ($Base$) = 100 \n- Element Size in Bytes ($W$) = 4 bytes \n- Target Element Row Index ($i$) = 15 \n- Target Element Column Index ($j$) = 25 \nWe first calculate the absolute dimensions of the matrix. The total number of rows $M = U1 - L1 + 1 = 10 - (-15) + 1 = 26$. The total number of columns $N = U2 - L2 + 1 = 40 - 15 + 1 = 26$."},{"type":"subheading","content":"Calculation via Row-Major Order"},{"type":"paragraph","content":"The universal formula for Address Calculation in Row-Major Order is mathematically defined as: $Address = Base + W \\times [(i - L1) \\times N + (j - L2)]$."},{"type":"math","expression":"Address = 100 + 4 \\times [(15 - (-15)) \\times 26 + (25 - 15)]","displayMode":true},{"type":"math","expression":"Address = 100 + 4 \\times [30 \\times 26 + 10] = 100 + 4 \\times [780 + 10] = 100 + 4 \\times [790]","displayMode":true},{"type":"math","expression":"Address = 100 + 3160 = 3260","displayMode":true},{"type":"subheading","content":"Calculation via Column-Major Order"},{"type":"paragraph","content":"Conversely, the universal formula for Address Calculation in Column-Major Order is defined as: $Address = Base + W \\times [(j - L2) \\times M + (i - L1)]$."},{"type":"math","expression":"Address = 100 + 4 \\times [(25 - 15) \\times 26 + (15 - (-15))]","displayMode":true},{"type":"math","expression":"Address = 100 + 4 \\times [10 \\times 26 + 30] = 100 + 4 \\times [260 + 30] = 100 + 4 \\times [290]","displayMode":true},{"type":"math","expression":"Address = 100 + 1160 = 1260","displayMode":true},{"type":"paragraph","content":"Through meticulous substitution and execution, the specific memory address is 3260 under Row-Major constraints and 1260 under Column-Major constraints."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q13","number":13,"marks":4,"tags":["linked-list","circular-linked-list"],"text":[{"type":"paragraph","content":"Write an algorithm to insert a node at specific location in circular linked list."}],"answer":{"summary":"A systematic procedural algorithm for inserting a newly instantiated node at a highly specific index location within a dynamically linked circular list.","explanation":[{"type":"heading","content":"Node Insertion in Circular Linked Lists"},{"type":"paragraph","content":"A circular linked list is a specialized, non-linear variation of a standard linked list architecture where the terminal, final node does not point to a NULL memory address, but instead dynamically loops back to establish a referential connection with the initial head node, forming a continuous, unbroken ring structure. Inserting a new node into this continuously looping structure at a specific integer location $k$ requires careful manipulation of pointer references to ensure the cyclic integrity is never accidentally severed."},{"type":"subheading","content":"Initialization and Edge Cases"},{"type":"paragraph","content":"The algorithmic procedure commences with the dynamic instantiation of a new memory block for the node and the assignment of the incoming data payload. \n**Step 1:** Initialize a new node pointer `newNode` via dynamic allocation (e.g., `malloc` or `new`) and strictly assign its `data` property. \n**Step 2 (Empty List):** If the foundational `head` pointer is currently NULL, the list is completely empty. The `newNode` must become the singular `head`, and crucially, its `next` pointer must loop back to explicitly reference itself: `newNode->next = newNode; head = newNode`. \n**Step 3 (Insertion at Position 1):** If the requested location is the absolute beginning, we must painstakingly traverse the entire cyclic ring to locate the absolute last node. Once found, the new node is inserted: `newNode->next = head; lastNode->next = newNode; head = newNode`."},{"type":"subheading","content":"Algorithmic Traversal and Insertion"},{"type":"paragraph","content":"If the insertion targets a location deep within the cyclic structure (where location $k > 1$), the algorithm relies on sequential traversal. \n**Step 4:** Initialize a temporary traversal pointer `temp` mapped identically to `head`. Initialize an integer counter starting at 1. \n**Step 5:** Initiate a traversal loop, advancing `temp = temp->next` and incrementing the counter until the counter mathematically equals $k - 1$. This maneuver strategically positions the `temp` pointer precisely at the node located immediately before the intended insertion point. \n**Step 6:** Execute the pointer reassignment logic to splice the new node into the chain. First, secure the forward connection: `newNode->next = temp->next`. Second, sever and reroute the preceding connection to complete the insertion: `temp->next = newNode`. This guarantees the seamless integration of the node while preserving the circular topology."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q14","number":14,"marks":4,"tags":["tree","traversal"],"text":[{"type":"paragraph","content":"The in-order and pre-order traversal sequence of nodes in a binary tree are given below:"},{"type":"paragraph","content":"In-order: Q, B, K, C, F, A, G, P, E, D, H, R"},{"type":"paragraph","content":"Pre-order: G, B, Q, A, C, K, F, P, D, E, R, H"},{"type":"paragraph","content":"Draw the binary tree."}],"answer":{"summary":"A step-by-step logical reconstruction of a hierarchical binary tree utilizing uniquely provided In-order and Pre-order traversal sequences.","explanation":[{"type":"heading","content":"Binary Tree Reconstruction from Traversals"},{"type":"paragraph","content":"A unique, structurally sound binary tree can be logically and deterministically reconstructed if and only if both its In-order traversal and its Pre-order (or alternatively, Post-order) traversal sequences are provided. The fundamental algorithmic strategy relies heavily on the inherent definitions of these traversal methods. The Pre-order traversal sequence strictly guarantees that the absolute first element encountered is unequivocally the overarching root of the current tree or subtree. Conversely, the In-order traversal sequence provides crucial topological mapping: locating that established root element within the In-order sequence instantaneously partitions all remaining elements into two distinct, mutually exclusive subsets representing the entire left subtree and the entire right subtree."},{"type":"subheading","content":"Reconstruction Step-by-Step"},{"type":"paragraph","content":"We are provided with the following sequences: \nIn-order: `Q, B, K, C, F, A, G, P, E, D, H, R` \nPre-order: `G, B, Q, A, C, K, F, P, D, E, R, H`"},{"type":"paragraph","content":"**Step 1 (Root Identification):** Analyzing the Pre-order sequence, the very first element is `G`. Therefore, node **`G` is the absolute root of the entire binary tree**. \n**Step 2 (Partitioning):** We locate `G` within the In-order sequence. The sequence splits perfectly around `G`: \nLeft Subtree Elements: `{Q, B, K, C, F, A}` \nRight Subtree Elements: `{P, E, D, H, R}`"},{"type":"paragraph","content":"**Step 3 (Reconstructing the Left Subtree):** We filter the Pre-order sequence for only the left elements: `B, Q, A, C, K, F`. The first element is `B`, making it the root of the left subtree (child of `G`). Locating `B` in the left In-order subset (`Q, B, K, C, F, A`) shows `Q` is to its left (left child of `B`), and `{K, C, F, A}` is to its right. Filtering Pre-order for this right subset yields `A, C, K, F`. Thus, `A` is the right child of `B`. In In-order `{K, C, F, A}`, `A` is at the end, meaning `{K, C, F}` forms its left subtree. Pre-order for this is `C, K, F`. So, `C` is the left child of `A`. In-order for `C` is `K, C, F`, making `K` the left child and `F` the right child of `C`."},{"type":"paragraph","content":"**Step 4 (Reconstructing the Right Subtree):** We filter the Pre-order sequence for the right elements: `P, D, E, R, H`. The first element is `P`, making it the right child of the main root `G`. Locating `P` in the right In-order subset (`P, E, D, H, R`) shows it has no left children, and `{E, D, H, R}` forms its right subtree. Pre-order for this is `D, E, R, H`. So, `D` is the right child of `P`. In-order for `D` is `E, D, H, R`, making `E` the left child of `D`, and `{H, R}` the right subtree. Pre-order for this is `R, H`. So `R` is the right child of `D`. In-order is `H, R`, making `H` the left child of `R`."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q15","number":15,"marks":4,"tags":["queue","priority-queue"],"text":[{"type":"paragraph","content":"What is Priority Queue? How can it be implemented? Write an applications of priority Queue."}],"answer":{"summary":"A detailed exploration of the Priority Queue abstract data type, examining its structural implementations, algorithmic efficiency, and real-world computational applications.","explanation":[{"type":"heading","content":"Understanding Priority Queues"},{"type":"paragraph","content":"A Priority Queue is a highly specialized, abstract data type (ADT) that functions similarly to a traditional queue or stack, but introduces a crucial differentiating characteristic: every single element inserted into the queue is inherently associated with a predefined \"priority\" value. When elements are dequeued or served from the queue, the element possessing the highest mathematically defined priority is always removed first, completely irrespective of its chronological arrival time. If two distinct elements share the exact same priority value, they are subsequently served according to their order of insertion, adhering to the standard First-In-First-Out (FIFO) principle."},{"type":"subheading","content":"Structural Implementations and Efficiency"},{"type":"paragraph","content":"While theoretically conceptually simple, the underlying physical implementation of a priority queue drastically affects its algorithmic performance. \n1. **Unordered Arrays/Linked Lists:** Elements are simply appended in $O(1)$ time. However, finding the highest priority element requires scanning the entire structure, resulting in a highly inefficient $O(n)$ time complexity for deletion. \n2. **Ordered Arrays/Linked Lists:** Elements are meticulously sorted upon insertion, requiring an inefficient $O(n)$ time. However, deletion of the highest priority element becomes instantaneous at $O(1)$ time. \n3. **Binary Heaps (Optimal):** Utilizing a Min-Heap or Max-Heap tree structure provides the most mathematically balanced and efficient implementation. Both insertion and deletion operations gracefully scale with a logarithmic time complexity of $O(\\log n)$, making heaps the undisputed industry standard for priority queue implementation."},{"type":"subheading","content":"Practical Computational Applications"},{"type":"paragraph","content":"Priority Queues are fundamentally integral to numerous advanced algorithms and critical operating system functions: \n- **Graph Algorithms:** They are strictly required for the efficient execution of Dijkstra's Shortest Path algorithm and Prim's Minimum Spanning Tree algorithm to rapidly retrieve the next closest vertex. \n- **Operating System Schedulers:** CPU task scheduling algorithms heavily utilize priority queues to dynamically manage and execute high-priority system interrupts or real-time processes ahead of low-priority background tasks. \n- **Data Compression:** Huffman Coding algorithms employ priority queues to actively build the optimal prefix tree by continuously merging the two least frequent character nodes."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q16","number":16,"marks":4,"tags":["stack","postfix"],"text":[{"type":"paragraph","content":"Convert the following expression into its equivalent postfix expression."},{"type":"paragraph","content":"A+(B*C - (D/E^F)*G)*H"}],"answer":{"summary":"Executing a rigorous, step-by-step algorithmic conversion of a complex infix mathematical expression into its postfix equivalent using precedence rules.","explanation":[{"type":"heading","content":"Infix to Postfix Algorithmic Conversion"},{"type":"paragraph","content":"The problem demands the manual algorithmic conversion of the complex, human-readable infix mathematical expression `A + (B * C - (D / E ^ F) * G) * H` into its machine-readable postfix equivalent (Reverse Polish Notation). This systemic conversion process inherently relies on strict adherence to established mathematical operator precedence (where Exponentiation `^` > Multiplication/Division `* /` > Addition/Subtraction `+ -`) and respects the overriding associativity dictated by parentheses."},{"type":"subheading","content":"Step-by-Step Conversion Procedure"},{"type":"paragraph","content":"To execute this conversion flawlessly, we systematically evaluate the expression from the deepest nested parentheses outward, mathematically shifting operators to the immediate right of their corresponding operands."},{"type":"paragraph","content":"**Step 1 (Deepest Nested Parentheses):** We focus strictly on the innermost expression `(D / E ^ F)`. \nApplying operator precedence, Exponentiation (`^`) executes before Division (`/`). \nFirst, convert `E ^ F` $\\rightarrow$ `E F ^`. \nNext, integrate the division: `D / (E F ^)` $\\rightarrow$ `D E F ^ /`. \nThe overall expression transforms into: `A + (B * C - [D E F ^ /] * G) * H`."},{"type":"paragraph","content":"**Step 2 (Secondary Parentheses):** We now resolve the broader bracketed expression `(B * C - [D E F ^ /] * G)`. \nHere, Multiplication operations must execute before Subtraction. \nConvert the first multiplication: `B * C` $\\rightarrow$ `B C *`. \nConvert the second multiplication: `[D E F ^ /] * G` $\\rightarrow$ `D E F ^ / G *`. \nNow apply the subtraction to connect them: `[B C *] - [D E F ^ / G *]` $\\rightarrow$ `B C * D E F ^ / G * -`. \nThe overall expression now simplifies to: `A + [B C * D E F ^ / G * -] * H`."},{"type":"paragraph","content":"**Step 3 (Final Global Resolution):** We resolve the remaining operators on the global level: `A + [Complex Term] * H`. \nMultiplication must take precedence over Addition. \nConvert the multiplication: `[Complex Term] * H` $\\rightarrow$ `B C * D E F ^ / G * - H *`. \nFinally, apply the global addition operator: `A + [Result]` $\\rightarrow$ `A B C * D E F ^ / G * - H * +`. \nThis represents the final, correctly formatted postfix expression, ready for stack-based evaluation."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q17","number":17,"marks":4,"tags":["linked-list"],"text":[{"type":"paragraph","content":"Differentiate single linked list and circular linked list. Also write the advantage and disadvantages of circular linked list."}],"answer":{"summary":"A comparative analysis differentiating single linked lists from circular linked lists, outlining the unique topological advantages and computational disadvantages of circular structures.","explanation":[{"type":"heading","content":"Comparative Analysis: Singly vs. Circular Linked Lists"},{"type":"paragraph","content":"Both Singly Linked Lists (SLL) and Circular Linked Lists (CLL) are fundamental, dynamic, node-based linear data structures. However, they diverge significantly in their topological architecture and memory pointer management."},{"type":"subheading","content":"Structural Differentiation"},{"type":"paragraph","content":"In a standard Singly Linked List, data traversal is strictly unidirectional. The logical sequence undeniably terminates at the absolute last node in the chain, which is explicitly identified because its referential `next` pointer is firmly grounded to `NULL`. This physical `NULL` terminator provides a definitive endpoint for algorithmic loops. \nConversely, a Circular Linked List entirely eliminates this endpoint. The structural topology is modified such that the `next` pointer of the final node does not point to `NULL`; instead, it wraps around and explicitly points back to the memory address of the very first `head` node. This creates a continuous, unbroken, cyclic loop where mathematically, every node seamlessly possesses a successor."},{"type":"subheading","content":"Advantages of Circular Linked Lists"},{"type":"list","items":["**Continuous Iteration:** The primary computational advantage is the ability to continuously traverse the entire dataset endlessly without ever encountering a terminal `NULL` pointer and needing to forcefully reset a pointer back to the `head`.","**Universal Accessibility:** Any designated node can effectively act as a functional starting point. A full traversal of all data elements can confidently begin from any arbitrary node in the ring.","**Queue Implementation Efficiency:** They are highly optimal for implementing advanced Circular Queues or complex Round-Robin CPU scheduling algorithms in operating systems, where processes require continuous, cycling resource allocation."]},{"type":"subheading","content":"Disadvantages of Circular Linked Lists"},{"type":"list","items":["**Infinite Loop Risk:** If algorithmic termination conditions are not meticulously defined (e.g., checking if the traversal pointer has returned exactly to the original starting node), naive traversal algorithms will invariably plunge into fatal infinite loops.","**Algorithmic Complexity:** The logic required to execute basic insertion and deletion operations is inherently more complex, as developers must meticulously maintain and carefully update the cyclic back-pointer connecting the tail to the head.","**Reversal Difficulty:** Reversing the topological direction of a circular linked list is significantly more computationally intricate compared to reversing a standard linear singly linked list."]}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q18","number":18,"marks":10,"tags":["graph","mst","kruskal"],"text":[{"type":"paragraph","content":"Define the spanning tree. Write the Kruskal's algorithm to find the minimum cost spanning tree of the following."},{"type":"svg","content":"","alt":"Graph for Kruskal's Algorithm"}],"answer":{"summary":"A comprehensive guide to Spanning Trees and Kruskal's Algorithm, featuring a detailed step-by-step graphical resolution of a Minimum Spanning Tree for a specified weighted graph.","explanation":[{"type":"heading","content":"Spanning Trees and Kruskal's Algorithm"},{"type":"paragraph","content":"In the mathematical field of graph theory, the concept of a spanning tree is foundational for optimizing network designs, routing protocols, and clustering algorithms. Understanding spanning trees and the greedy algorithms utilized to minimize their total cost is a critical competency in advanced data structures."},{"type":"subheading","content":"1. Theoretical Definition of a Spanning Tree"},{"type":"paragraph","content":"Given a connected, undirected graph mathematically denoted as $G = (V, E)$—where $V$ represents the set of all vertices (nodes) and $E$ represents the set of all connecting edges—a Spanning Tree $T = (V, E')$ is rigorously defined as a specific subgraph of $G$ that strictly satisfies three immutable criteria:"},{"type":"list","items":["**Total Vertex Inclusion:** The subgraph $T$ must physically include every single vertex present in the original overarching graph $G$. None can be orphaned or omitted.","**Acyclic Topology:** The subgraph $T$ must be structurally a tree, meaning it is mathematically impossible to find any closed loops or cycles within its edge connections. A traversal from any node to any other node has exactly one unique path.","**Edge Minimization:** Consequently, to satisfy the above two conditions simultaneously, if the original graph $G$ possesses $N$ vertices, every valid spanning tree $T$ must contain exactly $N - 1$ edges."]},{"type":"paragraph","content":"While a single dense graph can theoretically spawn thousands of vastly different valid spanning trees, engineering problems usually demand optimization. In a weighted graph—where every edge is assigned a numerical cost, length, or resistance—the overarching objective is to discover the Minimum Cost Spanning Tree (MST). This is the specific unique spanning tree whose aggregate edge weights sum to the absolute mathematical minimum possible value."},{"type":"subheading","content":"2. Kruskal's Greedy Algorithmic Paradigm"},{"type":"paragraph","content":"Kruskal's algorithm is a highly efficient, greedy algorithmic approach specifically designed to compute the MST of a given weighted graph. A \"greedy\" algorithm makes the locally optimal choice at every discrete stage with the hope of discovering the global optimum. Kruskal's methodology achieves this by sorting edges and iteratively building a forest."},{"type":"paragraph","content":"**Step-by-Step Algorithmic Procedure:**"},{"type":"list","items":["**Step 1 (Edge Sorting):** Extract every single edge from the graph $G$ and rigorously sort them into a sequentially ordered list strictly in ascending order based on their assigned numerical weights. This ensures the algorithm evaluates the cheapest options first.","**Step 2 (Forest Initialization):** Initialize a dynamic \"forest\". Treat every single isolated vertex in $V$ as its own independent, disconnected tree component. If there are $N$ vertices, you start with exactly $N$ isolated trees.","**Step 3 (Greedy Edge Selection):** Iteratively traverse the sorted edge list from cheapest to most expensive. For every candidate edge $(u, v)$ connecting vertex $u$ to vertex $v$, perform a crucial cyclic check.","**Step 4 (Cyclic Validation via Union-Find):** Determine if vertex $u$ and vertex $v$ already belong to the same connected tree component within the forest. If they do, adding this edge would disastrously create a closed cycle, violating the spanning tree definition. Therefore, unequivocally reject and discard the edge.","**Step 5 (Component Merging):** If vertex $u$ and vertex $v$ currently belong to completely separate, disjoint tree components, accept the edge. Add it to the official MST set, and mathematically merge (Union) the two separate tree components into a single, larger connected component.","**Step 6 (Termination Condition):** Continuously repeat Steps 3 through 5. The algorithm definitively terminates the exact moment the MST successfully accumulates exactly $N - 1$ accepted edges. At this precise point, all vertices are guaranteed to be interconnected into a single, unified minimum spanning tree."]},{"type":"subheading","content":"3. Practical Application and Step-by-Step Trace"},{"type":"paragraph","content":"We will now rigorously apply Kruskal's algorithm to the specific provided graph configuration. The graph consists of exactly 6 distinct vertices ($V = \\{A, B, C, D, E, F\\}$) and 9 weighted edges. To form a valid spanning tree, we strictly require $N - 1 = 6 - 1 = 5$ edges."},{"type":"paragraph","content":"**Phase 1: Sorting the Edge List:**"},{"type":"paragraph","content":"We compile and sort all available edges by weight in strict ascending order:"},{"type":"list","items":["1. Edge (B, C) - Weight: 1","2. Edge (A, C) - Weight: 2","3. Edge (D, E) - Weight: 2","4. Edge (E, F) - Weight: 3","5. Edge (A, B) - Weight: 4","6. Edge (B, D) - Weight: 5","7. Edge (D, F) - Weight: 6","8. Edge (C, D) - Weight: 8","9. Edge (C, E) - Weight: 10"]},{"type":"paragraph","content":"**Phase 2: Iterative Greedy Selection:**"},{"type":"paragraph","content":"We systematically evaluate each edge from our sorted list:"},{"type":"list","items":["**Iteration 1:** Evaluate Edge (B, C) [Weight 1]. Vertices B and C are disconnected. **Action:** ACCEPT. Components merge. (Edges in MST: 1)","**Iteration 2:** Evaluate Edge (A, C) [Weight 2]. Vertices A and C are disconnected. **Action:** ACCEPT. Components merge. (Edges in MST: 2)","**Iteration 3:** Evaluate Edge (D, E) [Weight 2]. Vertices D and E are disconnected. **Action:** ACCEPT. Components merge. (Edges in MST: 3)","**Iteration 4:** Evaluate Edge (E, F) [Weight 3]. Vertices E and F are disconnected. **Action:** ACCEPT. Components merge. (Edges in MST: 4)","**Iteration 5:** Evaluate Edge (A, B) [Weight 4]. Vertices A and B are already intimately connected through vertex C (A-C and C-B exist). Adding this edge creates the closed cycle A-C-B-A. **Action:** REJECT.","**Iteration 6:** Evaluate Edge (B, D) [Weight 5]. Vertex B (in the A-B-C component) and vertex D (in the D-E-F component) are completely disconnected. **Action:** ACCEPT. This massive bridge connects the two remaining large sub-components. (Edges in MST: 5)"]},{"type":"subheading","content":"4. Final Synthesis and Verification"},{"type":"paragraph","content":"We have successfully acquired exactly 5 accepted edges. The algorithmic termination condition is satisfied. The process definitively halts."},{"type":"paragraph","content":"The accepted Minimum Spanning Tree encompasses the edges: (B, C), (A, C), (D, E), (E, F), and (B, D). To verify the ultimate optimal cost, we simply aggregate their weights: $1 + 2 + 2 + 3 + 5 = 13$. The total minimum cost of the spanning tree is precisely 13 units."},{"type":"svg","content":"","alt":"Final Minimum Spanning Tree (MST)"}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q19","number":19,"marks":10,"tags":["tree","avl-tree"],"text":[{"type":"paragraph","content":"What is an AVL Tree? Explain the concept of Balancing factor. Create an AVL tree using following sequence: 21, 26, 30, 9, 4, 14, 28, 18, 15, 10, 2, 3, 7"}],"answer":{"summary":"A deep architectural dive into AVL Trees, covering self-balancing mechanisms, Balance Factor mathematics, and a rigorous step-by-step construction of an AVL tree through a sequence of complex rotations.","explanation":[{"type":"heading","content":"AVL Trees: Self-Balancing Binary Search Architecture"},{"type":"paragraph","content":"While standard Binary Search Trees (BSTs) theoretically offer highly efficient $O(\\log n)$ time complexities for critical operations like searching, insertion, and deletion, they harbor a severe architectural vulnerability. If data is inserted in a strictly sorted or highly ordered manner, a standard BST will rapidly degrade into a skewed, linear linked list configuration. In this degraded state, the operational time complexity collapses to a disastrous $O(n)$, completely negating the structural advantage of the tree format. To definitively solve this systemic issue, computer scientists G.M. Adelson-Velsky and E.M. Landis invented the AVL Tree in 1962."},{"type":"subheading","content":"1. Theoretical Definition of an AVL Tree"},{"type":"paragraph","content":"An AVL tree is a rigorously self-balancing Binary Search Tree. It imposes a strict mathematical structural constraint on every single node within its hierarchy: the height difference between any node's left contiguous subtree and its right contiguous subtree can never exceed a magnitude of 1. This singular, powerful rule universally guarantees that the overall tree remains asymptotically balanced at all times, mathematically forcing the tree's maximum depth to remain strictly proportional to $O(\\log n)$. Consequently, all search and modification operations are eternally bound to $O(\\log n)$ worst-case performance."},{"type":"subheading","content":"2. The Mathematics of the Balance Factor"},{"type":"paragraph","content":"To continuously monitor and enforce this structural rule, AVL algorithms rely on calculating a specific metric called the Balance Factor (BF) for every node. The calculation is straightforward: \n$Balance Factor (Node) = Height(Left Subtree) - Height(Right Subtree)$."},{"type":"paragraph","content":"In a structurally healthy AVL tree, the Balance Factor for any node is strictly confined to the permissible set of integers $\\{-1, 0, 1\\}$. \n- $BF = 0$: The node is perfectly balanced; subtrees are equal height.\n- $BF = +1$: The node is slightly left-heavy, but within legal limits.\n- $BF = -1$: The node is slightly right-heavy, but within legal limits."},{"type":"paragraph","content":"The absolute moment an insertion or deletion operation causes any node's Balance Factor to mutate to $+2$ or $-2$, the AVL structural integrity is officially compromised. The tree immediately triggers a corrective sequence of algorithmic \"rotations\" to forcefully restore the legal balance factor constraints."},{"type":"subheading","content":"3. Step-by-Step AVL Tree Construction Trace"},{"type":"paragraph","content":"We will now meticulously construct an AVL tree by sequentially inserting the dataset: `21, 26, 30, 9, 4, 14, 28, 18, 15, 10, 2, 3, 7`. Every insertion must be validated for balance."},{"type":"list","items":["**Insert 21:** Node 21 becomes the root. Tree is balanced.","**Insert 26:** 26 > 21, inserted as right child of 21. Tree is balanced.","**Insert 30:** 30 > 26, inserted as right child of 26. \n**Imbalance Detected:** Node 21 now has $BF = -2$ (Right-Right heavy). \n**Correction:** Execute a **Left Rotation (LL Rotation)** pivoting around 21. Node 26 elevates to become the new root. 21 becomes its left child, 30 remains its right child.","**Insert 9:** 9 < 26, 9 < 21, inserted as left child of 21. Tree is balanced.","**Insert 4:** 4 < 21, 4 < 9, inserted as left child of 9. \n**Imbalance Detected:** Node 21 now has $BF = +2$ (Left-Left heavy). \n**Correction:** Execute a **Right Rotation (RR Rotation)** pivoting around 21. Node 9 elevates. 4 remains left child of 9, 21 becomes right child of 9.","**Insert 14:** 14 < 26, 14 > 9, 14 < 21, inserted as left child of 21. Tree is balanced.","**Insert 28:** 28 > 26, 28 < 30, inserted as left child of 30. Tree is balanced.","**Insert 18:** 18 < 26, 18 > 9, 18 < 21, 18 > 14, inserted as right child of 14. \n**Imbalance Detected:** Node 21 has $BF = +2$ (Left subtree of 21 is heavy, specifically the Right child 14 is heavy $\\rightarrow$ Left-Right case). \n**Correction:** Execute a complex **Left-Right Rotation (LR Rotation)**. First, Left Rotate around 9 (child). Then, Right Rotate around 21 (parent). Node 14 elevates to balance.","**Insert 15:** 15 < 18, inserted as left child of 18. Tree is balanced.","**Insert 10:** 10 < 14, inserted as left child of 14 (right of 9). Tree is balanced.","**Insert 2:** 2 < 4, inserted as left child of 4. Tree is balanced.","**Insert 3:** 3 > 2, inserted as right child of 2. \n**Imbalance Detected:** Node 4 has $BF = +2$ (Left-Right case). \n**Correction:** **LR Rotation**. Left rotate on 2, Right rotate on 4. Node 3 elevates.","**Insert 7:** 7 > 4, inserted as right child of 4. Tree remains perfectly balanced within AVL tolerances."]},{"type":"paragraph","content":"Through this rigorous, continuous application of calculated structural rotations, the tree perpetually defends its $O(\\log n)$ operational efficiency, completely immune to the sequential ordering of the input data."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q20","number":20,"marks":10,"tags":["hashing"],"text":[{"type":"paragraph","content":"What is hashing and collision? Discuss the advantages and disadvantages of hashing over other searching techniques."}],"answer":{"summary":"An extensive analytical review of Hashing architectures, detailing the mathematics of hash functions, the inevitability of collisions, conflict resolution strategies, and a comprehensive comparative analysis of hashing versus traditional search algorithms.","explanation":[{"type":"heading","content":"Hashing: The Pursuit of $O(1)$ Search Efficiency"},{"type":"paragraph","content":"In the vast landscape of data structures, the ultimate holy grail for data retrieval is achieving $O(1)$, or constant time, efficiency. Traditional search methodologies—ranging from linear arrays to sophisticated self-balancing binary trees—inherently require comparative scanning, tethering their performance to the total volume of data ($O(n)$ or $O(\\log n)$). Hashing represents a paradigm shift. It completely abandons the comparative search model in favor of a direct mathematical mapping approach, theoretically allowing instantaneous data retrieval regardless of database size."},{"type":"subheading","content":"1. The Core Mechanics of Hashing"},{"type":"paragraph","content":"Hashing is fundamentally a structural technique utilized to uniquely map large, complex identifier keys (such as strings, database UUIDs, or large integers) directly into the integer indices of a pre-allocated, contiguous memory array, commonly referred to as a Hash Table. This translation is executed by a mathematically deterministic algorithm known as a **Hash Function**, $h(K)$."},{"type":"paragraph","content":"When a record needs to be stored or retrieved, the system feeds the record's unique Key ($K$) into the Hash Function. The function mathematically transforms this key into an integer array index. The system then instantly jumps to that exact memory address to deposit or extract the data. If the hash function calculates perfectly, the search process requires zero comparisons."},{"type":"subheading","content":"2. The Mathematical Inevitability of Collisions"},{"type":"paragraph","content":"While mathematically beautiful in theory, practical hashing suffers from a fundamental constraint grounded in the Pigeonhole Principle. Because the universe of possible identifier keys is virtually infinite, but the physical memory array constituting the Hash Table is strictly finite and relatively small, it is mathematically guaranteed that eventually, the Hash Function will independently map two completely different, distinct keys into the exact same array index. \n\nFor example, $h(Key1) = 45$ and $h(Key2) = 45$. This event is formally defined as a **Collision**."},{"type":"paragraph","content":"A robust hashing system must implement structural strategies to manage and resolve these inevitable collisions. Primary resolution techniques include:"},{"type":"list","items":["**Separate Chaining (Open Hashing):** The hash table array does not store data directly; instead, it stores pointers to secondary Linked Lists. When a collision occurs at an index, the new record is simply appended to the linked list residing at that index.","**Open Addressing (Closed Hashing):** All data is stored directly within the main array. If a target index is already occupied due to a collision, the algorithm systematically probes forward through the array (using Linear Probing, Quadratic Probing, or Double Hashing) until it discovers the next available empty slot."]},{"type":"subheading","content":"3. Comparative Analysis: Advantages over Traditional Searching"},{"type":"paragraph","content":"Hashing offers unparalleled advantages when deployed in appropriate computational environments:"},{"type":"list","items":["**Unmatched Retrieval Speed:** The primary advantage is the theoretical $O(1)$ constant time complexity for insertions, deletions, and lookups. In massive, high-load database systems, hashing vastly outperforms Binary Search ($O(\\log n)$) and Linear Search ($O(n)$).","**Simplicity of Implementation:** Compared to the extreme algorithmic complexity required to balance AVL or Red-Black trees, a basic hash table is architecturally straightforward to code and maintain.","**Cryptographic and Security Applications:** Advanced cryptographic hash functions (like SHA-256) are foundational to cybersecurity, passwords, and blockchain technologies."]},{"type":"subheading","content":"4. Structural Disadvantages and Limitations"},{"type":"paragraph","content":"However, the decision to utilize hashing must weigh severe structural trade-offs:"},{"type":"list","items":["**Total Loss of Data Ordering:** Hashing mathematically scrambles data locations. Therefore, it is completely impossible to perform range queries (e.g., \"find all employees earning between $50k and $60k\"), find minimum/maximum values, or print data in sorted order. Trees are strictly required for these operations.","**Worst-Case Degradation:** If the chosen hash function is poorly designed and clusters data, or if the table exceeds its load factor, collisions cascade. In the absolute worst-case scenario (where every key collides), efficiency collapses to a disastrous $O(n)$, identical to a raw linked list.","**Memory Inefficiency:** Hash tables fundamentally require over-allocation of memory to maintain a low load factor and minimize collisions. A significantly full hash table performs terribly, necessitating expensive, highly disruptive dynamic resizing and complete table rehashing operations."]}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q21","number":21,"marks":10,"tags":["sorting","insertion-sort"],"text":[{"type":"paragraph","content":"Write an algorithm of Insertion sort. Sort the following elements using Insertion sort: 68, 17, 26, 54, 77, 93, 31, 44, 55, 20"}],"answer":{"summary":"A definitive guide to the Insertion Sort algorithm, detailing its operational mechanics, algorithmic code structure, and a comprehensive, step-by-step trace executing the sort on a provided unsorted array.","explanation":[{"type":"heading","content":"Algorithmic Mechanics of Insertion Sort"},{"type":"paragraph","content":"Insertion Sort is a fundamental, comparison-based sorting algorithm that physically mirrors the intuitive human approach to sorting a hand of playing cards. It is an \"in-place\" algorithm, meaning it requires minimal external memory space, and it is highly \"stable,\" guaranteeing that identical duplicate elements will absolutely retain their original relative chronological order. While its overarching $O(n^2)$ time complexity renders it highly inefficient for massive datasets, its near $O(n)$ efficiency on nearly-sorted data and exceptionally low operational overhead make it the undisputed optimal algorithm for sorting very small, localized arrays."},{"type":"subheading","content":"1. Operational Methodology"},{"type":"paragraph","content":"The algorithm operates by conceptually dividing the single array into two distinct logical partitions: a \"sorted\" subarray occupying the left side, and an \"unsorted\" subarray occupying the right. \n\nInitially, the very first element (index 0) is arbitrarily considered the entirety of the sorted subarray. The algorithm then iterates through the remaining unsorted elements one by one. For each unsorted element, it temporarily extracts the value (calling it the \"key\"). It then systematically compares this key against the elements in the sorted left subarray, scanning from right to left. Any sorted element larger than the key is physically shifted one position to the right to create a physical gap. The key is finally inserted into this newly created, perfectly ordered gap."},{"type":"subheading","content":"2. Structural Algorithm"},{"type":"code","language":"text","code":"Algorithm InsertionSort(A, N)\nInput: Array A of N elements\nOutput: Array A sorted in ascending order\n\n1. FOR i = 1 TO N - 1 DO\n2. key = A[i] // Extract the first unsorted element\n3. j = i - 1 // Set pointer to the end of the sorted subarray\n4. \n5. // Shift elements of the sorted subarray that are greater than the key\n6. WHILE (j >= 0 AND A[j] > key) DO\n7. A[j + 1] = A[j] // Shift element right\n8. j = j - 1 // Move pointer left\n9. END WHILE\n10. \n11. // Insert the key into its correct sorted position\n12. A[j + 1] = key\n13. END FOR"},{"type":"subheading","content":"3. Step-by-Step Execution Trace"},{"type":"paragraph","content":"We will now rigorously trace the execution of this algorithm on the specifically provided array sequence: `[68, 17, 26, 54, 77, 93, 31, 44, 55, 20]`."},{"type":"list","items":["**Initialization:** The array is `[68 | 17, 26, 54, 77, 93, 31, 44, 55, 20]`. The pipe `|` denotes the conceptual boundary. `68` is considered sorted.","**Pass 1 (i=1, key=17):** Compare `17` with `68`. Since `68 > 17`, shift `68` to the right. Insert `17`. \nArray becomes: `[17, 68 | 26, 54, 77, 93, 31, 44, 55, 20]`","**Pass 2 (i=2, key=26):** Compare `26` with `68`. Shift `68`. Compare `26` with `17`. No shift. Insert `26`. \nArray becomes: `[17, 26, 68 | 54, 77, 93, 31, 44, 55, 20]`","**Pass 3 (i=3, key=54):** Compare `54` with `68`. Shift `68`. Compare `54` with `26`. No shift. Insert `54`. \nArray becomes: `[17, 26, 54, 68 | 77, 93, 31, 44, 55, 20]`","**Pass 4 (i=4, key=77):** Compare `77` with `68`. No shift needed. The element is already in place. \nArray becomes: `[17, 26, 54, 68, 77 | 93, 31, 44, 55, 20]`","**Pass 5 (i=5, key=93):** Compare `93` with `77`. No shift needed. \nArray becomes: `[17, 26, 54, 68, 77, 93 | 31, 44, 55, 20]`","**Pass 6 (i=6, key=31):** This requires extensive shifting. Compare `31` with 93, 77, 68, 54. Shift all of them to the right. Compare with `26`. No shift. Insert `31`. \nArray becomes: `[17, 26, 31, 54, 68, 77, 93 | 44, 55, 20]`","**Pass 7 (i=7, key=44):** Shift 93, 77, 68, 54. Insert `44`. \nArray becomes: `[17, 26, 31, 44, 54, 68, 77, 93 | 55, 20]`","**Pass 8 (i=8, key=55):** Shift 93, 77, 68. Insert `55`. \nArray becomes: `[17, 26, 31, 44, 54, 55, 68, 77, 93 | 20]`","**Pass 9 (i=9, key=20):** Shift 93, 77, 68, 55, 54, 44, 31, 26. Insert `20` immediately after `17`. \nArray becomes: `[17, 20, 26, 31, 44, 54, 55, 68, 77, 93 | ]`"]},{"type":"paragraph","content":"The primary loop terminates as the unsorted partition is now empty. The algorithm concludes, successfully yielding the fully sorted array: `[17, 20, 26, 31, 44, 54, 55, 68, 77, 93]`."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2024-q22","number":22,"marks":10,"tags":["linked-list","doubly-linked-list"],"text":[{"type":"paragraph","content":"Write down the algorithm for following operations of doubly linked list:"},{"type":"paragraph","content":"a) Insertion of a node in the middle location."},{"type":"paragraph","content":"b) Delete a node from last location."}],"answer":{"summary":"A highly structured algorithmic breakdown of Doubly Linked List mechanics, specifically detailing the precise pointer manipulation required for middle-insertion and tail-deletion operations.","explanation":[{"type":"heading","content":"Pointer Dynamics in Doubly Linked Lists"},{"type":"paragraph","content":"A Doubly Linked List (DLL) is a highly versatile, bi-directional linear data structure. Unlike a standard Singly Linked List which restricts traversal strictly to a forward trajectory, every node within a DLL is architecturally fortified with three distinct internal components: a data payload field, a forward-pointing reference (`next`) linking to the subsequent node, and crucially, a backward-pointing reference (`prev`) linking directly to the antecedent node. This dual-pointer architecture vastly accelerates reverse traversals and highly specific deletion operations, albeit at the expense of increased memory consumption and significantly more complex pointer reassignment logic during list modifications."},{"type":"subheading","content":"Algorithm A: Insertion of a Node in a Middle Location"},{"type":"paragraph","content":"Inserting a new node into the interior of a DLL requires surgical precision. We must effectively sever an existing link between two adjacent nodes and seamlessly splice the new node into the gap, requiring the updating of four independent pointer references."},{"type":"paragraph","content":"**Pre-conditions:** We possess a pointer to the `head` of the list, the specific integer `position` where insertion is desired, and the `data` payload."},{"type":"code","language":"text","code":"Algorithm DLL_Insert_Middle(head, position, data)\n\n1. // Memory Allocation and Initialization\n Allocate memory for newNode\n newNode.data = data\n newNode.prev = NULL\n newNode.next = NULL\n\n2. // Traversal to Target Location\n Set temp = head\n Set counter = 1\n \n // Traverse until temp points to the node CURRENTLY at (position - 1)\n WHILE (counter < position - 1 AND temp != NULL) DO\n temp = temp.next\n counter = counter + 1\n END WHILE\n\n3. // Safety check for out-of-bounds\n IF (temp == NULL) THEN\n PRINT \"Position out of bounds.\"\n RETURN\n END IF\n\n4. // Pointer Reassignment and Splicing\n // Step A: Connect newNode forward to the right-side node\n newNode.next = temp.next\n \n // Step B: Connect right-side node backward to newNode (if it exists)\n IF (temp.next != NULL) THEN\n temp.next.prev = newNode\n END IF\n \n // Step C: Connect temp forward to newNode\n temp.next = newNode\n \n // Step D: Connect newNode backward to temp\n newNode.prev = temp\n\n5. END Algorithm"},{"type":"subheading","content":"Algorithm B: Deletion of a Node from the Last Location"},{"type":"paragraph","content":"Deleting the terminal tail node of a DLL is relatively straightforward but requires careful edge-case handling to ensure the overarching `head` pointer is correctly managed if the list is completely emptied by the operation."},{"type":"paragraph","content":"**Pre-conditions:** We possess a pointer to the `head` of the list."},{"type":"code","language":"text","code":"Algorithm DLL_Delete_Last(head)\n\n1. // Edge Case 1: Empty List\n IF (head == NULL) THEN\n PRINT \"List is already empty. Underflow Error.\"\n RETURN\n END IF\n\n2. // Edge Case 2: Only One Node Exists\n IF (head.next == NULL) THEN\n Free memory of head\n head = NULL\n PRINT \"Deleted the only node. List is now empty.\"\n RETURN\n END IF\n\n3. // Traversal to the Absolute End\n Set temp = head\n \n // Traverse until temp points to the absolute last node\n WHILE (temp.next != NULL) DO\n temp = temp.next\n END WHILE\n\n4. // Disconnection and Cleanup\n // Sever the forward link of the second-to-last node\n temp.prev.next = NULL\n \n // Free the memory of the extracted tail node\n Free memory of temp\n\n5. END Algorithm"},{"type":"paragraph","content":"By strictly adhering to these procedural pointer adjustments, the structural integrity and bi-directional traversal capabilities of the Doubly Linked List are perfectly preserved across all dynamic modifications."}]}}]},{"id":"rtu-cs-y2-s3-data-structures-paper-2023","title":"Data Structures and Algorithms — Semester 3 (2023)","subjectSlug":"data-structures","subjectName":"Data Structures","universitySlug":"rtu","branchSlug":"computer-science","year":2,"semester":3,"examYear":2023,"paperCode":"3E1202","questions":[{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q1","number":1,"marks":2,"tags":["stack"],"text":[{"type":"paragraph","content":"How stack is represented using dynamic array? Explain with example."}],"answer":{"summary":"A dynamic array stack automatically resizes its underlying contiguous memory block when its capacity is fully exhausted.","explanation":[{"type":"paragraph","content":"A dynamic array stack is initialized with a fixed capacity. When `push()` operations exceed this capacity, the system automatically allocates a new, larger array (typically double the size), meticulously copies over all existing elements, and subsequently frees the old memory. For example, in C++, `std::vector` effortlessly handles this dynamic resizing underlying the stack logic."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q2","number":2,"marks":2,"tags":["stack"],"text":[{"type":"paragraph","content":"Identify the applications of stack."}],"answer":{"summary":"Stacks are utilized for function call tracking, arithmetic expression evaluation, and executing algorithmic backtracking logic.","explanation":[{"type":"paragraph","content":"Primary applications of the stack data structure include meticulously managing nested function calls and their local variables within the system Call Stack, parsing and algorithmically evaluating complex mathematical expressions (like infix to postfix conversions), and driving recursive backtracking algorithms such as Depth First Search (DFS) in complex graphs."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q3","number":3,"marks":2,"tags":["linked-list","array"],"text":[{"type":"paragraph","content":"Elaborate the disadvantages of Linked List over Arrays."}],"answer":{"summary":"Linked lists suffer from high memory overhead per node and the complete inability to perform $O(1)$ random access.","explanation":[{"type":"paragraph","content":"The primary disadvantages of a Linked List compared to an Array include the severe lack of direct random access (forcing inefficient $O(n)$ sequential traversals to reach specific elements), and significantly higher memory overhead because every single node must definitively allocate extra structural memory for its referential pointers."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q4","number":4,"marks":2,"tags":["queue","circular-queue"],"text":[{"type":"paragraph","content":"Justify how circular queue is different from normal queue."}],"answer":{"summary":"A circular queue mathematically connects its absolute end back to its beginning to completely eliminate wasted, empty memory spaces.","explanation":[{"type":"paragraph","content":"In a standard linear queue, once the `rear` pointer reaches the array boundary, no new elements can be inserted even if empty spaces exist at the front due to prior dequeues. A Circular Queue elegantly solves this by using modulo arithmetic to conceptually link the last array index directly back to the first, actively recycling freed memory."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q5","number":5,"marks":2,"tags":["search"],"text":[{"type":"paragraph","content":"Differentiate between sequential and binary search."}],"answer":{"summary":"Sequential search scans sequentially $O(n)$, while binary search optimally halves a strictly sorted dataset in $O(\\log n)$ time.","explanation":[{"type":"paragraph","content":"Sequential (Linear) Search blindly checks every single element one by one from the beginning, requiring an inefficient $O(n)$ time complexity, but inherently works on completely unsorted data. Binary Search requires a strictly pre-sorted dataset, but achieves exceptional $O(\\log n)$ efficiency by repeatedly comparing the target to the middle element and immediately discarding half the remaining search space."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q6","number":6,"marks":2,"tags":["tree","bst"],"text":[{"type":"paragraph","content":"Illustrate different traversal techniques used in binary search tree."}],"answer":{"summary":"Binary Search Trees utilize standard depth-first traversals: In-order, Pre-order, and Post-order to systematically visit nodes.","explanation":[{"type":"paragraph","content":"A Binary Search Tree (BST) is systematically explored using three primary depth-first traversal techniques: **In-order** (Left, Root, Right), which crucially prints the nodes in strict ascending sorted order; **Pre-order** (Root, Left, Right), highly useful for perfectly cloning or copying the tree; and **Post-order** (Left, Right, Root), typically used for safely deleting the tree from the leaves upward."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q7","number":7,"marks":2,"tags":["sorting","complexity"],"text":[{"type":"paragraph","content":"List out best, average and worst case complexity of merge and quick sort."}],"answer":{"summary":"Merge Sort guarantees $O(n \\log n)$, while Quick Sort degrades to $O(n^2)$ strictly in its worst-case scenario.","explanation":[{"type":"paragraph","content":"Merge Sort provides exceptional algorithmic stability, operating in strictly $O(n \\log n)$ time complexity across its Best, Average, and Worst cases. Quick Sort performs highly efficiently at $O(n \\log n)$ in its Best and Average cases, but severely degrades to a disastrous $O(n^2)$ Worst-case complexity if the selected pivot is consistently the absolute smallest or largest element."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q8","number":8,"marks":2,"tags":["tree","avl-tree"],"text":[{"type":"paragraph","content":"Examine the relationship between number of nodes and height of AVL tree."}],"answer":{"summary":"AVL trees enforce a strict logarithmic mathematical relationship between their total node count and maximum depth.","explanation":[{"type":"paragraph","content":"Due to its rigorous self-balancing architectural constraints, an AVL tree mathematically guarantees that its maximum height $h$ is strictly bounded logarithmically relative to its total number of constituent nodes $N$. The absolute worst-case (maximum possible) height for an AVL tree with $N$ nodes is mathematically approximated and strictly bounded by $h \\approx 1.44 \\log_2(N)$."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q9","number":9,"marks":2,"tags":["graph"],"text":[{"type":"paragraph","content":"Determine advantages and disadvantages of adjacent matrix representation for graphs."}],"answer":{"summary":"Adjacency matrices provide instantaneous $O(1)$ edge lookups but suffer from extreme $O(V^2)$ memory waste for sparse graphs.","explanation":[{"type":"paragraph","content":"An Adjacency Matrix offers the supreme advantage of instantaneous $O(1)$ time complexity for determining if an edge exists between any two specific vertices. However, its primary, often fatal disadvantage is its extreme $O(V^2)$ memory space consumption, which leads to massive memory waste (storing mostly zeroes) when structurally representing highly sparse graphs with very few connecting edges."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q10","number":10,"marks":2,"tags":["hashing"],"text":[{"type":"paragraph","content":"Explain how quadratic probing is done."}],"answer":{"summary":"Quadratic probing resolves hash collisions by probing forward in progressively larger, quadratic jump intervals.","explanation":[{"type":"paragraph","content":"Quadratic probing is a sophisticated open addressing collision resolution strategy. When a primary collision inevitably occurs at hash index $h(k)$, the algorithm does not simply check the immediate next slot. Instead, it systematically probes forward using a quadratic mathematical polynomial sequence: $(h(k) + 1^2) \\pmod N$, then $(h(k) + 2^2) \\pmod N$, then $(h(k) + 3^2) \\pmod N$, effectively eliminating primary clustering issues."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q11","number":11,"marks":4,"tags":["stack","postfix"],"text":[{"type":"paragraph","content":"Convert the following infix expression into postfix expression:"},{"type":"paragraph","content":"A + B - (C + D) / E * F - (G + H) / I"}],"answer":{"summary":"A step-by-step algorithmic conversion of a complex infix mathematical expression containing multiple parenthetical groupings into Reverse Polish Notation (Postfix).","explanation":[{"type":"heading","content":"Infix to Postfix Algorithmic Conversion"},{"type":"paragraph","content":"The problem demands the conversion of the specific infix expression `A + B - (C + D) / E * F - (G + H) / I` into postfix notation. We strictly adhere to standard mathematical operator precedence (Multiplication/Division `* /` > Addition/Subtraction `+ -`) and left-to-right associativity."},{"type":"subheading","content":"Step-by-Step Conversion Trace"},{"type":"paragraph","content":"**Step 1 (Parenthetical Resolution):** We immediately resolve the deepest, explicitly bracketed sub-expressions first to establish baseline terms."},{"type":"paragraph","content":"First bracket: `(C + D)` mathematically converts to `C D +`."},{"type":"paragraph","content":"Second bracket: `(G + H)` mathematically converts to `G H +`."},{"type":"paragraph","content":"The overall expression temporarily simplifies to: `A + B - [C D +] / E * F - [G H +] / I`"},{"type":"paragraph","content":"**Step 2 (Multiplication and Division - Left to Right):** We now scan the entire simplified expression strictly from left to right, hunting exclusively for the higher precedence `/` and `*` operators."},{"type":"paragraph","content":"Found division: `[C D +] / E`. The operator shifts to the right, yielding `C D + E /`."},{"type":"paragraph","content":"The expression is now: `A + B - [C D + E /] * F - [G H +] / I`"},{"type":"paragraph","content":"Continuing the scan, we find multiplication involving the previous result: `[C D + E /] * F`. This converts to `C D + E / F *`."},{"type":"paragraph","content":"The expression is now: `A + B - [C D + E / F *] - [G H +] / I`"},{"type":"paragraph","content":"Continuing the scan, we find the final division: `[G H +] / I`. This converts to `G H + I /`."},{"type":"paragraph","content":"The expression is now fully devoid of high-precedence operators: `A + B - [C D + E / F *] - [G H + I /]`"},{"type":"paragraph","content":"**Step 3 (Addition and Subtraction - Left to Right):** Finally, we resolve the remaining `+` and `-` operators, strictly adhering to left-to-right processing."},{"type":"paragraph","content":"First, the leading addition: `A + B` converts to `A B +`."},{"type":"paragraph","content":"The expression is: `[A B +] - [C D + E / F *] - [G H + I /]`"},{"type":"paragraph","content":"Second, the first subtraction: `[A B +] - [C D + E / F *]` converts to `A B + C D + E / F * -`."},{"type":"paragraph","content":"The expression is: `[A B + C D + E / F * -] - [G H + I /]`"},{"type":"paragraph","content":"Third, the final, global subtraction: `[...Left Term...] - [G H + I /]` converts to `A B + C D + E / F * - G H + I / -`."},{"type":"paragraph","content":"The definitive, syntactically correct Postfix expression is: **`A B + C D + E / F * - G H + I / -`**"}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q12","number":12,"marks":4,"tags":["tree","bst"],"text":[{"type":"paragraph","content":"Consider the preorder of a BST: 20, 5, 3, 4, 10, 15, 30, 25, 40"},{"type":"paragraph","content":"What will be the post-order?"}],"answer":{"summary":"A logical deduction reconstructing a Binary Search Tree purely from its Pre-order traversal, subsequently generating the required Post-order sequence.","explanation":[{"type":"heading","content":"Reconstructing a BST from Pre-order Traversal"},{"type":"paragraph","content":"The problem provides the explicit Pre-order traversal of a Binary Search Tree (BST): `20, 5, 3, 4, 10, 15, 30, 25, 40` and requests the corresponding Post-order traversal. Crucially, because this is explicitly stated to be a **Binary Search Tree (BST)**, we possess a hidden, secondary piece of information: the In-order traversal of any valid BST is mathematically guaranteed to be the strictly ascending, sorted order of its constituent nodes."},{"type":"subheading","content":"Step 1: Ascertaining the In-order Sequence"},{"type":"paragraph","content":"By extracting the nodes from the provided Pre-order list and simply numerically sorting them, we immediately derive the required In-order sequence."},{"type":"paragraph","content":"In-order (Sorted): `3, 4, 5, 10, 15, 20, 25, 30, 40`"},{"type":"paragraph","content":"Pre-order (Given): `20, 5, 3, 4, 10, 15, 30, 25, 40`"},{"type":"subheading","content":"Step 2: Logical Tree Reconstruction"},{"type":"paragraph","content":"Using the Pre-order sequence to identify roots, and the In-order sequence to define spatial boundaries, we reconstruct the physical tree topology:"},{"type":"list","items":["Root is `20`. Left subtree elements: `{3, 4, 5, 10, 15}`. Right subtree elements: `{25, 30, 40}`.","Left Subtree (`5, 3, 4, 10, 15`): Root is `5`. Its left child is `3`. The right child of `3` is `4`. The right child of `5` is `10`. The right child of `10` is `15`.","Right Subtree (`30, 25, 40`): Root is `30`. Its left child is `25`. Its right child is `40`."]},{"type":"subheading","content":"Step 3: Generating the Post-order Sequence"},{"type":"paragraph","content":"With the tree perfectly reconstructed, we can now execute a strict Post-order traversal (Left, Right, Root)."},{"type":"paragraph","content":"Visiting the left subtree of 20 (rooted at 5): Leftmost is 3, but it has a right child 4. So we visit 4, then 3. Then right subtree of 5 (rooted at 10): Left is empty, right is 15. So we visit 15, then 10. Then the root 5. Sequence so far: `4, 3, 15, 10, 5`."},{"type":"paragraph","content":"Visiting the right subtree of 20 (rooted at 30): Left child is 25. Right child is 40. Root is 30. Sequence so far: `25, 40, 30`."},{"type":"paragraph","content":"Finally, visit the absolute root: `20`."},{"type":"paragraph","content":"The definitively calculated, complete Post-order sequence is: **`4, 3, 15, 10, 5, 25, 40, 30, 20`**."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q13","number":13,"marks":4,"tags":["queue"],"text":[{"type":"paragraph","content":"Write an algorithm to enqueue and dequeue an element in a queue."}],"answer":{"summary":"A detailed algorithmic presentation of the Enqueue and Dequeue operational mechanics for a standard linear queue data structure implemented via an array.","explanation":[{"type":"heading","content":"Queue Operations: Enqueue and Dequeue"},{"type":"paragraph","content":"A Queue is a fundamental linear data structure operating strictly on the First-In-First-Out (FIFO) principle. Elements are exclusively added at one terminal end (the `REAR`) and exclusively removed from the opposite terminal end (the `FRONT`). Assuming the queue is implemented using a static, zero-indexed array `Q` with a maximum capacity `MAX`, we require two tracking pointer variables: `FRONT` (initially -1) and `REAR` (initially -1)."},{"type":"subheading","content":"1. The Enqueue Algorithm (Insertion)"},{"type":"paragraph","content":"The Enqueue operation inserts a newly provided data element `VAL` at the absolute rear of the queue structure. The algorithm must inherently protect against \"Overflow\" scenarios where the array is entirely full."},{"type":"code","language":"text","code":"Algorithm ENQUEUE(Q, VAL, MAX, FRONT, REAR)\n\n1. // Step 1: Strict Overflow Verification\n IF (REAR == MAX - 1) THEN\n PRINT \"QUEUE OVERFLOW ERROR: Cannot insert element\"\n RETURN\n END IF\n\n2. // Step 2: Handle Initial Insertion Edge Case\n IF (FRONT == -1 AND REAR == -1) THEN\n FRONT = 0\n REAR = 0\n ELSE\n // Step 3: Increment the REAR pointer to the next available slot\n REAR = REAR + 1\n END IF\n\n3. // Step 4: Physically insert the value into the array\n Q[REAR] = VAL\n PRINT \"Successfully inserted: \" + VAL\n\n4. END Algorithm"},{"type":"subheading","content":"2. The Dequeue Algorithm (Deletion)"},{"type":"paragraph","content":"The Dequeue operation permanently extracts and returns the chronologically oldest data element currently residing at the front of the queue structure. The algorithm must vigorously protect against \"Underflow\" scenarios where the queue is entirely empty."},{"type":"code","language":"text","code":"Algorithm DEQUEUE(Q, FRONT, REAR)\n\n1. // Step 1: Strict Underflow Verification\n IF (FRONT == -1 OR FRONT > REAR) THEN\n PRINT \"QUEUE UNDERFLOW ERROR: Queue is empty\"\n RETURN NULL\n END IF\n\n2. // Step 2: Extract the targeted value from the front\n Set extracted_val = Q[FRONT]\n\n3. // Step 3: Advance the FRONT pointer logically removing the element\n FRONT = FRONT + 1\n\n4. // Step 4: Reset state if the queue has been entirely emptied\n IF (FRONT > REAR) THEN\n FRONT = -1\n REAR = -1\n END IF\n\n5. // Step 5: Return the extracted payload\n RETURN extracted_val\n\n6. END Algorithm"}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q14","number":14,"marks":4,"tags":["sorting","quick-sort"],"text":[{"type":"paragraph","content":"Sort the following elements using quick sort: 28, 5, 16, 36, 11, 19, 25"}],"answer":{"summary":"A meticulous, step-by-step algorithmic trace executing the Quick Sort divide-and-conquer methodology on a designated array sequence.","explanation":[{"type":"heading","content":"Quick Sort Execution Trace"},{"type":"paragraph","content":"Quick Sort is a highly efficient, recursively driven divide-and-conquer algorithm. Its core mechanic revolves around selecting a \"pivot\" element from the array, and physically partitioning all other elements such that values smaller than the pivot reside to its left, and values larger reside to its right. This specific partitioning action guarantees that the chosen pivot is placed in its absolute, final, correct sorted location. The array provided is: `[28, 5, 16, 36, 11, 19, 25]`."},{"type":"subheading","content":"Initial Partitioning (Pass 1)"},{"type":"paragraph","content":"We conventionally select the absolute first element as our primary pivot. \n**Pivot:** `28`. \nWe initialize two tracking pointers: `left` scanning forward from index 1, and `right` scanning backward from the final index."},{"type":"paragraph","content":"The algorithmic goal is to locate an element `> 28` from the left, and an element `< 28` from the right, and violently swap them. \n`left` scans forward: 5, 16... halts at `36` (because 36 > 28). \n`right` scans backward: halts immediately at `25` (because 25 < 28). \n**Swap Condition Met:** We physically swap the values at the `left` and `right` pointers: `36` and `25`."},{"type":"paragraph","content":"Array becomes: `[28 | 5, 16, 25, 11, 19, 36]`. \nWe resume scanning. \n`left` moves forward from 25: 11, 19, 36. Halts at `36`. \n`right` moves backward from 36: 19. Halts at `19`. \nAt this exact juncture, the `right` pointer has structurally crossed over the `left` pointer (`right < left`). This physical crossing signifies the definitive end of the current partitioning phase. \nWe conclude by swapping the original Pivot (`28`) with the element currently residing at the `right` pointer (`19`)."},{"type":"paragraph","content":"Array becomes: `[19, 5, 16, 25, 11] | 28 | [36]`."},{"type":"paragraph","content":"The pivot `28` is now permanently locked in its correct sorted position. We now recursively apply the exact same algorithm to the newly created left and right subarrays."},{"type":"subheading","content":"Recursive Sorting of Subarrays"},{"type":"paragraph","content":"**Solving the Left Subarray: `[19, 5, 16, 25, 11]`** \nNew Pivot: `19`. \n`left` halts at `25` (>19). `right` halts at `11` (<19). Swap them. \nArray: `[19 | 5, 16, 11, 25]`. \n`left` halts at `25`. `right` halts at `11`. Pointers mathematically cross. \nSwap Pivot `19` with `right` pointer `11`. \nResult: `[11, 5, 16] | 19 | [25]`. `19` is locked."},{"type":"paragraph","content":"**Solving Sub-Subarray: `[11, 5, 16]`** \nNew Pivot: `11`. \n`left` halts at `16` (>11). `right` halts at `5` (<11). Pointers immediately cross. \nSwap Pivot `11` with `right` pointer `5`. \nResult: `[5] | 11 | [16]`. All elements single, thus sorted."},{"type":"paragraph","content":"The overall recursively sorted array flawlessly merges back together, yielding the final ordered sequence: `[5, 11, 16, 19, 25, 28, 36]`."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q15","number":15,"marks":4,"tags":["graph","dfs"],"text":[{"type":"paragraph","content":"Write an algorithm for DFS traversal."}],"answer":{"summary":"A detailed algorithmic outlining of the Depth-First Search (DFS) graph traversal methodology utilizing a stack-based structure and a visited array.","explanation":[{"type":"heading","content":"Depth-First Search (DFS) Traversal Algorithm"},{"type":"paragraph","content":"Depth-First Search (DFS) is a fundamental, aggressive graph traversal algorithm. Its core methodology involves selecting an arbitrary starting vertex and immediately plunging as deeply as physically possible along each branching path before finally hitting a dead end and being forced to backtrack. This specific behavior is inherently Last-In-First-Out, meaning DFS requires a Stack data structure (either explicitly managed in memory, or implicitly utilizing the system call stack via mathematical recursion) to actively track the traversal path and facilitate backtracking. It also strictly requires an auxiliary boolean array to track previously visited vertices to prevent infinite cyclic loops."},{"type":"subheading","content":"Explicit Stack-Based Implementation Algorithm"},{"type":"code","language":"text","code":"Algorithm DFS_Iterative(Graph, start_vertex, Total_Vertices)\n\n1. // Initialization Phase\n Initialize an empty Stack data structure named S.\n Initialize a Boolean array VISITED of size Total_Vertices, setting all indices to FALSE.\n \n2. // Bootstrap the Traversal\n Push start_vertex onto Stack S.\n Set VISITED[start_vertex] = TRUE.\n PRINT start_vertex\n \n3. // Core Traversal Loop\n WHILE (Stack S is NOT empty) DO\n Set current_vertex = PEEK top element of Stack S.\n Set found_unvisited_neighbor = FALSE.\n \n // Edge Traversal\n FOR EACH neighbor OF current_vertex in Graph DO\n IF (VISITED[neighbor] == FALSE) THEN\n // Deep Dive: Mark, Print, and Push to continue down this path\n VISITED[neighbor] = TRUE\n PRINT neighbor\n PUSH neighbor onto Stack S\n Set found_unvisited_neighbor = TRUE\n BREAK out of the FOR loop immediately (Go deeper!)\n END IF\n END FOR\n \n // Backtracking Protocol\n IF (found_unvisited_neighbor == FALSE) THEN\n // Dead end reached. Backtrack by removing the node.\n POP element from Stack S\n END IF\n \n END WHILE\n \n4. END Algorithm"},{"type":"paragraph","content":"This iterative algorithm guarantees that every reachable vertex in the connected component is systematically visited and processed exactly once, yielding an optimal $O(V + E)$ time complexity."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q16","number":16,"marks":4,"tags":["graph","mst"],"text":[{"type":"paragraph","content":"What is a MST? Differentiate between Kruskal and Prim's algorithm with their time complexity."}],"answer":{"summary":"A definitive comparison differentiating Kruskal's edge-based greedy algorithm from Prim's vertex-based algorithm for finding Minimum Spanning Trees.","explanation":[{"type":"heading","content":"Minimum Spanning Trees: Kruskal vs. Prim"},{"type":"paragraph","content":"A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a strict acyclic subgraph that systematically connects all constituent vertices together while mathematically ensuring the aggregate total of its edge weights is the absolute minimum possible."},{"type":"subheading","content":"Differentiating the Algorithmic Approaches"},{"type":"paragraph","content":"Both Kruskal's and Prim's algorithms employ greedy logic to construct an MST, but their fundamental architectural approaches to graph exploration are entirely distinct:"},{"type":"list","items":["**Kruskal's Algorithm (Edge-Centric):** Kruskal's algorithm fundamentally views the graph strictly as a vast collection of independent edges. It begins by aggressively sorting all edges globally by weight. It then iteratively builds a \"forest\" of disconnected trees by greedily selecting the absolute cheapest edge anywhere in the graph, merging disjoint trees together, provided the new edge does not introduce a structural cycle (managed via a Union-Find data structure). It is highly optimal for **sparse graphs**.","**Prim's Algorithm (Vertex-Centric):** Prim's algorithm operates completely differently. It selects a single, arbitrary starting vertex and views the MST as a single, continuously expanding connected entity. It iteratively expands this unified tree by scanning all edges that connect the *current* tree to any unvisited vertex, and greedily pulling in the absolutely cheapest connecting edge. It is highly optimal for dense, highly connected graphs."]},{"type":"subheading","content":"Time Complexity Analysis"},{"type":"paragraph","content":"The architectural differences lead to distinct computational time complexities based heavily on their underlying implementation structures:"},{"type":"list","items":["**Kruskal's Complexity:** The dominating factor is the initial global sorting of all $E$ edges. Utilizing efficient algorithms like Merge Sort, this strictly bounds the overall time complexity to $O(E \\log E)$ or equivalently $O(E \\log V)$.","**Prim's Complexity:** The efficiency of Prim's relies entirely on the data structure managing the expanding frontier. Using a simple Adjacency Matrix yields a sluggish $O(V^2)$. However, utilizing an Adjacency List paired with a highly optimized Binary Min-Heap (Priority Queue) drastically reduces the time complexity to an exceptionally fast $O(E \\log V)$, making it superior for dense networks where $E \\approx V^2$."]}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q17","number":17,"marks":4,"tags":["linked-list","doubly-linked-list"],"text":[{"type":"paragraph","content":"Explain the algorithm for deleting an element from doubly linked list."}],"answer":{"summary":"A step-by-step algorithmic breakdown for physically deleting a specific, targeted element from anywhere within a Doubly Linked List structure.","explanation":[{"type":"heading","content":"Element Deletion in Doubly Linked Lists"},{"type":"paragraph","content":"Deleting a specific node containing a targeted value from a Doubly Linked List (DLL) is structurally complex. The algorithm must first execute a linear search to locate the specific node, and subsequently execute precise pointer reassignments to cleanly decouple the target node from its surrounding neighbors without severing the overarching list continuity."},{"type":"subheading","content":"Algorithmic Procedure"},{"type":"code","language":"text","code":"Algorithm DLL_Delete_Specific_Element(head, target_value)\n\n1. // Step 1: Initial Empty Verification\n IF (head == NULL) THEN\n PRINT \"Error: List is currently empty. Deletion failed.\"\n RETURN\n END IF\n\n2. // Step 2: Linear Traversal to Target\n Set temp = head\n WHILE (temp != NULL AND temp.data != target_value) DO\n temp = temp.next\n END WHILE\n\n3. // Step 3: Verification of Existence\n IF (temp == NULL) THEN\n PRINT \"Error: Target element not found in the list.\"\n RETURN\n END IF\n\n4. // Step 4: Edge Case A - Deleting the singular Head Node\n IF (temp == head) THEN\n head = temp.next // Advance head\n IF (head != NULL) THEN\n head.prev = NULL // Clean backward pointer\n END IF\n Free memory of temp\n RETURN\n END IF\n\n5. // Step 5: Core Pointer Decoupling Logic\n // Sever the forward link from the preceding node\n temp.prev.next = temp.next\n \n // Edge Case B - Ensure we are not deleting the final Tail Node\n IF (temp.next != NULL) THEN\n // Sever the backward link from the succeeding node\n temp.next.prev = temp.prev\n END IF\n\n6. // Step 6: Memory Cleanup\n Free memory of temp\n PRINT \"Element deleted successfully.\"\n\n7. END Algorithm"},{"type":"paragraph","content":"This algorithm rigorously handles all topological cases, including deleting the absolute front node, the absolute tail node, or any interior node, ensuring memory safety."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q18","number":18,"marks":10,"tags":["sorting","radix-sort"],"text":[{"type":"paragraph","content":"Examine each step involved with Radix sort to sort the given array - 329, 457, 657, 839, 436, 720, 355"}],"answer":{"summary":"A detailed step-by-step trace of the Radix Sort algorithm, demonstrating its non-comparative bucket-based sorting methodology utilizing stable Counting Sort across the ones, tens, and hundreds digit places.","explanation":[{"type":"heading","content":"Radix Sort: Non-Comparative Bucket Sorting"},{"type":"paragraph","content":"Radix Sort fundamentally diverges from traditional comparative sorting methodologies (like Quick Sort or Merge Sort). Instead of mathematically comparing the magnitude of entire values against each other, Radix Sort aggressively exploits the structural, positional nature of number systems. It processes the individual digits of every number sequentially, distributing them into corresponding \"buckets\" (0-9) based on their specific digit value at a given position. Crucially, to maintain overall sequence integrity, Radix Sort rigorously mandates the use of a mathematically stable subroutine sorting algorithm—almost universally Counting Sort—for processing each individual digit column."},{"type":"subheading","content":"1. Algorithmic Overview and Setup"},{"type":"paragraph","content":"The given unsorted input array sequence is: `[329, 457, 657, 839, 436, 720, 355]`. \nBefore initiating the sorting loops, the algorithm must precisely determine the maximum value residing within the array to deduce the maximum number of structural digits required. The maximum value here is `839`, which consists of exactly three digits ($d = 3$). Therefore, the overarching Radix Sort algorithm must execute exactly three discrete sorting passes, strictly processing from the Least Significant Digit (LSD - the \"ones\" place) progressively toward the Most Significant Digit (MSD - the \"hundreds\" place)."},{"type":"subheading","content":"2. Pass 1: Sorting by the Least Significant Digit (Ones Place)"},{"type":"paragraph","content":"The algorithm extracts exclusively the final digit (the ones place) from every single element in the array to determine its bucket placement."},{"type":"list","items":["`329` $\\rightarrow$ Digit: 9","`457` $\\rightarrow$ Digit: 7","`657` $\\rightarrow$ Digit: 7","`839` $\\rightarrow$ Digit: 9","`436` $\\rightarrow$ Digit: 6","`720` $\\rightarrow$ Digit: 0","`355` $\\rightarrow$ Digit: 5"]},{"type":"paragraph","content":"The stable counting sort subroutine now systematically distributes these values into numerical buckets (0-9) strictly based on their extracted digit. \n- Bucket 0: `720` \n- Bucket 5: `355` \n- Bucket 6: `436` \n- Bucket 7: `457, 657` (The stable sort strictly preserves their original relative order) \n- Bucket 9: `329, 839`"},{"type":"paragraph","content":"The array is systematically re-assembled by concatenating the buckets sequentially from 0 to 9. \n**Array Post-Pass 1:** `[720, 355, 436, 457, 657, 329, 839]`"},{"type":"subheading","content":"3. Pass 2: Sorting by the Middle Digit (Tens Place)"},{"type":"paragraph","content":"The algorithm advances one position to the left, extracting strictly the middle digit (the tens place) from the newly reorganized array."},{"type":"list","items":["`720` $\\rightarrow$ Digit: 2","`355` $\\rightarrow$ Digit: 5","`436` $\\rightarrow$ Digit: 3","`457` $\\rightarrow$ Digit: 5","`657` $\\rightarrow$ Digit: 5","`329` $\\rightarrow$ Digit: 2","`839` $\\rightarrow$ Digit: 3"]},{"type":"paragraph","content":"Again, the stable sorting subroutine distributes the values into buckets based on this new extraction. \n- Bucket 2: `720, 329` \n- Bucket 3: `436, 839` \n- Bucket 5: `355, 457, 657`"},{"type":"paragraph","content":"The array is carefully re-assembled from the buckets. \n**Array Post-Pass 2:** `[720, 329, 436, 839, 355, 457, 657]`"},{"type":"subheading","content":"4. Pass 3: Sorting by the Most Significant Digit (Hundreds Place)"},{"type":"paragraph","content":"The algorithm advances to the final structural position, extracting the leading digit (the hundreds place)."},{"type":"list","items":["`720` $\\rightarrow$ Digit: 7","`329` $\\rightarrow$ Digit: 3","`436` $\\rightarrow$ Digit: 4","`839` $\\rightarrow$ Digit: 8","`355` $\\rightarrow$ Digit: 3","`457` $\\rightarrow$ Digit: 4","`657` $\\rightarrow$ Digit: 6"]},{"type":"paragraph","content":"Final distribution into buckets based on the highest-order digit. \n- Bucket 3: `329, 355` \n- Bucket 4: `436, 457` \n- Bucket 6: `657` \n- Bucket 7: `720` \n- Bucket 8: `839`"},{"type":"paragraph","content":"The array is sequentially re-assembled for the final time. \n**Final Sorted Array:** `[329, 355, 436, 457, 657, 720, 839]`"},{"type":"paragraph","content":"By rigorously sorting strictly from the least significant structural positional digit up to the most significant positional digit, the array is systematically organized. The time complexity for this process is firmly bounded at $O(d(n+k))$, where $n$ is the total volume of numbers, $d$ is the maximum number of digit places, and $k$ represents the size of the radix base (10 for standard decimals)."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q19","number":19,"marks":10,"tags":["linked-list"],"text":[{"type":"paragraph","content":"Write a C program to add a node with data 'X' before a node with data 'Y' in a singly linked list."}],"answer":{"summary":"A complete, deeply annotated C programming implementation demonstrating the precise memory pointer manipulation required to insert a specific node immediately prior to another specific node in a Singly Linked List.","explanation":[{"type":"heading","content":"Targeted Node Insertion in C"},{"type":"paragraph","content":"Modifying a Singly Linked List requires surgical manipulation of memory pointers. The specific task requires inserting a newly instantiated node bearing the payload 'X' immediately geometrically before a pre-existing target node holding the payload 'Y'. Because Singly Linked Lists lack a `prev` backward pointer, we mathematically cannot simply find node 'Y' and step backward. The algorithmic architecture necessitates utilizing a trailing-pointer technique or halting the primary traversal strictly one structural link before the target."},{"type":"subheading","content":"1. Structuring the C Code Algorithm"},{"type":"paragraph","content":"The overarching function must rigorously manage multiple edge cases: finding a completely empty list, discovering the target 'Y' is the absolute first head node, and handling the scenario where target 'Y' does not exist anywhere within the list structure."},{"type":"code","language":"c","code":"#include \n#include \n\n// 1. Defining the fundamental Node structure\nstruct Node {\n char data;\n struct Node* next;\n};\n\n// 2. Core Operational Function\nvoid insertBeforeY(struct Node** head_ref, char X, char Y) {\n // Phase A: Memory Allocation and Initialization\n struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n if (newNode == NULL) {\n printf(\"CRITICAL ERROR: Heap Memory Exhausted.\\n\");\n return;\n }\n newNode->data = X;\n newNode->next = NULL;\n\n // Phase B: Edge Case - List is Completely Empty\n if (*head_ref == NULL) {\n printf(\"Error: The linked list is empty. Target node \\'%c\\' cannot be found.\\n\", Y);\n free(newNode); // Prevent memory leaks\n return;\n }\n\n // Phase C: Edge Case - Target is the Absolute Head Node\n if ((*head_ref)->data == Y) {\n // The new node fundamentally becomes the new head of the list\n newNode->next = *head_ref;\n *head_ref = newNode;\n printf(\"Successfully inserted \\'%c\\' before \\'%c\\'.\\n\", X, Y);\n return;\n }\n\n // Phase D: Deep Traversal Logic (Trailing Pointer Methodology)\n struct Node* temp = *head_ref;\n \n // We aggressively scan forward, actively inspecting the NEXT node's data payload\n while (temp->next != NULL && temp->next->data != Y) {\n temp = temp->next;\n }\n\n // Phase E: Algorithmic Resolution\n // Scenario 1: The loop exhausted the list without ever discovering 'Y'\n if (temp->next == NULL) {\n printf(\"Error: Target node \\'%c\\' does not exist within the list.\\n\", Y);\n free(newNode); // Cleanup dynamically allocated memory\n return;\n }\n\n // Scenario 2: Target 'Y' discovered. Splicing logic executes.\n // temp is currently pointing to the node physically PRECEDING target 'Y'\n newNode->next = temp->next; // 1. Connect new node forward to 'Y'\n temp->next = newNode; // 2. Connect trailing node forward to new node\n \n printf(\"Successfully inserted \\'%c\\' before \\'%c\\'.\\n\", X, Y);\n}\n"},{"type":"subheading","content":"2. Deep Algorithmic Analysis"},{"type":"paragraph","content":"The fundamental architectural challenge here is strictly maintaining continuity. In \"Phase C\", modifying the head pointer requires dereferencing a double pointer (`**head_ref`), ensuring the overarching overarching program context accurately reflects the new memory address of the list start. In \"Phase D\", by actively inspecting `temp->next->data`, the algorithm forcefully halts exactly one step prior. This brilliant maneuver mathematically mimics the behavior of a doubly linked list's `prev` pointer, enabling flawless structural splicing."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q20","number":20,"marks":10,"tags":["tree","avl-tree"],"text":[{"type":"paragraph","content":"Create an AVL tree using the following nodes 10, 6, 11, 12, 1, 7, 0, 2, 3. What will be the resulting AVL tree if node 12 is deleted from above AVL tree?"}],"answer":{"summary":"A detailed trace executing the complex insertion and rotation sequence to build an AVL tree from a dataset, followed by the rigorous rebalancing protocol required after targeted node deletion.","explanation":[{"type":"heading","content":"Advanced AVL Tree Operations: Construction and Deletion"},{"type":"paragraph","content":"An AVL tree fiercely maintains its $O(\\log n)$ operational efficiency by continuously enforcing a strict structural constraint: the absolute mathematical difference in height (Balance Factor) between any given node's left and right subtrees must never exceed 1. We must meticulously trace the construction of the tree with the sequence `10, 6, 11, 12, 1, 7, 0, 2, 3`, applying structural rotations whenever this critical tolerance is violated."},{"type":"subheading","content":"Part A: Step-by-Step AVL Tree Construction Trace"},{"type":"list","items":["**Insert 10:** Root established. Tree is perfectly balanced.","**Insert 6:** Placed as left child of 10. Tree is balanced (BF of 10 is +1).","**Insert 11:** Placed as right child of 10. Tree is perfectly balanced (BF of 10 is 0).","**Insert 12:** Placed as right child of 11. Tree is balanced (BF of 10 is -1, BF of 11 is -1).","**Insert 1:** Placed as left child of 6. Tree is balanced (BF of 10 is +1, BF of 6 is +1).","**Insert 7:** Placed as right child of 6. Tree is perfectly balanced (BF of 6 is 0, BF of 10 is 0).","**Insert 0:** Placed as left child of 1. \n**CRITICAL IMBALANCE:** Node 6 now possesses a Left-Left heavy imbalance ($BF = +2$). \n**Correction:** Execute an immediate **Right Rotation (LL case)** aggressively pivoting entirely around Node 6. Node 1 physically elevates to replace 6. Node 0 remains left child of 1. Node 6 violently drops to become the right child of 1. Node 7 remains right child of 6.","**Insert 2:** Placed as right child of 0. \n**CRITICAL IMBALANCE:** Node 10 (the Root) now detects a severe Left-Left heavy imbalance ($BF = +2$). \n**Correction:** Execute a massive **Right Rotation (LL case)** pivoting completely around the primary Root 10. Node 1 fiercely elevates to become the absolute new Root of the entire tree. Node 10 mathematically drops to become the right child of 1. The previous right child of 1 (which was the entire subtree rooted at 6) mathematically transfers to become the new left child of 10.","**Insert 3:** Placed as right child of 2. \n**CRITICAL IMBALANCE:** Node 0 detects a Left-Right heavy imbalance ($BF = -2$). \n**Correction:** Execute a complex two-step **Left-Right (LR) Rotation**. First, Left rotate pivoting on 2. Node 3 elevates, 2 drops. Second, Right rotate pivoting on 0. Node 3 violently elevates again to replace 0."]},{"type":"paragraph","content":"**Final Top-Level Architectural Structure after complete insertion:** \n- Absolute Root: **1** \n- Root's Left Child: **3** (with Left Child 0, Right Child 2) \n- Root's Right Child: **10** (with Left Child 6 [Left empty, Right 7], and Right Child 11 [Right 12])."},{"type":"subheading","content":"Part B: The Deletion Protocol"},{"type":"paragraph","content":"The algorithm now mandates the deletion of target node **12**. \n**Step 1 (Physical Deletion):** Locate node 12. As a terminal leaf node (child of 11), it is trivially severed and its memory freed without requiring complex structural replacement protocols."},{"type":"paragraph","content":"**Step 2 (Ascending Rebalance Check):** Following deletion, the algorithm must re-traverse the path upward back to the root, exhaustively recalculating the Balance Factor of every node along the ascending trajectory."},{"type":"list","items":["Check Node 11: Left subtree height = 0, Right subtree height = 0. $BF = 0$. Balanced.","Check Node 10: Left subtree (rooted at 6) height = 2. Right subtree (rooted at 11) height = 1. $BF = +1$. Balanced.","Check Root 1: Left subtree (rooted at 3) height = 2. Right subtree (rooted at 10) height = 3. $BF = -1$. Balanced."]},{"type":"paragraph","content":"The post-deletion structural verification process mathematically confirms that the violent removal of node 12 did not perturb the overarching tree architecture beyond allowable limits. No further corrective algorithmic rotations are necessary. The AVL tree retains its strict $O(\\log n)$ integrity."}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q21","number":21,"marks":10,"tags":["graph","mst","prim"],"text":[{"type":"paragraph","content":"Consider the following graph - "},{"type":"svg","content":"","alt":"Graph for Prim's Algorithm"},{"type":"paragraph","content":"Find the minimum spanning tree using Prim's algorithm."}],"answer":{"summary":"An exhaustive, step-by-step graphical tracing of Prim's greedy algorithmic methodology to aggressively construct a Minimum Spanning Tree from a complexly weighted initial graph topology.","explanation":[{"type":"heading","content":"Prim's Algorithm for Minimum Spanning Trees"},{"type":"paragraph","content":"Prim's algorithm operates completely differently from Kruskal's edge-based approach. It is fundamentally vertex-centric. The algorithm conceptualizes the Minimum Spanning Tree (MST) as a single, rapidly expanding, cohesive entity. It initializes from an arbitrary starting vertex and continuously expands outward like a shockwave by greedily pulling in the absolutely cheapest available edge that connects the established MST to a previously undiscovered exterior vertex. This process mathematically prevents cycles and guarantees optimal total weight."},{"type":"subheading","content":"Algorithmic Trace"},{"type":"paragraph","content":"We are presented with a graph of 7 vertices ($0, 1, 2, 3, 4, 5, 6$) connected by 11 weighted edges. \nWe initialize two structural lists: the `Visited Set` (representing the MST) and the `Unvisited Set`."},{"type":"paragraph","content":"**Initialization:** \nLet us arbitrarily select Vertex `0` as the absolute mathematical origin point. \n`Visited Set`: {0} \n`Unvisited Set`: {1, 2, 3, 4, 5, 6}"},{"type":"paragraph","content":"**Iteration 1:** \nAnalyze all edges extending outward from the `Visited Set` ({0}): \n- Edge (0, 1) $\\rightarrow$ Weight 2 \n- Edge (0, 3) $\\rightarrow$ Weight 6 \nThe algorithm greedily selects the minimum available edge: **(0, 1)**. Vertex 1 is absorbed. \n`Visited Set`: {0, 1}"},{"type":"paragraph","content":"**Iteration 2:** \nAnalyze edges extending from {0, 1}: \n- Edge (0, 3) $\\rightarrow$ Weight 6 \n- Edge (1, 2) $\\rightarrow$ Weight 3 \n- Edge (1, 3) $\\rightarrow$ Weight 8 \n- Edge (1, 4) $\\rightarrow$ Weight 5 \nMinimum edge is **(1, 2)**. Vertex 2 is absorbed. \n`Visited Set`: {0, 1, 2}"},{"type":"paragraph","content":"**Iteration 3:** \nAnalyze edges extending from {0, 1, 2}: \n- Edge (0, 3) $\\rightarrow$ Weight 6 \n- Edge (1, 3) $\\rightarrow$ Weight 8 \n- Edge (1, 4) $\\rightarrow$ Weight 5 \n- Edge (2, 4) $\\rightarrow$ Weight 7 \nMinimum edge is **(1, 4)**. Vertex 4 is absorbed. \n`Visited Set`: {0, 1, 2, 4}"},{"type":"paragraph","content":"**Iteration 4:** \nAnalyze edges extending from {0, 1, 2, 4}: \n- Edge (0, 3) $\\rightarrow$ Weight 6 \n- Edge (1, 3) $\\rightarrow$ Weight 8 \n- Edge (2, 4) $\\rightarrow$ Weight 7 (Redundant, both in set) \n- Edge (4, 3) $\\rightarrow$ Weight 9 \n- Edge (4, 5) $\\rightarrow$ Weight 1 \n- Edge (4, 6) $\\rightarrow$ Weight 4 \nMinimum edge is **(4, 5)**. Vertex 5 is absorbed. \n`Visited Set`: {0, 1, 2, 4, 5}"},{"type":"paragraph","content":"**Iteration 5:** \nAnalyze edges extending from {0, 1, 2, 4, 5}: \n- Edge (0, 3) $\\rightarrow$ Weight 6 \n- Edge (1, 3) $\\rightarrow$ Weight 8 \n- Edge (4, 3) $\\rightarrow$ Weight 9 \n- Edge (4, 6) $\\rightarrow$ Weight 4 \n- Edge (5, 3) $\\rightarrow$ Weight 11 \n- Edge (5, 6) $\\rightarrow$ Weight 2 \nMinimum edge is **(5, 6)**. Vertex 6 is absorbed. \n`Visited Set`: {0, 1, 2, 4, 5, 6}"},{"type":"paragraph","content":"**Iteration 6:** \nAnalyze remaining edges connecting to unvisited vertex 3: \n- Edge (0, 3) $\\rightarrow$ Weight 6 \n- Edge (1, 3) $\\rightarrow$ Weight 8 \n- Edge (4, 3) $\\rightarrow$ Weight 9 \n- Edge (5, 3) $\\rightarrow$ Weight 11 \nMinimum connecting edge is **(0, 3)**. Vertex 3 is absorbed. \n`Visited Set`: {0, 1, 2, 3, 4, 5, 6} (All Vertices Included!)"},{"type":"subheading","content":"Final Synthesis and Conclusion"},{"type":"paragraph","content":"The mathematical algorithm explicitly terminates as every single vertex from the original graph has been successfully fully absorbed into the overarching Spanning Tree structure."},{"type":"paragraph","content":"The definitively constructed Minimum Spanning Tree is composed precisely of the following calculated edges: \n(0, 1) [wt: 2] \n(1, 2) [wt: 3] \n(1, 4) [wt: 5] \n(4, 5) [wt: 1] \n(5, 6) [wt: 2] \n(0, 3) [wt: 6]"},{"type":"paragraph","content":"The absolute total optimal minimum cost of the network is the mathematical summation of these isolated weights: $2 + 3 + 5 + 1 + 2 + 6 = 19$."},{"type":"svg","content":"","alt":"Final Minimum Spanning Tree (MST)"}]}},{"id":"rtu-cs-y2-s3-data-structures-paper-2023-q22","number":22,"marks":10,"tags":["recursion","stack"],"text":[{"type":"paragraph","content":"(a) Write a recursive program for towers of Hanoi."},{"type":"paragraph","content":"(b) What is a stack? Calculate the following expression - 8 2 3 ^ / 2 3 * + 5 1 * -"}],"answer":{"summary":"A bipartite explanation detailing the complex recursive logic driving the Towers of Hanoi solution, coupled with a rigorous stack-based computational trace evaluating a highly complex Reverse Polish Notation (Postfix) algebraic expression.","explanation":[{"type":"heading","content":"Part A: The Recursive Towers of Hanoi Algorithm"},{"type":"paragraph","content":"The Towers of Hanoi puzzle exemplifies the sheer mathematical power of recursive programming logic. A recursive algorithm solves a massive, complex problem by forcefully breaking it down into incrementally smaller, perfectly identical sub-problems until an easily solvable base case is achieved. The core methodology for relocating $n$ disks from the primary source rod to a designated destination rod explicitly requires the utilization of an intermediary auxiliary rod."},{"type":"code","language":"c","code":"void solveHanoi(int n, char source, char destination, char auxiliary) {\n // 1. The Definitive Base Case: Trivial single disk transfer\n if (n == 1) {\n printf(\"Move disk 1 from rod %c to rod %c\\n\", source, destination);\n return;\n }\n \n // 2. Recursive Descent (Phase 1):\n // Move the towering top stack of (n-1) disks away from the source, \n // parking them temporarily on the auxiliary rod.\n solveHanoi(n - 1, source, auxiliary, destination);\n \n // 3. The Core Operation:\n // Now unimpeded, directly move the absolute largest remaining \n // disk straight to its final destination.\n printf(\"Move disk %d from rod %c to rod %c\\n\", n, source, destination);\n \n // 4. Recursive Ascent (Phase 2):\n // Retrieve the parked (n-1) disks from the auxiliary rod, \n // stacking them perfectly onto the final destination rod.\n solveHanoi(n - 1, auxiliary, destination, source);\n}"},{"type":"subheading","content":"Part B: Defining and Utilizing Stack Mechanics"},{"type":"paragraph","content":"A Stack is a highly specialized, abstract linear data structure fundamentally governed by the LIFO (Last-In-First-Out) operational protocol. This strict architectural constraint demands that the absolute most recently inserted data element (via a `push` operation) is strictly mandated to be the absolute first element extracted (via a `pop` operation). This structural mechanic makes Stacks the undisputed optimal architectural choice for algorithms requiring chronological state tracking, such as parsing nested compiler syntaxes or, crucially, evaluating compiler-generated Postfix expressions."},{"type":"paragraph","content":"**Evaluating Postfix Expression: `8 2 3 ^ / 2 3 * + 5 1 * -`**"},{"type":"paragraph","content":"The evaluation algorithm scans stringently from left to right. Numbers are immediately pushed onto the stack. Upon encountering an operator, the top two numbers are popped, the mathematical operation executed, and the resulting value forcefully pushed right back onto the top of the stack."},{"type":"list","items":["Scan `8`: Push to stack. Stack: `[8]`","Scan `2`: Push to stack. Stack: `[8, 2]`","Scan `3`: Push to stack. Stack: `[8, 2, 3]`","Scan `^` (Power Operator): Pop `3`, Pop `2`. Calculate $2^3 = 8$. Push result. Stack: `[8, 8]`","Scan `/` (Division Operator): Pop `8`, Pop `8`. Calculate $8 / 8 = 1$. Push result. Stack: `[1]`","Scan `2`: Push to stack. Stack: `[1, 2]`","Scan `3`: Push to stack. Stack: `[1, 2, 3]`","Scan `*` (Multiplication): Pop `3`, Pop `2`. Calculate $2 * 3 = 6$. Push result. Stack: `[1, 6]`","Scan `+` (Addition): Pop `6`, Pop `1`. Calculate $1 + 6 = 7$. Push result. Stack: `[7]`","Scan `5`: Push to stack. Stack: `[7, 5]`","Scan `1`: Push to stack. Stack: `[7, 5, 1]`","Scan `*` (Multiplication): Pop `1`, Pop `5`. Calculate $5 * 1 = 5$. Push result. Stack: `[7, 5]`","Scan `-` (Subtraction): Pop `5`, Pop `7`. Calculate $7 - 5 = 2$. Push result. Stack: `[2]`"]},{"type":"paragraph","content":"The algorithmic scan successfully completes. The solitary value remaining encapsulated within the stack (`2`) represents the final, definitively calculated result of the complex algebraic expression."}]}}]}],"loading":false,"error":null}}}

Q8Data Structures

Question

Answer