TAOCP 2.2.6: Arrays and Orthogonal Lists
Section 2.2.6 exercises: 24/24 solved.
Section 2.2.6. Arrays and Orthogonal Lists
Exercises from TAOCP Volume 1 Section 2.2.6: 24/24 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | solved | 33s | |
| 2 | ▶ [**] | solved | 46s | |
| 3 | [**] | solved | 29s | |
| 4 | [**] | solved | 29s | |
| 5 | [**] | solved | 36s | |
| 6 | ▶ [**] | solved | 36s | |
| 7 | [**] | solved | 36s | |
| 8 | [**] | solved | 37s | |
| 9 | [**] | solved | 36s | |
| 10 | [**] | solved | 34s | |
| 11 | [**] | solved | 34s | |
| 12 | ▶ [**] | solved | 38s | |
| 13 | ▶ [**] | solved | 37s | |
| 14 | [**] | solved | 33s | |
| 15 | ▶ [**] | solved | 36s | |
| 16 | [**] | solved | 31s | |
| 17 | [**] | solved | 28s | |
| 18 | [**] | solved | 34s | |
| 19 | [**] | solved | 30s | |
| 20 | [**] | solved | 32s | |
| 21 | [**] | solved | 27s | |
| 22 | [**] | solved | 35s | |
| 23 | [**] | solved | 41s | |
| 24 | ▶ [**] | solved | 37s |
TAOCP 2.2.6 Exercise 1
Let the matrix (1) have indices $0 \le J \le m$ and $0 \le K \le n$, and suppose each node occupies $c=2$ words.
TAOCP 2.2.6 Exercise 2
Suppose we have a $k$-dimensional array `A[I_1,I_2,\ldots,I_k]` with $l_r \le I_r \le u_r$ for $1 \le r \le k$.
TAOCP 2.2.6 Exercise 3
If the lower triangular matrix is indexed by $1 \le k \le j \le n$, the lexicographic order becomes A[1,1],\; A[2,1],A[2,2],\; \ldots,\; A[n,1],A[n,2],\ldots,A[n,n].
TAOCP 2.2.6 Exercise 4
In lexicographic order, the elements are stored as A[0,0],A[0,1],\ldots,A[0,n],A[1,1],A[1,2],\ldots,A[1,n],\ldots,A[n,n].
TAOCP 2.2.6 Exercise 5
Let `J` and `K` be stored in index registers `I1` and `I2`, respectively.
TAOCP 2.2.6 Exercise 6
For the array `A[i,j,k]` with $0 \le k \le j \le i \le n$, storing the elements in lexicographic order of the indices means that `k` varies fastest, then `j`, then `i`.
TAOCP 2.2.6 Exercise 7
Let T_k(n)=\#\{(i_1,\ldots,i_k):0\le i_k\le\cdots\le i_1\le n\}.
TAOCP 2.2.6 Exercise 8
We can generalize the two-dimensional trick of equation (10) to the case of six tetrahedral arrays `A[I,J,K]`, `B[I,J,K]`, `C[I,J,K]`, `D[I,J,K]`, `E[I,J,K]`, `F[I,J,K]`.
TAOCP 2.2.6 Exercise 9
Let `RESULT` be initially empty.
TAOCP 2.2.6 Exercise 10
A more efficient organization of the personnel table can be obtained by employing _orthogonal indexing_ rather than single-directional linked lists.
TAOCP 2.2.6 Exercise 11
Each nonzero entry is represented by a node containing three words.
TAOCP 2.2.6 Exercise 12
In the notation of (13), let the pivot element be $a$, let the other nonzero elements in the pivot row be represented by the coefficients $b$, and let the other nonzero elements in the pivot column be...
TAOCP 2.2.6 Exercise 13
Circular lists are used because they eliminate end-of-list cases.
TAOCP 2.2.6 Exercise 14
In a sequential representation of a sparse matrix, the nonzero entries of each row may be stored consecutively, together with their column indices.
TAOCP 2.2.6 Exercise 15
A direct transcription of Algorithm $S$ into MIXAL is possible if the fields `ROW`, `COL`, `VAL`, `LEFT`, and `UP` are assigned fixed offsets within each node, and if the floating-point instructions `...
TAOCP 2.2.6 Exercise 16
Let `A` be the given sparse matrix represented with circularly linked row and column lists, with head nodes `BASEROW[i]` and `BASECOL[j]`.
TAOCP 2.2.6 Exercise 17
Let the matrices be represented by orthogonal circular lists as in Fig.
TAOCP 2.2.6 Exercise 18
We begin with the given upper-triangular matrix A = \begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix}.
TAOCP 2.2.6 Exercise 19
The matrix should remain in the sparse orthogonal-list representation throughout.
TAOCP 2.2.6 Exercise 20
A tridiagonal matrix contains exactly the elements $A[I,J]$ for which $|I-J|\le 1$.
TAOCP 2.2.6 Exercise 21
Since $n$ is variable, the allocation function must encode the size of the matrix together with the indices.
TAOCP 2.2.6 Exercise 22
For $k=2$, the classical Cantor polynomial p(i_1,i_2)=\frac{(i_1+i_2)(i_1+i_2+1)}2+i_2 has the required property.