Question 1:

Letting $a_{ij}$ and $b_{ij}$ denote the elements of
row $i$ and column $j$ of matrices $A$ and $B$, respectively, then the
transpose of matrix $A$
is the matrix $B$ with $b_{ij}=a_{ji}$.

1. Give an algorithm to transpose a matrix represented by an MX quadtree.

2. How many interchange operations are needed to transpose an MX
quadtree representation of a $2^n \times 2^n$ matrix so that it is not
sparse (i.e., all blocks are of size 1)?'

3. Compare the savings in space and time requirements when a
matrix is represented as an MX quadtree and as an array.
Use the time required to perform a transpose
operation as the basis of the comparison.
You should assume the worst case which occurs when there is no
sparseness (i.e., all blocks are of size 1).

4. Give an algorithm for multiplying two matrices
stored as MX quadtrees.

--------------------------------------------------------------------

Question 2:

A region quadtree on a checker-board image $B$ essentially resembles a 
MX quadtree on $B$. How do you represent the image more compactly ?