TAOCP 5.3.1: Minimum-Comparison Sorting
Section 5.3.1 exercises: 36/36 solved.
Section 5.3.1. Minimum-Comparison Sorting
Exercises from TAOCP Volume 3 Section 5.3.1: 36/36 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [20] | medium | verified | 1m04s |
| 2 | [M24] | math-medium | verified | 1m12s |
| 3 | [M22] | math-medium | solved | 4m27s |
| 4 | [HM22] | hm-medium | verified | 2m50s |
| 5 | [16] | medium | verified | 3m21s |
| 6 | ▶ [M22] | math-medium | solved | 5m39s |
| 7 | [20] | medium | verified | 2m41s |
| 8 | [26] | hard | solved | 4m19s |
| 9 | [M20] | math-medium | solved | 27m14s |
| 10 | ▶ [M25] | math-medium | solved | 19m50s |
| 11 | [HM22] | hm-medium | solved | 25m02s |
| 12 | ▶ [M25] | math-medium | solved | 3m41s |
| 13 | [M28] | math-hard | solved | 15m49s |
| 14 | [M24] | math-medium | solved | 44m16s |
| 15 | [M21] | math-medium | solved | 13m12s |
| 16 | [HM26] | hm-hard | solved | 22m58s |
| 17 | [M20] | math-medium | solved | 13m06s |
| 18 | [20] | medium | solved | 4m51s |
| 19 | [40] | project | solved | 8m36s |
| 20 | ▶ [M26] | math-hard | solved | 7m08s |
| 21 | [M21] | math-medium | solved | 52s |
| 22 | [M24] | math-medium | solved | 10m03s |
| 23 | [10] | simple | solved | 52s |
| 24 | [27] | hard | solved | 18m21s |
| 25 | [11] | simple | solved | 1m50s |
| 26 | [M42] | math-project | solved | 16m45s |
| 27 | ▶ [20] | medium | solved | 4m28s |
| 28 | [40] | project | solved | 11m31s |
| 29 | [M25] | math-medium | solved | 8m42s |
| 30 | [M29] | math-hard | solved | 4m11s |
| 31 | [M38] | math-project | solved | 11m50s |
| 32 | [M42] | math-project | solved | 4m51s |
| 33 | [M30] | math-hard | solved | 10m19s |
| 34 | [M50] | math-research | solved | 20m40s |
| 35 | [29] | hard | solved | 15m31s |
| 36 | [M50] | math-research | solved | 1m34s |
TAOCP 5.3.1 Exercise 1
For $n>0$, the recurrence $P_n=\sum_{k=1}^{n} \binom{n}{k} P_{n-k}$ together with $P_0=1$ is multiplied by $z^n/n!$ and summed over all $n\ge 1$.
TAOCP 5.3.1 Exercise 2
The root node compares $K_1$ and $K_2$.
TAOCP 5.3.1 Exercise 3
We must construct an **extended ternary decision tree for sorting four elements drawn from $\{-1,0,+1\}$** using comparison nodes with outcomes $<,=,>$, and determine a tree with **minimum average num...
TAOCP 5.3.1 Exercise 4
The goal is to determine the sorted order of $n$ keys, knowing each key is either $0$ or $1$.
TAOCP 5.3.1 Exercise 5
The previous solution fails because it treats the problem as one of extracting information from a fixed probabilistic comparison outcome, whereas the task is a deterministic decision problem in the co...
TAOCP 5.3.1 Exercise 6
Let keys lie in the ordered set $\{1,2,\dots,m\}$, with $m$ fixed, and let $S_m(n)$ be the worst–case number of comparisons needed by an optimal comparison tree that produces a stable sorted order of...
TAOCP 5.3.1 Exercise 7
Let the computation be represented by a binary comparison tree.
TAOCP 5.3.1 Exercise 8
We restart the argument from the correct structural relationship between comparison trees and comparison–exchange trees, and avoid any “locking” interpretation of swaps.
TAOCP 5.3.1 Exercise 9
We consider the problem of sorting \(n\) elements when it is known that each key is either \(0\) or \(1\).
TAOCP 5.3.1 Exercise 10
We consider the problem of sorting \(n\) elements whose keys are known to be either 0 or 1.
TAOCP 5.3.1 Exercise 11
We need to solve exercise 11: "When sorting n elements as in exercise 5, and knowing that all keys are members of the set {1,2,.
TAOCP 5.3.1 Exercise 12
Let $T$ be a comparison tree with no redundant comparisons.
TAOCP 5.3.1 Exercise 13
We consider the **merge insertion** (Ford-Johnson) algorithm as described in the text.
TAOCP 5.3.1 Exercise 14
The sum (19) in the text is the total number of comparisons required by merge insertion to sort \(n\) elements, which is \[ S(n) = \sum_{k=1}^n \left\lceil \log_2 \frac{3k}{4} \right\rceil.
TAOCP 5.3.1 Exercise 15
The maximum number of comparisons for binary insertion is given in the text (Eq.
TAOCP 5.3.1 Exercise 16
Let \(F(n)\) denote the number of comparisons performed by the merge‑insertion (Ford-Johnson) algorithm when sorting \(n\) distinct elements.
TAOCP 5.3.1 Exercise 17
Let \(F(n)\) be the number of comparisons used by the merge‑insertion algorithm to sort \(n\) distinct keys.
TAOCP 5.3.1 Exercise 18
The efficiency of a comparison tree that sorts \(n\) elements (with no redundant comparisons) is defined as the number of leaves divided by \(2^{h}\), where \(h\) is the height of the tree (the maximu...
TAOCP 5.3.1 Exercise 19
We consider the problem of constructing a minimum-comparison sorting tree for \(n\) distinct elements \(K_1,\dots,K_n\).
TAOCP 5.3.1 Exercise 20
An **extended binary tree** is a finite rooted tree in which every internal node has exactly two children.
TAOCP 5.3.1 Exercise 21
Let \(T\) be an extended binary tree.
TAOCP 5.3.1 Exercise 22
We prove that an extended binary tree has minimum external path length among all extended binary trees with the same number \(N\) of external nodes **iff** for every internal node \(x\) \[ |t(x)-2\,t(...
TAOCP 5.3.1 Exercise 23
The information-theoretic lower bound \(\lceil \lg n!
TAOCP 5.3.1 Exercise 24
We are asked to find a comparison tree (sorting tree) for six distinct elements such that all 720 external nodes (leaves) appear on levels 10 and 11.
TAOCP 5.3.1 Exercise 25
The minimum average number of comparisons for sorting \(n\) distinct elements is achieved by a comparison tree (a full binary tree) with \(n!
TAOCP 5.3.1 Exercise 26
We consider the problem of sorting 7 distinct elements using only binary comparisons.
TAOCP 5.3.1 Exercise 27
We are given the six possible orders of three distinct keys \(K_1, K_2, K_3\) with their probabilities: \[ \begin{array}{c|c} \text{Order} & \text{Probability} \\ \hline K_1 < K_2 < K_3\;(123) & 0.
TAOCP 5.3.1 Exercise 28
The exercise asks for a MIX program that sorts five one‑word keys in as few machine cycles as possible.
TAOCP 5.3.1 Exercise 29
We model the algorithm as a binary decision tree $T$.
TAOCP 5.3.1 Exercise 30
We work with the definitions given in the exercise.
TAOCP 5.3.1 Exercise 31
We need to solve exercise 31 from Volume 3, Section 5.
TAOCP 5.3.1 Exercise 32
Let \(S_e(n)\) denote the minimum worst-case number of comparison-exchanges required to sort \(n\) distinct elements, as defined in Exercise 30.
TAOCP 5.3.1 Exercise 33
Let \(f(x)\) denote the minimum possible weighted path length (WPL) of a real‑valued search tree of order \(x\) and resolution \(1\).
TAOCP 5.3.1 Exercise 34
We need to solve Exercise 34 from TAOCP Volume 3, Section 5.