Two-Dimensional Arrays and Address Calculation (ISC Class 12 Computer Science)

Understand Two-Dimensional Arrays and Address Calculation

Two-Dimensional Arrays and Address Calculation: key facts

Row-major address

• •Address = B + w x [(i - l1) x N + (j - l2)]
• •N = u2 - l2 + 1 columns
• •Elements are stored row by row

B is the address of A[l1][l2].

Column-major address

• •Address = B + w x [(j - l2) x M + (i - l1)]
• •M = u1 - l1 + 1 rows
• •Elements are stored column by column

Swap the roles of rows and columns.

Size of the array

• •Elements = M x N
• •Bytes = M x N x w
• •Last element is at index M x N - 1 from the base

Use it to check the answer.

Java matrix facts

• •new int[r][c] has r x c elements
• •m.length = rows
• •m[0].length = columns
• •Diagonals: m[i][i] and m[i][n-1-i]

Indices start at 0.

How to answer Two-Dimensional Arrays and Address Calculation questions

1. 1Write the bounds l1, u1, l2, u2 and the element size w and the base B.
2. 2Calculate M = u1 - l1 + 1 and N = u2 - l2 + 1.
3. 3Write the formula for row-major or column-major as asked, with the numbers substituted.
4. 4Compute the number of elements before the target, then multiply by w.
5. 5Add the base address and give the units if mentioned.
6. 6Check the result lies inside the array and compare with the other order if asked.

Two-Dimensional Arrays and Address Calculation in real life

The idea, met in an everyday situation. Answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Tricks to remember Two-Dimensional Arrays and Address Calculation

Short memory aids. Say each one aloud once, then use it on a question the same day.

• Row-major = rows times columns-count

  Skip complete rows: (i - l1) times N, then walk j - l2 along the row.

  Use it when: Row-major formula.

• Column-major = columns times rows-count

  Skip complete columns: (j - l2) times M, then walk i - l1 down the column.

  Use it when: Column-major formula.

• Count from the lower bound

  Every index is measured from its lower bound, never from zero.

  Use it when: Non-zero or negative bounds.

• N is columns, M is rows

  N for the number of columns that makes a row long; M for the number of rows.

  Use it when: Choosing M and N.

Two-Dimensional Arrays and Address Calculation: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

int[][] m = {{2, 7, 1}, {4, 5, 9}, {3, 8, 6}};
int d = 0, a = 0, r = 0;
for (int i = 0; i < 3; i++) {
    d += m[i][i];
    a += m[i][2 - i];
    r += m[1][i];
}
System.out.println(d + " " + a + " " + r);

Where students lose marks in Two-Dimensional Arrays and Address Calculation

The slips examiners see most often, and what to write instead.

• ✗Mistake: Using the wrong bound for N or M

  N is the number of columns, M the number of rows; a swap changes the answer.

  Wrong working

  Row-major with M instead of N

  Right working

  Row-major uses N (columns); column-major uses M (rows)

  ✓Do this: Write M and N from the bounds first.

  Usually costs: 1 mark

• ✗Mistake: Forgetting the lower bound

  Positions are counted from the lower bound, not from zero.

  Wrong working

  A[1..5][1..4], element A[3][2]: (3 x 4 + 2)

  Right working

  (3 - 1) x 4 + (2 - 1) = 9

  ✓Do this: Subtract l1 and l2 every time.

  Usually costs: 1 mark

• ✗Mistake: Using u - l instead of u - l + 1

  The number of values from l to u includes both ends.

  Wrong working

  N = 6 - 2 = 4 for columns 2 to 6

  Right working

  N = 6 - 2 + 1 = 5

  ✓Do this: Always add 1.

  Usually costs: 1 mark

Practice questions on Two-Dimensional Arrays and Address Calculation

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · MCQBoard level

   Elements stored column after column are said to be in
   (a) row-major order (b) column-major order (c) sorted order (d) heap order

   Hint

   Named after the unit that is stored together.

   Answer

   (b) column-major order

2. Q2 · 2 marks · Short answerBoard level

   For int[][] b = new int[4][3]; write b.length, b[0].length and the total number of elements.

   Hint

   First size is rows.

   Answer

   b.length = 4 (rows), b[0].length = 3 (columns), total 4 x 3 = 12 elements.

3. Q3 · 4 marks · Short answerHarder board level

   An array A[0..9][0..7] stores 4-byte elements with base address 3000. Find the address of A[6][5] in row-major and column-major order.

   Hint

   M = 10, N = 8.

   Answer

   M = 10, N = 8. Row-major: 6 x 8 + 5 = 53 elements before, so 3000 + 4 x 53 = 3212. Column-major: 5 x 10 + 6 = 56 elements before, so 3000 + 4 x 56 = 3224.

4. Q4 · 4 marks · Short answerHarder board level

   M[-2..3][-1..2] stores 8-byte elements with base address 100. Find the address of M[1][0] in row-major and column-major order.

   Hint

   Rows = 6, columns = 4.

   Answer

   M = 3 - (-2) + 1 = 6 rows; N = 2 - (-1) + 1 = 4 columns. Row-major: (1 + 2) x 4 + (0 + 1) = 13 elements before; 100 + 8 x 13 = 204. Column-major: (0 + 1) x 6 + (1 + 2) = 9; 100 + 8 x 9 = 172.

5. Q5 · 4 marks · Case-basedHOTS / competency

   A program transposes a 2 x 3 matrix:

   int[][] a = {{1, 2, 3}, {4, 5, 6}};
   int[][] t = new int[3][2];
   for (int i = 0; i < 2; i++)
       for (int j = 0; j < 3; j++)
           t[j][i] = a[i][j];
   for (int i = 0; i < 3; i++) {
       for (int j = 0; j < 2; j++)
           System.out.print(t[i][j] + " ");
       System.out.println();
   }

   (i) Write the output. (ii) Why must t be declared as [3][2] and not [2][3]?

   Hint

   Rows become columns.

   Answer

   (i) The output lines are:
   1 4
   2 5
   3 6
   (ii) Transposing turns the 2 rows and 3 columns of a into 3 rows and 2 columns of t; with [2][3] the assignment t[j][i] with j up to 2 would go out of bounds and throw ArrayIndexOutOfBoundsException.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.What is the row-major formula?Show answer

   B + w x [(i - l1) x N + (j - l2)].

2. 2.What is the column-major formula?Show answer

   B + w x [(j - l2) x M + (i - l1)].

3. 3.How many columns does A[2..7][3..9] have?Show answer

   7.

4. 4.How does Java store a 2-D array?Show answer

   As rows (row-major in practice).

5. 5.How do you get the number of rows of m in Java?Show answer

   m.length.

6. 6.Which element of a 3 x 3 matrix is on the other diagonal in row i?Show answer

   m[i][2 - i].

Two-Dimensional Arrays and Address Calculation: frequently asked questions