TAOCP 2.3.5: Lists and Garbage Collection
Section 2.3.5 exercises: 12/12 solved.
Section 2.3.5. Lists and Garbage Collection
Exercises from TAOCP Volume 1 Section 2.3.5: 12/12 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 1m01s | |
| 2 | [**] | verified | 1m11s | |
| 3 | [**] | solved | 5m42s | |
| 4 | [**] | solved | 3m06s | |
| 5 | [**] | solved | 2m54s | |
| 6 | [**] | verified | 43s | |
| 7 | [**] | verified | 1m14s | |
| 8 | [**] | verified | 2m19s | |
| 9 | [**] | verified | 1m13s | |
| 10 | [**] | verified | 1m07s | |
| 11 | [**] | verified | 3m08s | |
| 12 | [**] | verified | 1m09s |
TAOCP 2.3.5 Exercise 1
A List can be described as a directed graph in which each node corresponds to a List element or atom, and each pointer (`DLINK`, `RLINK`, or `LLINK`) corresponds to a directed edge from one node to an...
TAOCP 2.3.5 Exercise 2
Yes, List structures can be threaded analogously to trees.
TAOCP 2.3.5 Exercise 3
Let the root node be $P$.
TAOCP 2.3.5 Exercise 4
**Corrected Solution to Exercise 2.
TAOCP 2.3.5 Exercise 5
A correct solution must first remove the ambiguity in the previous attempt: there is only one active control mechanism at any time, and “E-mode” is not a second concurrent process.
TAOCP 2.3.5 Exercise 6
The term $c_2 M$ arises from the tracing phase of the garbage collection procedure, in which all nodes that are reachable from the list heads are marked by following their structural links.
TAOCP 2.3.5 Exercise 7
Let $x$ denote the current node.
TAOCP 2.3.5 Exercise 8
We give a fully precise in-place DFS marking algorithm that works for variable-size nodes and uses no auxiliary stack beyond the existing link fields.
TAOCP 2.3.5 Exercise 9
Let $K \leftarrow 0$.
TAOCP 2.3.5 Exercise 10
Use the `REF` fields temporarily to record the correspondence between original nodes and copied nodes.