Data Structures, Algorithms, & Applications in Java
Chapter 8, Exercise 35

(a)

A sample antidiagonal matrix is given below:

0 0 0 1
0 0 3 0
0 0 0 0
6 0 0 0


(b)

In an antidiagonal matrix there can be at most one nonzero entry in each row; for row i, this nonzero entry is in column n+1-i. Therefore, an n x n antidiagonal matrix can have at most n nonzero entries. A test program and output appear in the files AntidiagonalMatrix.*.

(c)

We can put the antidiagonal element M(i, n+1-j) in position i-1 of a one-dimensional array.

(d)

The code for the class is given below.

---

public class AntidiagonalMatrix
{
   // data members
   int rows;            // matrix dimension
   int rowsPlus1;       // rows + 1
   Object zero;         // zero element
   Object [] element;   // element array

   // constructor
   public AntidiagonalMatrix(int theRows, Object theZero)
   {
      // validate theRows
      if (theRows < 1)
         throw new IllegalArgumentException
               ("number of rows must be > 0");
   
      // create and initialize the matrix
      rows = theRows;
      zero = theZero;
      rowsPlus1 = rows + 1;
      element = new Object [rows];
      for (int i = 0; i < rows; i++)
         element[i] = zero;
   }
   
   // methods
   /** throws IndexOutOfBoundsException when i < 1
     * or j < 1 or i > rows or j > rows */
   void checkIndex(int i, int j)
   {
      if (i < 1 || j < 1 || i > rows || j > rows)
         throw new IndexOutOfBoundsException
                   ("i = " + i + " j = " + j +
                    " rows = " + rows + " cols = " + rows);
   }

   /** return the element this(i,j)
     * throws IndexOutOfBoundsException when i or j invalid */
   public Object get(int i, int j)
   {
      checkIndex(i, j);

      // determine element to return
      if (i + j == rowsPlus1)
         return element[i - 1];  // antidiagonal element
      else return zero;          // nonantidiagonal element
   }
   
   /** set this(i,j) = newValue
     * throws IndexOutOfBoundsException when i or j invalid */
   public void set(int i, int j, Object newValue)
   {
      checkIndex(i, j);

      if (i + j == rowsPlus1)
         // save the antidiagonal element
         element[i - 1] = newValue;
      else
         // newValue should be zero
         if (!((Zero) newValue).equalsZero())
            throw new IllegalArgumentException
                  ("nonantidiagonal elements must be zero");
   }
}

---

(e)

The complexity of each statement of the store and retrieve methods is O(1). Since neither of these methods has a loop in it, the complexity of each method is also O(1).