GENERAL FORMULATION OF MX QUADTREE MATRIX REPRESENTATION HOMEWORK

Give an algorithm to transpose a $2^n \times 2^n$ matrix that is
represented as an MX quadtree using its tree access structure.  Assume
the worst case of the matrix which occurs when there is no
sparseness (i.e., all blocks are of size 1).  Compare the cost of 
representing a square matrix with an MX quadtree to that using an
array and also the time required by these two representations to
perform the transpose operation.  Do you see any interesting behavior?

MORE PRECISE FORMULATION OF MX QUADTREE MATRIX REPRESENTATION HOMEWORK:

1.  Give an algorithm to transpose a $2^n \times 2^n$ matrix that is
    represented as an MX quadtree using its tree access structure.
    Assume the worst case of the matrix which occurs when there is no
    sparseness (i.e., all blocks are of size 1). 

2.  Give the time requirements for this algorithm.  

3.  What is the cost of representing a $2^n \times 2^n$ square matrix
    with no sparseness as an MX quadtree. 

4.  Compare the cost of representing a square matrix with an MX
    quadtree to that using an array and also the time required by
    these two representations to perform the transpose operation.  Do
    you see any interesting behavior?