TAOCP 6.1: Sequential Searching
Section 6.1 exercises: 22/22 solved.
Section 6.1. Sequential Searching
Exercises from TAOCP Volume 3 Section 6.1: 22/22 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M20] | math-medium | verified | 1m01s |
| 2 | [15] | simple | verified | 1m |
| 3 | [16] | medium | verified | 2m50s |
| 4 | ▶ [17] | medium | solved | 56s |
| 5 | [20] | medium | solved | 3m42s |
| 6 | ▶ [20] | medium | solved | 4m01s |
| 7 | [M20] | math-medium | verified | 1m01s |
| 8 | [HM22] | hm-medium | verified | 1m03s |
| 9 | ▶ [HM28] | hm-hard | solved | 1m14s |
| 10 | [M20] | math-medium | verified | 1m09s |
| 11 | [M30] | math-hard | verified | 2m27s |
| 12 | [M23] | math-medium | solved | 2m37s |
| 13 | [M27] | math-hard | solved | 8m14s |
| 14 | [M21] | math-medium | solved | 2m07s |
| 15 | ▶ [M22] | math-medium | solved | 1m39s |
| 16 | [M22] | math-medium | solved | 1m12s |
| 17 | [M23] | math-medium | solved | 3m09s |
| 18 | [M30] | math-hard | solved | 4m49s |
| 19 | [M20] | math-medium | verified | 1m09s |
| 20 | [M28] | math-hard | solved | 4m35s |
| 21 | [M28] | math-hard | solved | 5m07s |
| 22 | ▶ [20] | medium | verified | 1m31s |
TAOCP 6.1 Exercise 1
In a successful sequential search through $N$ records, every position $i \in {1,\dots,N}$ occurs with probability $1/N$.
TAOCP 6.1 Exercise 2
Let $P$ be a pointer to a record, with $FIRST$ pointing to the first record and the last record linked to the sentinel $A$.
TAOCP 6.1 Exercise 3
We restart the analysis from the instruction-level behavior of the MIX program.
TAOCP 6.1 Exercise 4
Yes, the sentinel technique of Algorithm Q adapts directly to linked-memory representation.
TAOCP 6.1 Exercise 5
We restart the analysis from the actual structure of the comparison, without introducing abstract per-iteration cost parameters.
TAOCP 6.1 Exercise 6
The previous solution fails because it violates MIX syntax (memory increment and malformed immediate comparisons) and because it does not specify a legitimate instruction-level control structure tied...
TAOCP 6.1 Exercise 7
The probability distribution (5) is p_k = 2^{-k}\quad (1 \le k \le N-1), \qquad p_N = 2^{-(N-1)}.
TAOCP 6.1 Exercise 8
Let H_N^{(\theta)}=\sum_{k=1}^{N} k^{-\theta}, \qquad \theta \neq 1.
TAOCP 6.1 Exercise 9
Let $p_k$ be probabilities on ${1,2,\dots,N}$ with $\sum_{k=1}^N p_k=1$.
TAOCP 6.1 Exercise 10
Let $p_1, p_2, \dots, p_N$ be the probabilities that the argument equals $K_1, K_2, \dots, K_N$, with $\sum_{i=1}^N p_i = 1$.
TAOCP 6.1 Exercise 11
The reviewer is correct: the proposed solution does not address the problem at all.
TAOCP 6.1 Exercise 12
Equation (17) gives the limiting average number of comparisons for the move‑to‑front self‑organizing file: \[ \widetilde C_N = 1 + \sum_{1\le i<j\le N} \frac{2p_i p_j}{p_i+p_j}.
TAOCP 6.1 Exercise 13
The wedge-shaped probability distribution (6) is \[ p_1 = Nc,\; p_2 = (N-1)c,\; \dots,\; p_N = c,\qquad c = \frac{2}{N(N+1)}.
TAOCP 6.1 Exercise 14
Let \(x_1, x_2, \dots, x_n\) and \(y_1, y_2, \dots, y_n\) be two sequences of real numbers.
TAOCP 6.1 Exercise 15
Let the subroutines be arranged in some order \(a_1, a_2, \dots, a_N\).
TAOCP 6.1 Exercise 16
We want to test conditions \(1,\ldots,n\) in some order \(\sigma\) (a permutation of \(\{1,\ldots,n\}\)).
TAOCP 6.1 Exercise 17
Let a schedule be a permutation $a_1 a_2 \dots a_n$ of the jobs $1,2,\dots,n$.
TAOCP 6.1 Exercise 18
Let the positions be $1,2,\dots,N$.
TAOCP 6.1 Exercise 19
Let a fixed permutation of the records be given, and let $\pi(i)\in{1,\dots,N}$ denote the position of record $R_i$ in the array.
TAOCP 6.1 Exercise 20
The previous solution failed because it tried to analyze the function $\delta(t)=d(t,i)-d(t,i+1)$ directly on the cycle, where it is not monotone and in fact has multiple regime changes.