TAOCP 6.1: Sequential Searching
Section 6.1 exercises: 16/16 solved.
Section 6.1. Sequential Searching
Exercises from TAOCP Volume 3 Section 6.1: 16/16 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M20] | math-medium | verified | 1m01s |
| 2 | [15] | simple | verified | 1m |
| 3 | [16] | medium | verified | 2m50s |
| 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 |
| 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 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 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.