TAOCP 5.3.4: Networks for Sorting
Section 5.3.4 exercises: 68/68 solved.
Section 5.3.4. Networks for Sorting
Exercises from TAOCP Volume 3 Section 5.3.4: 68/68 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [30] | hard | verified | 3m26s |
| 2 | [22] | medium | solved | 2m16s |
| 3 | [M20] | math-medium | solved | 2m14s |
| 4 | ▶ [M23] | math-medium | solved | 3m28s |
| 5 | [M16] | math-medium | verified | 1m05s |
| 6 | [28] | hard | solved | 3m39s |
| 7 | [25] | medium | solved | 8m55s |
| 8 | [M20] | math-medium | solved | 16m13s |
| 9 | [M25] | math-medium | solved | 10m50s |
| 10 | [M22] | math-medium | solved | 15m |
| 11 | [M23] | math-medium | solved | 6m25s |
| 12 | [M20] | math-medium | solved | 1m45s |
| 13 | ▶ [24] | medium | solved | 6m07s |
| 14 | ▶ [M27] | math-hard | solved | 17m31s |
| 15 | [20] | medium | solved | 12m15s |
| 16 | [M22] | math-medium | solved | 17m26s |
| 17 | [M25] | math-medium | solved | 3m32s |
| 18 | ▶ [M20] | math-medium | solved | 10m24s |
| 19 | [M22] | math-medium | solved | 25m38s |
| 20 | [28] | hard | solved | 15m38s |
| 21 | [21] | medium | solved | 8m23s |
| 22 | [M17] | math-medium | solved | 1m06s |
| 23 | [M18] | math-medium | solved | 20m03s |
| 24 | ▶ [M21] | math-medium | solved | 28m59s |
| 25 | [M30] | math-hard | solved | 12m03s |
| 26 | [M24] | math-medium | solved | 18m25s |
| 27 | ▶ [M20] | math-medium | solved | 6m38s |
| 28 | ▶ [M20] | math-medium | solved | 1m40s |
| 29 | [M20] | math-medium | solved | 3m57s |
| 30 | [HM22] | hm-medium | solved | 1m20s |
| 31 | [M24] | math-medium | solved | 1m15s |
| 32 | [M28] | math-hard | solved | 17m12s |
| 33 | ▶ [M22] | math-medium | solved | 1h20m |
| 34 | [23] | medium | solved | 8m34s |
| 35 | [20] | medium | solved | 3m09s |
| 36 | ▶ [22] | medium | solved | 5m20s |
| 37 | [M22] | math-medium | solved | 18m43s |
| 38 | ▶ [43] | project | solved | 5m54s |
| 39 | [25] | medium | solved | 46m06s |
| 40 | [HM44] | hm-project | solved | 32m43s |
| 41 | [M47] | math-research | solved | 29m54s |
| 42 | ▶ [25] | medium | solved | 17m18s |
| 43 | [48] | research | solved | 2m51s |
| 44 | [50] | research | solved | 1m07s |
| 45 | [M20] | math-medium | solved | 13m09s |
| 46 | ▶ [30] | hard | solved | 38m24s |
| 47 | [47] | research | solved | 11m37s |
| 48 | ▶ [26] | hard | solved | 16m40s |
| 49 | [M23] | math-medium | solved | 6m04s |
| 50 | [HM46] | hm-research | solved | 5m06s |
| 51 | ▶ [M25] | math-medium | solved | 5m35s |
| 52 | ▶ [32] | hard | solved | 15m23s |
| 53 | [30] | hard | solved | 19m08s |
| 54 | [42] | project | solved | 21m28s |
| 55 | [23] | medium | solved | 9m27s |
| 56 | ▶ [25] | medium | solved | 17m12s |
| 57 | [M35] | math-hard | solved | 12m36s |
| 58 | [21] | medium | solved | 7m39s |
| 59 | ▶ [30] | hard | solved | 11m09s |
| 60 | [26] | hard | solved | 23m25s |
| 61 | [34] | hard | solved | 7m53s |
| 62 | [49] | research | solved | 14m42s |
| 63 | [23] | medium | solved | 9m44s |
| 64 | [24] | medium | solved | 11m15s |
| 65 | [M38] | math-project | solved | 23m03s |
| 66 | [M29] | math-hard | solved | 14m07s |
| 67 | [M48] | math-research | solved | 2m32s |
| 68 | [25] | medium | solved | 15m40s |
TAOCP 5.3.4 Exercise 1
Let the input to the merge network be two sorted sequences of lengths $m=3$ and $n=5$: (x_1,x_2,x_3) \quad \text{and} \quad (y_1,y_2,y_3,y_4,y_5).
TAOCP 5.3.4 Exercise 2
Let $n$ be fixed and consider Pratt’s sorting network constructed from all 3-smooth numbers d = 2^i 3^j \le n.
TAOCP 5.3.4 Exercise 3
Apply equation (5) twice, first with $(m,n)=(m,m-1)$ and then with $(m,n)=(m,m)$.
TAOCP 5.3.4 Exercise 4
Let $T(6)$ denote the minimum depth of a sorting network on 6 inputs.
TAOCP 5.3.4 Exercise 5
The odd-even merge network is composed of two independent recursive merge networks, one acting on the odd subsequences and one acting on the even subsequences, followed by a single layer of comparison...
TAOCP 5.3.4 Exercise 6
We work in the model where a _stage_ consists of a set of pairwise disjoint comparisons, and all comparisons in a stage are executed simultaneously.
TAOCP 5.3.4 Exercise 7
The network for \(n = 10\) shown in Fig.
TAOCP 5.3.4 Exercise 8
We prove the inequality \[ \hat{M}(m_1+m_2,\, n_1+n_2) \;\ge\; \hat{M}(m_1,n_1) + \hat{M}(m_2,n_2) + \min(m_1,n_2) \qquad (m_1,m_2,n_1,n_2 \ge 0), \] which is the intended form of the exercise (the or...
TAOCP 5.3.4 Exercise 9
A comparator network merges two sorted sequences of lengths \(m\) and \(n\) correctly for all inputs if and only if it does so for all \(0\)-\(1\) inputs where the first sequence consists of \(k\) zer...
TAOCP 5.3.4 Exercise 10
We first recall the definitions of Batcher's bitonic sorter and the bitonic merger from the remarks preceding equation (15).
TAOCP 5.3.4 Exercise 11
We prove that Batcher's bitonic sorter of order \(2^t\) sorts not only bitonic sequences \(z_0\ge\cdots\ge z_k\le\cdots\le z_{2^t-1}\) but also reverse bitonic sequences \(z_0\le\cdots\le z_k\ge\cdots...
TAOCP 5.3.4 Exercise 12
We disprove the statement by providing a counterexample.
TAOCP 5.3.4 Exercise 13
We prove that the network described sorts any sequence of \(2^t\) elements by using the zero‑one principle and induction on the stage number.
TAOCP 5.3.4 Exercise 14
We need to solve exercise 14 from TAOCP Volume 3 Section 5.
TAOCP 5.3.4 Exercise 15
A nonstandard sorting network for four elements using only five comparator modules is \[ \boxed{[1:3],\;[1:4],\;[2:3],\;[2:4],\;[1:2]}.
TAOCP 5.3.4 Exercise 16
We prove that the algorithm transforms any sorting network into a standard sorting network of the same length.
TAOCP 5.3.4 Exercise 17
The quantities $\bar{U}_t(n)$, $\bar{V}_t(n)$, $\bar{W}_t(n)$ are defined in the text as the minimum number of comparators required in a *standard* network (i.
TAOCP 5.3.4 Exercise 18
We prove the lower bound by applying the zero‑one principle and an adversary argument that extends the proof of Theorem A in the text.
TAOCP 5.3.4 Exercise 19
For $n \ge 2$ consider the following sequence of comparators: \[ [1:n],\; [2:n],\; \dots,\; [n-2:n],\qquad [1:n-1],\; [2:n-1],\; \dots,\; [n-2:n-1].
TAOCP 5.3.4 Exercise 20
We are given Exercise 20 from Section 5.
TAOCP 5.3.4 Exercise 21
**False.
TAOCP 5.3.4 Exercise 22
Let an $n$-network $\alpha$ be a finite sequence of comparators.
TAOCP 5.3.4 Exercise 23
**Definitions.
TAOCP 5.3.4 Exercise 24
Let \(\alpha\) be an \(n\)-network.
TAOCP 5.3.4 Exercise 25
Let $\alpha$ be an $n$-network.
TAOCP 5.3.4 Exercise 26
Let \(D_n = \{0,1\}^n\) be the set of all \(0\)-\(1\) vectors of length \(n\), and let \(P_n\) be the set of all permutations of \(\{1,2,\dots,n\}\).
TAOCP 5.3.4 Exercise 27
The exercise contains a notational inconsistency: the statement “$(x\alpha)_i \le (y\alpha)_i$ if and only if, for every choice of $j$ elements from $y$ …” uses $j$ on the right without it appearing o...
TAOCP 5.3.4 Exercise 28
Let \(x_1, x_2, \dots, x_n\) be elements of a totally ordered set.
TAOCP 5.3.4 Exercise 29
The merged sequence of 8 elements is given by the following formulas using the operators \(\wedge\) (minimum) and \(\vee\) (maximum): \[ \begin{aligned} z_1 &= x_1 \wedge y_1,\\[2pt] z_2 &= (x_1 \wedg...
TAOCP 5.3.4 Exercise 30
We need to solve Exercise 30 from TAOCP Volume 3, Section 5.
TAOCP 5.3.4 Exercise 31
A canonical form as described in exercise 30 is a disjunction \[ \tau_1 \lor \tau_2 \lor \cdots \lor \tau_k \qquad (k \ge 1) \] where each \(\tau_i = \bigwedge \{x_j \mid j \in S_i\}\) for some subset...
TAOCP 5.3.4 Exercise 32
We are given the recursive definition of sets \(G_i\) of binary strings: - \(G_1 = \{00, 01, 11\}\).
TAOCP 5.3.4 Exercise 33
Assume, for a contradiction, that there exists a comparator network with inputs \(x_1,\dots ,x_n\) and an output line that computes \[ f(x_1,x_2,x_3,x_4)=(x_1\land x_2)\lor(x_2\land x_3)\lor(x_3\land...
TAOCP 5.3.4 Exercise 34
The network shown in the figure is the standard 4‑element sorting network obtained by Batcher’s odd‑even merge construction.
TAOCP 5.3.4 Exercise 35
We prove the statement using the zero‑one principle (Section 5.
TAOCP 5.3.4 Exercise 36
Consider the input vector \(y = \langle n, n-1, \ldots, 1\rangle\).
TAOCP 5.3.4 Exercise 37
The odd‑even transposition network for \(n\) elements is *primitive* (it uses only adjacent comparators \([i:i+1]\)).
TAOCP 5.3.4 Exercise 38
Let \(N = \binom{n}{2}\).
TAOCP 5.3.4 Exercise 39
We are given exercise 39 from TAOCP Volume 3, Section 5.
TAOCP 5.3.4 Exercise 40
The bubble sort configuration for $n$ lines (Fig.
TAOCP 5.3.4 Exercise 41
We consider the following random process on \(n\) lines.
TAOCP 5.3.4 Exercise 42
Let \(\hat{S}(n)\) denote the minimum number of comparators in an \(n\)-line sorting network.
TAOCP 5.3.4 Exercise 43
An \((m,n)\)-merging network is a comparator network that accepts two sorted sequences \(\langle x_1,\dots,x_m\rangle\) and \(\langle y_1,\dots,y_n\rangle\) as inputs and produces the sorted merge of...
TAOCP 5.3.4 Exercise 44
Let \(\hat{S}(n)\) denote the minimum number of comparator modules required in a sorting network for \(n\) elements.
TAOCP 5.3.4 Exercise 45
We prove the lower bound by using the zero‑one principle and analyzing the information flow in a comparator network without multiple fanout.
TAOCP 5.3.4 Exercise 46
We prove that any network that merges two sorted sequences of lengths \(m\) and \(n\) using simultaneous disjoint comparisons (i.
TAOCP 5.3.4 Exercise 47
Let \(T(n)\) be the minimum number of stages required to sort \(n\) numbers by an **adaptive parallel algorithm** that in each stage performs any set of disjoint comparisons (the choice of comparisons...
TAOCP 5.3.4 Exercise 48
We need to solve Exercise 48 from TAOCP Vol 3, Section 5.
TAOCP 5.3.4 Exercise 49
We work in the setting of Exercise 48: \(x,y,z\) are multisets of \(m\) numbers.
TAOCP 5.3.4 Exercise 50
For a fixed integer \(m \ge 1\), let \(\mathbf{A}_m\) be the algebra whose universe consists of all multisets of size \(m\) taken from an infinite totally ordered set (e.
TAOCP 5.3.4 Exercise 51
We need to solve Exercise 51 from Section 5.
TAOCP 5.3.4 Exercise 52
We consider the family of comparator networks shown in Fig.
TAOCP 5.3.4 Exercise 53
Let \(n = 2^t\).
TAOCP 5.3.4 Exercise 54
An **\(m\)-sorter** is a module with \(m\) inputs and \(m\) outputs that sorts its inputs into nondecreasing order.
TAOCP 5.3.4 Exercise 55
The following sequence of eight modules forms a permutation network for five elements: \[ [1:2],\quad [3:4],\quad [1:3],\quad [2:5],\quad [2:3],\quad [4:5],\quad [1:2],\quad [3:4].
TAOCP 5.3.4 Exercise 56
We prove the following statement by induction on \(n\): > For any unsorted bit vector \(x \in D_n\) (where \(D_n\) is the set of all \(0\)-\(1\) sequences of length \(n\)), there exists a comparator n...
TAOCP 5.3.4 Exercise 57
We define the **even-odd merge** for two sorted sequences \(X = \langle x_1,\dots,x_m\rangle\) and \(Y = \langle y_1,\dots,y_n\rangle\) as follows.
TAOCP 5.3.4 Exercise 58
We first recall the definition of the multihead sorter.
TAOCP 5.3.4 Exercise 59
We consider the multihead sorting method described in the exercise.
TAOCP 5.3.4 Exercise 60
We consider the multihead sorting method described in Exercise 57 with $n=N$.
TAOCP 5.3.4 Exercise 61
We consider the multihead sorter as defined in the text preceding Exercise 58.
TAOCP 5.3.4 Exercise 62
A *multihead sorter* consists of $m$ read/write heads fixed at positions $1 = h_1 < h_2 < \dots < h_m = N$ on a tape of length $N$.
TAOCP 5.3.4 Exercise 63
We first recall the model of a multihead sorter as described in the text preceding Exercise 60.
TAOCP 5.3.4 Exercise 64
We process the $\binom{N}{2}$ pairs $(a,b)$ with $1\le a<b\le N$ in lexicographic order: \[ (1,2),\;(1,3),\;\ldots,\;(1,N),\;(2,3),\;(2,4),\;\ldots,\;(N-1,N).
TAOCP 5.3.4 Exercise 65
Let $N$ be the number of elements to be sorted, and let $M = \binom{N}{2}$.
TAOCP 5.3.4 Exercise 66
We need to solve Exercise 66 from Volume 3, Section 5.
TAOCP 5.3.4 Exercise 67
A **uniform sorting algorithm** (Exercise 64) processes all $\binom{N}{2}$ pairs $(a,b)$ with $1\le a<b\le N$ in a fixed sequence $(a_1,b_1), (a_2,b_2), \ldots, (a_M,b_M)$, $M=\binom{N}{2}$.