## Assignment 5

Submission site  |  Show solution  |  Hide solution ]

Consider a matrix M of size 2k x 2k. A Z-listing of the elements of the matrix is described in the following figure. Part (a) illustrates the special case k = 3. Part (b) describes a recursive strategy for the Z-listing. First break M into four 2k-1 x 2k-1 submatrices and recursively print the submatrices in the order: "top-left", "top-right", "bottom-left" and "bottom-right". When the dimension of the matrix is 1 x 1, the only element of the matrix is printed without further recursive calls.

In this assignment, you are asked to populate a 2k x 2k matrix M with the integers 1,2,3,...,22k in such a manner that the Z-listing of M prints the integers 1,2,3,...,22k in sorted order.

Define a structure to represent a two-dimensional matrix.

```   #define MAXDIM 50
typedef struct {
unsigned int r;          /* row dimension */
unsigned int c;          /* column dimension */
int elt[MAXDIM][MAXDIM]; /* 2-d array of the elements of the matrix */
} matrix;
```

Part 1 [Credit: 20%]

Write a function that accepts a matrix as its sole argument and prints the matrix in the standard row-major order. Print a line break after every row of the matrix.

```   void printMat ( matrix M );
```

Now I provide a function that prints the Z-listing of the elements of a matrix. The function assumes that the matrix is of dimension 2k x 2k for some k. The function prints a new-line charater after printing 15 array elements in a line. This line-breaking is controlled by the second argument neltp passed to the function.

```   int printMatZ ( matrix M, int neltp )
{
matrix N;
int i,j,n;

/* No recursive calls are made for 1 x 1 matrices */
if (M.r == 1) {
printf("%5d", M.elt[0][0]);
if (++neltp == 15) { printf("\n"); neltp = 0; }
return neltp;
}

/* Set the dimensions of the submatrices */
n = (M.r) / 2;
N.r = N.c = n;

/* Recursively print the top left submatrix */
for (i=0; i<n; ++i) for (j=0; j<n; ++j) N.elt[i][j] = M.elt[i][j];
neltp = printMatZ(N,neltp);

/* Recursively print the top right submatrix */
for (i=0; i<n; ++i) for (j=0; j<n; ++j) N.elt[i][j] = M.elt[i][n+j];
neltp = printMatZ(N,neltp);

/* Recursively print the bottom left submatrix */
for (i=0; i<n; ++i) for (j=0; j<n; ++j) N.elt[i][j] = M.elt[n+i][j];
neltp = printMatZ(N,neltp);

/* Recursively print the bottom right submatrix */
for (i=0; i<n; ++i) for (j=0; j<n; ++j) N.elt[i][j] = M.elt[n+i][n+j];
neltp = printMatZ(N,neltp);

return neltp;
}
```

Part 2 [Credit: 60%]

You are now asked to write a recursive function initMatRec() that, upon input k, returns a 2k x 2k matrix whose Z-listing produces the integers 1,2,3,...,22k in sorted order. Assign values to the array elements in the same order they are printed by the function printMatZ() given above. You may maintain a global counter, or pass a pointer to an integer counter, that generates the integers 1,2,3,...,22k in that sequence.

```   matrix initMatRec ( unsigned int k, unsigned int *cnt );
```

Part 3: [Credit: 20%]

Write a function that returns the same matrix as initMatRec() without making any recursive call. Look at the pattern of the array elements for the case k = 3 below and generalize for higher dimensions. More precisely, initially set the top-left element to 1. Then for d = 0,1,2,...,k-1, make three copies with appropriate shifts of the 2d x 2d submatrix at the top-left corner so as to obtain the correct 2d+1 x 2d+1 submatrix at the top-left corner.

```   matrix initMatItr ( unsigned int k );
```

Your main() function should look like the following:

```   int main ()
{
matrix M, N;
unsigned int k;
unsigned int cnt = 0;

printf("k = "); scanf("%u", &k); printf("%u\n", k);

M = initMatRec(k,&cnt);
printf("\nRow-major listing of M:\n");
printMat(M);
printf("\nZ-listing of M:\n");
printMatZ(M,0);
printf("\n");

N = initMatItr(k);
printf("\nRow-major listing of N:\n");
printMat(N);
printf("\nZ-listing of N:\n");
printMatZ(N,0);
printf("\n");
}
```

Sample output

```   k = 3

Row-major listing of M:
1    2    5    6   17   18   21   22
3    4    7    8   19   20   23   24
9   10   13   14   25   26   29   30
11   12   15   16   27   28   31   32
33   34   37   38   49   50   53   54
35   36   39   40   51   52   55   56
41   42   45   46   57   58   61   62
43   44   47   48   59   60   63   64

Z-listing of M:
1    2    3    4    5    6    7    8    9   10   11   12   13   14   15
16   17   18   19   20   21   22   23   24   25   26   27   28   29   30
31   32   33   34   35   36   37   38   39   40   41   42   43   44   45
46   47   48   49   50   51   52   53   54   55   56   57   58   59   60
61   62   63   64

Row-major listing of N:
1    2    5    6   17   18   21   22
3    4    7    8   19   20   23   24
9   10   13   14   25   26   29   30
11   12   15   16   27   28   31   32
33   34   37   38   49   50   53   54
35   36   39   40   51   52   55   56
41   42   45   46   57   58   61   62
43   44   47   48   59   60   63   64

Z-listing of N:
1    2    3    4    5    6    7    8    9   10   11   12   13   14   15
16   17   18   19   20   21   22   23   24   25   26   27   28   29   30
31   32   33   34   35   36   37   38   39   40   41   42   43   44   45
46   47   48   49   50   51   52   53   54   55   56   57   58   59   60
61   62   63   64
```

Report the output of your program for k = 5.

Submission site  |  Show solution  |  Hide solution ]