1. Consider matrix M shown in Figure 1. Each row has exactly four Xs. Matrix M has the property that we can permute the rows and columns of M so that we group all of the Xs in each row into a single run (block) of Xs; and so that those blocks overlap to form a tiling of the columns. Figure 2 shows one such permutation of the rows and columns, resulting in the matrix M. To be more precise about the meaning of a tiling, reading top to bottom in M, the blocks in the tiling start at the right end of the matrix; extend to the left end; each block overlaps with the block immediately below it; and the ends of each block are either the same as, or to the right of, the block immediately below it. So, the tiling looks like an uneven staircase. Definition: We say that a matrix M, where each row has the same number of Xs, is tilable if and only its rows and columns can be permuted to create a tiling of the columns of M.

Problem 1: Give an example of a matrix with the same number of Xs in each row, that is not tilable. Give a convincing argument that the matrix really is not tilable.

Problem 2: In the example above, several of the rows are identical. Explain why we can remove rows so that only one copy of each identical row remains, without changing the tilability of the matrix. So, if we want to determine if a matrix is tilable, we can assume that each row is distinct, i.e.,there are no identical rows.

Problem 3: Give an simple, efficient algorithm to take in a matrix M, where each row has the same number of Xs, and determine if the matrix is tilable. If the matrix is tilable, the algorithm should produce a permutation of the rows and columns of M that create the matrix M, and a tiling of

1

M

abcdefghijklmnopqrs

1: --X------------XXX-

2: -X---X------X-----X

3: ---X---X-X---X-----

4: X----X---------XX--

5: ---X---X-X---X-----

6: ----X-X---XX-------

7: -X----X-----X-----X

8: -------XX--X--X----

9: ----X-X---X-X------

10: ----X-X---XX-------

11: ---X---X-X---X-----

12: -------XX--X--X----

13: -X----X-----X-----X

14: -X---X------X-----X

15: ---X---X-X---X-----

Figure 1: The given input matrix

M

.

it. Give an argument that your algorithm is always correct, and explain why

you think it is efficient.

crpqafbsmgekliohdjn

15: ---------------XXXX

11: ---------------XXXX

5: ---------------XXXX

3: ---------------XXXX

12: ------------XXXX---

8: ------------XXXX---

10: ---------XXXX------

6: ---------XXXX------

9: --------XXXX-------

13: ------XXXX---------

7: ------XXXX---------

14: -----XXXX----------

2: -----XXXX----------

4: --XXXX-------------

1: XXXX---------------

Figure 2: A permutation of the rows and columns of M, creating matrix

M

, so that in each row, all of the Xs appear in a single run (block), and so

that the blocks form a successively overlapping tiling of the columns. The

blocks form an uneven staircase.