TAOCP 2.2.4: Circular Lists
Section 2.2.4 exercises: 18/18 solved.
Section 2.2.4. Circular Lists
Exercises from TAOCP Volume 1 Section 2.2.4: 18/18 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [21] | medium | solved | 32s |
| 2 | [20] | medium | verified | 1m34s |
| 3 | [20] | medium | solved | 44s |
| 4 | [20] | medium | solved | 7m26s |
| 5 | [21] | medium | solved | 39s |
| 6 | [18] | medium | solved | 35s |
| 7 | [10] | simple | verified | 44s |
| 8 | [10] | simple | verified | 45s |
| 9 | [23] | medium | solved | 5m33s |
| 10 | [20] | medium | solved | 39s |
| 11 | [24] | medium | verified | 45s |
| 12 | [21] | medium | solved | 43s |
| 13 | [20] | medium | solved | 34s |
| 14 | [22] | medium | verified | 3m01s |
| 15 | [24] | medium | solved | 43s |
| 16 | [M28] | math-hard | solved | 1m25s |
| 17 | [22] | medium | solved | 35s |
| 18 | [25] | medium | solved | 36s |
TAOCP 2.2.4 Exercise 1
Let the empty circular list be represented by PTR = LOC(PTR), instead of
TAOCP 2.2.4 Exercise 2
Let $L_1$ consist of nodes a_1, a_2, \dots, a_m, with pointer $\mathrm{PTR}_1 = a_m$ and
TAOCP 2.2.4 Exercise 3
Let the circular list be N_1 \to N_2 \to \cdots \to N_k \to N_1, and suppose both `PTR₁` and `PTR₂` point to nodes of this same list.
TAOCP 2.2.4 Exercise 4
In representation (4), a circular linked list is maintained with a distinguished head node `HEAD`.
TAOCP 2.2.4 Exercise 5
Let a circular list be represented as in (1), with `PTR` pointing to the last node, so that `LINK(PTR)` points to the first node.
TAOCP 2.2.4 Exercise 6
Each polynomial is represented by a circular list whose nodes are arranged in decreasing order of the field `ABC`.
TAOCP 2.2.4 Exercise 7
The decreasing order of the `ABC` fields makes it possible to combine two polynomials efficiently by a single systematic scan through their lists.
TAOCP 2.2.4 Exercise 8
The pointer `Q1` trails `Q` by one node to simplify insertions and deletions in `polynomial(Q)`.
TAOCP 2.2.4 Exercise 9
Algorithm `A` does **not** work properly when `P = Q`.
TAOCP 2.2.4 Exercise 10
We wish to adapt Algorithms `A` (addition) and `M` (multiplication) for polynomials in a single variable $x$, allowing exponents up to $b^3 - 1$.
TAOCP 2.2.4 Exercise 11
We are asked to create a subroutine `COPY` that produces a complete duplicate of a given polynomial represented as a circularly linked list with a sentinel node, preserving the original list and retur...
TAOCP 2.2.4 Exercise 12
Let $n$ be the number of nonzero terms of `polynomial(P)`.
TAOCP 2.2.4 Exercise 13
We are asked to write a subroutine `ERASE` that adds a polynomial, represented as a circular list with a sentinel node, to the `AVAIL` list.
TAOCP 2.2.4 Exercise 14
In the representation used in §2.
TAOCP 2.2.4 Exercise 15
We are asked to design an efficient algorithm to "erase" an entire circular list by placing all its nodes onto the `AVAIL` stack.
TAOCP 2.2.4 Exercise 16
Let - $p$ denote the number of nonzero terms of `polynomial(P)`, - $q$ denote the number of nonzero terms of `polynomial(Q)` at entry, - $m$ denote the number of nonzero terms of `polynomial(M)`.
TAOCP 2.2.4 Exercise 17
The principal advantage is that the circular representation eliminates special cases at the ends of the list.
TAOCP 2.2.4 Exercise 18
Represent the circular list by storing in each node $x_i$ a single link field L(x_i)=\operatorname{addr}(x_{i-1})\oplus \operatorname{addr}(x_{i+1}), where $\oplus$ denotes bitwise exclusive-or of mac...