Recursion is a programming technique in which a function calls itself directly or indirectly to solve a problem. A recursive function solves a problem by breaking it down into smaller subproblems of the same type until it reaches a base ...

--- A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Formal Definition: A binary tree is either: - An empty tree (null), OR - A node consisting of a ro...

• Array to sort: 40, 6, 5, 21, 3, 100, 90, 7, 8, 12, 30 (11 elements) - Sorting method: Merge Sort - Discussion topic: limitation of first-element pivot in Quick Sort --- Quick Sort selects a pivot and partitions the array into elements ...

A data type is a classification that specifies: - The type of values a variable can hold - The set of operations that can be performed on those values Example: int data type stores integer values and supports operations like addition, su...

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. Using a linked list to implement a queue allows dynamic memory allocation, avoiding the fixed-size limitation of array-based queues. --- Each node ...

--- A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Formal Definition: A binary tree is either: - An empty tree (null), OR - A node consisting of a ro...

Recursion is a programming technique in which a function calls itself directly or indirectly to solve a problem. A recursive function solves a problem by breaking it down into smaller subproblems of the same type until it reaches a base ...

In a simple linear queue implemented using an array, two pointers are maintained: - Front - points to the first element - Rear - points to the last element Consider a queue of size 5: After Enqueue A, B, C, D, E and then Dequeue A, B: No...

• Array to sort: 40, 6, 5, 21, 3, 100, 90, 7, 8, 12, 30 (11 elements) - Sorting method: Merge Sort - Discussion topic: limitation of first-element pivot in Quick Sort --- Quick Sort selects a pivot and partitions the array into elements ...

A data type is a classification that specifies: - The type of values a variable can hold - The set of operations that can be performed on those values Example: int data type stores integer values and supports operations like addition, su...

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. Using a linked list to implement a queue allows dynamic memory allocation, avoiding the fixed-size limitation of array-based queues. --- Each node ...

In many applications, we need to search, insert, and delete data efficiently. Traditional data structures have the following limitations: Structure Search Time ------ Unsorted Array O(n) Sorted Array (Binary Search) O(log n) BST (balance...

Quick Sort is a divide-and-conquer sorting algorithm. It selects a pivot element and partitions the array so that all elements less than or equal to the pivot are on its left, and all greater elements are on its right. The pivot is then ...

--- An Abstract Data Type (ADT) is a mathematical model for a data type where the data type is defined by its behavior (operations) from the user's point of view, rather than by its implementation details. An ADT specifies: - What data i...

A priority queue is a special type of queue in which each element is associated with a priority value, and elements are served (removed) based on their priority rather than their insertion order. - An element with higher priority is dequ...

Given Data

Infix expression to convert: $$7 * 8 + 10 - 2$$

Operator precedence:

• *, / : higher
• +, - : lower

Associativity: left to right.

Conversion Rules (Stack Method)

1. Scan tokens left to right.
2. Operand → append to output.
3. Operator → pop operators from stack with precedence greater than or equal to the current one (for left-associative operators), append them to output, then push the current operator.
4. End → pop all remaining operators to output.

Step-by-Step Trace

Verification (evaluate postfix)

Given values: $7,8,+,*$ etc. Compute $7 \times 8 = 56$; $56 + 10 = 66$; $66 - 2 = 64$. Infix: $7 \times 8 + 10 - 2 = 56 + 10 - 2 = 64$. ✓ Matches.

Result

$$\boxed{7\ 8\ *\ 10\ +\ 2\ -}$$

Each node has three fields: PREV (pointer to previous node), DATA, and NEXT (pointer to next node). In a doubly circular linked list: - The last node's NEXT points to the first node - The first node's PREV points to the last node --- Ste...

Time and Space Complexity + Round Robin Algorithm for MST

(a) Time and Space Complexity

Time Complexity

Time complexity is a measure of the amount of time (number of basic operations) an algorithm takes to complete as a function of the input size n. It describes how the running time grows with increasing input.

Example: Linear search has time complexity O(n).

Space Complexity

Space complexity is a measure of the amount of memory space an algorithm requires as a function of the input size n. It includes both auxiliary space and space used by the input.

Example: An algorithm storing an n x n matrix has space complexity O(n²).

(b) Round Robin Algorithm for MST

Background

The Round Robin (also called Boruvka's Algorithm) is one of the oldest algorithms for finding a Minimum Spanning Tree (MST) of a weighted, connected, undirected graph.

• Proposed by Otakar Boruvka in 1926.
• It works by simultaneously growing multiple components and merging them.

Key Idea

In each round (phase), every component (initially each vertex is its own component) selects the minimum weight edge that connects it to a different component. All such edges are added to the MST, and components are merged.

Algorithm Steps

Input: Graph G = (V, E) with weighted edges
Output: Minimum Spanning Tree T

1. Initialize each vertex as its own component.
   T = {} (empty set of MST edges)

2. Repeat until only one component remains:
   a. For each component C:
      - Find the minimum weight edge (u, v) such that
        u ∈ C and v ∉ C (cheapest outgoing edge).
   
   b. Add all such selected edges to T
      (avoid duplicates if two components select the same edge).
   
   c. Merge the connected components.

3. Return T as the MST.

Example

Consider the graph:

    4       2
A ------B ------C
|       |       |
6|      |3      |1
|       |       |
D ------E ------F
    5       8

Edges: A-B(4), B-C(2), A-D(6), B-E(3), C-F(1), D-E(5), E-F(8)

Round 1: Each vertex is its own component {A},{B},{C},{D},{E},{F}

Selected edges (removing duplicates): C-F(1), B-C(2), B-E(3), A-B(4), D-E(5)

After merging: {A,B,C,E,F} and {D} merge further -> one component.

MST edges: C-F, B-C, B-E, A-B, D-E
Total Weight: 1+2+3+4+5 = 15

Complexity Analysis

• Each phase reduces the number of components by at least half.
• So there are at most O(log V) phases.
• Each phase scans all E edges.

Advantages

• Naturally parallelizable (all components work simultaneously).
• Efficient for dense graphs.
• Works well in distributed computing environments.

Summary

Boruvka's Round Robin Algorithm builds the MST by repeatedly selecting the minimum cost edge from each component and merging components until a single spanning tree is formed, achieving O(E log V) time complexity.

STEP 1 - EXTRACT: Given Data

Task: Traverse a given tree in pre-order and in-order.

Tree structure: The tree diagram/image is NOT provided in the question. Only the instruction and the mark allocation ([5]) are given.

Missing data: The actual tree (nodes and their parent/child relationships) is missing. Without the specific tree, an exact, verifiable set of traversal sequences cannot be produced. The correct output depends entirely on the omitted diagram.

Since the tree cannot be recovered, I will state the required methods precisely and demonstrate them on a clearly labelled assumed sample tree (so the traversal logic can still be checked), while noting this is illustrative only.

STEP 2 - SOLVE (using an assumed sample tree, since the real tree is missing)

Assumed Sample Tree

        A
       / \
      B   C
     / \ / \
    D  E F  G

1. Pre-order Traversal (Root → Left → Right)

Rule: visit Root, then Left subtree, then Right subtree.

• Visit A (root)
• Left subtree of A (rooted at B): visit B, then D, then E
• Right subtree of A (rooted at C): visit C, then F, then G

$$\text{Pre-order: } A \to B \to D \to E \to C \to F \to G$$

2. In-order Traversal (Left → Root → Right)

Rule: traverse Left subtree, visit Root, traverse Right subtree.

• Left subtree of A: D, B, E
• Visit A
• Right subtree of A: F, C, G

$$\text{In-order: } D \to B \to E \to A \to F \to C \to G$$

Summary

Important note: These results are valid only for the assumed sample tree shown above. Because the actual tree from the exam paper was not supplied, the definitive answer cannot be produced. If the real tree differs, apply the same rules:

• Pre-order = Root, Left, Right
• In-order = Left, Root, Right