TAOCP 2.2.3: Linked Allocation
Section 2.2.3 exercises: 28/28 solved.
Section 2.2.3. Linked Allocation
Exercises from TAOCP Volume 1 Section 2.2.3: 28/28 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | solved | 39s |
| 2 | [22] | medium | solved | 35s |
| 3 | [22] | medium | solved | - |
| 4 | [22] | medium | solved | - |
| 5 | [24] | medium | verified | 34s |
| 6 | [21] | medium | solved | 39s |
| 7 | [23] | medium | verified | 47s |
| 8 | [24] | medium | solved | 30s |
| 9 | [20] | medium | verified | 47s |
| 10 | [M21] | math-medium | verified | 35s |
| 11 | [24] | medium | solved | 3m37s |
| 12 | [M20] | math-medium | verified | 48s |
| 13 | [M48] | math-research | verified | 38s |
| 14 | [M21] | math-medium | verified | 33s |
| 15 | [M25] | math-medium | verified | 1m49s |
| 16 | [M22] | math-medium | verified | 29s |
| 17 | [21] | medium | solved | 34s |
| 18 | [20] | medium | verified | 1m52s |
| 19 | [18] | medium | solved | 41s |
| 20 | [24] | medium | verified | 40s |
| 21 | [21] | medium | verified | 45s |
| 22 | [23] | medium | solved | 5m29s |
| 23 | [27] | hard | verified | 1m07s |
| 24 | [24] | medium | solved | 38s |
| 25 | [47] | research | solved | 1m03s |
| 26 | [29] | hard | solved | 44s |
| 27 | [25] | medium | solved | 5m34s |
| 28 | [40] | project | solved | 7m58s |
TAOCP 2.2.3 Exercise 1
Operation (8) does not mention `OVERFLOW` because it assumes that a new node can always be obtained from the `AVAIL` stack or the storage pool.
TAOCP 2.2.3 Exercise 2
We are asked to write a general-purpose MIX subroutine to perform the linked-stack insertion operation corresponding to equation (10).
TAOCP 2.2.3 Exercise 3
We are asked to write a general-purpose MIX subroutine to perform the deletion operation from a linked stack, corresponding to operation (9) in Section 2.
TAOCP 2.2.3 Exercise 4
In program (10), overflow is detected by LD1 AVAIL J1Z OVERFLOW When `AVAIL = Λ`, register `rI1` contains zero and control passes to `OVERFLOW`.
TAOCP 2.2.3 Exercise 5
Let the queue be represented by link variables `F` and `R`, pointing respectively to the front and rear nodes of the queue, with the convention that `F = \Lambda` if and only if the queue is empty.
TAOCP 2.2.3 Exercise 6
In operation (14), a new node is inserted at the rear of the queue.
TAOCP 2.2.3 Exercise 7
Let the linked list be represented by the pointer `FIRST` to the first node, and assume each node has fields `INFO` and `LINK` as in (3).
TAOCP 2.2.3 Exercise 8
Let the linked linear list be represented by the pointer `FIRST`, with each node containing the fields `INFO` and `LINK` as in (3).
TAOCP 2.2.3 Exercise 9
A relation $\preceq$ is a partial ordering if and only if it is reflexive, antisymmetric, and transitive.
TAOCP 2.2.3 Exercise 10
Assume that the relation "$\subset$" satisfies properties (i) and (ii) of a partial ordering, namely: (i) Transitivity: x \subset y,\ y \subset z \implies x \subset z.
TAOCP 2.2.3 Exercise 11
Let the directed graph of Fig.
TAOCP 2.2.3 Exercise 12
Let $S$ be a set of $n$ elements.
TAOCP 2.2.3 Exercise 13
Let $B_n$ denote the family of all $2^n$ subsets of an $n$-element set, partially ordered by inclusion.
TAOCP 2.2.3 Exercise 14
Assume first that $\preceq$ is a linear ordering on the finite set $S$.
TAOCP 2.2.3 Exercise 15
Let $(S,\preceq)$ be a partially ordered set.
TAOCP 2.2.3 Exercise 16
Let $S = {x_1, \dots, x_n}$ be a finite set with a partial ordering $\preceq$, and let $(a_{ij})$ be its incidence matrix defined by a_{ij} = \begin{cases} 1,& \text{if } x_i \preceq x_j,\\ 0,& \text{...
TAOCP 2.2.3 Exercise 17
Exercise 2.
TAOCP 2.2.3 Exercise 18
Algorithm `T` of Section 2.
TAOCP 2.2.3 Exercise 19
In Algorithm `T`, the front element of the queue is examined in step `T5`, but it remains on the queue until step `T7`.
TAOCP 2.2.3 Exercise 20
Yes.
TAOCP 2.2.3 Exercise 21
Algorithm `T` in Section 2.
TAOCP 2.2.3 Exercise 22
Program `T` should reject any input that violates the assumptions under which the algorithm was designed.
TAOCP 2.2.3 Exercise 23
Algorithm `T` performs a topological sort on a directed graph whose vertices are the objects being ordered and whose relations are the pairs $j \prec k$ represented in the successor lists.
TAOCP 2.2.3 Exercise 24
Program `T` in Section 2.
TAOCP 2.2.3 Exercise 25
Let $S$ be a finite partially ordered set whose ordering relation is given as a collection of pairs $(u,v)$, meaning $u<v$.
TAOCP 2.2.3 Exercise 26
We are asked to design an algorithm to determine the relocation addresses for a set of subroutines to be loaded from a tape library, taking into account the dependencies among subroutines.