TAOCP 5.3.1: Minimum-Comparison Sorting
Section 5.3.1 exercises: 8/8 solved.
Section 5.3.1. Minimum-Comparison Sorting
Exercises from TAOCP Volume 3 Section 5.3.1: 8/8 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 1m04s | |
| 2 | [**] | verified | 1m12s | |
| 3 | [**] | solved | 4m27s | |
| 4 | [**] | verified | 2m50s | |
| 5 | [**] | verified | 3m21s | |
| 6 | [**] | solved | 5m39s | |
| 7 | [M25] | math-medium | verified | 2m41s |
| 8 | [M23] | math-medium | solved | 4m19s |
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.