TAOCP 5.2.3: Sorting by Selection
Section 5.2.3 exercises: 38/38 solved.
Section 5.2.3. Sorting by Selection
Exercises from TAOCP Volume 3 Section 5.2.3: 38/38 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | verified | 1m16s |
| 2 | [15] | simple | verified | 1m27s |
| 3 | [M21] | math-medium | solved | 7m38s |
| 4 | ▶ [M25] | math-medium | verified | 2m56s |
| 5 | [20] | medium | solved | 6m05s |
| 6 | [M29] | math-hard | verified | 3m39s |
| 7 | [M41] | math-project | verified | 1m42s |
| 8 | ▶ [24] | medium | verified | 4m45s |
| 9 | [M25] | math-medium | verified | 2m26s |
| 10 | [12] | simple | verified | 2m10s |
| 11 | [10] | simple | verified | 2m05s |
| 12 | [M20] | math-medium | verified | 1m28s |
| 13 | [20] | medium | verified | 5m53s |
| 14 | [10] | simple | verified | 3m52s |
| 15 | ▶ [M22] | math-medium | verified | 8m12s |
| 16 | [20] | medium | solved | 5m10s |
| 17 | [20] | medium | solved | 2m21s |
| 18 | ▶ [21] | medium | solved | 5m19s |
| 19 | [21] | medium | solved | 10m17s |
| 20 | [M20] | math-medium | solved | 11m52s |
| 21 | [M24] | math-medium | solved | 25m31s |
| 22 | ▶ [20] | medium | solved | 5m54s |
| 23 | [M28] | math-hard | solved | 18m29s |
| 24 | [M32] | math-hard | solved | 1h15m |
| 25 | [M20] | math-medium | solved | 25m10s |
| 26 | [M30] | math-hard | solved | 33m28s |
| 27 | [M25] | math-medium | solved | 57s |
| 28 | [35] | hard | solved | 13m24s |
| 29 | [26] | hard | solved | 1m33s |
| 30 | ▶ [HM25] | hm-medium | solved | 21m32s |
| 31 | [37] | project | solved | 8m57s |
| 32 | [M33] | math-hard | solved | 25m47s |
| 33 | [21] | medium | solved | 54s |
| 34 | [M41] | math-project | solved | 49m33s |
| 35 | [26] | hard | solved | 13m47s |
| 36 | [18] | medium | solved | 17s |
| 37 | [HM32] | hm-hard | solved | 16m56s |
| 38 | [M21] | math-medium | solved | 14m22s |
TAOCP 5.2.3 Exercise 1
For a fixed value of $j$, step S2 selects the maximum of the keys $K_1,\ldots,K_j$.
TAOCP 5.2.3 Exercise 2
For the input $N,N-1,\ldots,2,1$, the sequence $K_1, K_2, \ldots, K_j$ is strictly decreasing for every $j \ge 2$.
TAOCP 5.2.3 Exercise 3
The previous solution failed because it used unsupported structural claims about cycles and an undefined “charging” argument.
TAOCP 5.2.3 Exercise 4
Let $R_j$ be the number of right-to-left maxima among $K_1,\dots,K_j$.
TAOCP 5.2.3 Exercise 5
The previous solution correctly implemented a left-to-right maximum search, but it never established the _inter-iteration structure_ that makes the modification useful.
TAOCP 5.2.3 Exercise 6
We analyze the algorithm of Exercise 5.
TAOCP 5.2.3 Exercise 7
After 14 outputs, all but two elements have been replaced by $-\infty$ in the tournament structure of Fig.
TAOCP 5.2.3 Exercise 8
**Corrected Solution: Exercise 5.
TAOCP 5.2.3 Exercise 9
Let the file contain $2^n$ elements and consider the bottom-up method of Fig.
TAOCP 5.2.3 Exercise 10
Let the standard heapsort “sift-down” step be denoted by the variables of Algorithm H, where a key at position $k$ is moved downward by repeatedly comparing it with its children at $2k$ and $2k+1$, an...
TAOCP 5.2.3 Exercise 11
Let elements arrive in a sequence at times $t = 1,2,\ldots$.
TAOCP 5.2.3 Exercise 12
Let $r$ denote the current odd integer under consideration and let $H$ be a priority queue keyed by the first unprocessed odd composite associated with each prime.
TAOCP 5.2.3 Exercise 13
**Exercise 5.
TAOCP 5.2.3 Exercise 14
Exercise 16 describes the standard heap insertion operation: append the new key at the end of the heap and repeatedly interchange it with its parent until the heap property is restored.
TAOCP 5.2.3 Exercise 15
**Corrected Solution for Exercise 5.
TAOCP 5.2.3 Exercise 16
**Algorithm I** (*Heap insertion*).
TAOCP 5.2.3 Exercise 17
No, the two methods do not always create the same heap.
TAOCP 5.2.3 Exercise 18
The selection phase of heapsort (Algorithm H) repeatedly extracts the maximum element from a heap of size \(N\).
TAOCP 5.2.3 Exercise 19
Let the heap be stored in an array `K[1.
TAOCP 5.2.3 Exercise 20
We consider a heap of size \(N\) stored in an array \(1,2,\ldots,N\) as a complete binary tree: the root is at index \(1\); for any node \(k\), its left child is \(2k\) and its right child is \(2k+1\)...
TAOCP 5.2.3 Exercise 21
We first recall the relevant definitions from the text.
TAOCP 5.2.3 Exercise 22
The heapcreation phase of Algorithm H (heapsort) for \(N = 5\) builds a heap by applying the sift-down operation first at node \(2\) and then at node \(1\).
TAOCP 5.2.3 Exercise 23
We consider the heap creation phase of Algorithm H (heapsort) as described in Section 5.
TAOCP 5.2.3 Exercise 24
We need to derive an exact formula for the standard deviation of B_N, the total length of scan during the heap-creation phase of Algorithm H (Heapsort).
TAOCP 5.2.3 Exercise 25
We need to solve Exercise 25 from TAOCP Volume 3, Section 5.
TAOCP 5.2.3 Exercise 26
The siftup algorithm for a node at index \(l\) when the current heap size is \(r\) is \[ \begin{aligned} i &\gets l,\; j \gets 2i;\\ \text{while } j &\le r:\\ &\quad\text{if } j<r \text{ and } K_j < K...
TAOCP 5.2.3 Exercise 27
The identity is an equality of formal power series (or absolutely convergent series for \(|x|<1\)).
TAOCP 5.2.3 Exercise 28
A **ternary heap** is a complete ternary tree stored in an array `A[1.
TAOCP 5.2.3 Exercise 29
Solution to TAOCP 5.2.3 Exercise 29.
TAOCP 5.2.3 Exercise 30
We are given exercise 30 from Volume 3, Section 5.
TAOCP 5.2.3 Exercise 31
We represent the priority deque as a **deap** (double-ended heap), which consists of a min‑heap and a max‑heap placed “back to back” in a single array that stores a complete binary tree with a dummy r...
TAOCP 5.2.3 Exercise 32
We need to solve Exercise 32 from Section 5.
TAOCP 5.2.3 Exercise 33
A *leftist tree* is a binary tree in which each node contains a key and a *null path length* (denoted `dist`).
TAOCP 5.2.3 Exercise 34
We need to solve exercise 34: "How many leftist trees with N nodes are possible, ignoring the KEY values?
TAOCP 5.2.3 Exercise 35
A **leftist tree** is a binary tree where each node \(x\) has a field \(\operatorname{DIST}(x)\) defined as \[ \operatorname{DIST}(x) = \begin{cases} 0 & \text{if } x \text{ is external (null)}, \\ 1...
TAOCP 5.2.3 Exercise 36
The required data structure is a **doubly linked list** (or a circular doubly linked list with a sentinel node) that maintains the nodes in order of recency of use, with the most recently used node at...