TAOCP 5: Introduction to Sorting
Section 5 exercises: 25/25 solved.
Section 5. Introduction to Sorting
Exercises from TAOCP Volume 3 Section 5: 25/25 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M20] | math-medium | verified | 1h11m |
| 2 | [21] | medium | verified | 1h01m |
| 3 | [M25] | math-medium | verified | 1m |
| 4 | ▶ [21] | medium | solved | 21m16s |
| 5 | ▶ [M28] | math-hard | verified | 15m14s |
| 6 | [15] | simple | verified | 7m41s |
| 7 | [17] | medium | verified | 31m04s |
| 8 | ▶ [30] | hard | verified | 1h07m |
| 9 | [M27] | math-hard | verified | 6m33s |
| 10 | [15] | simple | verified | 10m07s |
| 11 | [18] | medium | verified | 14m32s |
| 12 | [M25] | math-medium | verified | 19m11s |
| 13 | [M26] | math-hard | verified | 8m32s |
| 14 | [20] | medium | verified | 6m35s |
| 15 | [18] | medium | verified | 7m26s |
| 16 | [20] | medium | verified | 20m17s |
| 17 | ▶ [33] | hard | solved | 2m22s |
| 18 | [M25] | math-medium | verified | 9m07s |
| 19 | ▶ [24] | medium | verified | 7m57s |
| 20 | ▶ [25] | medium | verified | 25m58s |
| 21 | [22] | medium | verified | 9m08s |
| 22 | [M28] | math-hard | verified | 12m07s |
| 23 | [30] | hard | verified | 12m11s |
| 24 | ▶ [30] | hard | verified | 1h19m |
| 25 | [M21] | math-medium | verified | 12m18s |
TAOCP 5 Exercise 1
**Corrected Solution.
TAOCP 5 Exercise 2
The reviewer is correct.
TAOCP 5 Exercise 3
Each input word $a_{i,j}$ is read in the given row-major order and assigned the column index $j$.
TAOCP 5 Exercise 4
Our systems have detected unusual activity coming from your system.
TAOCP 5 Exercise 5
Let each catalog card be considered as a record $R_j$ with a key $K_j$ that reflects the text of the card, including author, title, and date information.
TAOCP 5 Exercise 6
The MIX computer represents integers in sign‑magnitude form: each word consists of a sign (±) and five bytes, giving a magnitude in the range \(0 \le M \le 64^5-1\).
TAOCP 5 Exercise 7
The following MIXAL subroutine `COMPARE` implements multiprecision lexicographic comparison of two sequences of words stored at `A+1 … A+n` and `B+1 … B+n`, where `n ≥ 1` is given in `rI1`.
TAOCP 5 Exercise 8
We are given two MIX words in locations `A` and `B`.
TAOCP 5 Exercise 9
Let \(X_1, X_2, \ldots, X_N\) be independent random variables, each uniformly distributed on \([0,1]\).
TAOCP 5 Exercise 10
We are given a tape containing \(N = 10^6\) words and have at most a few thousand words of internal memory (say \(M\) words, where \(M \ll N\)) and about six tape units.
TAOCP 5 Exercise 11
We are given two large files: - **Information returns**: each record is a pair $(id, amount)$ where $id$ identifies the payee and $amount$ is the payment reported by the payer.
TAOCP 5 Exercise 12
We are given a magnetic tape containing \(10^6\) words representing a \(1000 \times 1000\) matrix in row-major order: \[ a_{1,1}, a_{1,2}, \dots, a_{1,1000},\; a_{2,1}, \dots, a_{2,1000},\; \dots,\; a...
TAOCP 5 Exercise 13
We are given a file of \(N\) words (records) \(R_1, R_2, \ldots, R_N\) stored on external storage (e.
TAOCP 5 Exercise 14
Let the two computers be \(A\) and \(B\).
TAOCP 5 Exercise 15
We are given a list of \(N\) records, each consisting of a person's name and the U.
TAOCP 5 Exercise 16
The cross-reference routine is designed as a four-pass external-sorting pipeline.
TAOCP 5 Exercise 17
We need to solve exercise 17 from TAOCP Volume 3, Section 5.
TAOCP 5 Exercise 18
We are searching for positive integers \(u,v,w,x,y,z\) satisfying \[ u^6 + v^6 + w^6 + x^6 + y^6 = z^6 \qquad\text{(Euler's conjecture for }n=6\text{)}.
TAOCP 5 Exercise 19
Let \(C = 2^{36} - 1 = (11\ldots 1)_2\) (36 ones).
TAOCP 5 Exercise 20
We are given \(N = 1000\) words \(x_1, x_2, \dots, x_{1000}\), each of length 30 bits.
TAOCP 5 Exercise 21
We are given a dictionary of English words.
TAOCP 5 Exercise 22
We are given a collection of directed graphs \(G_1, G_2, \ldots, G_m\).
TAOCP 5 Exercise 23
We are given an undirected graph \(G = (V, E)\) with \(|V| = 4096\) vertices (people) and \(|E| \approx 200\,000\) edges (acquaintance pairs).