TAOCP 5.4.8: Two-Tape Sorting

Section 5.4.8 exercises: 8/8 solved.

8 items

Section 5.4.8. Two-Tape Sorting

Exercises from TAOCP Volume 3 Section 5.4.8: 8/8 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
6	[M30]	math-hard	solved	4m33s
7	[M40]	math-project	solved	1m32s
8	[M32]	math-hard	solved	4m48s
10	[20]	medium	verified	1m13s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.4.8: Two-Tape Sorting ›

TAOCP 5.4.8 Exercise 1

Let the original order-$P$ bubble sort be defined as in Section 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.4.8: Two-Tape Sorting ›

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.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.4.8: Two-Tape Sorting ›

TAOCP 5.4.8 Exercise 3

Let $N$ records reside initially on tape $T_0$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.4.8: Two-Tape Sorting ›

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$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.4.8: Two-Tape Sorting ›

TAOCP 5.4.8 Exercise 6

The reviewer is correct that the previous argument failed at the single-trajectory constraint.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.4.8: Two-Tape Sorting ›

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$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.4.8: Two-Tape Sorting ›

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.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.4.8: Two-Tape Sorting ›

TAOCP 5.4.8 Exercise 10

Let the multireel file consist of a sequence of records distributed over several reels, with no restriction on where a run begins or ends relative to reel boundaries.