Data Structures and Algorithms Practice Problems

Q1. Array Address Calculation (Row & Column Major)

Problem: An array ARR[-5...15, 10...20] stores elements in Row Major with each element requiring 2 bytes. Base address is 2500. Find the address of ARR[10][15].

Answer:

• Row range: -5 to 15, so Lr = -5, Ur = 15
• Column range: 10 to 20, so Lc = 10, Uc = 20
• Element size (w) = 2 bytes
• Base Address (BA) = 2500

Step 1: Calculate dimensions

• Number of rows (M) = Ur - Lr + 1 = 15 - (-5) + 1 = 21
• Number of columns (N) = Uc - Lc + 1 = 20 - 10 + 1 = 11

Step 2: Row Major Order Formula

Address(A[i][j]) = BA + [(i - Lr) × N + (j - Lc)] × w
Address(ARR[10][15]) = 2500 + [(10 - (-5)) × 11 + (15 - 10)] × 2
= 2500 + [15 × 11 + 5] × 2
= 2500 + [165 + 5] × 2
= 2500 + 170 × 2 = 2840

Step 3: Column Major Order Formula

Address(A[i][j]) = BA + [(j - Lc) × M + (i - Lr)] × w
Address(ARR[10][15]) = 2500 + [(15 - 10) × 21 + (10 - (-5))] × 2
= 2500 + [5 × 21 + 15] × 2
= 2500 + [105 + 15] × 2
= 2500 + 120 × 2 = 2740

Result: Row Major = 2840, Column Major = 2740

Q2. Polynomial Representation and Addition

Polynomial Representation: A polynomial like 5x³ + 4x² + 2x + 1 is represented as a linked list where each node contains:

• Coefficient (coef)
• Exponent (exp)
• Pointer to next term (next)

Node Structure:

struct Node { int coef; int exp; struct Node *next; };

Example: 5x³ + 4x² + 2x + 1 → [5|3] → [4|2] → [2|1] → [1|0] → NULL

Q3. Asymptotic Notations

Asymptotic notations describe the growth rate of algorithms as input size approaches infinity.

1. Big-O Notation O(g(n)) - Upper Bound

f(n) = O(g(n)) if there exist constants c > 0 and n≥0 such that f(n) ≤ c·g(n) for all n ≥ n≥0. Example: f(n) = 3n² + 5n + 2 is O(n²).

2. Big-Omega Notation Ω(g(n)) - Lower Bound

f(n) = Ω(g(n)) if there exist constants c > 0 and n≥0 such that f(n) ≥ c·g(n) for all n ≥ n≥0.

3. Big-Theta Notation Θ(g(n)) - Tight Bound

f(n) = Θ(g(n)) if f(n) = O(g(n)) AND f(n) = Ω(g(n)).

Q4. Linked List vs Arrays

Disadvantages of Linked List:

• Extra memory for pointers
• No random access - O(n) to access nth element
• Not cache-friendly (non-contiguous memory)
• Reverse traversal not possible in singly linked list

Q5. Infix to Postfix Conversion

Algorithm:

1. Scan infix expression left to right.
2. If operand, add to output.
3. If '(', push to stack.
4. If ')', pop and output until '(' is found, discard '('.
5. If operator: Pop operators with higher/equal precedence, add to output, then push current operator.
6. After scanning, pop all remaining operators to output.

Example: Convert A+B*C-D/F to Postfix Result: ABC*+DF/-

Q6. Postfix Expression Evaluation

Algorithm:

1. Scan postfix expression left to right.
2. If operand, push onto stack.
3. If operator, pop two operands, apply operator, push result.
4. Final value in stack is the result.

Example: Evaluate 3*(5-3) → Postfix: 3 5 3 - * Result: 6

Q7. Stack Implementation using Linked List

Advantages: Dynamic size, no overflow (until memory exhausted).