TAOCP 5.4.8: Two-Tape Sorting
Section 5.4.8 exercises: 10/10 solved.
Section 5.4.8. Two-Tape Sorting
Exercises from TAOCP Volume 3 Section 5.4.8: 10/10 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [20] | medium | solved | 2m35s |
| 2 | [M26] | math-hard | verified | 2m55s |
| 3 | [38] | project | verified | 50s |
| 4 | [M23] | math-medium | solved | 1m04s |
| 5 | ▶ [M23] | math-medium | solved | 6m25s |
| 6 | [M30] | math-hard | solved | 4m33s |
| 7 | [M40] | math-project | solved | 1m32s |
| 8 | [M32] | math-hard | solved | 4m48s |
| 9 | ▶ [M25] | math-medium | solved | 8m35s |
| 10 | [20] | medium | verified | 1m13s |
TAOCP 5.4.8 Exercise 1
Let the original order-$P$ bubble sort be defined as in Section 5.
TAOCP 5.4.8 Exercise 2
From the definition in (3), the procedures `SORTOO`, `SORT11`, `SORT01`, and `SORT10` differ only by a swap of tape roles.
TAOCP 5.4.8 Exercise 3
Let $N$ records reside initially on tape $T_0$.
TAOCP 5.4.8 Exercise 4
Let floors $p<q$ satisfy $g_q>p+2$, $u_p>0$, $u_q>0$, and $u_{p+1}=\cdots=u_{q-1}=0$.
TAOCP 5.4.8 Exercise 5
The statement is **false**.
TAOCP 5.4.8 Exercise 6
The reviewer is correct that the previous argument failed at the single-trajectory constraint.
TAOCP 5.4.8 Exercise 7
Let $T=(V,E)$ be a finite tree with positive edge lengths $\ell(e)>0$ for $e\in E$.
TAOCP 5.4.8 Exercise 8
We restart from the definition of the condition and first extract its actual global consequence, instead of interpreting it geometrically.