Data Structures, Algorithms, & Applications in C++
Chapter 7, Exercise 1

(a)

The row-major ordering of the indexes is:

[0][0][0][0] [0][0][0][1] [0][0][1][0] [0][0][1][1]


[0][1][0][0] [0][1][0][1] [0][1][1][0] [0][1][1][1]


[0][2][0][0] [0][2][0][1] [0][2][1][0] [0][2][1][1]


[1][0][0][0] [1][0][0][1] [1][0][1][0] [1][0][1][1]


[1][1][0][0] [1][1][0][1] [1][1][1][0] [1][1][1][1]


[1][2][0][0] [1][2][0][1] [1][2][1][0] [1][2][1][1]

(b)

Let the dimensions be u1, u2, u3, and u4. In a row-major mapping, the u2 u3 u4 elements with first index equal to zero come first. These are followed by the elements with first index equal to 1 and so on. So, the elements with first index i1 are preceded by i1 u2 u3 u4 elements that have a smaller first index. Each block of elements with the same first index is stored in row-major order also. Since each block is a three dimensional array, we may use the formula for a three dimensional array to get the position of an element withing a block of elements with the same first dimension. If the second, third, and fourth indices are i2, i3, and i4, then the element position in the i1 block is i2 u3 u4 + i3 u4 + i4. As a result,

map(i1, i2, i3, i4) = i1 u2 u3 u4 + i2 u3 u4 + i3 u4 + i4