TAOCP 2.2.6 Exercise 11
Each nonzero entry is represented by a node containing three words.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 11. [**] [11] Suppose that we have a $200 \times 200$ matrix in which there are at most four nonzero entries per row. How much storage is required to represent this matrix as in Fig. 14, if we use three words per node except for list heads, which will use one word?
Verified: no
Solve time: 34s
Each nonzero entry is represented by a node containing three words. Since there are at most four nonzero entries per row in a $200 \times 200$ matrix, the total number of nonzero entries is at most
$$ 200 \cdot 4 = 800. $$
Hence the storage required for matrix entries is
$$ 800 \cdot 3 = 2400 $$
words.
There are also list heads for every row and column. Since the matrix has $200$ rows and $200$ columns, there are
$$ 200 + 200 = 400 $$
list heads, each using one word. Therefore the total storage required is
$$ 2400 + 400 = 2800 $$
words.
Thus the sparse representation requires at most
$$ \boxed{2800\text{ words}}. $$