TAOCP 2.2.2: Sequential Allocation
Section 2.2.2 exercises: 19/19 solved.
Section 2.2.2. Sequential Allocation
Exercises from TAOCP Volume 1 Section 2.2.2: 19/19 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [15] | simple | solved | - |
| 2 | [22] | medium | solved | - |
| 3 | [21] | medium | solved | - |
| 4 | [25] | medium | verified | 3m08s |
| 5 | [35] | hard | solved | - |
| 6 | [10] | simple | solved | - |
| 7 | [12] | simple | solved | - |
| 8 | [26] | hard | solved | - |
| 9 | [M27] | math-hard | solved | - |
| 10 | [M28] | math-hard | solved | - |
| 11 | [M30] | math-hard | solved | - |
| 12 | [M28] | math-hard | solved | - |
| 13 | [HM42] | hm-project | solved | - |
| 14 | [HM43] | hm-project | solved | - |
| 15 | [40] | project | solved | - |
| 16 | [20] | medium | solved | 46s |
| 17 | [30] | hard | solved | 44s |
| 18 | [M30] | math-hard | solved | 46s |
| 19 | [16] | medium | solved | 45s |
TAOCP 2.2.2 Exercise 1
Let $X[1], \ldots, X[M]$ be the memory locations for the queue, with `F` and `R` the front and rear pointers, respectively, as in (6a) and (7a).
TAOCP 2.2.2 Exercise 2
In addition to the front pointer `F` and rear pointer `R`, introduce the convention that the deque occupies the circular array `X[1],\ldots,X[M]`, with `F` pointing to the front element and `R` to the...
TAOCP 2.2.2 Exercise 3
The purpose of (8) is to replace fixed-base addressing by relative addressing when the base location $L_0$ varies.
TAOCP 2.2.2 Exercise 4
The flaw in the previous solution is the assumption that link traversal alone can accumulate multiple index register contributions during effective address formation.
TAOCP 2.2.2 Exercise 5
Exercise 3 introduces address modifications of the form `I1:I2`, where modification 7 means: interpret the addressed location as another address specification and continue the address-modification pro...
TAOCP 2.2.2 Exercise 6
Using the memory configuration of Fig.
TAOCP 2.2.2 Exercise 7
Step `G4` of Algorithm `G` sets \alpha \leftarrow 0.
TAOCP 2.2.2 Exercise 8
We are asked to extend the sequential allocation scheme for multiple stacks, as described by equations (9) and (10) and the repacking algorithm (Algorithm G), to the case in which one or more of the l...
TAOCP 2.2.2 Exercise 9
Let the successive operations be represented by a sequence a_1,a_2,\ldots,a_m, where each $a_t$ denotes the stack on which the $t$th insertion is performed.
TAOCP 2.2.2 Exercise 10
Let $n$ denote the number of sequential stacks, and let $m$ denote the total number of insertions $a_1, a_2, \ldots, a_m$, where $a_j \in {1, 2, \ldots, n}$ specifies the stack chosen for the $j$th in...
TAOCP 2.2.2 Exercise 11
Let $n$ be the number of stacks and $m$ the total number of insertions performed, as in exercise 9.
TAOCP 2.2.2 Exercise 12
Let $a_1,a_2,\ldots,a_m$ be a sequence of insertions as in exercise 9, with $n=2$.
TAOCP 2.2.2 Exercise 13
Let $(k_1,k_2)$ denote the numbers of occupied locations in the two tables when the process terminates.
TAOCP 2.2.2 Exercise 14
Let E_m=\frac{m!
TAOCP 2.2.2 Exercise 15
The exercise asks for an empirical evaluation of Algorithm $G$ under varying stochastic patterns of insertions and deletions.
TAOCP 2.2.2 Exercise 16
No.
TAOCP 2.2.2 Exercise 17
Let C=L_\infty-L_0 be the total amount of available memory.