Data Structures: Derivation of Index Formula for 1-D, 2-D, and Multi-D Arrays

Course Overview and Learning Objectives

• Course Information:

  • Course Name: Data Structures

  • Course Code: R1UC302B

  • Session Number: 5

  • Instructor: Mriganka Shekhar Das

  • Class Duration: 50 mins

  • Date of Conduction: 16 Aug 2026

  • Instructional Framework: GSCALE (Galgotias Student Centered Active Learning Ecosystem), which incorporates Critical Thinking, Collaboration, Learning Engagement, and Experiential Learning.

• Session Learning Outcomes:

  • Calculate the memory address of any given element in 1D, 2D, and 3D arrays under various storage orders using formal address formulas.

  • Explain the step-by-step derivation process of index formulas for 1-D, 2-D, and multi-D arrays in both row-major and column-major order.

Array Classification and Storage Orders

• Array Types Based on Size:

  • Fixed Size Array: Memory size is predetermined during declaration and cannot be resized during runtime.

  • Dynamic Size Array: Memory size can grow or shrink dynamically during program execution.

• Array Types Based on Dimensions:

  • One-Dimensional (1D) Array: A linear sequence of elements stored in contiguous memory locations.

  • Multi-Dimensional Array: Higher-dimensional structures, including Two-Dimensional (2D) Arrays, Three-Dimensional (3D) Arrays, and higher dimensions.

• Two-Dimensional Storage Orders:

  • Row-Major Order: Matrix elements are stored in memory row by row sequentially. For a matrix containing elements $a_{11}, a_{12}, a_{13}, a_{21}, a_{22}, a_{23}, a_{31}, a_{32}, a_{33}$, the row-major memory sequence is:

    $a_{11}, a_{12}, a_{13}, a_{21}, a_{22}, a_{23}, a_{31}, a_{32}, a_{33}$

• Column-Major Order: Matrix elements are stored in memory column by column sequentially. For the same matrix, the column-major memory sequence is:

    $a_{11}, a_{21}, a_{31}, a_{12}, a_{22}, a_{32}, a_{13}, a_{23}, a_{33}$

Warm-Up Problem: Theater Ticket Sales Calculation

• Problem Scenario:

  • A theater auditorium contains 20 rows, with 30 seats in each row.

  • Each ticket costs $\text{₹}150$.

  • Tickets are sold seat by seat in row-major order (from left to right in a row, then proceeding to the first seat of the next row).

  • The last ticket sold was for Row 7, Seat 12.

• Step-by-Step Calculation:

  • Fully sold rows: Row 1 through Row 6 = $6\,rows$.

  • Total seats sold in full rows = $6 \times 30 = 180\,seats$.

  • Seats sold in Row 7 = Seats 1 through 12 = $12\,seats$.

  • Total tickets sold = $180 + 12 = 192\,tickets$.

  • Total money collected = $192 \times 150 = 28800\,rupees$ ($\text{₹}28800$).

Address Calculation in One-Dimensional (1D) Arrays

• Parameters and Definitions:

  • Base Address ($B$): The actual memory address of the first element in the array.

  • Element Width ($W$): The memory space acquired by each individual element in bytes.

  • Lower Bound ($LB$): The starting index or lower limit of the subscript (assumed to be $0$ if not explicitly provided).

  • Index ($\text{Index}$): The specific subscript location of the element whose address is being calculated.

• Address Calculation Formula:

  $\text{Address of } A[\text{Index}] = B + W \times (\text{Index} - LB)$

• Concrete Memory Example:

  • Given Base Address $B = 1100$.

  • Given Element Width $W = 4\,bytes$.

  • Given Lower Bound $LB = 0$.

  • Array Elements: $[15, 7, 11, 44, 93, 20]$ stored at indices $0, 1, 2, 3, 4, 5$.

  • Memory addresses calculated for each index:

  • Address of $A[0] = 1100 + 4 \times (0 - 0) = 1100$

  • Address of $A[1] = 1100 + 4 \times (1 - 0) = 1104$

  • Address of $A[2] = 1100 + 4 \times (2 - 0) = 1108$

  • Address of $A[3] = 1100 + 4 \times (3 - 0) = 1112$

  • Address of $A[4] = 1100 + 4 \times (4 - 0) = 1116$

  • Address of $A[5] = 1100 + 4 \times (5 - 0) = 1120$

Address Calculation in Two-Dimensional (2D) Arrays

• Row-Major Order Calculation:

  • Formula:

    $\text{Address of } A[I][J] = B + W \times (M \times (I - LR) + (J - LC))$

• Parameter Definitions:

  • $I$: Row index of the target element.

  • $J$: Column index of the target element.

  • $B$: Base address of the array.

  • $W$: Memory size of one array element in bytes.

  • $LR$: Lower limit of row index / starting row index (default is $0$ if omitted).

  • $LC$: Lower limit of column index / starting column index (default is $0$ if omitted).

  • $M$: Total number of columns in the matrix.

  • Column-Major Order Calculation:

• Formula:

    $\text{Address of } A[I][J] = B + W \times ((I - LR) + N \times (J - LC))$

• Parameter Definitions:

  • $N$: Total number of rows in the matrix.

  • All other parameters ($I$, $J$, $B$, $W$, $LR$, $LC$) carry identical definitions to the Row-Major Order formula.

Address Calculation in Multi-Dimensional (3D) Arrays

• Row-Major Order Formula for 3D Array $A[I][J][K]$:

  $\text{Address of } A[I][J][K] = B + W \times (N \times L \times (I - x) + L \times (J - y) + (K - z))$

• Column-Major Order Formula for 3D Array $A[I][J][K]$:

  $\text{Address of } A[I][J][K] = B + W \times (N \times L \times (I - x) + (J - y) + (K - z) \times N)$

• Parameter Definitions for 3D Array Formulas:

  • $B$: Base Address (start address of the array).

  • $W$: Weight / storage size of one element in bytes.

  • $N$: Height / Layer (total number of cells depth-wise).

  • $M$: Total number of rows.

  • $L$: Total number of columns.

  • $x$: Lower Bound of Row index ($LR$).

  • $y$: Lower Bound of Column index ($LC$).

  • $z$: Lower Bound of Height/Depth index ($LH$).

Peer Learning Activities and Problem Solutions

• Peer Learning Activity Design:

  • Group Structure: 6 members split into 3 pairs.

  • Task Distribution:

  • Pair 1: 1D Array Problem

  • Pair 2: 2D Array Row-Major Order Problem

  • Pair 3: 2D Array Column-Major Order Problem

  • Timing Protocol: Total 5 minutes (2 minutes individual problem-solving, followed by 3 minutes pair discussion and consensus).

  • Comparison Phase: Pairs present solutions to the entire group and compare formula structures across array types.

• Problem 1 (1D Array Address Calculation):

  • Problem Statement: An array $A[0 \dots 9]$ is stored in memory with base address $1000$. Each element takes $4\,bytes$. Find the address of $A[6]$.

  • Given Data: $B = 1000$, $W = 4\,bytes$, $LB = 0$, $\text{Index} = 6$

  • Derivation:

    $\text{Address}(A[6]) = B + W \times (\text{Index} - LB)$

    $\text{Address}(A[6]) = 1000 + 4 \times (6 - 0)$

    $\text{Address}(A[6]) = 1000 + 24 = 1024$

• Problem 2 (2D Array Row-Major Order Calculation):

  • Problem Statement: A matrix $B[0 \dots 3][0 \dots 4]$ is stored in row-major order. Base address = $2000$, element size = $2\,bytes$. Find the address of $B[2][3]$.

  • Given Data: $B = 2000$, $W = 2\,bytes$, $LR = 0$, $LC = 0$, $I = 2$, $J = 3$

  • Matrix Dimensions: Rows $0 \dots 3 \implies N = 4$, Columns $0 \dots 4 \implies M = 5$

  • Derivation:

    $\text{Address}(B[2][3]) = B + W \times (M \times (I - LR) + (J - LC))$

    $\text{Address}(B[2][3]) = 2000 + 2 \times (5 \times (2 - 0) + (3 - 0))$

    $\text{Address}(B[2][3]) = 2000 + 2 \times (5 \times 2 + 3)$

    $\text{Address}(B[2][3]) = 2000 + 2 \times (10 + 3) = 2000 + 26 = 2026$

• Problem 3 (2D Array Column-Major Order Calculation):

  • Problem Statement: A matrix $C[1 \dots 4][1 \dots 5]$ is stored in column-major order. Base address = $5000$, element size = $2\,bytes$. Find the address of $C[3][4]$.

  • Given Data: $B = 5000$, $W = 2\,bytes$, $LR = 1$, $LC = 1$, $I = 3$, $J = 4$

  • Matrix Dimensions: Rows $1 \dots 4 \implies N = 4 - 1 + 1 = 4$, Columns $1 \dots 5 \implies M = 5 - 1 + 1 = 5$

  • Derivation:

    $\text{Address}(C[3][4]) = B + W \times ((I - LR) + N \times (J - LC))$

    $\text{Address}(C[3][4]) = 5000 + 2 \times ((3 - 1) + 4 \times (4 - 1))$

    $\text{Address}(C[3][4]) = 5000 + 2 \times (2 + 4 \times 3)$

    $\text{Address}(C[3][4]) = 5000 + 2 \times (2 + 12) = 5000 + 28 = 5028$

Summary of Array Address Formulas

• 1D Array:

  • Formula: $\text{Addr}(A[\text{Index}]) = B + W \times (\text{Index} - LB)$

  • Parameters: $B$ = Base address, $W$ = Size of one element (bytes), $LB$ = Lower bound of index.

• 2D Array (Row-Major Order):

  • Formula: $\text{Addr}(A[I][J]) = B + W \times (M \times (I - LR) + (J - LC))$

  • Parameters: $B$ = Base address, $W$ = Element size, $LR$ = Row lower bound, $LC$ = Column lower bound, $M$ = Number of columns.

• 2D Array (Column-Major Order):

  • Formula: $\text{Addr}(A[I][J]) = B + W \times ((I - LR) + N \times (J - LC))$

  • Parameters: $N$ = Number of rows, all other symbols identical to Row-Major Order.

• 3D Array (Row-Major Order):

  • Formula: $\text{Addr}(A[I][J][K]) = B + W \times (N \times L \times (I - x) + L \times (J - y) + (K - z))$

  • Parameters: $B$ = Base address, $W$ = Element size, $N$ = Depth/Height, $M$ = Rows, $L$ = Columns, $x, y, z$ = Lower bounds for row, column, and depth.

• 3D Array (Column-Major Order):

  • Formula: $\text{Addr}(A[I][J][K]) = B + W \times (N \times L \times (I - x) + (J - y) + (K - z) \times N)$

  • Parameters: Identical parameter definitions to 3D Row-Major Order.

Assessment and Next Session Preview

• Learning Outcome Verification:

  • Confirmation of formula application for memory addresses across 1D, 2D, and 3D arrays.

  • Mastery of formula derivation steps for Row-Major and Column-Major memory layouts.

• Interactive Assessment Tools and Review:

  • Pre-Assessment Lecture 05 - DS

  • Post-Assessment Lecture 05 - DS

  • Interactive reinforcement tools: WooClap and WooFlash.

• Next Session Topics:

  • Practical Applications of Arrays

  • Sparse Matrices

  • Memory Representations of Sparse Matrices