Multi-Dimensional Arrays, Address Translation & Stack Mechanics
“Row-major vs column-major indexing, 3D tensor addresses, operator precedence stack mechanics, and recursion frames.”
1.Physical Memory Mapping of Multi-Dimensional Arrays
§ 1.1.Computer RAM is a flat, 1-dimensional sequence of byte addresses. Multi-dimensional matrices must be mapped onto this linear physical space.
1. Row-Major Ordering (Lexicographical / C / Python):
Consecutive elements of a row are placed contiguously in memory. Moving from row i to row i + 1 requires skipping an entire row of N = U2 - L2 + 1 elements.
General 2D formula: text{Addr}(A[i, j]) = text{Base} + c [ (i - L1) N + (j - L2) ].
General 3D formula for A[L1..U1, L2..U2, L3..U3] with dimensions D1, D2, D3:
text{Addr}(A[i, j, k]) = text{Base} + c [ (i - L1) D2 D3 + (j - L2) D3 + (k - L3) ].
2. Column-Major Ordering (Fortran / MATLAB / R):
Consecutive elements of a column are placed contiguously. Moving from column j to j + 1 requires skipping M = U1 - L1 + 1 elements.
text{Addr}(A[i, j]) = text{Base} + c [ (j - L2) M + (i - L1) ].
2.Stack Mechanics & Infix-to-Postfix Shunting-Yard Algorithm
§ 1.2.A Stack operates on the Last-In First-Out (LIFO) principle.
Infix to Postfix Conversion (Dijkstra's Shunting-Yard Algorithm):
1. Operands are immediately appended to the output postfix string.
2. When an operator op arrives:
- While the stack is non-empty and the top operator has greater precedence than op (or equal precedence if op is left-associative), pop the stack to the output.
- Push op onto the stack.
3. Left parenthesis ( has the lowest in-stack precedence but highest incoming precedence.
4. When ) arrives, pop operators to output until ( is encountered, then discard (.
5. At end of input, pop all remaining operators.
3. Worked Problem: 3D Array Address Calculation with Custom Bounds
Always compute the dimension spans D1, D2, D3 as U - L + 1 before setting up the multiplication offsets.
Problem: An array A[1..5, -2..3, 0..4] is stored in Row-Major order starting at Base Address 2000. Each element occupies 2 bytes. Compute the exact byte address of element A[3, 1, 2].
Step 1: Compute dimensions of each axis:
Axis 1: L1 = 1, U1 = 5 => D1 = 5 - 1 + 1 = 5 planes.
Axis 2: L2 = -2, U2 = 3 => D2 = 3 - (-2) + 1 = 6 rows per plane.
Axis 3: L3 = 0, U3 = 4 => D3 = 4 - 0 + 1 = 5 columns per row.
Element size c = 2 bytes, Base = 2000.
Step 2: Apply 3D Row-Major offset formula:
Offset in elements = (i - L1) D2 D3 + (j - L2) * D3 + (k - L3)
Step 3: Substitute i = 3, j = 1, k = 2:
Plane offset = (3 - 1) (6 5) = 2 * 30 = 60 elements.
Row offset within plane = (1 - (-2)) 5 = 3 5 = 15 elements.
Column offset within row = (2 - 0) = 2 elements.
Total elements skipped = 60 + 15 + 2 = 77 elements.
Step 4: Compute physical memory address:
Addr = Base + (Total elements * c)
Addr = 2000 + (77 * 2) = 2000 + 154 = 2154.
Final Answer: Byte address of A[3, 1, 2] is 2154.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Visual thinkers who want to see each algorithm step animated clearly.
GATE-targeted coverage with step-by-step GATE PYQ walkthroughs.