GTU 3130702 Data Structures (DS) Summer 2025 Solved Paper & Solutions

Time Complexity Analysis

1. Best-Case Time Complexity ($\Omega$ notation):

• The minimum amount of time or operations an algorithm requires to execute for an input of size $n$, under the most favorable circumstances.
• Example: Linear search on an array where the search key is at the first index ($O(1)$).

2. Worst-Case Time Complexity ($O$ notation):

• The maximum amount of time or operations an algorithm can ever take for an input of size $n$, under the least favorable (adversarial) input.
• Provides a guaranteed upper bound on performance.
• Example: Linear search when the element is at the last position or not present ($O(n)$).

3. Average-Case Time Complexity ($\Theta$ notation):

• The expected number of operations an algorithm executes across all possible valid input permutations of size $n$, assuming a uniform probability distribution.
• Example: Linear search where the element is found around index $n/2$ on average ($\frac{n+1}{2} \implies O(n)$).

Row-Major vs Column-Major Representation of 2D Arrays

In computer memory, multi-dimensional arrays are mapped to a linear 1D address space using two standard conventions:

Address Calculation Formulas:

Let $A[R][C]$ have Base Address $B$, element size $W$ bytes, row indices $0 \le i < R$, and column indices $0 \le j < C$:

1. Row-Major Order (C, C++, Java, Python):

• Elements are stored row-by-row consecutively in memory.

2. Column-Major Order (Fortran, MATLAB, R):

• Elements are stored column-by-column consecutively in memory.

1. Construction of Binary Search Tree (BST)

Given Data Sequence: 21, 51, 12, 45, 17, 71, 19, 47, 78

Insertion Steps (Left if smaller, Right if larger):

1. Insert 21: Root node $\to \mathbf{21}$.
2. Insert 51: $51 > 21 \implies$ right child of $21$.
3. Insert 12: $12 < 21 \implies$ left child of $21$.
4. Insert 45: $45 > 21$, $45 < 51 \implies$ left child of $51$.
5. Insert 17: $17 < 21$, $17 > 12 \implies$ right child of $12$.
6. Insert 71: $71 > 21$, $71 > 51 \implies$ right child of $51$.
7. Insert 19: $19 < 21$, $19 > 12$, $19 > 17 \implies$ right child of $17$.
8. Insert 47: $47 > 21$, $47 < 51$, $47 > 45 \implies$ right child of $45$.
9. Insert 78: $78 > 21$, $78 > 51$, $78 > 71 \implies$ right child of $71$.

2. Constructed BST Structure

3. Tree Traversals

• In-order Traversal (Left $\to$ Root $\to$ Right):

(Property: Always yields strictly ascending sorted order for any valid BST!)

• Pre-order Traversal (Root $\to$ Left $\to$ Right):

• Post-order Traversal (Left $\to$ Right $\to$ Root):

Binary Tree Definitions:

1. Full Binary Tree (Strict / Proper Binary Tree):

• A binary tree in which every node has either zero or two children. No node has exactly one child.
• Property: If it has $L$ leaves, total internal nodes $= L - 1$.

2. Complete Binary Tree:

• A binary tree in which every level, except possibly the last level, is completely filled, and all nodes in the last level are as far left as possible.
• Property: Used directly to implement binary heaps using contiguous 1D arrays without pointer overhead.

3. Skewed Binary Tree:

• A binary tree in which every internal node has only one child:
• Left-Skewed: Every node has only a left child.
• Right-Skewed: Every node has only a right child.
• Degenerates into a linear linked list with worst-case search time $O(n)$.

1. Importance of Asymptotic Analysis

• Evaluates algorithm performance as input size $n \to \infty$, focusing on growth rate.
• Provides a machine-independent and programming-language-independent comparison metric.
• Eliminates minor hardware variations, clock speeds, and constant factor coefficients.

2. Is $O(n \log_2 n^2)$ Faster Than $O(n^2)$?

Yes, $O(n \log_2 n^2)$ is strictly faster than $O(n^2)$.

Justification:

Using the logarithmic power identity $\log(a^b) = b \log a$:

Now compare growth rates as $n \to \infty$:

• Since the ratio approaches $0$, $n \log n$ grows significantly slower than $n^2$, making it much faster.

Numerical Example ($n = 1024$):

• For $O(n \log_2 n^2) \implies 1024 \times \log_2(1024^2) = 1024 \times 20 = \mathbf{20,480\text{ operations}}$.
• For $O(n^2) \implies 1024^2 = \mathbf{1,048,576\text{ operations}}$.
• $O(n \log_2 n^2)$ is approximately 50 times faster at $n = 1024$.

Infix to Postfix Conversion Using Stack

Given Expression: ((a + b) ^ ((c * d) / (e - f)))

• Operator Precedence:
• Highest: Parentheses ( )
• Next: Exponentiation ^ (Right-to-Left associativity)
• Next: Multiplication * and Division / (Left-to-Right)
• Lowest: Addition + and Subtraction - (Left-to-Right)

Step-by-Step Stack Trace:

Use of Stack in Recursion

In recursive execution, the system uses the Call Stack (Runtime Stack) to manage active function calls:

1. Pushing Activation Records (Winding):

• Each time a recursive function calls itself, an activation frame containing its parameters, local variables, and return address is pushed onto the stack.
• State of caller is suspended and preserved.

2. Base Case & Pop (Unwinding):

• When the base case is reached, execution returns the base value, and frames are sequentially popped off the stack in reverse order (LIFO), delivering return values to their callers.

Example: Computing fact(3)

Calling Phase (Push):        Return Phase (Pop):
| fact(1): n=1 -> returns 1 |  ---> 1
| fact(2): n=2 -> 2 * 1     |  ---> 2
| fact(3): n=3 -> 3 * 2     |  ---> 6  (Returns 6 to OS)
+---------------------------+

Threaded Binary Tree

In a standard binary tree with $N$ nodes, $N + 1$ child pointers are NULL. A Threaded Binary Tree utilizes these wasted null pointers as threads to enable fast in-order traversal without requiring recursion or an auxiliary stack.

Types:

1. One-Way (Single) Threaded: Only NULL right pointers point to the in-order successor.
2. Two-Way (Double) Threaded:

• NULL left pointers point to the in-order predecessor.
• NULL right pointers point to the in-order successor.

Node Structure:

• Each node includes two boolean flags (isLeftThread, isRightThread) to distinguish genuine child pointers from thread pointers.
• Advantage: Enables linear $O(n)$ in-order traversal with $O(1)$ auxiliary space.

C Program for Circular Queue Operations

• Full Condition: (rear + 1) % SIZE == front
• Empty Condition: front == -1

Definitions:

1. Field:

• The smallest indivisible, meaningful data item representing a single attribute of an entity.
• Example: Roll_No = 101, Student_Name = "Raj".

2. Record:

• A collection of related fields treated as a single cohesive unit, describing all attributes of a specific instance of an entity.
• Example: A student record containing {Roll_No: 101, Name: "Raj", Sem: 3, CPI: 8.5}.

3. File:

• A named collection of logically related records stored permanently on secondary storage (disk/SSD).
• Example: students.dat containing records for all registered university students.

Merge Sort Step-by-Step

Input Array: [50, 20, 70, 05, 30, 80, 55, 25]

Step 1: Divide Phase (Split until arrays of size 1)

[50, 20, 70, 05, 30, 80, 55, 25]
                     /                           \
          [50, 20, 70, 05]                   [30, 80, 55, 25]
           /            \                     /            \
      [50, 20]        [70, 05]           [30, 80]        [55, 25]
       /    \          /    \             /    \          /    \
     [50]   [20]     [70]   [05]        [30]   [80]     [55]   [25]

Step 2: Merge Phase (Combine sorted sub-arrays)

• Merge Pairs of 1:
• [50] and [20] $\to$ [20, 50]
• [70] and [05] $\to$ [05, 70]
• [30] and [80] $\to$ [30, 80]
• [55] and [25] $\to$ [25, 55]
• Merge Pairs of 2:
• [20, 50] and [05, 70] $\to$ [05, 20, 50, 70]
• [30, 80] and [25, 55] $\to$ [25, 30, 55, 80]
• Final 4-way Merge:
• [05, 20, 50, 70] and [25, 30, 55, 80]
• $\to$ [05, 20, 25, 30, 50, 55, 70, 80]

• Time Complexity: $O(n \log n)$ in all cases.

Minimum Spanning Tree Using Kruskal’s Algorithm

From the given graph (Fig. 1), there are 7 vertices: $\{A, B, C, D, E, F, H\}$.
A Minimum Spanning Tree (MST) requires exactly $V - 1 = 7 - 1 = \mathbf{6\text{ edges}}$ without forming any cycle.

Step 1: List and Sort All Edges by Weight in Ascending Order:

Step 2: Edges in Final MST:

1. $(H, D)$ with weight $1$
2. $(B, H)$ with weight $2$
3. $(A, B)$ with weight $4$
4. $(H, E)$ with weight $4$
5. $(A, F)$ with weight $5$
6. $(C, E)$ with weight $5$

Linear Search vs Binary Search

C Program for Bubble Sort

• Best-Case Time: $O(n)$ with swapped optimization.
• Worst/Average Time: $O(n^2)$.

Hash Collisions and Collision Resolution Techniques

A Hash Collision occurs when two distinct keys $k_1 \ne k_2$ produce the exact same hash address:

1. Open Addressing (Closed Hashing)

All elements are stored directly within the hash table itself. When a collision occurs, alternative slots are probed systematically:

1. Linear Probing:

• Probes consecutive slots linearly: $h(k, i) = (h'(k) + i) \bmod m$.
• Drawback: Suffers from primary clustering (long continuous blocks of occupied slots build up, degrading lookup time to $O(n)$).

2. Quadratic Probing:

• Probes quadratic offsets: $h(k, i) = (h'(k) + c_1 i + c_2 i^2) \bmod m$.
• Drawback: Eliminates primary clustering but causes secondary clustering.

3. Double Hashing:

• Uses two independent hash functions: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m$.
• Excellent uniform distribution with no clustering issues.

2. Separate Chaining (Open Hashing)

Each slot in the hash table points to a linked list of records that hash to the same index.

• Advantages:
• Table never fills up (no overflow exceptions).
• Deletion is simple (standard linked list node removal).
• Disadvantages:
• Extra memory overhead for next-pointers.