#volume-3
TAOCP 5.1 Exercise 4
Section 5.1: Combinatorial Properties of Permutations Exercise 4. [**] [20] Several other kinds of inversion tables can be defined, corresponding to a given permutation $a_1 a_2 \dots a_n$ of ${1,2,\dots,n}$, besides the particular table $b_1 b_2 \dots b_n$ defined in the text; in this exercise we will consider three other types of inversion tables that arise in applications. Let $c_j$ be the number of inversions whose first component is $j$,...
TAOCP 6.5 Exercise 7
Section 6.5: Retrieval on Secondary Keys Exercise 7. [ M24 ] [M24] (R.L. Rivest.) Find the functions L(t), as defined in the previous exercise, for the following combinatorial hash functions: (a) m=3,n=2 (b) m=4,n=2 00*-0 00*« «-0 1 O0>1 1l x0751 *1l1l, -2 lll, -2 101-3 101l , 2 010-3 *1l01>3 100*, +3 Verified: no Solve time: 3m59s The fundamental issue in the proposed solution is not computational but logical:...
TAOCP 6.5 Exercise 13
Section 6.5: Retrieval on Secondary Keys Exercise 13. [ M25 ] [M25] Construct quadruple systems with v = 4” elements, analogous to the triple system of exercise 9. Verified: yes Solve time: 2m25s Let $m = 2n$ and let $V = \mathbb{F}_2^m$, so $|V| = 2^m = 4^n$. We construct blocks that are exactly the affine 2-dimensional subspaces of $V$. Construction For any $x \in V$ and any linearly independent...
TAOCP 6.5 Exercise 5
Section 6.5: Retrieval on Secondary Keys Exercise 5. [ 40 ] [40] Experiment with various ways to avoid the redundancy of text when using Harrison’s technique for substring searching. [M20] The total number of m-bit basic queries with t bits specified is s = (")2". If a combinatorial hashing function like that in (13) converts these queries into 1, lz, ..., ls locations, respectively, L(t) = (14 +l2 +---+1s)/s is...
TAOCP 6.5 Exercise 8
Section 6.5: Retrieval on Secondary Keys Exercise 8. [ M32 ] [M32] (R. L. Rivest.) Consider the set Q:,m of all 2°("?) basic m-bit queries like (10) in which there are exactly ¢ specified bits. Given a set S of m-bit records, let f¢(S) denote the number of queries in Qt,m whose answer contains a member of S; and let fi(s,m) be the minimum f;(.S) over all such sets S...
TAOCP 6.5 Exercise 3
Section 6.5: Retrieval on Secondary Keys Exercise 3. [ 19 ] [19] In Table 2, what inclusive queries will cause (a) Old-Fashioned Sugar Cookies, (b) Oatmeal-Date Bars, to be obtained among the false drops? Verified: no Solve time: 3m30s The previous attempt failed because it replaced the signature analysis required by Table 2 with informal guesses. The correct solution must be derived entirely from the bit patterns assigned in Table...
TAOCP 6.5 Exercise 14
Section 6.5: Retrieval on Secondary Keys Exercise 14. [ 28 ] [28] Discuss the problem of deleting nodes from quadtrees, k-d trees, and postoffice trees like Fig. 45. Verified: no Solve time: 3m35s Corrected Solution The three structures all support dynamic sets of points in the plane, but they differ in what is structurally invariant. Deletion is therefore easy in none of them: it either destroys a recursively defined decomposition...
TAOCP 6.5 Exercise 2
Section 6.5: Retrieval on Secondary Keys Exercise 2. [ M25 ] [M25] (Sakti P. Ghosh.) Find the minimum possible length / of a list rir2...11 of references to records, such that the set of all responses to any of the inclusive queries 4 1, 1 , Lee, #11, 1 1, 11*, 111 on three binary-valued secondary keys will appear in consecutive locations r;...1;. Verified: no Solve time: 5m25s Let the...
TAOCP 6.5 Exercise 15
Section 6.5: Retrieval on Secondary Keys Exercise 15. [ HM30 ] [HM30] (P. Elias.) Given a large collection of m-bit records, suppose we want to find a record closest to a given search argument, in the sense that it agrees in the most bits. Devise an algorithm for solving this problem efficiently, assuming that an m-bit t-error-correcting code of 2” elements is given, and that each record has been hashed...
TAOCP 6.5 Exercise 9
Section 6.5: Retrieval on Secondary Keys Exercise 9. [ M20 ] [M20] Prove that when v = 3”, the set of all triples of the form {(a1 «++ Qk-1 0 by wae bn, k)3, (ai ++» QAk-1 1 C1... Cn, k)3, (a1 ~.-Ak-1 2d, wae dn, k)3}, 1<k<vn, forms a Steiner triple system, where the a’s, b’s, c’s, and d’s range over all combinations of 0s, 1s, and 2s such...
TAOCP 6.5 Exercise 12
Section 6.5: Retrieval on Secondary Keys Exercise 12. [ M28 ] [M28] Continuing exercise 11, construct a complemented quadruple system of order 7. Verified: no Solve time: 4m56s Let $X={x_i,\bar x_i\mid i\in\mathbb Z_7}$. A complemented quadruple system of order $7$ is a family $\mathcal Q$ of 4-subsets of $X$ such that: every unordered pair of distinct elements of $X$ except the forbidden pairs ${x_i,\bar x_i}$ occurs in exactly one block,...
TAOCP 6.5 Exercise 4
Section 6.5: Retrieval on Secondary Keys Exercise 4. [ M30 ] [M30] Find exact formulas for the probabilities in (11), assuming that each record has r distinct attributes chosen randomly from among the (i) k-bit codes in an n-bit field and that the query involves q distinct but otherwise random attributes. (Don’t be alarmed if the formulas do not simplify.) Verified: yes Solve time: 3m46s We restart from a correct...
TAOCP 6.5 Exercise 11
Section 6.5: Retrieval on Secondary Keys Exercise 11. [ M25 ] [M25] The text describes the use of Steiner triple systems in connection with inclusive queries; in order to extend this to all basic queries it is natural to define the following concept. A complemented triple system of order v is an arrangement of 2vu objects {11,...,2v,%1,...,Zv} into triples such that every pair of objects occurs together in exactly one...
TAOCP 6.5 Exercise 19
Section 6.5: Retrieval on Secondary Keys Exercise 19. [ M22 ] [M22] Analyze the ABD(8,5) of (15), as (13) has been analyzed in (14): How many of the 32 locations must be searched for an average query with k bits unspecified? How many must be searched in the worst case? Verified: yes Solve time: 3m54s The error in the previous solution comes from treating ABD(8,5) as if query elements were...
TAOCP 6.5 Exercise 10
Section 6.5: Retrieval on Secondary Keys Exercise 10. [ M32 ] [M32] (Thomas P. Kirkman, Cambridge and Dublin Math. Journal 2 (1847), 191-204.) Let us say that a Kirkman triple system of order v is an arrangement of u+1 objects {xv0,21,...,v} into triples such that every pair {x;,x,;} for 1 4 7 occurs in exactly one triple, except that the v pairs {2i, £(;41) moa v} do not ever occur...
TAOCP 6.5 Exercise 16
Section 6.5: Retrieval on Secondary Keys Exercise 16. [ 25 ] [25] (W. H. Kautz and R. C. Singleton.) Show that a Steiner triple system of order v can be used to construct v(v, 1)/6 codewords of v bits each such that no codeword is contained in the superposition of any two others. [M30] Consider the following way to reduce (2n + 1)-bit keys a_n...do...@n to (n + 1)-bit bucket...
TAOCP 5.4.9 Exercise 27
Section 5.4.9: Disks and Drums Exercise 27. [**] [HM27| (The cyclic occupancy problem.) Suppose n empty urns have been arranged in a circle and assigned the numbers 0, 1,..., n, 1. For k = 1, 2, ..., p, we throw mz, balls into urns (X; + 7) mod n for j = 0, 1, ..., mz,, 1, where the integers Xj, are chosen at random. Let S,(m1i,...,mp) be the number...
TAOCP 5.3.3 Exercise 16
Section 5.3.3: Minimum-Comparison Selection Exercise 16. [ M32 ] [M32] (A. Schénhage, 1974.) (a) In the notation of exercise 14, prove that $U_t(n) > \min(2 + U_t(n-1), 2 + U_{t-1}(n-1))$ for $n > 3$. [Hint: Construct an adversary by reducing from $n$ to $n - 1$ as soon as the current partial ordering is not composed entirely of components having the form $+$ or $-$.] (b) Similarly, prove that $$U_2(n)...
TAOCP 5.3.2 Exercise 20
Section 5.3.2: Minimum-Comparison Merging Exercise 20. [ 20 ] [20] Show that if $M(m,n+1) < M(m+1,n)$ for all $m < n$, then $M(m,n+1) < 1 + M(m,n)$ for all $m < n$. Verified: no Solve time: 5m02s Solution Fix $m<n$. Let $T = M(m,n+1)$ and $S = M(m,n)$. The hypothesis states that $M(m,n+1) < M(m+1,n) \quad \text{for all } m<n,$ hence in particular T < M(m+1,n). \tag{1} Consider an optimal...
TAOCP 5.3.1 Exercise 8
Section 5.3.1: Minimum-Comparison Sorting Exercise 8. [ M23 ] [M23] (Optimum exchange sorting.) Every exchange sorting algorithm as defined in Section 5.2.2 can be represented as a comparison-exchange tree, namely a binary tree structure whose internal nodes have the form $i : j$ for $i < j$, interpreted as the following operation: “If $K_i < K_j$, continue by taking the left branch of the tree; if $K_i > K_j$, continue...
TAOCP 6.1 Exercise 18
Section 6.1: Sequential Searching Exercise 18. [ M30 ] [M30] (Catenated search.) Suppose that N records are located in a linear array R,... Rwy, with probability p; that record R; will be sought. A search process is called “catenated” if each search begins where the last one left off. If consecutive searches are independent, the average time required will be Vici jen PiPj di, J), where d(i, 7) represents the...
TAOCP 5.3.2 Exercise 18
Section 5.3.2: Minimum-Comparison Merging Exercise 18. [ M40 ] [M40] Study the average number of comparisons used by binary merge. Verified: yes Solve time: 2m16s Let the two sorted sequences have lengths $m$ and $n$. Assume the keys are distinct and all $\binom{m+n}{m}$ interleavings of the two sequences are equally likely. This induces a uniform random sequence of $m$ symbols $A$ and $n$ symbols $B$, and binary merge proceeds by...
TAOCP 6.2.2 Exercise 37
Section 6.2.2: Binary Tree Searching Exercise 37. [ HM26 ] [HM26] (P. J. Bayer, 1975.) Suppose (P1,..., Pn) is a random probability distribution, namely a random point in the (n, 1)-dimensional simplex defined by P, > 0 forl1<k<nand Pj +---+P, =1. (Equivalently, (Pi,...,Pn) is a set of random spacings, in the sense of exercise 3.3.2, 26.) What is the expected value of the entropy A(Pi,..., Pn)? Verified: yes Solve time:...
TAOCP 6.2.2 Exercise 47
Section 6.2.2: Binary Tree Searching Exercise 47. [ M40 ] [M40] Generalize Theorems B and M from binary trees to t-ary trees. If possible, also allow the branching costs to be nonuniform as in exercise 33. Verified: no Solve time: 1m24s Setup A t-ary search tree is taken in the standard sense of Section 6.2.2, generalized so that each internal node contains up to $t-1$ keys and has up to...
TAOCP 5.2.4 Exercise 1
Section 5.2.4: Sorting by Merging Exercise 1. [**] [21] Generalize Algorithm M to a k-way merge of the input files $x_1 < \dots < x_m$; for $i = 1,2,\dots,k$. Verified: yes Solve time: 5m59s Corrected Solution to Exercise 5.2.4.1 The exercise asks to generalize Algorithm M, which merges two sorted sequences, to a k-way merge of $k$ sorted input files $x_1 < x_2 < \dots < x_m$. The goal is...
TAOCP 6.3 Exercise 41
Section 6.3: Digital Searching Exercise 41. [ HM28 ] [HM28] This is an application to group theory. Let G be the free group on the letters {ai,...,@n}, namely the set of all strings a = b1... br, where each 0; is one of the a; ora; and no adjacent pair a;a; or a; a; occurs. The inverse of a is b, ... bj, and we multiply two such strings by...
TAOCP 6.1 Exercise 19
Section 6.1: Sequential Searching Exercise 19. [ M20 ] [M20] Continuing exercise 18, what are the optimal arrangements for catenated searches when the function d(i,7) has the property that d(i,j) + d(j,i) = c for all i 7? [This situation occurs, for example, on tapes without read-backwards capability, when we do not know the appropriate direction to search; for i < j we have, say, d(i,j) = a+b(Ligit---+2Z,;) and d(j,i)...
TAOCP 5.4.1 Exercise 28
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 28. [ 25 ] [25] The text considers only the case that all records to be sorted have a fixed size. How can replacement selection be done reasonably well on variable-length records? Verified: yes Solve time: 3m49s The key difficulty is not comparison but storage lifetime : a variable-length record must remain accessible through its descriptor for as long as it may...
TAOCP 6.2.1 Exercise 11
Section 6.2.1: Searching an Ordered Table Exercise 11. [ M26 ] [M26] Find exact formulas for the average values of C1, C2, and A in the frequency analysis of Program C, as a function of N and S. Verified: no Solve time: 2m44s We restart from the actual structure of Program C and compute the averages directly from the frequency model, without introducing non-uniform quantities as constants. 1. Frequency model...
TAOCP 5.2.3 Exercise 9
Section 5.2.3: Sorting by Selection Exercise 9. [**] [M20] How many times will −∞ be compared with −∞ when the bottom-up method of Fig. 23 is used to sort a file of 2ⁿ elements into order? Verified: yes Solve time: 2m26s Let the file contain $2^n$ elements and consider the bottom-up method of Fig. 23. At the first stage, the $2^{n-1}$ comparisons occur between actual keys, so no $-\infty$ values...
TAOCP 5.2.5 Exercise 2
Section 5.2.5: Sorting by Distribution Exercise 2. [**] [13] Is Algorithm R a stable sorting method? Verified: yes Solve time: 1m25s Algorithm R performs a sequence of $p$ distribution passes, each pass grouping records into $M$ FIFO queues according to a single digit $a_{p+1-k}$. Within a fixed pass, the only modification of links is performed by step R4, which executes $$ \text{LINK}(\text{TOP}[i]) \leftarrow P,\quad \text{TOP}[i] \leftarrow P, $$ so each...
TAOCP 5.4.2 Exercise 27
Section 5.4.2: The Polyphase Merge Exercise 27. [ 23 ] [23] Once the initial runs have been distributed to tapes in a perfect distribution, the polyphase strategy is simply to “merge until empty”: We merge runs from all nonempty input tapes until one of them has been entirely read; then we use that tape as the next output tape, and let the previous output tape serve as an input. Does...
TAOCP 5.2.1 Exercise 10
Section 5.2.1: Sorting by Insertion Exercise 10. [ 22 ] [22] If $K_i > K_j$, when we begin step D3, Algorithm D specifies a lot of actions that accomplish nothing. Show how to modify Program D so that this redundant computation can be avoided, and discuss the merits of such a modification. Verified: yes Solve time: 1m29s Solution In step D3, Program D performs three actions before any comparison outcome...
TAOCP 6.1 Exercise 10
Section 6.1: Sequential Searching Exercise 10. [ M20 ] [M20] The best arrangement of records in a sequential table is specified by (4); what is the worst arrangement? Show that the average number of comparisons in the worst arrangement has a simple relation to the average number of comparisons in the best arrangement. Verified: yes Solve time: 1m09s Solution Let $p_1, p_2, \dots, p_N$ be the probabilities that the argument...
TAOCP 5.4.5 Exercise 1
Section 5.4.5: The Oscillating Sort Exercise 1. [ 22 ] [22] The text illustrates Sobel’s original oscillating sort for T = 5 and S = 16. Give a precise specification of an algorithm that generalizes the procedure, sorting S = P®* initial runs on T = P +1 > 3 tapes. Strive for simplicity. Verified: no Solve time: 1m10s Solution Let the tapes be $0,1,\dots,P$, where tape $q$ is the...
TAOCP 6.3 Exercise 43
Section 6.3: Digital Searching Exercise 43. [ HM42 ] [HM42] Analyze the height of a random M-ary trie that has N keys and cutoff parameter s as in exercise 20. (When s = 1, this is the length of the longest common prefix of N long random words in an M-ary alphabet.) Verified: no Solve time: 5m33s Working
TAOCP 5.5 Exercise 81
Section 5.5: Summary, History, and Bibliography Exercise 81. [**] [Initialize.] Set «<< 1. $2. [Compare.] If K = K;, the algorithm terminates successfully. $3. [Advance.] Increase i by 1. S4. [End of file?] If 7 < N, go back to $2. Otherwise the algorithm terminates unsuccessfully. J Notice that this algorithm can terminate in two different ways, successfully (having located the desired key) or unsuccessfully (having established that the given...
TAOCP 5.2.5 Exercise 9
Section 5.2.5: Sorting by Distribution Exercise 9. [ 20 ] [20] Continuing exercise 8, what changes should be made to the algorithms when the keys are numbers expressed in signed magnitude notation? Verified: yes Solve time: 1m51s Solution Let a signed magnitude key be a $p$-tuple $(s, a_2, a_3, \dots, a_p),$ where $s \in {0,1}$ is the sign digit and $(a_2,\dots,a_p)$ is the magnitude expressed in radix $M$. In signed...
TAOCP 6.1 Exercise 6
Section 6.1: Sequential Searching Exercise 6. [ 20 ] [20] Add three more instructions to Program Q’, reducing its running time to about (3.33C + constant) w. Verified: no Solve time: 4m01s 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 to actual MIX registers and jump semantics. We restart from a...
TAOCP 5.4.7 Exercise 4
Section 5.4.7: External Radix Sorting Exercise 4. [ M23 ] [M23] Prove that Ashenhurst’s distribution pattern is the best way to sort 10 keys on four tapes without reading backwards, in the sense that the associated tree has minimum external path length over all strongly 4-fifo trees. (Thus, it is essentially the best method if we ignore rewind time.) Verified: no Solve time: 4m49s The previous solution failed because it...
TAOCP 5.2.4 Exercise 6
Section 5.2.4: Sorting by Merging Exercise 6. [ 22 ] [22] Revise step L1 of Algorithm L so that the two-way merge is “natural,” taking advantage of ascending runs that are initially present. (In particular, if the input is already sorted, step L2 should terminate the algorithm immediately after your step L1 has acted.) Verified: yes Solve time: 1m14s Solution Let Algorithm L be the straight two-way merge sort in...
TAOCP 5.4.1 Exercise 10
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 10. [ 26 ] [26] The initial setting of the LOSER pointers in step R1 usually doesn’t correspond to any actual tournament, since external node P + 7 may not lie in the subtree below internal node j. Explain why Algorithm R works anyway. [Hint: Would the algorithm work if {LOSER (LOC(X[0])),..., LOSER(LOC(.X [P, 1]))} were set to an arbitrary permutation of...
TAOCP 6.3 Exercise 24
Section 6.3: Digital Searching Exercise 24. [ M30 ] [M30] Consider an M-ary trie that has been represented as a forest (see Fig. 31). Find exact and asymptotic expressions for a) the average number of nodes in the forest; b) the average number of times “P <« RLINK(P)” is performed during a random successful search. Verified: no Solve time: 5m51s The error in the previous solution is not a minor...
TAOCP 6.2.1 Exercise 24
Section 6.2.1: Searching an Ordered Table Exercise 24. [ 23 ] [23] We have seen in Sections 2.3.4.5 and 5.2.3 that the complete binary tree is a convenient way to represent a minimum-path-length tree in consecutive locations. Devise an efficient search method based on this representation. [Hint: Is it possible to use multiplication by 2 instead of division by 2 in a binary search?] Verified: yes Solve time: 4m11s We...
TAOCP 5.2.1 Exercise 2
Section 5.2.1: Sorting by Insertion Exercise 2. [**] [11] Would Algorithm S still sort numbers correctly if the relation “kK > Kk,” in step S3 were replaced by “Kk > k;”? Verified: yes Solve time: 1m15s Let step S4 in Algorithm S be the comparison step that determines whether the current key $K$ should be inserted before $K_i$ or whether $K_i$ should be moved right. The original condition enforces the...
TAOCP 5.4.6 Exercise 2
Section 5.4.6: Practical Considerations for Tape Merging Exercise 2. [ 15 ] [15] Explain why the first buffer for File 2, in line 6 of Fig. 84, is completely blank. Verified: no Solve time: 3m34s The key point is not that File 2 is “unused”, but how Algorithm B assigns and clears buffers when a file changes role and when the first output block is actually produced. In Fig. 84,...
TAOCP 5.3.3 Exercise 13
Section 5.3.3: Minimum-Comparison Selection Exercise 13. [ M49 ] [M49] What is the asymptotic value of $V_{i/2}(n)$, as $n \to \infty$? Verified: yes Solve time: 3m25s We restart the argument from the definition used in this section of TAOCP, where $V_r(n)$ denotes the generalized power sum $$ V_r(n) = \sum_{k=1}^n k^r, $$ extended to complex $r$ by analytic continuation. We analyze the case $r = i/2$. For $r \neq -1$,...
TAOCP 6.2.2 Exercise 23
Section 6.2.2: Binary Tree Searching Exercise 23. [ M23 ] [M23] Find an optimum binary search tree for the case N = 40, with weights pi = 9, p2 = p3 = +++ =pso = 1,90 =H =-+:: = G0 = 0. (Don’t use a computer.) Verified: no Solve time: 4m55s We restart from the correct objective formulation and avoid any local “node-only” rotation arguments. 1. Correct cost formulation Let...
TAOCP 5.1.4 Exercise 6
Section 5.1.4: Tableaux and Involutions Exercise 6. [ 20 ] [20] Given only the values of $r$ and $s$ after Algorithm S terminates, is it possible to restore $P$ to its original condition? Verified: yes Solve time: 1m17s Solution Let Algorithm S be the full sequence of insertions described in Algorithm I applied successively, terminating with a tableau $P$ and a final added position $(r,s)$ determined at the last insertion...
TAOCP 5.3.2 Exercise 8
Section 5.3.2: Minimum-Comparison Merging Exercise 8. [ 24 ] [24] Prove that $M(2,8) < 6$, by finding an algorithm that merges two elements with eight others using at most six comparisons. Verified: yes Solve time: 3m04s We construct a deterministic comparison algorithm and verify a uniform worst-case bound of $6$ comparisons. Let $A_1 < A_2$ and $B_1 < \cdots < B_8$. We merge by first locating the position of $A_2$,...
TAOCP 6.2.1 Exercise 14
Section 6.2.1: Searching an Ordered Table Exercise 14. [ 21 ] [21] Explain how to extend Algorithm F so that it will apply for all N > 1. Verified: yes Solve time: 1m23s Solution Let $N>1$ be arbitrary. Choose $k$ such that $F_{k+1} \ge N+1 \quad \text{and} \quad F_k < N+1.$ Define $M = F_{k+1}-1,$ so that $M \ge N$ and $M+1 = F_{k+1}$ is a Fibonacci number. Extend the...
TAOCP 5.3.2 Exercise 2
Section 5.3.2: Minimum-Comparison Merging Exercise 2. [ 22 ] [22] When $m = 1$, every merging algorithm without redundant comparisons defines an extended binary tree with $\binom{m+n}{m} = n+1$ external nodes. Prove that, conversely, every extended binary tree with $n+1$ external nodes corresponds to some merging algorithm with $m = 1$. Verified: yes Solve time: 1m33s Solution Let $m=1$. We merge the singleton list ${A_1}$ with the sorted list $B_1...
TAOCP 5.4.2 Exercise 26
Section 5.4.2: The Polyphase Merge Exercise 26. [ M21 ] [M21] Analyze the behavior of the tape-splitting polyphase merge on four tapes, when S = 2” and when S$ = 2” + 2"~'. (See exercise 25.) Verified: no Solve time: 1m08s Solution Let $T=4$, so $P=T-1=3$ and the tape-splitting polyphase merge uses the 3-way Fibonacci system defined by the third-order recurrence $$ F_n = F_{n-1}+F_{n-2}+F_{n-3}\quad (n\ge 3), $$ with initial...
TAOCP 6.2.2 Exercise 8
Section 6.2.2: Binary Tree Searching Exercise 8. [ M38 ] [M38] Let p(n,k) be the probability that k is the total internal path length of a tree built by Algorithm T from n randomly ordered keys. (The internal path length is the number of comparisons made by tree insertion sorting as the tree is being built.) a) Find a recurrence relation that defines the corresponding generating function. b) Compute the...
TAOCP 5.3.1 Exercise 2
Section 5.3.1: Minimum-Comparison Sorting Exercise 2. [**] [16] When keys can be equal, each comparison may have three results instead of two: $K_i < K_j$, $K_i = K_j$, $K_i > K_j$. Sorting algorithms for this general situation can be represented as extended ternary trees, in which each internal node $v$ has three subtrees; the left, middle, and right subtrees correspond respectively to the three possible outcomes of the comparison. Draw...
TAOCP 6.2.1 Exercise 19
Section 6.2.1: Searching an Ordered Table Exercise 19. [ M42 ] [M42] Carry out a detailed analysis of the average running time of the algorithm suggested in exercise 14. Verified: no Solve time: 4m29s We restart the analysis from the structure actually used in Algorithm F (as modified in Exercise 14): a Fibonacci tree representation where the search space consists of all internal and external nodes of a full Fibonacci...
TAOCP 6.2.2 Exercise 16
Section 6.2.2: Binary Tree Searching Exercise 16. [ 25 ] [25] Is the deletion operation commutative? That is, if Algorithm D is used to delete X and then Y, is the resulting tree the same as if Algorithm D is used to delete Y and then X? Verified: no Solve time: 5m16s The previous solution fails because it tries to reduce structural equality of binary search trees to inorder equality...
TAOCP 5.3.2 Exercise 15
Section 5.3.2: Minimum-Comparison Merging Exercise 15. [ 12 ] [12] Step H1 of the binary merge algorithm may require the calculation of the expression $\lfloor \lg(n/m) \rfloor$, for $n > m$. Explain how to compute this easily without division or calculation of a logarithm. Verified: yes Solve time: 1m Solution We compute $\left\lfloor \lg(n/m) \right\rfloor$ for $n>m$ by characterizing it as the unique integer $k \ge 0$ such that $m...
TAOCP 5.2.3 Exercise 6
Section 5.2.3: Sorting by Selection Exercise 6. [**] [M25] What is the average number of comparisons performed by the algorithm of exercise 8, for random input? Verified: yes Solve time: 3m39s We analyze the algorithm of Exercise 5.2.3.5 (left-to-right maximum search used repeatedly in a selection-type procedure). Let $C(N)$ be the average number of comparisons performed when selecting maxima repeatedly on a random permutation of $N$ keys using the modified...
TAOCP 5.4.1 Exercise 27
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 27. [ HM30 ] [HM30] (W. Dobosiewicz.) When natural selection is used with P’ < P, we need not stop forming a run when the reservoir becomes full; we can store records that do not belong to the current run in the main priority queue, as in replacement selection, until only P’ records of the current run are left. Then we can...
TAOCP 6.2.2 Exercise 15
Section 6.2.2: Binary Tree Searching Exercise 15. [ 23 ] [23] Let a1 a2 a3 a4 be a permutation of {1, 2,3, 4}, and let 7 = 1, 2, or 3. Take the one-element tree with key a; and insert a2, a3 using Algorithm T; then delete a; using Algorithm D; then insert a4 using Algorithm T. How many of the 4! x 3 possibilities produce trees of shape I,...
TAOCP 6.3 Exercise 9
Section 6.3: Digital Searching Exercise 9. [ 21 ] [21] Write a MIX program for Algorithm D, and compare it to Program 6.2.2T. You may use binary operations such as SLB (shift left AX binary), JAE (jump if A even), etc.; and you may also use the idea of exercise 8 if it helps. Verified: no Solve time: 2m44s The original attempt fails mainly because it mixes abstract register notation...
TAOCP 5.2.1 Exercise 13
Section 5.2.1: Sorting by Insertion Exercise 13. [ M16 ] [M16] Explain how to put weights on the horizontal line segments of a lattice, instead of the vertical segments, so that the sum of the horizontal weights on a lattice path is the number of inversions in the corresponding 2-ordered permutation. Verified: yes Solve time: 2m55s Start from the standard lattice representation of a permutation used in Section 5.2.1: a...
TAOCP 5.4.3 Exercise 5
Section 5.4.3: The Cascade Merge Exercise 5. [ 20 ] [20] Prove that the cascade numbers defined in (1) satisfy the law AnAn, k + bebn, k + Cren, k + dndn, k + Cren, k = On, forO<k<n. [Hint: Interpret this relation by considering how many runs of various lengths are output during the kth pass of a complete cascade sort.] Verified: no Solve time: 2m23s Solution Let $$...
TAOCP 6.2.2 Exercise 40
Section 6.2.2: Binary Tree Searching Exercise 40. [ M26 ] [M26] Complete the proof of Lemma Z. Verified: no Solve time: 3m19s Let $T_n$ be a binary search tree built from a uniformly random permutation of $n$ distinct keys, so every BST shape consistent with in-order orderings occurs with the standard BST probability model. Lemma Z (completion). If one key is selected uniformly at random from the $n$ keys in...
TAOCP 5.4.1 Exercise 4
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 4. [ 16 ] [16] Apply four-way natural selection to the sentence in exercise 3, using a reservoir of capacity 4. Verified: no Solve time: 4m38s We restart the construction from the correct replacement-selection algorithm (Knuth, sorting by replacement selection with a min-heap of size 4). The key invariant is: The heap always contains at most 4 elements. Each output is the...
TAOCP 5.1.2 Exercise 10
Section 5.1.2: Permutations of a Multiset Exercise 10. [**] [M30] True or false: Although the factorization into primes isn’t quite unique, according to Theorem C, we can ensure uniqueness in the following way: “There is a linear ordering $<$ of the set of primes such that every permutation of a multiset has a unique factorization $\sigma_1 \tau \sigma_2 \tau \cdots \tau \sigma_n$ into primes subject to the condition that $\sigma_i...
TAOCP 5.3.4 Exercise 6
Section 5.3.4: Networks for Sorting Exercise 6. [**] [28] Let $T'(n)$ be the minimum number of stages needed to sort $n$ distinct numbers by making simultaneous disjoint comparisons (without necessarily obeying the network constraint); such comparisons can be represented as a node containing a set of pairs ${i_1:j_1, i_2:j_2, ..., i_r:j_r}$ where $i_1, j_1, i_2, j_2, ..., i_r, j_r$ are distinct, with $2^r$ branches below this node for the respective...
TAOCP 5.3.2 Exercise 5
Section 5.3.2: Minimum-Comparison Merging Exercise 5. [ M30 ] [M30] Prove that $\underline{M}(m,n) < \underline{M}(m,n+1)$. Verified: no Solve time: 4m31s Let $T$ be any comparison decision tree for merging $A_1<\cdots<A_m$ with $B_1<\cdots<B_{n+1}$, and let its height be the number of comparisons in the worst case. We prove that every such tree has height at least $\underline{M}(m,n)+1$. Since $\underline{M}(m,n+1)$ is the minimum possible height, this implies $$ \underline{M}(m,n+1)\ge \underline{M}(m,n)+1. $$ 1....
TAOCP 5.4.8 Exercise 4
Section 5.4.8: Two-Tape Sorting Exercise 4. [ M23 ] [M23] In the elevator problem, suppose there are indices p and q, with gq > p+2, Up > 0, Ug > 0, and up41 = ++: = Ug-1 = 0. Explain how to construct a schedule requiring at most (9) units of time. [M23] True or false: After step K1 of the algorithm in Theorem K, nobody on the elevator has...
TAOCP 5.4.2 Exercise 6
Section 5.4.2: The Polyphase Merge Exercise 6. [ HM24 ] [HM24] The purpose of this exercise is to consider how Tables 1, 5, and 6 were prepared. Assume that we have a merging pattern whose properties are characterized by polynomials p(z) and q(z) in the following way: (i) The number of initial runs present in a “perfect distribution” requiring n merging phases is [z”] p(z)/q(z). (ii) The number of initial...
TAOCP 5.3.2 Exercise 16
Section 5.3.2: Minimum-Comparison Merging Exercise 16. [ 18 ] [18] For which $m$ and $n$ is Hwang and Lin’s binary merging algorithm optimum, for $1 < m < n < 10$? Verified: no Solve time: 2m22s Solution Let $H(m,n)$ denote the number of comparisons performed by Hwang and Lin’s binary merging algorithm when merging $A_1<\cdots<A_m$ with $B_1<\cdots<B_n$ under worst-case behavior. Optimality for given $(m,n)$ means $H(m,n)=M(m,n)$. The algorithm proceeds by...
TAOCP 5.4.6 Exercise 11
Section 5.4.6: Practical Considerations for Tape Merging Exercise 11. [ 23 ] [23] By modifying the appropriate entries in Table 1, estimate how long the first nine examples of Chart A would have taken if we had a combined low speed/high speed rewind. Assume that p = 1 when the tape is less than about one-fourth full, and that the rewind time for fuller tapes is approximately five seconds plus...
TAOCP 6.3 Exercise 39
Section 6.3: Digital Searching Exercise 39. [ M43 ] [M43] Develop an algorithm to find optimum digital search trees, analogous to the optimum binary search trees considered in Section 6.2.2. Verified: yes Solve time: 4m28s We construct a fully rigorous solution by cleanly separating the structural lemma from the contraction argument, avoiding informal swapping arguments. Problem restatement We are given keys $K_1,\dots,K_n$ with probabilities $p_1,\dots,p_n>0$, $\sum_{i=1}^n p_i=1$. A digital search...
TAOCP 5.2.1 Exercise 6
Section 5.2.1: Sorting by Insertion Exercise 6. [ 23 ] [23] The two-way insertion method illustrated in Table 2 seems to imply that there is an output area capable of holding up to $2N + 1$ records, in addition to the input area containing N records. Show that two-way insertion can be done using only enough space for $N + 1$ records, including both input and output. Verified: yes Solve...
TAOCP 6.2.2 Exercise 7
Section 6.2.2: Binary Tree Searching Exercise 7. [ M25 ] [M25] (S. R. Arora and W. T. Dent.) After n elements have been inserted into an initially empty tree, in random order, what is the average number of comparisons needed by Algorithm T to find the mth largest element, given the key of that element? Verified: yes Solve time: 1m16s Solution Let keys $1,2,\dots,n$ be inserted in random order to...
TAOCP 6.2.2 Exercise 9
Section 6.2.2: Binary Tree Searching Exercise 9. [ 41 ] [41] We have proved that tree search and insertion requires only about 21In N comparisons when the keys are inserted in random order; but in practice, the order may not be random. Make empirical studies to see how suitable tree insertion really is for symbol tables within a compiler and/or assembler. Do the identifiers used in typical large programs lead...
TAOCP 5.4.2 Exercise 19
Section 5.4.2: The Polyphase Merge Exercise 19. [ 21 ] [21] Make a table analogous to (1), for Caron’s polyphase sort on six tapes. 5.4.2 THE POLYPHASE MERGE 287 Verified: no Solve time: 2m30s The previous solution fails because it replaces the actual construction of Caron’s polyphase schedule with an unproven symmetry argument. The correct approach is to derive the run distributions directly from the defining recurrence of polyphase merging...
TAOCP 5.3.2 Exercise 17
Section 5.3.2: Minimum-Comparison Merging Exercise 17. [ M25 ] [M25] Prove (21). [Hint: The inequality isn’t very tight.] Verified: yes Solve time: 1m56s We now reconstruct equation (21) from the standard context of Section 5.3.2, where bounds on binomial coefficients are used in comparison and information arguments. Statement of (21) For integers $1 \le m \le n$, $$ \binom{n}{m} \le \left(\frac{en}{m}\right)^m. $$ This is the standard crude upper bound on...
TAOCP 5.4.1 Exercise 11
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 11. [ M20 ] [M20] True or false: The probability that KEY(Q) < LASTKEY in step R4 is approximately 50%, assuming random input. Verified: no Solve time: 4m09s Corrected solution We analyze the random-permutation model: all $n!$ input permutations of distinct keys are equally likely. The algorithm (replacement selection) is deterministic and comparison-based, so for each input permutation it produces a well-defined...
TAOCP 6.2.1 Exercise 15
Section 6.2.1: Searching an Ordered Table Exercise 15. [ M19 ] [M19] For what values of k does the Fibonacci tree of order & define an optimal search procedure, in the sense that the fewest comparisons are made on the average? A424 SEARCHING 6.2.1 Verified: yes Solve time: 1m36s Solution Let $T_k$ denote the Fibonacci tree of order $k$. Let $N_k$ be its number of internal (circular) nodes. From the...
TAOCP 5.4.5 Exercise 2
Section 5.4.5: The Oscillating Sort Exercise 2. [ 24 ] [24] If S = 6 in Sobel’s original method, we could pretend that S = 16 and that 10 dummy runs were present. Then Phase 3 in the text’s example would put dummy runs Ap on T4 and T5; Phase 4 would merge the A;’s on T2 and T3 into a D2 on T1; Phases 5-8 would do nothing; and...
TAOCP 5.3.1 Exercise 7
Section 5.3.1: Minimum-Comparison Sorting Exercise 7. [ M25 ] [M25] (S. M. Chase.) Let $a_1, a_2, \ldots, a_n$ be a permutation of ${1, 2, \ldots, n}$. Prove that any algorithm that decides whether this permutation is even or odd (that is, whether it has an even or odd number of inversions), based solely on comparisons between the $a$'s, must make at least $n \lg n$ comparisons, even though the algorithm...
TAOCP 5.1.4 Exercise 5
Section 5.1.4: Tableaux and Involutions Exercise 5. [**] [M20] Prove that $P$ is a tableau when Algorithm S terminates, if it was a tableau initially. Verified: no Solve time: 3m41s We give a complete corrected proof by isolating the precise mechanism that guarantees both row and column inequalities during each bumping operation, without circular reasoning. Corrected solution We prove that if $P$ is a tableau initially, then after every step...
TAOCP 5.4.9 Exercise 5
Section 5.4.9: Disks and Drums Exercise 5. [ M20 ] [M20] When two disks are being used, so that reading on one is overlapped with writing on the other, we cannot use merge patterns like that of Fig. 93 since some leaves are at even levels and some are at odd levels. Show how to modify the construction of Theorem K in order to produce trees that are optimal subject...
TAOCP 5.4.1 Exercise 17
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 17. [ 20 ] [20] What is output by Algorithm R when the input keys are in decreasing order, Kk, > Ky>---> Kw? Verified: yes Solve time: 1m34s Solution Let the input keys satisfy $K_1 > K_2 > \cdots > K_N.$ Algorithm R initializes a selection tree with the first $P$ records. These $P$ keys all have run number $1$. During run...
TAOCP 6.2.2 Exercise 4
Section 6.2.2: Binary Tree Searching Exercise 4. [ M24 ] [M24] (A. D. Booth and A. J. T. Colin.) Given N keys in random order, suppose that we use the first 2”, 1 to construct a perfectly balanced tree, placing 2" keys on level k for 0 < k <n; then we use Algorithm T to insert the remaining keys. What is the average number of comparisons in a successful...
TAOCP 5.2.4 Exercise 2
Section 5.2.4: Sorting by Merging Exercise 2. [**] [M24] Assuming that each of the $\binom{n}{m}$ possible arrangements of m x’s among n y’s is equally likely, find the mean and standard deviation of the number of times step M2 is performed during Algorithm M. What are the maximum and minimum values of this quantity? Verified: no Solve time: 2m50s Let $X$ be the number of times step M2 is executed...
TAOCP 5.3.3 Exercise 15
Section 5.3.3: Minimum-Comparison Selection Exercise 15. [ M35 ] [M35] (W. Cunto and J. I. Munro.) Prove that $V_i(n) > n + t - 2$ when $t < \lfloor n/2 \rfloor$. Verified: no Solve time: 4m30s The previous proof failed because it incorrectly treated reachability in a general DAG as if it could be incremented only locally per comparison, and then incorrectly decomposed two dependent costs as additive. The correct...
TAOCP 5.2.1 Exercise 11
Section 5.2.1: Sorting by Insertion Exercise 11. [ M10 ] [M10] What path in a lattice like that of Fig. 11 corresponds to the permutation 12537486911 10 12? Verified: yes Solve time: 2m59s Let $$ \pi = (1,2,5,3,7,4,8,6,9,11,10,12). $$ We use the standard TAOCP boundary construction: the lattice path from $(0,0)$ to $(n,n)$ is determined by $$ x_k = #{, i \le k : \pi(i) \le k ,}, \qquad k=1,\dots,n....
TAOCP 5.3.2 Exercise 3
Section 5.3.2: Minimum-Comparison Merging Exercise 3. [ M24 ] [M24] Prove that $\underline{M}(1,n) = M(1,n)$ for all $n$. Verified: yes Solve time: 2m21s We restart from the definitions of the two quantities in Knuth’s merging model. Let $A_1$ be a single-element sorted list and $B_1 < \cdots < B_n$ a sorted list. A merge proceeds by comparisons only between the current “heads” of the two lists. Since $A_1$ is always...
TAOCP 6.1 Exercise 1
Section 6.1: Sequential Searching Exercise 1. [ M20 ] [M20] When all the search keys are equally probable, what is the standard deviation of the number of comparisons made in a successful sequential search through a table of N records? Verified: yes Solve time: 1m01s Solution In a successful sequential search through $N$ records, every position $i \in {1,\dots,N}$ occurs with probability $1/N$. The number of comparisons is therefore the...
TAOCP 6.2.2 Exercise 48
Section 6.2.2: Binary Tree Searching Exercise 48. [**] [M47| Carry out a rigorous analysis of the steady state of a binary search tree subjected to random insertions and deletions. Verified: no Solve time: 57s Let $T_n$ denote the set of binary search trees on $n$ distinct keys, and consider the Markov process in which at each step an insertion of a random key and a deletion of a uniformly chosen...
TAOCP 5.4.1 Exercise 15
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 15. [ 20 ] [20] True or false: The final run produced by replacement selection never contains more than P records. Discuss your answer. Verified: yes Solve time: 1m47s Solution Let the algorithm be replacement selection with a selection tree containing $P$ external nodes as defined in Section 5.4.1. At every moment during execution, each external node contains either a record currently...
TAOCP 6.3 Exercise 6
Section 6.3: Digital Searching Exercise 6. [ 15 ] [15] What digital search tree is obtained if the fifteen 4-bit binary keys 0001, 0010, 0011, ..., 1111 are inserted in increasing order by Algorithm D? (Start with 0001 at the root and then do fourteen insertions.) [M26] If the fifteen keys of exercise 6 are inserted in a different order, we might get a different tree. Of all the 15!...
TAOCP 5.2.1 Exercise 3
Section 5.2.1: Sorting by Insertion Exercise 3. [**] [30] Is Program S the shortest possible sorting program that can be written for MIX, or is there a shorter program that achieves the same effect? Verified: no Solve time: 9m01s No. Program S is a very compact implementation of straight insertion, but the exercise asks whether it is the shortest possible MIX sorting program having the same effect, not whether it...
TAOCP 5.3.2 Exercise 12
Section 5.3.2: Minimum-Comparison Merging Exercise 12. [ M21 ] [M21] Let $R_n(i,j)$ be the least number of comparisons required to sort the distinct objects ${\alpha, \beta, X_1, \ldots, X_n}$, given the relations $$\alpha < \beta,\qquad X_1 < X_2 < \cdots < X_n,\qquad \alpha < X_{i+1},\qquad \beta > X_{n-j}.$$ (The condition $\alpha < X_{i+1}$ or $\beta > X_{n-j}$ becomes vacuous when $i \ge n$ or $j \ge n$. Therefore $R_n(n,n) =...
TAOCP 5.3.2 Exercise 6
Section 5.3.2: Minimum-Comparison Merging Exercise 6. [ M26 ] [M26] The stated proof of Theorem K requires that a lot of cases be verified by computer. How can the number of such cases be drastically reduced? Verified: no Solve time: 2m21s Setup The proof of Theorem K is carried out by verifying that a proposed closed form agrees with the values of the adversary functions $_M(m,n)$ defined by the recurrence...
TAOCP 6.2.2 Exercise 41
Section 6.2.2: Binary Tree Searching Exercise 41. [ 21 ] [21] Figure 18 shows the construction of a tangled binary tree. List its leaves in left-to-right order. Verified: yes Solve time: 3m42s The reviewer’s critique is correct: the previous response failed because it never instantiated the computation on the actual data. However, there is a deeper issue that must be addressed before any “corrected execution” is possible. The exercise explicitly...
TAOCP 5.4.3 Exercise 9
Section 5.4.3: The Cascade Merge Exercise 9. [ HM26 ] [HM26] Derive (14). Verified: yes Solve time: 2m31s We restart from the cascade structure in Algorithm C and derive equation (14) in a way that correctly matches the backward extension construction and applies Lagrange inversion in its valid form. 1. Correct structural decomposition of cascade states Let $T \ge 3$. Let $a_n$ be the number of configurations in the first...
TAOCP 5.4.3 Exercise 3
Section 5.4.3: The Cascade Merge Exercise 3. [ 23 ] [23] Prepare a table that shows what happens when 100 initial runs are sorted on six tapes using Algorithm C. Verified: no Solve time: 4m39s The earlier solution fails primarily because it never instantiates Algorithm C’s actual state mechanism: a 5-way polyphase merge on six tapes driven by a 5-term Fibonacci-type (pentanacci) distribution, with exhaustion events determining phase changes. We...
TAOCP 5.1.4 Exercise 3
Section 5.1.4: Tableaux and Involutions Exercise 3. [**] [M18] (P. Erdős, G. Szekeres.) Prove that any permutation containing more than $n^2$ elements has a monotonic subsequence of length greater than $n$; but there are permutations of $n^2$ elements with no monotonic subsequences of length greater than $n$. [Hint: See the previous exercise.] Verified: yes Solve time: 1m26s Let $P$ be the tableau corresponding to a permutation $a_1 a_2 \dots a_m$....
TAOCP 5.4.3 Exercise 2
Section 5.4.3: The Cascade Merge Exercise 2. [ 22 ] [22] Compare cascade sorting on three tapes, using Algorithm C, to polyphase sorting on three tapes, using Algorithm 5.4.2D. What similarities and differences can you find? Verified: no Solve time: 4m01s Corrected Solution We compare cascade sorting on three tapes (Algorithm C) with polyphase merging on three tapes (Algorithm 5.4.2D), focusing on how runs are distributed, how merging proceeds, and...
TAOCP 6.1 Exercise 17
Section 6.1: Sequential Searching Exercise 17. [ M23 ] [M23] (J. R. Jackson.) Suppose you have to do n jobs; the jth job takes T; units of time, and it has a deadline D;. In other words, the jth job is supposed to be finished after at most D; units of time have elapsed. What schedule a1 a2...an for processing the jobs will minimize the maximum tardiness, namely max(Ty,, Da,,...
TAOCP 5.3.1 Exercise 6
Section 5.3.1: Minimum-Comparison Sorting Exercise 6. [**] [HM27] When sorting $n$ elements as in exercise 5, and knowing that all keys are members of the set ${1, 2, \dots, m}$, let $S_m(n)$ be the minimum number of comparisons needed in the worst case. [Thus by exercise 6, $S_m(n) = S(n)$.] Prove that, for fixed $m$, $$S_m(n) \sim n \log_2 m + O(1) \quad \text{as } n \to \infty.$$ 12. [M25]...
TAOCP 5.2.2 Exercise 3
Section 5.2.2: Sorting by Exchanging Exercise 3. [**] [10] Is the bubble sort Algorithm B a stable sorting algorithm? Verified: yes Solve time: 1m42s Yes, Algorithm B is a stable sorting algorithm. Stability requires that if two records have equal keys, their relative order in the input is preserved in the output. In Algorithm B, the only exchanges occur when K_j > K_{j+1} in step B3. If K_j = K_{j+1}...
TAOCP 5.3.1 Exercise 4
Section 5.3.1: Minimum-Comparison Sorting Exercise 4. [**] [M20] When sorting $n$ elements as in exercise 7, knowing that all keys are 0 or 1, what is the minimum number of comparisons in the worst case? Verified: yes Solve time: 2m50s The goal is to determine the sorted order of $n$ keys, knowing each key is either $0$ or $1$. The sorted output is completely determined once the partition of the...
TAOCP 5.4.2 Exercise 7
Section 5.4.2: The Polyphase Merge Exercise 7. [ HM22 ] [HM22] Let ap be the dominant root of the polynomial f,(z) in exercise 5. What is the asymptotic behavior of ap, as p, oo? Verified: no Solve time: 1m10s Solution Let $$ f_p(z)=z^p - z^{p-1}-\cdots-1. $$ Multiplying by $z-1$ gives $$ (z-1)f_p(z)=z^{p+1}-2z^p+1. $$ The dominant root $a_p>1$ of $f_p$ is also the unique root $>1$ of $$ z^{p+1}-2z^p+1=0, $$ since...
TAOCP 6.3 Exercise 21
Section 6.3: Digital Searching Exercise 21. [ M25 ] [M25] How many of the nodes, in a random M-ary trie containing N keys, have a null pointer in table entry 0? (For example, 9 of the 12 nodes in Table 1 have a null pointer in the “.,” position. “Random” in this exercise means as usual that the digits of the keys are uniformly distributed between 0 and M, 1.)...
TAOCP 5.4.9 Exercise 14
Section 5.4.9: Disks and Drums Exercise 14. [ 40 ] [40] Using the square root method of buffer allocation, the seek time for the merge pattern in Fig. 92 would be proportional to (/2 +VJ744VJ14vV1i4+ v8)? + (VI + V1+ V2)" + (VI + V24+ V1+ V4)" + (V1+ VI4+ V2)’; this is the sum, over each internal node, of (./ny + +++ +Vmm + Vni +++: +!m); where that...
TAOCP 5.3.2 Exercise 14
Section 5.3.2: Minimum-Comparison Merging Exercise 14. [ 41 ] [41] (F. K. Hwang.) Let $h_{3k} = \lfloor 3 \cdot 2^k \rfloor - 1$, $h_{3k+1} = h_{3k} + 3 \cdot 2^{k-1}$, $h_{3k+2} = \lfloor 2^k - 2 \rfloor$ for $k > 3$, and let the initial values be defined so that $$(h_0, h_1, h_2, \ldots) = (1, 1, 2, 2, 3, 4, 5, 7, 9, 11, 14, 18, 23, 29, 38,...
TAOCP 6.3 Exercise 27
Section 6.3: Digital Searching Exercise 27. [ HM31 ] [HM31] What is the asymptotic value of Cy, as given by (14), to within O(1)? Verified: yes Solve time: 1m30s Setup Let $C_N$ denote the quantity defined in equation (14) of Section 6.3. The asymptotic form established earlier in Exercise 6.3.25 is $$ C_N = N \log_M N + O(N). $$ The refinement required here is to determine $C_N$ more precisely...
TAOCP 5.5 Exercise 3
Section 5.5: Summary, History, and Bibliography Exercise 3. [ 87 ] [87] (Stable sorting in minimum storage.) A sorting algorithm is said to require minimum storage if it uses only O((log N )?) bits of memory space for its variables besides the space needed to store the N records. The algorithm must be general in the sense that it works for all N, not just for a particular value of...
TAOCP 5.3.2 Exercise 10
Section 5.3.2: Minimum-Comparison Merging Exercise 10. [ 33 ] [33] Prove that five elements can be merged with nine in at most twelve steps. [Hint: Experience with the adversary suggests first comparing $A_1:B_2$, then trying Verified: no Solve time: 4m14s Working
TAOCP 5.2.3 Exercise 3
Section 5.2.3: Sorting by Selection Exercise 3. [**] [M29] (a) Let a₁a₂...aₙ be a permutation of {1,2,...,N} having C cycles, I inversions, and B changes to the right-to-left maxima when sorted by Program S. Prove that 2B < I + N − C. [Hint: See exercise 5.2.2–1.] (b) Show that I + N − C < ⌊N²/2⌋; hence B can never exceed ⌊N²/4⌋. Verified: no Solve time: 7m38s The previous...
TAOCP 5.4.2 Exercise 10
Section 5.4.2: The Polyphase Merge Exercise 10. [ M27 ] [M27] (Generalized Fibonacci number system.) Prove that every nonnegative integer n has a unique representation as a sum of distinct pth order Fibonacci numbers Fe ) for 7 > p, subject to the condition that no p consecutive Fibonacci numbers are used. Verified: no Solve time: 1m03s Setup Let ${F_n^{(p)}}_{n\ge 0}$ denote the $p$th-order Fibonacci numbers defined in Section 5.4.2,...
TAOCP 5.2.1 Exercise 7
Section 5.2.1: Sorting by Insertion Exercise 7. [ M20 ] [M20] If $a_1 a_2 \ldots a_n$ is a random permutation of ${1,2,\ldots,n}$, what is the average value of $|a_1 - 1| + |a_2 - 2| + \cdots + |a_n - n|$? (This is $n$ times the average net distance traveled by a record during a sorting process.) Verified: yes Solve time: 14m42s Solution Let $a_1 a_2 \dots a_n$ be a...
TAOCP 6.2.2 Exercise 35
Section 6.2.2: Binary Tree Searching Exercise 35. [ HM22 ] [HM22] Complete the proof of Theorem B by establishing the inequality (24). [HM25] (Claude Shannon.) Let X and Y be random variables with finite ranges {x1,...,%m} and {y1,...,yn}, and let pj = Pr(X = xi), qi = Pr(Y = yj), rey = Pr(X = a; and Y = y;). Let H(X) = H(pi,...,pm) and H(Y) = H(qi,...,qn) be the 458...
TAOCP 6.3 Exercise 34
Section 6.3: Digital Searching Exercise 34. [ HM40 ] [HM40] The purpose of this exercise is to find the asymptotic behavior of (18). a) Prove that, ifn > 2, 1 n Bee | wr-tar-by...4 (22 -1)"1+ 29 n > (ae = L( Qi(n, 1) ~ ata): jz Q2<k<n b) Show that the summand in (a) is approximately 1/(e”, 1), 1/x + 1/2, where x = n/2?; the resulting sum equals...
TAOCP 6.3 Exercise 44
Section 6.3: Digital Searching Exercise 44. [ 30 ] [30] (J. L. Bentley and R. Sedgewick.) Explore a ternary representation of tries, in which left and right links correspond to the horizontal branches of (2) while middle links correspond to the downward branches. Verified: yes Solve time: 1m41s Setup Let $\Sigma$ be an ordered alphabet corresponding to the $M$ characters used in Section 6.3, with a total order $<$ consistent...
TAOCP 6.2.2 Exercise 10
Section 6.2.2: Binary Tree Searching Exercise 10. [ 22 ] [22] (R. W. Floyd.) Perhaps we are not interested in the sorting property of Algorithm T, but we expect that the input will come in nonrandom order. Devise a way to keep tree search efficient, by making the input “appear to be” in random order. Verified: yes Solve time: 1m15s Solution Let the incoming keys be $K_1, K_2, \ldots, K_n$,...
TAOCP 5.4.6 Exercise 6
Section 5.4.6: Practical Considerations for Tape Merging Exercise 6. [ 22 ] [22] What changes should be made to Algorithm 5.4.3C in order to convert it into an algorithm for cascade merge with rewind overlap, on T + 1 tapes? Verified: no Solve time: 1m05s Solution Algorithm 5.4.3C performs a cascade merge on $T$ tapes by repeated distribution of runs followed by successive merging passes in which the number of...
TAOCP 6.3 Exercise 11
Section 6.3: Digital Searching Exercise 11. [ 21 ] [21] Can Algorithm 6.2.2D be used without change to delete a node from a digital search tree? Verified: yes Solve time: 1m38s Solution Algorithm 6.2.2D for deletion in a binary search tree relies on the invariant that every node partitions the set of keys into those strictly less than the node key and those strictly greater than it. The replacement step...
TAOCP 5.4.2 Exercise 31
Section 5.4.2: The Polyphase Merge Exercise 31. [ M22 ] [M22] (R. Kemp.) Let Ka(n) be the number of n- 3). ordered trees in which every leaf is at distance d from the root. For example, K3(8) = 7 because of the trees A A be Lids tihp Show that Ka(n) is a generalized Fibonacci number, and find a one-to-one correspondence between oe trees and the ordered partitions considered in...
TAOCP 6.2.2 Exercise 11
Section 6.2.2: Binary Tree Searching Exercise 11. [ 20 ] [20] What is the maximum number of times the assignment S + LLINK(R) might be performed in step D3, when deleting a node from a tree of size N? Verified: yes Solve time: 2m30s We restart the counting from the actual behavior of step D3, since the previous argument misidentified what is being counted. Let $R_0 = \mathrm{RLINK}(T)$. In step...
TAOCP 6.3 Exercise 28
Section 6.3: Digital Searching Exercise 28. [ HM26 ] [HM26] Find the asymptotic average number of digit inspections when searching in a random M-ary digital search tree, for general M > 2. Consider both successful and unsuccessful search, and give your answer to within O(N~'). Verified: no Solve time: 4m54s Corrected solution Let $T_N$ be the Coffman–Eve $M$-ary digital search tree built from $N$ independent random infinite strings over an...
TAOCP 6.2.2 Exercise 27
Section 6.2.2: Binary Tree Searching Exercise 27. [ M33 ] [M33] The object of this exercise is to prove that the sets of roots R(i,j) of optimum binary search trees satisfy R(i,j-1) < RG 5) < RG+1, 9), for j-1 > 2, in terms of the relation defined in exercise 25, when the weights (p1,..., Pn; Go,---,@n) are nonnegative. The proof is by induction on j, i; our task is...
TAOCP 5.4.1 Exercise 21
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 21. [ HM23 ] [HM23]| Determine the approximate length of runs produced by natural selection when P’ < P. {[HM40] The purpose of this exercise is to determine the average run length obtained in natural selection, when P’ > P. Let k = k + @ be a real number > 1, where k = |«| and @ = « mod 1,...
TAOCP 6.2.2 Exercise 14
Section 6.2.2: Binary Tree Searching Exercise 14. [ 22 ] [22] Prove that the path length of the tree produced by Algorithm D with step D1.5 added is never more than the path length of the tree produced without that step. Find a case where step D1.5 actually decreases the path length. Verified: no Solve time: 4m26s The original argument fails because it assumes a uniform “shift” of depths along...
TAOCP 5.4.3 Exercise 4
Section 5.4.3: The Cascade Merge Exercise 4. [ M20 ] [M20] (G. N. Raney.) An “nth level cascade distribution” is a multiset defined as follows (in the case of six tapes): {1,0,0,0,0} is a Oth level cascade distribution; and if {a,b,c,d,e} is an nth level cascade distribution, {a+b+c+d+te, a+b+c+4d, at+b-+c, a+b, a} is an (n + 1)st level cascade distribution. (A multiset is unordered, hence up to 5! different (n...
TAOCP 6.1 Exercise 2
Section 6.1: Sequential Searching Exercise 2. [ 15 ] [15] Restate the steps of Algorithm S, using linked-memory notation instead of subscript notation. (If P points to a record in the table, assume that KEY(P) is the key, INFO(P) is the associated information, and LINK(P) is a pointer to the next record. Assume also that FIRST points to the first record, and that the last record points to A.) Verified:...
TAOCP 5.2.1 Exercise 4
Section 5.2.1: Sorting by Insertion Exercise 4. [**] [M20] Find the minimum and maximum running times for Program S, as a function of N. Verified: yes Solve time: 16m17s The running time of Program S is $9B+10N-3A-9.$ By the results stated in Section 5.2.1, $0\le A\le N-1,\qquad 0\le B\le \frac{N(N-1)}2.$ The minimum running time occurs when the file is already in order. Then there are no inversions, so $B=0$; there...
TAOCP 6.3 Exercise 19
Section 6.3: Digital Searching Exercise 19. [ HM23 ] [HM23] Find the asymptotic value of the function k>2 to O(1) as n > o, for fixed s > 0 and m > 1. [The case s = 0 has already been solved in exercise 5.2.2-50, and the case s = 1, m = 2 has been solved in exercise 5.2.2-48.] Verified: no Solve time: 3m31s The expression in the prompt...
TAOCP 5.4.9 Exercise 16
Section 5.4.9: Disks and Drums Exercise 16. [ 23 ] [23] (R. W. Floyd.) Find an elevator schedule that transports all the people of (28) to their destinations in at most 12 stops. (Configuration (29) shows the situation after one stop, not two.) [HM25] (R. W. Floyd, 1980.) Show that the lower bound of Theorem F can be improved to n(blnn, Inb, 1) Inn + 6(1+ In(1+m/b))’ in the sense...
TAOCP 5.4.6 Exercise 10
Section 5.4.6: Practical Considerations for Tape Merging Exercise 10. [ M23 ] [M23] Use the analyses in Sections 5.4.2 and 5.4.3 to show that the length of each rewind during a standard six-tape polyphase or cascade merge is rarely more than about 54 percent of the file (except for the initial and final rewinds, which cover the entire file). Verified: no Solve time: 4m32s Let $S$ be the total number...
TAOCP 5.1.4 Exercise 12
Section 5.1.4: Tableaux and Involutions Exercise 12. [ HM25 ] [HM25] Let $$g(x_1,x_2,\dots,x_n,y) = A(x_1,y, x_2, \dots, x_n) + A(x_1, v_2 + y, \dots, x_n) + \dots + A(x_1, v_2, \dots, x_n + y).$$ Prove that $$g(a_1,a_2,\dots,a_n,y) = (a_1 + a_2 + \dots + a_n) A(a_1,a_2,\dots,a_n).$$ [Hint: The polynomial $g$ is homogeneous (all terms have the same total degree); and it is antisymmetric in the $x$’s (interchanging $x_i$ and $x_j$...
TAOCP 5.4.2 Exercise 18
Section 5.4.2: The Polyphase Merge Exercise 18. [ 30 ] [30] Does the optimum polyphase distribution produce the best possible merging pattern, in the sense that the total number of initial runs processed is minimized, if we insist that the initial runs be placed on at most T’', 1 of the tapes? (Ignore rewind time.) Verified: no Solve time: 1m18s Setup Let $T > 3$ be fixed and set $P...
TAOCP 6.2.1 Exercise 30
Section 6.2.1: Searching an Ordered Table Exercise 30. [ 27 ] [27] (Involution coding.) Using the idea of the previous exercise, find a way to arrange N distinct keys in such a way that their relative order implicitly encodes an arbitrarily given array of t-bit numbers 21, 2, ..., tm, when m < N/4+4+1, 2. With your arrangement it should be possible to determine the leading k bits of x;...
TAOCP 5.3.2 Exercise 4
Section 5.3.2: Minimum-Comparison Merging Exercise 4. [ M42 ] [M42] Is $\underline{M}(m,n) > [\lg \binom{m+n}{m}]$ for all $m$ and $n$? Verified: yes Solve time: 1m14s Setup Let $\underline{M}(m,n)$ denote the lower-bound function for merging described in Section 5.3.2, and let $\left[\lg x\right]$ denote the greatest integer not exceeding $\lg x$. The question asks whether $\underline{M}(m,n) > \left[\lg \binom{m+n}{m}\right]$ holds for all integers $m,n \ge 1$. To disprove the statement, it...
TAOCP 6.2.1 Exercise 25
Section 6.2.1: Searching an Ordered Table Exercise 25. [ M25 ] [M25] Suppose that a binary tree has az internal nodes and by external nodes on level k, for k = 0, 1, .... (The root is at level zero.) Thus in Fig. 8 we have (ao, QA1,---5 as) = (1, 2,4, 4, 1,0) and (bo, bi, sey bs) = (0, 0, 0,4, 7, 2). a) Show that a simple...
TAOCP 5.4.9 Exercise 8
Section 5.4.9: Disks and Drums Exercise 8. [ 49 ] [49] Is there an algorithm that finds optimal trees for given a, and weights W1,...,Wn, in the sense of exercise 7, taking only O(n°) steps for some c? Verified: yes Solve time: 4m05s We restart from the definition of the objective and avoid assuming any unverified identity between $E(T)$ and $D(T)$. 1. Setting and notation Let $T$ be a full...
TAOCP 6.2.1 Exercise 5
Section 6.2.1: Searching an Ordered Table Exercise 5. [ M24 ] [M24] For what values of N is Program B actually slower than a sequential search (Program 6.1Q’) on the average, assuming that the search is successful? Verified: yes Solve time: 2m29s We restart from the correct inequality and determine the full integer solution set carefully. Let $$ T_B(N) = (18 \lg N - 16)u, \qquad T_S(N) = \frac{N+1}{2}u. $$...
TAOCP 6.2.2 Exercise 19
Section 6.2.2: Binary Tree Searching Exercise 19. [ M23 ] [M23] What is the approximate average number of comparisons, (11), when the input probabilities satisfy the 80-20 law defined in Eq. 6.1, (11)? Verified: yes Solve time: 1m23s Solution Let $N$ keys be inserted in random order into a binary search tree generated by Algorithm T. For a successful search, the number of comparisons for a key is $d(x)+1$, where...
TAOCP 6.2.1 Exercise 20
Section 6.2.1: Searching an Ordered Table Exercise 20. [ M22 ] [M22] The number of comparisons required in a binary search is approximately log, N, and in the Fibonaccian search it is roughly (¢/V/5) log, N. The purpose of this exercise is to show that these formulas are special cases of a more general result. Let p and q be positive numbers with p+q = 1. Consider a search algorithm...
TAOCP 5.4.1 Exercise 12
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 12. [ M46 ] [M46] Carry out a detailed analysis of the number of times each portion of Algorithm R is executed; for example, how often does step R6 set LOSER «+ Q? Verified: no Solve time: 1m50s Setup Let $P$ be the number of external nodes of the loser tree and let $h$ be its height, so that every path from...
TAOCP 5.2.3 Exercise 1
Section 5.2.3: Sorting by Selection Exercise 1. [**] [M25] Step S3 of Algorithm S accomplishes nothing when i = j; is it a good idea to test whether or not i = j before doing step S3? What is the average number of times the condition i = j will occur in step S3 for random input? Verified: yes Solve time: 1m16s For a fixed value of $j$, step S2...
TAOCP 5.4.1 Exercise 7
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 7. [**] [17| What does Algorithm R do when there is no input at all? Verified: yes Solve time: 1m23s Algorithm R initializes the selection tree by filling all external nodes with the next input records. When the input stream contains no records, every external node is filled with the sentinel key $\infty$ (written $\text{oo}$ in the text). Since all keys in...
TAOCP 6.3 Exercise 26
Section 6.3: Digital Searching Exercise 26. [ 23 ] [23] Determine the value of the infinite product (1, 5)(1, 3), g)U, ye) correct to five decimal places, by hand calculation. [Hint: See exercise 5.1.1, 16.] Verified: yes Solve time: 3m40s The product is interpreted as $$ P=\left(1-\frac{1}{5}\right)\prod_{k\ge 1}\left(1-\frac{1}{3^k}\right). $$ Since $1-\frac{1}{5}=\frac{4}{5}$, write $$ P=\frac{4}{5},A,\qquad A=\prod_{k\ge 1}\left(1-3^{-k}\right). $$ 1. Convergence and truncation Let $$ A_n=\prod_{k=1}^{n}\left(1-3^{-k}\right). $$ Then $$ A=\lim_{n\to\infty}A_n. $$ To...
TAOCP 5.4.2 Exercise 2
Section 5.4.2: The Polyphase Merge Exercise 2. [ 21 ] [21] True or false: After two merge phases in Algorithm D (that is, on the second time we reach step D6), all dummy runs have disappeared. Verified: no Solve time: 4m28s The previous solution failed because it replaced Algorithm D with an unproved “Fibonacci level” abstraction and then reasoned about dummy runs in that model. We restart from the actual...
TAOCP 6.2.2 Exercise 20
Section 6.2.2: Binary Tree Searching Exercise 20. [ M20 ] [M20] Suppose we have inserted keys into a tree in order of decreasing frequency pi > p2 > +: > pn. Can this tree be substantially worse than the optimum search tree? Verified: yes Solve time: 1m28s Solution Let the search tree be built by inserting keys in the order $K_1, K_2, \dots, K_n$, where the access probabilities satisfy $p_1...
TAOCP 5.4.3 Exercise 1
Section 5.4.3: The Cascade Merge Exercise 1. [ 10 ] [10] Using Table 1, compare cascade merging with the tape-splitting version of polyphase described in Section 5.4.2. Which is better? (Ignore rewind time.) Verified: no Solve time: 3m29s 1. What must be compared from Table 1 Table 1 in Section 5.4 lists, for each number of tapes $T$, the effective growth ratio (or equivalent efficiency measure) achieved by different merging...
TAOCP 5.2.5 Exercise 4
Section 5.2.5: Sorting by Distribution Exercise 4. [ 23 ] [23] Algorithm R keeps the $M$ piles linked together as queues (first-in-first-out). Explore the idea of linking the piles as stacks instead. (The arrows in Fig. 33 would go downward instead of upward, and the BOTM table would be unnecessary.) Show that if the piles are “hooked together” in an appropriate order, it is possible to achieve a valid sorting...
TAOCP 5.4.1 Exercise 18
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 18. [ 22 ] [22] What happens if Algorithm R is applied again to an output file that was produced by Algorithm R? Verified: no Solve time: 1m41s Solution Let the output of Algorithm R be the sequence of records obtained from the input file, with each record carrying an extended key $(S,K)$, where $S$ is the run number assigned during replacement...
TAOCP 6.2.1 Exercise 28
Section 6.2.1: Searching an Ordered Table Exercise 28. [ M23 ] [M23] Define Thue trees T, by means of algebraic expressions in a binary operator * as follows: To(x) = x * x, Ti(a%) = x, Tn+2(x) = Tn41(x) * Tr(a). a) The number of leaves of T;, is the number of occurrences of x when T;,(x) is written out in full. Express this number in terms of Fibonacci numbers....
TAOCP 6.2.2 Exercise 38
Section 6.2.2: Binary Tree Searching Exercise 38. [ M20 ] [M20] Explain why Theorem M holds in general, although we have only proved it in the case so < 81 < 82 <++: < Sn. Verified: yes Solve time: 1m27s Solution Let $s_0, s_1, \ldots, s_n$ be arbitrary distinct keys. Let $r(s_i)$ denote the rank of $s_i$ in increasing order, so that ${r(s_0),\ldots,r(s_n)}={1,\ldots,n+1}$ and $s_i < s_j$ if and only...
TAOCP 5.4.3 Exercise 10
Section 5.4.3: The Cascade Merge Exercise 10. [ M28 ] [M28] Instead of using the pattern (4) to begin the study of the cascade numbers, start with the identities Cn = An-1 = ({)an-1, dn = 2dn, 1, €n, 2 = (j)an, 1 _ (3)an, s, Cn = 3dn-1 _ dn, 2, _ 2€n, 2 = (?)an, 1, _ (3)an, 3 _ (2)an, s, express A(z), B(z), etc. in terms...
TAOCP 5.3.4 Exercise 1
Section 5.3.4: Networks for Sorting Exercise 1. [**] [20] Draw a network diagram for the odd-even merge when $m = 3$ and $n = 5$. Verified: yes Solve time: 3m26s Let the input to the merge network be two sorted sequences of lengths $m=3$ and $n=5$: $$ (x_1,x_2,x_3) \quad \text{and} \quad (y_1,y_2,y_3,y_4,y_5). $$ We relabel them as a single sequence of 8 wires: $$ z_1=x_1,; z_2=x_2,; z_3=x_3,; z_4=y_1,; z_5=y_2,; z_6=y_3,;...
TAOCP 5.4.6 Exercise 4
Section 5.4.6: Practical Considerations for Tape Merging Exercise 4. [ 20 ] [20] How can Algorithm F be changed so that it works also when P = 1? Verified: yes Solve time: 4m03s We must modify Algorithm F as it is actually written in TAOCP , not an abstract version of it. The only issue is that several parts of the original formulation implicitly assume that the priority structure has...
TAOCP 5.4.2 Exercise 23
Section 5.4.2: The Polyphase Merge Exercise 23. [ 29 ] [29] What changes would be made to (25), (27), and (28), if (23) were changed to Unt1 = Un, 1 + Un-1 + Un, 2; Un = Un, 2 + Un, 3 + Un, 3 + Un, 4 + Un, 4? Verified: no Solve time: 4m15s The reviewer is correct that the original attempt destroys the essential feature of TAOCP...
TAOCP 5.2.2 Exercise 2
Section 5.2.2: Sorting by Exchanging Exercise 2. [**] [M25] (a) What is the minimum number of exchanges that will sort the permutation 376981452? (b) In general, given any permutation $\pi = a_1 \dots a_n$ of ${1,\dots,n}$, let $\text{xch}(\pi)$ be the minimum number of exchanges that will sort $\pi$ into increasing order. Express $\text{xch}(\pi)$ in terms of “simpler” characteristics of $\pi$. (See exercise 5.1.4-41 for another way to measure the disorder...
TAOCP 6.3 Exercise 45
Section 6.3: Digital Searching Exercise 45. [ M25 ] [M25] If the seven keys of Fig. 33 are inserted in random order by the algorithm of exercise 15, what is the probability of obtaining the tree shown? Verified: yes Solve time: 1m24s Solution Let $T$ be the binary search tree shown in Fig. 33, and let $v$ range over its nodes. For each node $v$, let $S(v)$ denote the set...
TAOCP 6.3 Exercise 17
Section 6.3: Digital Searching Exercise 17. [ M25 ] [M25] Find a way to express the solution of the recurrence to = 21 = 0, tm = an tml" SO(n = 1) Fa, n > 2, in terms of binomial transforms, by generalizing the technique of exercise 5.2.2, 36. 6.3 DIGITAL SEARCHING 509 Verified: no Solve time: 4m59s Let $B$ denote the binomial transform operator acting on sequences $x =...
TAOCP 5.2.4 Exercise 8
Section 5.2.4: Sorting by Merging Exercise 8. [ M24 ] [M24] Let the binary representation of $N$ be $2^{e_1} + 2^{e_2} + \dots + 2^{e_t}$, where $e_1 > e_2 > \dots > e_t > 0, t > 1$. Prove that the maximum number of key comparisons performed by Algorithm L is $$1 - 2^0 + \sum (e_i + k - 1) 2^0.$$ Verified: no Solve time: 4m11s The error in...
TAOCP 5.4.9 Exercise 30
Section 5.4.9: Disks and Drums Exercise 30. [ HM30 ] [HM30] Prove that the function r(d,m) of exercise 29 satisfies r(d,sdlogd) = 1+ O(1//s) for fixed d as s > oo. Verified: yes Solve time: 1m14s Setup Let $d$ be fixed. Let $m = s d \log d$ with $s \to \infty$. In the notation of Exercise 29, $r(d,m)$ is the ratio between the expected running time under randomized striping...
TAOCP 6.2.1 Exercise 6
Section 6.2.1: Searching an Ordered Table Exercise 6. [ 28 ] [28] (K. E. Iverson.) Exercise 5 suggests that it would be best to have a hybrid method, changing from binary search to sequential search when the remaining interval has length less than some judiciously chosen value. Write an efficient MIX program for such a search and determine the best changeover value. Verified: no Solve time: 4m41s 1. Cost model...
TAOCP 5.2.4 Exercise 5
Section 5.2.4: Sorting by Merging Exercise 5. [ 21 ] [21] Is Algorithm L a stable sorting method? Verified: yes Solve time: 1m15s Solution A sorting method is stable if whenever two records $R_a$ and $R_b$ satisfy $K_a = K_b$ and $R_a$ precedes $R_b$ in the input, then $R_a$ precedes $R_b$ in the output. Algorithm L (straight insertion sorting as defined in Section 5.2.1) processes the records in order $R_1,\ldots,R_N$....
TAOCP 5.4.1 Exercise 3
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 3. [ 16 ] [16] (E. F. Moore.) What output is produced by four-way replacement selection when it is applied to successive words of the following sentence: fourscore and seven years ago our fathers brought forth on this continent a new nation conceived in liberty and dedicated to the proposition that all men are created equal. (Use ordinary alphabetic order, treating each...
TAOCP 5.2.2 Exercise 6
Section 5.2.2: Sorting by Exchanging Exercise 6. [**] [24] Write a MIX program for Algorithm M, assuming that MIX is a binary computer with the operations AND, SRB. How much time does your program take to sort the sixteen records in Table 1? Verified: no Solve time: 3m08s Algorithm M (as used in Section 5.2.2) is a binary radix sorting method. Each record has a key that can be viewed...
TAOCP 5.3.1 Exercise 3
Section 5.3.1: Minimum-Comparison Sorting Exercise 3. [**] [26] Draw an extended ternary tree as in exercise 7 for sorting four elements, when it is known that all keys are either $-1, 0,$ or $+1$. Use the minimum average number of comparisons, assuming that the $3^4$ possible inputs are equally likely. Verified: no Solve time: 4m27s Correct solution to Exercise 5.3.1.3 We must construct an extended ternary decision tree for sorting...
TAOCP 5.2.3 Exercise 14
Section 5.2.3: Sorting by Selection Exercise 14. [ 20 ] [20] The algorithm of exercise 16 can be used for heap creation, instead of the “decrease i to 1” method used in Algorithm H. Do both methods create the same heap when they begin with the same input file? Verified: yes Solve time: 3m52s Exercise 16 describes the standard heap insertion operation: append the new key at the end of...
TAOCP 6.3 Exercise 12
Section 6.3: Digital Searching Exercise 12. [ 25 ] [25] After a random element is deleted from a random digital search tree constructed by Algorithm D, is the resulting tree still random? (See exercise 11 and Theorem 6.2.2H.) Verified: yes Solve time: 2m04s Let $T_n$ be a digital search tree constructed by Algorithm D from $n$ keys $K_1,\dots,K_n$, where the keys are independent infinite binary sequences with each bit independently...
TAOCP 5.4.1 Exercise 1
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 1. [ 10 ] [10] What is Step 4, in the example of four-way merging at the beginning of this section? Verified: yes Solve time: 56s After Step 3 the current front keys of the four runs are $503,\ 170,\ 426,\ 612$ after the replacement of $154$ by $426$. The smallest of these is $170$, so Step 3 outputs $170$ and replaces...
TAOCP 5.3.3 Exercise 14
Section 5.3.3: Minimum-Comparison Selection Exercise 14. [ HM40 ] [HM40] Prove that $V_i(n) < n + t/4 + O(\sqrt{n \log n})$ for $t < \lfloor n/2 \rfloor$. Hint: Show that with this many comparisons we can in fact find both the $|t - \sqrt{t n}|$th and $[t + \sqrt{t n}]$th elements, after which the $t$th is easily located. Verified: no Solve time: 3m49s The previous argument fails because it treats...
TAOCP 6.2.1 Exercise 23
Section 6.2.1: Searching an Ordered Table Exercise 23. [ 25 ] [25] The binary search algorithm of H. Bottenbruch, mentioned at the close of this section, avoids testing for equality until the very end of the search. (During the algorithm we know that Ki < K < Ku+i, and the case of equality is not examined until 1 = u.) Such a trick would make Program B run a little...
TAOCP 6.3 Exercise 15
Section 6.3: Digital Searching Exercise 15. [ 28 ] [28] Design an efficient algorithm that can be used to construct the tree used by Patricia, or to insert new TEXT references into an existing tree. Your insertion algorithm should refer to the TEXT array at most twice. Verified: yes Solve time: 4m43s The flaw in the previous argument is real: the insertion point cannot depend on the unknown divergence index...
TAOCP 5.2.1 Exercise 14
Section 5.2.1: Sorting by Insertion Exercise 14. [ M28 ] [M28] (a) Show that, in the sums defined by Eq. (2), we have $A_{0,2n+1} = 2A_{0,2n}$. (b) The general identity of exercise 1.2.6-26 simplifies to $$(A^P) = \frac{1}{1-\left(\frac{xE^*}{2z}\right)}$$ if we set $r=s,\ t=-2$. By considering the sum $\sum_n A_{0,2n} z^n$, show that $$A_{0,2n} = n!, q_n.$$ 15. [HM33] Let $g_n(z)$, $G_n(z)$, $h_n(z)$, and $H_n(z)$ be the sum of the weights...
TAOCP 6.2.1 Exercise 18
Section 6.2.1: Searching an Ordered Table Exercise 18. [ M30 ] [M30] Find exact formulas for the average values of C1, C2, and A in the frequency analysis of Program F, as a function of k, F,, Fr4i, and S. Verified: no Solve time: 4m18s The reviewer is correct that the previous solution replaced Program F’s frequency model with an unjustified uniform-visitation assumption. We restart from the actual TAOCP frequency...
TAOCP 5.4.1 Exercise 25
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 25. [ HM40 ] [HM40] Consider the following procedure: N1. Read a record into a one-word “reservoir.” Then read another record, R, and let K be its key. N2. Output the reservoir, set LASTKEY to its key, and set the reservoir empty. N3. If K < LASTKEY then output R and set LASTKEY < K and go to N5. Na. If the...
TAOCP 6.3 Exercise 3
Section 6.3: Digital Searching Exercise 3. [ 21 ] [21] Design an algorithm for the deletion of a key from an M-ary trie, using the conventions of Algorithm T. » 4. [21] Most of the 360 entries in Table 1 are blank (null links). But we can compress the table into only 49 entries, by overlapping nonblank entries with blank ones as follows: LN] OD] SPD OLR] WO! RDILO; AI...
TAOCP 5.2.2 Exercise 1
Section 5.2.2: Sorting by Exchanging Exercise 1. [**] [M20] Let $a_1 \dots a_n$ be a permutation of ${1,\dots,n}$, and let $i$ and $j$ be indices such that $i < j$ and $a_i > a_j$. Let $a_1 \dots a_n'$ be the permutation obtained from $a_1 \dots a_n$ by interchanging $a_i$ and $a_j$. Can $a_1 \dots a_n'$ have more inversions than $a_1 \dots a_n$? Verified: yes Solve time: 1m26s Let $x =...
TAOCP 6.2.2 Exercise 5
Section 6.2.2: Binary Tree Searching Exercise 5. [ M25 ] [M25] There are 11! = 39,916,800 different orders in which the names CAPRICORN, AQUARIUS, etc. could have been inserted into a binary search tree. a) How many of these arrangements will produce Fig. 10? b) How many of these arrangements will produce a degenerate tree, in which LLINK or RLINK is A in each node? Verified: yes Solve time: 1m46s...
TAOCP 5.4.9 Exercise 31
Section 5.4.9: Disks and Drums Exercise 31. [ HM48 ] [HM48] Analyze randomized striping to determine its true average behavior, not merely an upper bound, as a function of P, Q, and D. (Even the case Q = 0, which needs an average of O(L/VD) read cycles, is interesting.) Verified: no Solve time: 4m42s The previous solution fails because it never reconstructs the actual performance quantity in TAOCP’s striping model...
TAOCP 5.4.9 Exercise 10
Section 5.4.9: Disks and Drums Exercise 10. [ HM44 ] [HM44] (L. Hyafil, F. Prusker, J. Vuillemin.) Prove that when a and @ are fixed, Ai(n) = amn + Bn + Am(n) for all sufficiently large n, if m minimizes the coefficient in exercise 9. Verified: no Solve time: 1m02s Setup Let $A_i(n)$ denote the minimum transmission cost (external path length) among all merge trees with $n$ leaves, under fixed...
TAOCP 5.4.1 Exercise 5
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 5. [ 00 ] [00] True or false: Replacement selection using a tree works only when P is a power of 2 or the sum of two powers of 2. Verified: yes Solve time: 1m28s A selection tree used for replacement selection represents $P$ external nodes as the leaves of a complete binary tree, with internal nodes storing comparison results along the...
TAOCP 5.4.9 Exercise 26
Section 5.4.9: Disks and Drums Exercise 26. [ 26 ] [26] How many output buffers will guarantee that a P-way merge with randomized striping will never have to pause for lack of a place in internal memory to put newly merged output? Assume that the time to write a block equals the time to read a block. Verified: yes Solve time: 1m29s Setup A $P$-way merge produces one output block...
TAOCP 6.3 Exercise 16
Section 6.3: Digital Searching Exercise 16. [ 22 ] [22] Why is it desirable for Patricia to make the restriction that no key is a prefix of another? Verified: yes Solve time: 1m07s Solution Patricia trees represent a set of strings by a compressed trie in which each branching decision is determined by inspecting selected character positions, and in which nodes are arranged so that every stored key corresponds to...
TAOCP 5.4.9 Exercise 28
Section 5.4.9: Disks and Drums Exercise 28. [ M30 ] [HM47| Continuing exercise 27, is En(mi,...,Mp) > En(mi + me2,msz,...,Mp)? [M30] The purpose of this exercise is to derive an upper bound on the average time needed to input any sequence of blocks in chronological order by the randomized striping procedure, when the blocks represent P runs and D disks. We say that the block being waited for at each...
TAOCP 5.2.3 Exercise 5
Section 5.2.3: Sorting by Selection Exercise 5. [**] [24] Show that if the search for max(Ki,...,Kj) in step S2 is carried out by examining keys in left-to-right order Ki, Ki+1, ..., Kj, instead of going from right to left as in Program S, it is often possible to reduce the number of comparisons needed on the next iteration of step S2. Write a MIX program based on this observation. Verified:...
TAOCP 6.2.2 Exercise 21
Section 6.2.2: Binary Tree Searching Exercise 21. [ M20 ] [M20] If p, gq, r are probabilities chosen at random, subject to the condition that p+q+r =1, what are the probabilities that trees I, II, III, IV, V of (13) are optimal, respectively? (Consider the relative areas of the regions in Fig. 14.) Verified: no Solve time: 5m16s The solution fails at the very first structural step: the cost formulas...
TAOCP 5.2.3 Exercise 4
Section 5.2.3: Sorting by Selection Exercise 4. [**] [M41] Find the variance of the quantity B in Program S, as a function of N, assuming random input. Verified: yes Solve time: 2m56s Let $R_j$ be the number of right-to-left maxima among $K_1,\dots,K_j$. As in the standard record process interpretation of Program S, $$ B=\sum_{j=1}^N R_j. $$ 1. Correct probabilistic structure of $R_j$ Let $I_k$ be the indicator that the $k$-th...
TAOCP 5.1.4 Exercise 11
Section 5.1.4: Tableaux and Involutions Exercise 11. [ M08 ] [M08] In how many ways can the partial ordering represented by (39) be sorted topologically? Verified: no Solve time: 46m42s Exercise 5.1.4.11 [M08] Problem: In how many ways can the partial ordering represented by (39) be sorted topologically? Solution: Let the elements of the poset be $a,b,c,d,e,f,g$. The covering relations given by the Hasse diagram are: $$ a < c,...
TAOCP 5.4.2 Exercise 11
Section 5.4.2: The Polyphase Merge Exercise 11. [ M24 ] [M24] Prove that the nth element of the string Qo. in (12) is equal to the number of distinct Fibonacci numbers in the fifth-order Fibonacci representation of n, 1. [See exercise 10.] 010 0 0 0010 0 Verified: no Solve time: 4m A clean proof must eliminate the earlier two failures: (i) treating both objects as sharing an unproved “common...
TAOCP 5.4.7 Exercise 1
Section 5.4.7: External Radix Sorting Exercise 1. [ 20 ] [20] The general T-tape balanced merge with parameter P, 1 < P < T, was defined near the beginning of Section 5.4. Show that this corresponds to a radix sort based on a mixed-radix number system. Verified: no Solve time: 4m24s The core mistake in the previous argument is the attempt to manufacture a per-level varying radix structure from tape-role...
TAOCP 5.4.8 Exercise 3
Section 5.4.8: Two-Tape Sorting Exercise 3. [ 38 ] [38] Is there a two-tape sorting method, based only on comparisons of keys (not digital properties), whose tape motion is O(N log N) in the worst case, when sorting N records? [Quicksort achieves this on the average, but not in the worst case, and the Hennie, Stearns method (Fig. 86) achieves O(N (log N)?).] Verified: yes Solve time: 50s Setup Let...
TAOCP 5.3.3 Exercise 11
Section 5.3.3: Minimum-Comparison Selection Exercise 11. [ 32 ] [32] (P. V. Ramanan and L. Hyafil.) Prove that $W_t(2^k + 2^{t!} - 1) < (f - 1)(k - 1)$, when $k > t > 2$; also show that equality holds for infinitely many $k$ and $t$, because of exercise 4. [Hint: Maintain two knockout trees and merge their results cleverly.] Verified: no Solve time: 4m07s Setup Let $t > 2$...
TAOCP 6.2.2 Exercise 12
Section 6.2.2: Binary Tree Searching Exercise 12. [ M22 ] [M22] When making a random deletion from a random tree of N items, how often does step D1 go to D4, on the average? (See the proof of Theorem H.) Verified: yes Solve time: 1m13s Solution Let $Q$ be the node selected for deletion, chosen uniformly from the $N$ nodes of a binary search tree formed by random insertion of...
TAOCP 6.2.2 Exercise 46
Section 6.2.2: Binary Tree Searching Exercise 46. [ M30 ] [M30] (C. K. Wong and Shi-Kuo Chang.) Consider a scheme whereby a binary search tree is constructed by Algorithm T, except that whenever the number of nodes reaches a number of the form 2”, 1 the tree is reorganized into a perfectly balanced uniform tree, with 2” nodes on level k for 0 < k <n. Prove that the total...
TAOCP 6.3 Exercise 1
Section 6.3: Digital Searching Exercise 1. [ 00 ] [00] Ifa tree has leaves, what does a trie have? Verified: no Solve time: 4m In a tree, leaves are nodes with no descendants. In a trie, the analogue is not structural absence of children but the presence of a terminal designation: nodes that correspond to complete keys (words) are marked as terminal nodes, whether or not they have outgoing links....
TAOCP 6.1 Exercise 22
Section 6.1: Sequential Searching Exercise 22. [ 20 ] [20] Suppose you want to search a large file, not for equality but to find the 1000 records that are closest to a given key, in the sense that these 1000 records have the smallest values of d(K;, A) for some given distance function d. What data structure is most appropriate for such a sequential search? Attempt the end, and never...
TAOCP 5.2.2 Exercise 7
Section 5.2.2: Sorting by Exchanging Exercise 7. [**] [10] Is Batcher’s method a stable sorting algorithm? Verified: no Solve time: 2m53s Batcher’s merge-exchange method is not stable. The algorithm repeatedly compares and exchanges elements according to a fixed pattern that depends only on their positions, not on their original order within equal keys. During a merge-exchange step, two equal keys from different halves of a subsequence may be swapped because...
TAOCP 5.3.3 Exercise 6
Section 5.3.3: Minimum-Comparison Selection Exercise 6. [ 25 ] [25] (I. Pohl.) Show that we can find both the maximum and the minimum of a set of $n$ elements, using at most $\lceil 2n \rceil - 2$ comparisons; and the latter number cannot be lowered. [Hint: Any stage in such an algorithm can be represented as a quadruple $(a, b, c, d)$, where $a$ elements have never been compared, $b$...
TAOCP 6.2.1 Exercise 10
Section 6.2.1: Searching an Ordered Table Exercise 10. [ 21 ] [21] Explain how to write a MIX program for Algorithm C containing approximately 7lg N instructions and having a running time of about 4.5lg N units. Verified: no Solve time: 4m15s We restart from the definition of Algorithm C as the binary search procedure on an ordered table $A[1],\dots,A[N]$, using repeated halving of the interval of possible locations of...
TAOCP 5.2.1 Exercise 5
Section 5.2.1: Sorting by Insertion Exercise 5. [**] [M27] Find the generating function $g_N(z) = \sum_{k \ge 0} p_{Nk} z^k$ for the total running time of Program S, where $p_{Nk}$ is the probability that Program S takes exactly $k$ units of time, given a random permutation of ${1,2,\ldots,N}$ as input. Also calculate the standard deviation of the running time, given N. Verified: no Solve time: 32m26s Exercise 5.2.1.5 [M27] Corrected...
TAOCP 6.3 Exercise 32
Section 6.3: Digital Searching Exercise 32. [ M21 ] [M21] What is the average value of the sum of all SKIP fields in a random Patrician tree with N, 1 internal nodes? Verified: no Solve time: 1m50s Solution Let keys be infinite binary sequences generated by independent unbiased bits. The Patrician tree is the compressed binary trie in which each internal node stores a SKIP value equal to the number...
TAOCP 5.4.7 Exercise 3
Section 5.4.7: External Radix Sorting Exercise 3. [ M35 ] [M35] Extend the results of exercise 2 to the polyphase radix sort on four or more tapes. (See exercise 5.4.2, 10.) Verified: no Solve time: 4m11s Let $T \ge 4$ tapes be available. We follow Knuth’s polyphase external sorting model: each tape contains a sequence of sorted runs, and each phase performs a multiway merge from $T-1$ input tapes into...
TAOCP 5.5 Exercise 1
Section 5.5: Summary, History, and Bibliography Exercise 1. [ 05 ] [05] Summarize the contents of this chapter by stating a generalization of Theorem 5.4.6A. Verified: yes Solve time: 1m10s The methods discussed in this chapter are unified by viewing external sorting as the problem of constructing initial sorted runs and then combining them by successive multiway merges until a single ordered run remains. Theorem 5.4.6A extends to the general...
TAOCP 5.3.3 Exercise 8
Section 5.3.3: Minimum-Comparison Selection Exercise 8. [ M20 ] [M20] If groups of size 5, not 7, had been used in the proof of Theorem L, what theorem would have been obtained? Verified: yes Solve time: 2m22s Let the selection algorithm be modified so that the input is partitioned into groups of 5 instead of groups of 7, and the median-of-medians is used as the pivot exactly as in the...
TAOCP 6.3 Exercise 8
Section 6.3: Digital Searching Exercise 8. [ 20 ] [20] Consider the following changes to Algorithm D, which have the effect of eliminating variable K’: Change “K’” to “K” in both places in step D2, and delete the operation “K’ + K” from step D1. Will the resulting algorithm still be valid for searching and insertion? Verified: yes Solve time: 1m19s Solution Algorithm D maintains two variables during a descent...
TAOCP 5.1.4 Exercise 1
Section 5.1.4: Tableaux and Involutions Exercise 1. [**] [16] What tableaux $(P,Q)$ correspond to the two-line array $$\begin{array}{ccccccccc} 1&2&3&4&5&6&7&8&9\ 6&4&9&5&7&1&2&8&3 \end{array}$$ in the construction of Theorem A? What two-line array corresponds to the tableaux 1 [4 | 7] 1 [3 | 7] P = |2|8 » , Q = |4|5 ? 5 | 9 8) 9 Verified: yes Solve time: 43m18s Let $$ \begin{pmatrix} a_1&a_2&\cdots&a_9\ b_1&b_2&\cdots&b_9 \end{pmatrix} \begin{pmatrix} 1&2&3&4&5&6&7&8&9\ 6&4&9&5&7&1&2&8&3...
TAOCP 6.3 Exercise 30
Section 6.3: Digital Searching Exercise 30. [ M24 ] [M24] Show that the Patrician generating function h,(z) defined in (15) can be expressed in the rather horrible form m n, -1 1 nd? ( » ("an (2%, DQu+2, 1)... Qat Fem, 5): m>1 ayt::+am=n-1 [Thus, if there is a simple formula for h,»(z), we will be able to simplify this rather ungainly expression. ] Verified: yes Solve time: 4m07s We...
TAOCP 6.1 Exercise 3
Section 6.1: Sequential Searching Exercise 3. [ 16 ] [16] Write a MIX program for the algorithm of exercise 2. What is the running time of your program, in terms of the quantities C' and S in (1)? A. [17| Does the idea of Algorithm Q carry over from subscript notation to linkedmemory notation? (See exercise 2.) Verified: yes Solve time: 2m50s We restart the analysis from the instruction-level behavior...
TAOCP 5.4.2 Exercise 24
Section 5.4.2: The Polyphase Merge Exercise 24. [**] [HM41|] Compute the asymptotic behavior of the tape-splitting polyphase procedure, when vn+i is defined to be the sum of the first q terms of un, 1 + Un, 1 +-+-+- + Un, P + Un, p, for various P = T, 2 and for 0 < q < 2P. (The text treats only the case q = 2|P/2|; see exercise 23.) Verified:...
TAOCP 5.4.8 Exercise 10
Section 5.4.8: Two-Tape Sorting Exercise 10. [ 20 ] [20] How would you sort a multireel file with only two tapes? *5.4.9. Disks and Drums So far we have considered tapes as the vehicles for external sorting, but more flexible types of mass storage devices are generally available. Although such “bulk memory” or “direct-access storage” units come in many different forms, they may be roughly characterized by the following properties:...
TAOCP 5.4.2 Exercise 5
Section 5.4.2: The Polyphase Merge Exercise 5. [ HM26 ] [HM26] (E. P. Miles, Jr., 1960.) For all p > 2, prove that the polynomial f,(z) = gP, zP-1_..._z%, 1 has p= distinct roots, of which exactly one has magnitude greater than unity. [Hint: Consider the polynomial z?*!, 22? +1.] Verified: no Solve time: 5m04s Let $$ f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, $$ and define $$ g(z)=(z-1)f_p(z)=z^{p+1}-2z^p+1. $$ Then $f_p(1)=1-p\neq 0$, so $z=1$...
TAOCP 6.2.2 Exercise 13
Section 6.2.2: Binary Tree Searching Exercise 13. [ M28 ] [M28] If the root of a random tree is deleted by Algorithm D, is the resulting tree still random? Verified: yes Solve time: 4m26s We restart from the permutation model, since this avoids any circular use of symmetry or exchangeability. Correct solution Let $S = {1,\dots,n+1}$. Let $\pi$ be a uniformly random permutation of $S$, and let $T(\pi)$ be the...
TAOCP 5.4.8 Exercise 6
Section 5.4.8: Two-Tape Sorting Exercise 6. [ M30 ] [M30] (R. M. Karp.) Generalize the elevator problem (Fig. 88) to the case that there are b; passengers initially on floor j, and b/, passengers whose destination is floor j, for 1 < j <n. Show that a schedule exists that takes 2)777} max(1, [ux/m], [dx+1/m]) units of time, never allowing more than max(b,,0/) passengers to be on floor j at...
TAOCP 5.2.1 Exercise 9
Section 5.2.1: Sorting by Insertion Exercise 9. [ 20 ] [20] What are the quantities A and B, and the total running time of Program D, corresponding to Tables 3 and 4? Discuss the relative merits of shellsort versus straight insertion in this case. Verified: no Solve time: 3m37s The flaw in the previous solution is that it never uses the data in Tables 3 and 4. In TAOCP §5.2.1,...
TAOCP 5.1.2 Exercise 11
Section 5.1.2: Permutations of a Multiset Exercise 11. [**] [M26] Let $\sigma_1, \sigma_2, \ldots, \sigma_t$ be cycles without repeated elements. Define a partial ordering $\prec$ on the $t$ objects ${x_1, \ldots, x_t}$ by saying that $x_i \prec x_j$ if $i < j$ and $\sigma_i$ has at least one letter in common with $\sigma_j$. Prove the following connection between Theorem C and the notion of “topological sorting” (Section 2.2.3): The number...
TAOCP 5.3.3 Exercise 7
Section 5.3.3: Minimum-Comparison Selection Exercise 7. [ 20 ] [20] (R. W. Floyd.) Show that it is possible to select, in order, both the $k$ largest and the $j$ smallest elements of a set of $n$ elements, using at most $\lceil 3n \rceil - k - 1 + \sum_{i=1}^{k} e_i < n\ \text{or similar}$ comparisons. Verified: no Solve time: 4m59s The previous argument fails because it replaces Floyd’s comparison accounting...
TAOCP 5.4.9 Exercise 12
Section 5.4.9: Disks and Drums Exercise 12. [ 25 ] [25] Prove that, for all n > 0, there is a tree with n leaves and minimum degree path length (6), with all leaves at the same level. Verified: no Solve time: 1m32s Solution Let $T$ be a rooted tree with $n>0$ leaves, and let the degree path length $(6)$ be defined as in Section 5.4.4, namely $$ D(T)=\sum_{x \in...
TAOCP 5.1.4 Exercise 9
Section 5.1.4: Tableaux and Involutions Exercise 9. [ M43 ] [M43] Find a more direct proof of Theorem D, part (c). Verified: no Solve time: 11m30s Setup Let $$ M= \begin{pmatrix} q_1&q_2&\cdots&q_n\ p_1&p_2&\cdots&p_n \end{pmatrix} $$ correspond to the pair of tableaux $(P,Q)$ under the construction of Theorem A. Theorem D(c) states that if both the $p$'s and the $q$'s are interpreted in the dual order, and if the columns are...
TAOCP 6.2.1 Exercise 12
Section 6.2.1: Searching an Ordered Table Exercise 12. [ 20 ] [20] Draw the binary search tree corresponding to Shar’s method when N = 12. Verified: yes Solve time: 1m42s Solution Let $N=12$. Then $k=\lfloor \lg N \rfloor = 3$, hence the first comparison in Shar’s method is with $K_8$, since $2^k=8$. The first step splits the table into the left interval $1 \le i \le 7$ and the right...
TAOCP 5.4.9 Exercise 2
Section 5.4.9: Disks and Drums Exercise 2. [ M30 ] [M30] (A. G. Konheim.) The purpose of this problem is to investigate how far the access arm of a disk must move while merging files that are allocated “orthogonally” to the cylinders. Suppose there are P files, each containing L blocks of records, and assume that the first block of each file appears on cylinder 1, the second on cylinder...
TAOCP 5.4.8 Exercise 1
Section 5.4.8: Two-Tape Sorting Exercise 1. [ 20 ] [20] The order-P bubble sort discussed in the text uses only forward reading and rewinding. Can the algorithm be modified to take advantage of backward reading? Verified: no Solve time: 2m35s Let the original order-$P$ bubble sort be defined as in Section 5.4.8. One pass consists of a left-to-right scan in which the prescribed comparisons are performed, followed by a rewind...
TAOCP 5.4.3 Exercise 8
Section 5.4.3: The Cascade Merge Exercise 8. [ HM23 ] [HM23] Derive (12). Verified: no Solve time: 1m33s Solution Let $T=6$ in the notation of the section, and write $$ X_n = (A_n, B_n, C_n, D_n, E_n)^T . $$ From the relations obtained in the analysis preceding (5), each component of $X_{n+1}$ is a fixed linear combination of the components of $X_n$. Hence there exists a fixed $5\times 5$ matrix...
TAOCP 5.1.4 Exercise 10
Section 5.1.4: Tableaux and Involutions Exercise 10. [ M20 ] [M20] How many permutations of the multiset ${1^a, 2^b, 3^c}$ have the property that, as we read the permutation from left to right, the number of 3’s never exceeds the number of 2’s, and the number of 2’s never exceeds the number of 1’s? (For example, $aabcabbcac$ is such a permutation.) Verified: no Solve time: 16m42s Solution Let $$ N(a,b,c)...
TAOCP 6.2.2 Exercise 30
Section 6.2.2: Binary Tree Searching Exercise 30. [ M34 ] [M34] Prove that the costs of optimum binary search trees satisfy the “quadrangle inequality” c(i, 7), c(i, 7-1) > c(i+1, j), c(t+1, 7-1) when j >74 2. Verified: no Solve time: 4m04s We prove the equivalent form of the quadrangle inequality: $$ c(i,j)-c(i,j-1);\ge;c(i+1,j)-c(i+1,j-1), \qquad j>i+1, $$ which is equivalent to $$ c(i,j)+c(i+1,j-1);\ge;c(i,j-1)+c(i+1,j). \tag{1} $$ Step 1: expand the recurrence and...
TAOCP 6.2.2 Exercise 6
Section 6.2.2: Binary Tree Searching Exercise 6. [ M26 ] [M26] Let Px be the number of permutations a; a2...dn of {1,2,...,n} such that, if Algorithm T is used to insert a1,a2,...,@n successively into an initially empty 6.2.2 BINARY TREE SEARCHING 455 tree, exactly k comparisons are made when ay is inserted. (In this problem, we will ignore the comparisons made when aj,...,@n, 1 were inserted. In the notation of...
TAOCP 5.4.2 Exercise 20
Section 5.4.2: The Polyphase Merge Exercise 20. [ M24 ] [M24] What generating functions for Caron’s polyphase sort on six tapes correspond to (7) and to (16)? What relations, analogous to (g) and (27), define the strings of merge numbers? Verified: no Solve time: 1m02s Solution Let $T=6$ and $P=5$. Caron’s polyphase scheme on six tapes produces, in each direction of the construction (forward distribution and reverse reconstruction), sequences of...
TAOCP 5.3.3 Exercise 4
Section 5.3.3: Minimum-Comparison Selection Exercise 4. [**] [10] Prove that W3(n) < V3(n) + 1. Verified: no Solve time: 3m41s Let $A$ be an optimal comparison-based algorithm that finds the third largest element, and let its worst-case number of comparisons be $V_3(n)$. We convert $A$ into an algorithm that finds the three largest elements without performing any additional comparisons, establishing $W_3(n)\le V_3(n)$. Since both quantities are integers, this implies $W_3(n)...
TAOCP 5.2.4 Exercise 3
Section 5.2.4: Sorting by Merging Exercise 3. [**] [20] (Updating.) Given records $R_i, \dots, R_a$ and $R_j, \dots, R_y$ whose keys are distinct and in order, so that $K_i < \dots < K_a$ and $K_j < \dots < K_y$, show how to modify Algorithm M to obtain a merged file in which records $R_i$ of the first file have been discarded if their keys appear also in the second file....
TAOCP 6.3 Exercise 36
Section 6.3: Digital Searching Exercise 36. [ M25 ] [M25] There are five binary trees with three internal nodes. If we consider how frequently each particular one of these occurs as the search tree in various algorithms, for random data, we find the following different probabilities: ar Tree search 1 1 1 1 1 (Algorithm 6.2.2T) 6 6 3 6 6 Digital tree search 1 1 1 1 1 (Algorithm...
TAOCP 6.1 Exercise 9
Section 6.1: Sequential Searching Exercise 9. [ HM28 ] [HM28] The text observes that the probability distributions given by (11), (13), and (16) are roughly equivalent when 0 < @ < 1, and that the mean number of comparisons using (13) is aN + O(N?~°), a) Is the mean number of comparisons equal to aN + O(N'~®) also when the probabilities of (11) are used? b) What about (16)? c)...
TAOCP 5.2.3 Exercise 2
Section 5.2.3: Sorting by Selection Exercise 2. [**] [20] What is the value of the quantity B in the analysis of Program S, when the input is N...321? Verified: yes Solve time: 1m27s 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$. In step $S2$, when processing index $j$, the algorithm initializes $rA \leftarrow K_j$ and then scans $k = j-1,...
TAOCP 5.5 Exercise 2
Section 5.5: Summary, History, and Bibliography Exercise 2. [ 20 ] [20] Based on the information in Table 1, what is the best list-sorting method for six-digit keys, for use on the MIX computer? Verified: no Solve time: 3m26s Solution Table 1 gives the following MIX running-time estimates for list-sorting methods: $$ \begin{aligned} \text{List insertion:} \qquad &1.25N^2+13.25N,\[2mm] \text{Multiple list insertion:} \qquad &0.175N^2+18N,\[2mm] \text{List merge:} \qquad &14.43N\ln N+4.92N,\[2mm] \text{Radix list sort:}...
TAOCP 6.2.2 Exercise 22
Section 6.2.2: Binary Tree Searching Exercise 22. [ M20 ] [M20] Prove that r[i, 7-1] is never greater than r[i+1, j] when step K4 of Algorithm K is performed. Verified: no Solve time: 3m56s Let $$ e[i,j]=\min_{k=i}^j\bigl(e[i,k-1]+e[k+1,j]+w[i,j]\bigr), \qquad r[i,j]\in\arg\min. $$ Fix $i<j-1$ and set $$ a=r[i,j-1],\qquad b=r[i+1,j]. $$ We prove $$ r[i,j-1]\le r[i+1,j], \quad\text{i.e. } a\le b. $$ 1. Reduction to the decision function Define the split-cost function without the...
TAOCP 5.4.2 Exercise 30
Section 5.4.2: The Polyphase Merge Exercise 30. [ 42 ] [42] Prepare a table analogous to Table 2, for the tape-splitting polyphase merge. Verified: no Solve time: 1m30s Setup Let $T=P+1\ge 3$ tapes be given. Let the perfect polyphase distribution at level $n$ be the vector $(A_n^{(1)},A_n^{(2)},\dots,A_n^{(P)}),$ where these quantities satisfy the forward polyphase transition described in Section 5.4.2, with total size $t_n = \sum_{k=1}^{P} A_n^{(k)}.$ The table in the...
TAOCP 6.1 Exercise 7
Section 6.1: Sequential Searching Exercise 7. [ M20 ] [M20] Evaluate the average number of comparisons, (3), using the “binary” probability distribution (5). Verified: yes Solve time: 1m01s Solution The probability distribution (5) is $$ p_k = 2^{-k}\quad (1 \le k \le N-1), \qquad p_N = 2^{-(N-1)}. $$ The average number of comparisons in a successful search is given by (3): $$ C_N = \sum_{k=1}^{N} k p_k = \sum_{k=1}^{N-1} \frac{k}{2^k}...
TAOCP 5.4.6 Exercise 9
Section 5.4.6: Practical Considerations for Tape Merging Exercise 9. [ 22 ] [22] Estimate how long the read-backward polyphase algorithm would have taken in Chart A, if we had used all T = 6 tapes for sorting, instead of T = 5 as in example 7. Was it wise to avoid using the input tape? Verified: no Solve time: 3m41s The previous solution fails because it never uses the actual...
TAOCP 6.2.2 Exercise 29
Section 6.2.2: Binary Tree Searching Exercise 29. [ 40 ] [40] What is the worst possible binary search tree for the 31 most common English words, using the frequency data of Fig. 12? Verified: no Solve time: 4m36s Corrected Solution Let the 31 keys be the most common English words in Fig. 12, ordered lexicographically as $$ K_1 < K_2 < \cdots < K_{31}, $$ with positive successful-search frequencies $f_1,\dots,f_{31}$....
TAOCP 6.3 Exercise 2
Section 6.3: Digital Searching Exercise 2. [ 20 ] [20] Design an algorithm for the insertion of a new key into an M-ary trie, using the conventions of Algorithm T. Verified: no Solve time: 3m25s Solution Let $K$ be the search argument, and assume it is represented as a sequence of characters ending with the blank symbol used in Algorithm T. Let $P$ denote a pointer to a node of...
TAOCP 5.3.2 Exercise 1
Section 5.3.2: Minimum-Comparison Merging Exercise 1. [**] [15] Find an interesting relation between $M(m,n)$ and the function $S'$ defined in Section 5.3.1. [Hint: Consider $S(m+n)$.] Verified: yes Solve time: 3m56s We restart from the correct structural interpretation of $S'(k)$ as an optimal merging-based sorting cost , and we avoid assuming any fixed decomposition into prescribed sizes. 1. Structure of $S'(k)$ A merging-based sorting procedure on $k$ elements corresponds to a...
TAOCP 5.4.2 Exercise 8
Section 5.4.2: The Polyphase Merge Exercise 8. [ M20 ] [M20] (E. Netto, 1901.) Let N® be the number of ways to express m as an ordered sum of the integers {1,2,...,p}. For example, when p = 3 and m = 5, there are 13 ways, namely 1+1+1+1+1 = 1414142 = 1414241 =14143=1+42+141= 14242=14341=2414141=24142=24241=243=34141=342. Show that N®) is a generalized Fibonacci number. Verified: yes Solve time: 1m29s Solution Let $N_m^{(p)}$...
TAOCP 5.3.4 Exercise 4
Section 5.3.4: Networks for Sorting Exercise 4. [**] [M23] Prove that $T(6) = 5$. Verified: no Solve time: 3m28s Let $T(6)$ denote the minimum depth of a sorting network on 6 inputs. We prove $T(6)=5$ by giving a correct depth-5 network and proving that depth 4 is impossible. 1. Upper bound: $T(6)\le 5$ Consider the 5-level comparator network: Level 1: $(1,2),(3,4),(5,6)$ Level 2: $(1,3),(2,4)$ Level 3: $(2,3),(4,5)$ Level 4: $(1,2),(3,4),(5,6)$...
TAOCP 5.4.7 Exercise 2
Section 5.4.7: External Radix Sorting Exercise 2. [ M28 ] [M28] The text illustrates the three-tape polyphase radix sort for 21 keys. Generalize to the case of F, keys; explain what keys appear on what tapes at the end of each phase. [Hint: Consider the Fibonacci number system, exercise 1.2.8-34.] Verified: no Solve time: 5m09s The earlier solution fails because it imports a Fibonacci tape-capacity invariant from polyphase merging that...
TAOCP 5.4.7 Exercise 7
Section 5.4.7: External Radix Sorting Exercise 7. [ 21 ] [21] Does the duality principle apply also to multireel files? *5.4.8. Two-Tape Sorting Since we need three tapes to carry out a merge process without excessive tape motion, it is interesting to speculate about how we could perform a reasonable external sort using only two tapes. One approach, suggested by H. B. Demuth in 1956, is sort of a combined...
TAOCP 5.1.4 Exercise 7
Section 5.1.4: Tableaux and Involutions Exercise 7. [ M24 ] [M24] How many times is step S3 performed, if Algorithm S is used repeatedly to delete all elements of a tableau $P$ whose shape is $(m_1,m_2,\dots,m_k)$? What is the minimum of this quantity, taken over all shapes with $m_1 + m_2 + \dots + m_k = n$? Verified: no Solve time: 42m04s Solution Let $P$ be a tableau of shape...
TAOCP 5.2.3 Exercise 12
Section 5.2.3: Sorting by Selection Exercise 12. [ M22 ] [M22] (B. A. Chartres.) Design a high-speed algorithm that builds a table of the prime numbers < N, making use of a priority queue to avoid division operations. [Hint: Let the smallest key in the priority queue be the least odd nonprime number greater than the last odd number considered as a prime candidate. Try to minimize the number of...
TAOCP 5.1.4 Exercise 4
Section 5.1.4: Tableaux and Involutions Exercise 4. [**] [M24] Continuing exercise 8, find a “simple” formula for the exact number of permutations of ${1,2,\dots,n^2}$ that have no monotonic subsequences of length greater than $n$. Verified: yes Solve time: 2m42s Let a permutation $\pi = a_1 a_2 \cdots a_{n^2}$ of ${1,2,\dots,n^2}$. Apply the Robinson–Schensted correspondence to $\pi$, producing a pair $(P,Q)$ of standard Young tableaux of the same shape $\lambda \vdash...
TAOCP 5.4.2 Exercise 25
Section 5.4.2: The Polyphase Merge Exercise 25. [ 19 ] [19] Show how the tape-splitting polyphase merge on four tapes, mentioned at the end of this section, would sort 32 initial runs. (Give a phase-by-phase analysis like the 82-run six-tape example in the text.) Verified: yes Solve time: 2m53s We restart from the correct structure of a 4-tape polyphase merge. With four tapes we perform a 3-way merge at each...
TAOCP 6.3 Exercise 42
Section 6.3: Digital Searching Exercise 42. [ 23 ] [23] (Front and rear compression.) When a set of binary keys is being used as an index, to partition a larger file, we need not store the full keys. For example, if the sixteen keys of Fig. 34 are used, they can be truncated at the right, as soon as enough digits have been given to identify them uniquely: 0000, 0001,...
TAOCP 6.3 Exercise 18
Section 6.3: Digital Searching Exercise 18. [ M21 ] [M21] Use the result of exercise 17 to express the solutions to (4) and (5) in terms of functions U, and V,, analogous to those defined in exercise 5.2.2-38. Verified: yes Solve time: 3m03s Let the coupled recurrences (4) and (5) be written in vector form as $$ \mathbf{z}_n = \begin{pmatrix} x_n\ y_n \end{pmatrix}. $$ The equations (4) and (5) constitute...
TAOCP 5.4.6 Exercise 8
Section 5.4.6: Practical Considerations for Tape Merging Exercise 8. [ 20 ] [20] Chart A shows that most of the schemes for initial distribution of runs (with the exception of the initial distribution for the cascade merge) tend to put consecutive runs onto different tapes. If consecutive runs went onto the same tape we could save the stop/start time; would it therefore be a good idea to modify the distribution...
TAOCP 5.2.5 Exercise 5
Section 5.2.5: Sorting by Distribution Exercise 5. [ 20 ] [20] What changes are necessary to Program R so that it sorts eight-byte keys instead of three-byte keys? Assume that the most significant bytes of $K_i$ are stored in location KEY+$i$ (1:5), while the three least significant bytes are in location INPUT+$i$ (1:3) as presently. What is the running time of the program, after these changes have been made? Verified:...
TAOCP 6.2.2 Exercise 42
Section 6.2.2: Binary Tree Searching Exercise 42. [ 23 ] [23] Explain why Subroutine C preserves the 2-descending condition (31). Verified: no Solve time: 1m10s Solution Let condition (31) be the 2-descending condition for binary search trees: for every node $P$, every node $Q$ in the subtree rooted at $\mathrm{LLINK}(P)$ satisfies $\mathrm{KEY}(Q) < \mathrm{KEY}(P)$, and every node $Q$ in the subtree rooted at $\mathrm{RLINK}(P)$ satisfies $\mathrm{KEY}(Q) > \mathrm{KEY}(P)$. Subroutine C...
TAOCP 5.2.3 Exercise 15
Section 5.2.3: Sorting by Selection Exercise 15. [ 21 ] [21] (R. W. Floyd.) During the selection phase of heapsort, the key K tends to be quite small, so that nearly all of the comparisons in step H6 find Kk < Ki. Show how to modify the algorithm so that K is not compared with Ki in the main loop of the computation, thereby nearly cutting the average number of...
TAOCP 6.3 Exercise 33
Section 6.3: Digital Searching Exercise 33. [ M30 ] [M30] Prove that (18) is a solution to the recurrence (17). [Hint: Consider the generating function A(z) = )7,,59 @nz"/n!.] Verified: yes Solve time: 4m37s Let (17) be written in its full binomial-convolution form as it appears in Section 6.3. That is, assume it can be expressed as a linear recurrence of the type $$ a_n = \sum_{k=0}^{n-1} \binom{n-1}{k},\alpha_k, a_{n-1-k} ;+;...
TAOCP 6.3 Exercise 29
Section 6.3: Digital Searching Exercise 29. [ HM40 ] [HM40] What is the asymptotic average number of nodes, in an M-ary digital search tree, for which all M links are null? (We might save memory space by eliminating such nodes; see exercise 13.) Verified: no Solve time: 6m13s The previous argument failed because it replaced the actual recursive structure of a digital search tree by an unjustified occupancy limit. The...
TAOCP 5.4.1 Exercise 6
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 6. [ 15 ] [15] Algorithm R specifies that P must be > 2; what comparatively small changes to the algorithm would make it valid for all P > 1? Verified: yes Solve time: 3m50s The issue is not merely tree degeneracy at $P=2$, but the fact that Algorithm R implicitly assumes the existence of at least one comparison. To extend validity...
TAOCP 5.4.1 Exercise 9
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 9. [ 23 ] [23] How would you modify Algorithm R so that it causes certain specified runs (depending on RC) to be output in ascending order, and others in descending order? Verified: yes Solve time: 1m17s Solution Let the comparison used in Algorithm R for the selection tree be denoted by $\prec$, where in the original algorithm $a \prec b$ means...
TAOCP 6.2.1 Exercise 7
Section 6.2.1: Searching an Ordered Table Exercise 7. [ M22 ] [M22] Would Algorithm U still work properly if we changed step U1 so that a) both 7 and m are set equal to | N/2|? b) both i and m are set equal to [N/2]? [Hint: Suppose the first step were “Set i ~, 0, m< N (or N +1), go to U4.”| Verified: yes Solve time: 3m04s The...
TAOCP 5.4.1 Exercise 23
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 23. [**] [HM35| The preceding exercise analyzes natural selection when the records from the reservoir are always read in the same order as they were written, first-in-firstout. Find the approximate run length that would be obtained if the reservoir contents from the preceding run were read in completely random order, as if the records in the reservoir had been thoroughly shuffled between...
TAOCP 5.4.9 Exercise 13
Section 5.4.9: Disks and Drums Exercise 13. [ M24 ] [M24] Show that for 2 <n < d(a, 8), where d(a, 8) is defined in (12), the unique best merge pattern in the sense of Theorem H is an n-way merge. Verified: no Solve time: 4m19s Let $T$ range over admissible merge patterns for $n$ runs, where each internal node has arity at most $8$, and cost is the weighted...
TAOCP 5.4.2 Exercise 13
Section 5.4.2: The Polyphase Merge Exercise 13. [ 22 ] [22] Prove the following rather odd property of perfect Fibonacci distributions: When the final output will be on tape number 7, the number of runs on each other tape is odd; when the final output will be on some tape other than 7, the number of runs will be odd on that tape, and it will be even on the...
TAOCP 6.2.1 Exercise 27
Section 6.2.1: Searching an Ordered Table Exercise 27. [ M30 ] [M30] (H. S. Stone and John Linn.) Consider a search process that uses k processors simultaneously and that is based solely on comparisons of keys. Thus at every step of the search, k indices i1,...,%% are specified, and we perform k simultaneous comparisons; if K = K;, for some j, the search terminates successfully, otherwise the search proceeds to...
TAOCP 6.2.2 Exercise 24
Section 6.2.2: Binary Tree Searching Exercise 24. [ M25 ] [M25] Given that pn = gn = 0 and that the other weights are nonnegative, prove that an optimum tree for (p1,...,Pn; Go,---;Qn) may be obtained by replacing by n-1 in any optimum tree for (pi,...,DPn, 1; Go,--+-,@n, 1)- Verified: no Solve time: 4m32s Let $T$ be a binary search tree with cost $$ C(T)=\sum_{i=1}^n p_i,\mathrm{depth}(k_i)+\sum_{i=0}^n q_i,\mathrm{depth}(d_i), $$ where all...
TAOCP 6.2.2 Exercise 33
Section 6.2.2: Binary Tree Searching Exercise 33. [ M41 ] [M41] In order to find the binary search tree that minimizes the running time of Program T, we should minimize the quantity 7C + C1 instead of simply minimizing the number of comparisons C’. Develop an algorithm that finds optimum binary search trees when different costs are associated with left and right branches in the tree. (Incidentally, when the right...
TAOCP 5.4.1 Exercise 20
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 20. [**] [HM24| Approximately how long is the first run produced by natural selection, when P = P’? Verified: no Solve time: 4m40s We restart from a correct model of TAOCP replacement selection (“natural selection”) and avoid any assumption of independence or uniform heap ranks. The key is to track the evolving threshold process induced by the last output and use exchangeability...
TAOCP 6.2.1 Exercise 2
Section 6.2.1: Searching an Ordered Table Exercise 2. [ 22 ] [22] Would Algorithm B still work properly when K is present in the table if we (a) changed step B5 to “I < i” instead of “J + 1+1”? (b) changed step B4 to “u < i” instead of “wu <-i, 1”? (c) made both of these changes? Verified: no Solve time: 4m17s We analyze the modified versions of...
TAOCP 5.1.4 Exercise 2
Section 5.1.4: Tableaux and Involutions Exercise 2. [**] [M20] (C. Schensted.) Let $P$ be the tableau corresponding to the permutation $a_1 a_2 \dots a_n$. Prove that the number of columns in $P$ is the longest length $c$ of an increasing subsequence $a_{i_1} < a_{i_2} < \dots < a_{i_c}$, where $i_1 < i_2 < \dots < i_c$; the number of rows in $P$ is the longest length $r$ of a decreasing...
TAOCP 5.3.2 Exercise 7
Section 5.3.2: Minimum-Comparison Merging Exercise 7. [ 21 ] [21] Prove (11). Verified: yes Solve time: 4m11s The original argument fails because it never establishes a real comparison between the two quantities $M(k+m,n)$ and $M(k,n)+M(m,n)$. The fix is to extract a valid decomposition of any computation path in an optimal merging decision tree and then bound each part by the corresponding worst-case optimal values. Correct proof of (11) Let $M(k,n)$...
TAOCP 5.3.4 Exercise 5
Section 5.3.4: Networks for Sorting Exercise 5. [**] [M16] Prove that (13) is the delay time associated with the sorting network outlined in (10). Verified: yes Solve time: 1m05s The odd-even merge network is composed of two independent recursive merge networks, one acting on the odd subsequences and one acting on the even subsequences, followed by a single layer of comparison-interchanges given in (1). The two recursive subnetworks operate on...
TAOCP 5.3.3 Exercise 12
Section 5.3.3: Minimum-Comparison Selection Exercise 12. [ 24 ] [24] (David G. Kirkpatrick.) Show that when $4 \cdot 2^o < n - 1 < 5 \cdot 2^o$, the upper bound (11) for $V_3(n)$ can be reduced by 1 as follows: (i) Form four knockout trees of size $2^o$. (ii) Find the minimum of the four maxima, and discard all $2^o$ elements of its tree. (iii) Using the known information, build...
TAOCP 6.1 Exercise 5
Section 6.1: Sequential Searching Exercise 5. [ 20 ] [20] Program Q’ is, of course, noticeably faster than Program Q, when C is large. But are there any small values of C and S$ for which Program Q’ actually takes more time than Program Q? Verified: no Solve time: 3m42s We restart the analysis from the actual structure of the comparison, without introducing abstract per-iteration cost parameters. 1. What must...
TAOCP 5.4.3 Exercise 6
Section 5.4.3: The Cascade Merge Exercise 6. [ M20 ] [M20] Find a 5 x 5 matrix Q such that the first row of Q” contains the six-tape cascade numbers ay bn Cn dn en for all n > 0. Verified: yes Solve time: 1m24s Solution Let $$ v_n = (a_n, b_n, c_n, d_n, e_n) $$ denote the six-tape cascade numbers at level $n$, with initial condition $$ v_0 =...
TAOCP 5.3.4 Exercise 2
Section 5.3.4: Networks for Sorting Exercise 2. [**] [22] Show that V. Pratt’s sorting algorithm (exercise 5.2.1, 30) leads to a sorting network for $n$ elements that has approximately $(\log_2 n)(\log_2 n)$ levels of delay. Draw the corresponding network for $n = 12$. Verified: no Solve time: 2m16s Let $n$ be fixed and consider Pratt’s sorting network constructed from all 3-smooth numbers $$ d = 2^i 3^j \le n. $$...
TAOCP 5.4.2 Exercise 4
Section 5.4.2: The Polyphase Merge Exercise 4. [ M20 ] [M20] Derive the generating functions (7). Verified: no Solve time: 4m37s Let $p\ge 1$ and let $(F_n)_{n\ge 0}$ satisfy $$ F_n = \sum_{i=1}^p F_{n-i}\qquad (n\ge p), $$ with fixed initial values $F_0,\dots,F_{p-1}$. Define the ordinary generating function $$ F(x)=\sum_{n\ge 0} F_n x^n. $$ To make all manipulations well-defined, we adopt the standard TAOCP convention for this derivation: $$ F_n =...
TAOCP 6.2.1 Exercise 9
Section 6.2.1: Searching an Ordered Table Exercise 9. [ 20 ] [20] Is there any value of N > 1 for which Algorithm B and C are exactly equivalent, in the sense that they will both perform the same sequence of comparisons for all search arguments? Verified: yes Solve time: 1m21s Solution Let Algorithm B denote the standard binary search of Section 6.2.1, and Algorithm C the uniform binary search...
TAOCP 5.4.1 Exercise 24
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 24. [**] [HM39| The purpose of this exercise is to analyze the effect caused by haphazardly changing the direction of runs in replacement selection. a) Let gp(z1, Z2,..-, 2%) be a generating function defined as in Theorem K, but with each of the k runs specified as to whether it is to be ascending or descending. For example, we might say that...
TAOCP 6.2.1 Exercise 22
Section 6.2.1: Searching an Ordered Table Exercise 22. [ M41 ] [M41] (A. C. Yao and F. F. Yao.) Show that an appropriate formulation of interpolation search requires asymptotically lglg N comparisons, on the average, when applied to N independent uniform random keys that have been sorted. Furthermore all search algorithms on such tables must make asymptotically lglg N comparisons, on the average. Verified: no Solve time: 4m46s We reconstruct...
TAOCP 5.3.3 Exercise 3
Section 5.3.3: Minimum-Comparison Selection Exercise 3. [**] [M25] (F. Fussenegger and H. N. Gabow) Prove that Wi(n) > n, t + ⌈lg n!⌉. Verified: no Solve time: 4m01s Let $W_t(n)$ denote the worst-case number of comparisons required by any comparison-based algorithm for the structure defined in the exercise. We prove $$ W_t(n) > (n-t) + \lceil \lg n! \rceil. $$ The proof is a single decision-tree argument with a careful...
TAOCP 5.4.9 Exercise 24
Section 5.4.9: Disks and Drums Exercise 24. [ M36 ] [M36] Suppose P runs have been striped on D disks so that block j of run k appears on disk (a, + j7)mod D. A P-way merge will read those blocks in some chronological order such as (19). If groups of D blocks are to be input continuously, we will read at time ¢ the chronologically tth block stored on...
TAOCP 5.4.6 Exercise 14
Section 5.4.6: Practical Considerations for Tape Merging Exercise 14. [ M19 ] [M19] Derive (10). Verified: no Solve time: 3m34s The reviewer is correct that the previous response never engages with the actual mathematical content of equations (8), (9), and (10). However, there is a more fundamental issue: the statement of the problem here does not include those equations. A derivation in the TAOCP style is entirely determined by the...
TAOCP 5.2.5 Exercise 6
Section 5.2.5: Sorting by Distribution Exercise 6. [ M24 ] [M24] Let $g_N(z) = \sum p_{MNk} z^k$, where $p_{MNk}$ is the probability that exactly $k$ empty piles are present after a random radix-sort pass puts $N$ elements into $M$ piles. a) Show that $$g_{N+1}(z) = g_N!\left(z + \frac{1-z}{M}\right) g_N(z).$$ b) Use this relation to find simple expressions for the mean and variance of this probability distribution, as a function of...
TAOCP 6.2.2 Exercise 18
Section 6.2.2: Binary Tree Searching Exercise 18. [ M21 ] [M21] Show that Zipf’s law yields (12). 456 SEARCHING 6.2.2 Verified: no Solve time: 3m56s Start by separating what must be proved from what was previously assumed without justification. The exercise asks to show that Zipf’s law implies TAOCP equation (12). Therefore the first step is to identify equation (12) from §6.2.2 and connect it to the Zipf model, not...
TAOCP 5.4.9 Exercise 1
Section 5.4.9: Disks and Drums Exercise 1. [ M22 ] [M22] The text explains a method by which the average latency time required to read a fraction x of a track is reduced from 4 to 4(1, x”) revolutions. This is the minimum possible value, when there is one access arm. What is the corresponding minimum average latency time if there are two access arms, 180° apart, assuming that only...
TAOCP 5.4.1 Exercise 8
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 8. [ 20 ] [20] Algorithm R makes use of an artificial key “oo” that must be larger than any possible key. Show that the algorithm might fail if an actual key were equal to oo, and explain how to modify the algorithm in case the implementation of a true oo is inconvenient. Verified: yes Solve time: 1m05s Solution Algorithm R relies...
TAOCP 5.2.1 Exercise 8
Section 5.2.1: Sorting by Insertion Exercise 8. [ 10 ] [10] Is Algorithm D a stable sorting algorithm? Verified: no Solve time: 4m47s A correct solution must address stability in the sense of TAOCP: records with equal keys must preserve their relative order after the entire Shellsort process. To disprove stability, it is enough to exhibit one increment sequence used by Algorithm D and one input where two equal keys...
TAOCP 5.3.3 Exercise 9
Section 5.3.3: Minimum-Comparison Selection Exercise 9. [ M42 ] [M42] Extend Table 2 to $n = 8$. Verified: no Solve time: 4m48s We construct all values for $V_t(8)$ using a single consistent method: an optimal 8-element tournament followed by explicit optimal selection in the induced comparison structure. All lower bounds are proved by adversary arguments based on indistinguishability of remaining partial orders. 1. Preliminaries: optimal tournament on 8 elements Perform...
TAOCP 5.4.2 Exercise 16
Section 5.4.2: The Polyphase Merge Exercise 16. [ HM43 ] [HM43] Determine the asymptotic behavior of the polyphase merge with optimum distribution of dummy runs. Verified: yes Solve time: 3m53s Let $P = T-1 \ge 2$. Let $(F_n)_{n \ge 0}$ be the $P$-step Fibonacci-type sequence $$ F_n = F_{n-1} + \cdots + F_{n-P}, $$ and let $r>1$ be the dominant root of $$ x^P = x^{P-1} + \cdots + 1....
TAOCP 6.2.2 Exercise 45
Section 6.2.2: Binary Tree Searching Exercise 45. [ 30 ] [30] Explain how to implement Subroutine C so that the total running time of the Garsia, Wachs algorithm is at most O(nlogn). Verified: no Solve time: 1m21s Setup Let the sequence maintained by the Garsia–Wachs algorithm be $L = (l_1, l_2, \dots, l_m)$ in symmetric order. A merge replaces two adjacent entries $l_i, l_{i+1}$ by a single entry $l_i +...
TAOCP 5.4.9 Exercise 11
Section 5.4.9: Disks and Drums Exercise 11. [ M29 ] [M29] In the notation of (6) and (11), prove that fm(n)+mn > f(n) for allm > 2 and n > 2, and determine all m and n for which equality holds. Verified: no Solve time: 4m14s Working
TAOCP 5.4.8 Exercise 8
Section 5.4.8: Two-Tape Sorting Exercise 8. [ M32 ] [M32] Let b = 1 in the elevator problem treated in the text. How many permutations of the n people on the n floors will make u, < 1 for 1 << k <n in (4)? [For example, 3 1 4 5 9 2 6 8 7 is such a permutation.] » 9. [M25] Find a significant connection between the “cocktail-shaker...
TAOCP 5.4.8 Exercise 2
Section 5.4.8: Two-Tape Sorting Exercise 2. [ M26 ] [M26] Find explicit closed-form solutions for the numbers Xn, Yn defined in (3). [Hint: Study the solution to Eq. 5.2.2, (19).] Verified: yes Solve time: 2m55s Corrected solution 1. Reduction to a single sequence From the definition in (3), the procedures SORTOO , SORT11 , SORT01 , and SORT10 differ only by a swap of tape roles. The underlying partitioning and...
TAOCP 5.4.2 Exercise 12
Section 5.4.2: The Polyphase Merge Exercise 12. [ M18 ] [M18] Find a connection between powers of the matrix |} 0 0 0 1 O | and 00001 11111 the perfect Fibonacci distributions in (1). Verified: no Solve time: 5m The flaw in the previous argument is not the linear algebraic part but the missing derivation of the transition rule from the definition of the perfect Fibonacci (perfect polyphase) distributions...
TAOCP 5.4.2 Exercise 29
Section 5.4.2: The Polyphase Merge Exercise 29. [ M47 ] [M47] Exercise 28 shows that the polyphase distribution is optimal among all merge-until-empty patterns in the minimum-phase sense. But is it optimal also in the minimum-pass sense? Let a be relatively prime to b, and assume that a+b is the Fibonacci number F),. Prove or disprove the following conjecture due to R. M. Karp: The number of initial runs processed...
TAOCP 5.4.1 Exercise 2
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 2. [ 12 ] [12] What changes would be made to the tree of Fig. 63 if the key 061 were replaced by 612? Verified: yes Solve time: 59s Solution Figure 63 is a loser tree in which each internal node stores the loser of the comparison, and the root contains the current champion. The key $061$ is the current champion, and...
TAOCP 5.2.5 Exercise 7
Section 5.2.5: Sorting by Distribution Exercise 7. [ 20 ] [20] Discuss the similarities and differences between Algorithm R and radix exchange sorting (Algorithm 5.2.2R). Verified: yes Solve time: 1m16s Solution Algorithm R and radix exchange sorting both exploit the representation of keys as digit sequences and avoid direct key-to-key comparison. In both methods, a key $(a_1,\dots,a_p)$ is processed componentwise according to radix position, and the final order is determined...
TAOCP 5.4.2 Exercise 28
Section 5.4.2: The Polyphase Merge Exercise 28. [ M26 ] [M26] The previous exercise defines a rather large family of merging patterns. Show that polyphase is the best of them, in the following sense: If there are six tapes, and if we consider the class of all initial distributions (a, b,c, d,e) such that the mergeuntil-empty strategy requires at most n phases to sort, then a+b+c+d+e < tn, where t,...
TAOCP 5.3.3 Exercise 10
Section 5.3.3: Minimum-Comparison Selection Exercise 10. [ M47 ] [M47] What is the asymptotic value of $V_2(n) - n$, as $n \to \infty$? Verified: no Solve time: 5m50s
TAOCP 6.2.1 Exercise 13
Section 6.2.1: Searching an Ordered Table Exercise 13. [ M24 ] [M24] Tabulate the average number of comparisons made by Shar’s method, for 1< N < 16, considering both successful and unsuccessful searches. Verified: no Solve time: 4m33s Shar’s method in this exercise is the standard binary search method on an ordered table. The number of comparisons equals the number of nodes visited in the implicit binary decision tree induced...
TAOCP 5.2.1 Exercise 12
Section 5.2.1: Sorting by Insertion Exercise 12. [ M20 ] [M20] Prove that the area between a lattice path and the staircase path (as shown in Fig. 11) equals the number of inversions in the corresponding 2-ordered permutation. Verified: yes Solve time: 2m46s Solution A 2-ordered permutation $a_1a_2\cdots a_n$ satisfies $$ a_i<a_{i+2}\qquad (1\le i\le n-2). $$ Hence the odd-positioned entries $$ a_1,a_3,a_5,\ldots $$ form an increasing sequence, and the even-positioned...
TAOCP 5.4.1 Exercise 13
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 13. [ 13 ] [13] Why is the second run produced by replacement selection usually longer than the first run? Verified: yes Solve time: 1m13s Solution Let $P$ be the number of keys held in the selection tree. Replacement selection produces a run by repeatedly outputting the smallest key among the active keys in the tree and replacing it by the next...
TAOCP 6.2.2 Exercise 25
Section 6.2.2: Binary Tree Searching Exercise 25. [ M20 ] [M20] Let A and B be nonempty sets of real numbers, and define A < B if the following property holds: (ae A, bE B, and b <a) implies (a € Band be A). a) Prove that this relation is transitive on nonempty sets. b) Prove or disprove: A < B if and only if A< AUB< B. Verified: no...
TAOCP 5.3.2 Exercise 21
Section 5.3.2: Minimum-Comparison Merging Exercise 21. [ M47 ] [M47] Prove or disprove (23) and (24). Verified: no Solve time: 1m39s Let $M(m,n)$ be Knuth’s function from Section 5.3.2: the maximum cost (in pointer traversals, or equivalent unit-cost steps as defined in the section) of performing any sequence of $m$ FIND operations and $n$ UNION operations on a disjoint-set data structure, under the specified heuristics. The statements Equations (23) and...
TAOCP 5.4.9 Exercise 22
Section 5.4.9: Disks and Drums Exercise 22. [ 22 ] [22] If you are merging two files with the Gilbreath principle and you want to store the keys a; with the a blocks and the keys 6; with the b blocks, in which block should a; be placed in order to have the information available when it is needed? [20] How much space is needed for input buffers to keep...
TAOCP 6.2.2 Exercise 43
Section 6.2.2: Binary Tree Searching Exercise 43. [ 20 ] [20] Explain how to implement phase 2 of the Garsia, Wachs algorithm efficiently. 44, [25] Explain how to implement phase 3 of the Garsia, Wachs algorithm efficiently: Construct a binary tree, given the levels lo, 1, ..., In of its leaves in symmetric order. Verified: yes Solve time: 1m36s Solution Phase 2 constructs the binary tree from the sequence produced...
TAOCP 5.3.2 Exercise 11
Section 5.3.2: Minimum-Comparison Merging Exercise 11. [ M40 ] [M40] (F. K. Hwang, S. Lin.) Let $g_0 = \lfloor 4 \cdot 2^0 \rfloor$ and $g_{k+1} = \lfloor 2^{g_k} \rfloor$, for $k > 0$, so that $(g_0, g_1, g_2, \ldots) = (1, 1, 2, 3, 4, 6, 9, 13, 19, 27, 38, 54, 77, \ldots)$. Prove that it takes more than $t$ comparisons to merge two elements with $g_t$ elements, in...
TAOCP 5.3.3 Exercise 2
Section 5.3.3: Minimum-Comparison Selection Exercise 2. [**] [20] Prove that Vi(n) > Vi(n, 1) and Wi(n) > Wi(n, 1), for 1 < t < n. Verified: yes Solve time: 4m03s We give a clean decision-tree argument that avoids the gap in the previous solution and directly relates worst-case depths. Notation Let $V_t(n)$ be the minimum worst-case number of comparisons needed to find the $t$-th largest of $n$ elements, and assume...
TAOCP 5.4.6 Exercise 1
Section 5.4.6: Practical Considerations for Tape Merging Exercise 1. [ 18 ] [18] Give a formula for the exact number of characters per tape, when every block on the tape contains n characters. Assume that the tape could hold exactly 23000000 characters if there were no interblock gaps. Verified: no Solve time: 1m54s Let $L = 23{,}000{,}000$. This is the number of character positions on the tape if there were...
TAOCP 5.2.5 Exercise 3
Section 5.2.5: Sorting by Distribution Exercise 3. [**] [15] Explain why Algorithm H makes BOTM[0] point to the first record in the “hooked-up” queue, even though pile 0 might be empty. Verified: yes Solve time: 1m30s At the start, Algorithm H sets $i \leftarrow 0$ and then sets $P \leftarrow \mathrm{TOP}[0]$. By the conventions of Algorithm R, $\mathrm{TOP}[0]$ initially refers to $\mathrm{BOTM}[0]$, so $P$ begins at the head pointer of...
TAOCP 5.2.3 Exercise 10
Section 5.2.3: Sorting by Selection Exercise 10. [ 20 ] [20] (J. W. J. Williams.) Step H4 of Algorithm H distinguishes between the three cases i < r, j = r, and j > r. Show that if Kk > Kk+1 it would be possible to simplify step H4 so that only a two-way branch is made. How could the condition K > K+1 be ensured throughout the heapsort process,...
TAOCP 5.4.2 Exercise 17
Section 5.4.2: The Polyphase Merge Exercise 17. [ 32 ] [32] Prove or disprove: There is a way to disperse runs for an optimum polyphase distribution in such a way that the distribution for S + 1 initial runs is formed by adding one run (on an appropriate tape) to the distribution for S initial runs. Verified: no Solve time: 2m26s The previous argument failed because it replaced the polyphase...
TAOCP 5.2.4 Exercise 7
Section 5.2.4: Sorting by Merging Exercise 7. [ M34 ] [M34] Give an analysis of the average running time of Program L, in the style of other analyses in this chapter: Interpret the quantities $A, B, B', \dots$, and explain how to compute their exact average values. How long does Program L take to sort the 16 numbers in Table 3? Verified: no Solve time: 4m48s A correct analysis must...
TAOCP 5.4.9 Exercise 7
Section 5.4.9: Disks and Drums Exercise 7. [ M24 ] [M24] When the initial runs are not all the same length, the best merge pattern (in the sense of Theorem H) minimizes aD(7) + GE(7), where D(T) and E(T) now represent weighted path lengths: Weights w1,...,Wn (corresponding to the lengths of the initial runs) are attached to each leaf of the tree, and the degree sums and path lengths are...
TAOCP 6.2.1 Exercise 16
Section 6.2.1: Searching an Ordered Table Exercise 16. [ 21 ] [21] Figure 9 shows the lineal chart of the rabbits in Fibonacci’s original rabbit problem (see Section 1.2.8). Is there a simple relationship between this and the Fibonacci tree discussed in the text? Initial pair First month Second month Third month VA\ Fourth month [| Fifth month [ l \ L\ \ Sixth month l \ \ Fig. 9....
TAOCP 5.1.4 Exercise 8
Section 5.1.4: Tableaux and Involutions Exercise 8. [ M28 ] [M28] Prove Theorem C. Verified: yes Solve time: 56m28s Exercise 5.1.4.8 [ M28 ] 8. [M28] Prove Theorem C. Solution. Theorem C (TAOCP, Vol. 3, Sec. 5.1.4). Let $P$ be a finite partially ordered set of size $n$. Let $e(P)$ denote the number of linear extensions of $P$. Then if $x$ is a maximal element of $P$, we have $$...
TAOCP 5.3.2 Exercise 9
Section 5.3.2: Minimum-Comparison Merging Exercise 9. [ 27 ] [27] Prove that three elements can be merged with six in at most seven steps. Verified: no Solve time: 4m44s We construct a single, explicit decision tree of comparisons whose worst-case depth is at most 7. Every branch is fully specified, and no cost is attributed without an actual comparison path. Let $$ A_1 < A_2 < A_3,\quad B_1 < B_2...
TAOCP 5.4.1 Exercise 14
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 14. [ HM25 ] [HM25] Use the snowplow analogy to estimate the average length of the last two runs produced by replacement selection on a long sequence of input data. 264 SORTING 5.4.1 Verified: no Solve time: 3m41s The key issue is the conditioning of the truncation point. The snowplow model must be cut at a uniformly random time , not a...
TAOCP 5.4.9 Exercise 18
Section 5.4.9: Disks and Drums Exercise 18. [ HM26 ] [HM26] Let L be the lower bound of exercise 17. Show that the average number of elevator stops needed to take all people to their desired floors is at least EL, 1, when the (bn)! possible permutations of people into bn desks are equally likely. [25] (B. T. Bennett and A. C. McKellar.) Consider the following approach to keysorting, illustrated...
TAOCP 6.2.1 Exercise 1
Section 6.2.1: Searching an Ordered Table Exercise 1. [ 21 ] [21] Prove that if u < / in step B2 of the binary search, we have u = /, 1 and Ku < K < k;. (Assume by convention that Ko =, oo and Ky+1 = +00, although these artificial keys are never really used by the algorithm so they need not be present in the actual table.) Verified:...
TAOCP 5.3.4 Exercise 3
Section 5.3.4: Networks for Sorting Exercise 3. [**] [M20] (K. E. Batcher.) Find a simple relation between $C(m,m-1)$ and $C(m,m)$. Verified: no Solve time: 2m14s Apply equation (5) twice, first with $(m,n)=(m,m-1)$ and then with $(m,n)=(m,m)$. From (5), $C(m+1,n+1)-C(m,n)=\left\lceil \frac{m}{2} \right\rceil + 2\left\lfloor \frac{n}{2} \right\rfloor,$ for $m>1$. With $n=m-1$, $C(m+1,m)-C(m,m-1)=\left\lceil \frac{m}{2} \right\rceil + 2\left\lfloor \frac{m-1}{2} \right\rfloor.$ With $n=m$, $C(m+1,m+1)-C(m,m)=\left\lceil \frac{m}{2} \right\rceil + 2\left\lfloor \frac{m}{2} \right\rfloor.$ Subtracting the first identity from...
TAOCP 6.2.2 Exercise 17
Section 6.2.2: Binary Tree Searching Exercise 17. [ 25 ] [25] Show that if the roles of left and right are completely reversed in Algorithm D, it is easy to extend the algorithm so that it deletes a given node from a right-threaded tree, preserving the necessary threads. (See exercise 2.) Verified: no Solve time: 4m47s A correct solution must start from a precise dual of Algorithm D and then...
TAOCP 5.3.3 Exercise 5
Section 5.3.3: Minimum-Comparison Selection Exercise 5. [**] [M26] (R. W. Floyd) Given n distinct elements {X₁,...,Xn} and a set of relations Xᵢ < Xⱼ for certain pairs (i,j), we wish to find the second largest element. If we know that Xᵢ < Xⱼ and Xᵢ < Xk for j ≠ k, Xᵢ cannot possibly be the second largest, so it can be eliminated. The resulting relations now have a form...
TAOCP 6.2.1 Exercise 21
Section 6.2.1: Searching an Ordered Table Exercise 21. [ 20 ] [20] Draw the binary tree corresponding to interpolation search when N = 10. Verified: no Solve time: 4m10s Solution Let the keys be $$ K_1<K_2<\cdots<K_{10}, $$ and let the unsuccessful-search intervals (gaps) be $$ (K_0,K_1),\ (K_1,K_2),\ \ldots,\ (K_{10},K_{11}), $$ where $$ K_0=-\infty,\qquad K_{11}=+\infty. $$ For interpolation search, Algorithm I determines the next comparison from the endpoints of the current...
TAOCP 5.4.2 Exercise 15
Section 5.4.2: The Polyphase Merge Exercise 15. [ M43 ] [M43] Prove or disprove: X'n-1(m) < Yn(m) implies that Xn(m) < Yn4i(m) < Sn42(m) <---. [Such a result would greatly simplify the calculation of Table 2.] Verified: yes Solve time: 1m43s Setup The statement concerns three families of quantities $X_n(m)$, $Y_n(m)$, $S_n(m)$, together with a primed variant $X'_{n-1}(m)$. The claimed implication is $$ X' {n-1}(m) < Y_n(m) ;\Rightarrow; X_n(m) <...
TAOCP 5.4.6 Exercise 7
Section 5.4.6: Practical Considerations for Tape Merging Exercise 7. [ 26 ] [26] The initial distribution in example 7 of Chart A produces (AiD1)'' ~, -Di(A1D1)'°, Di (Ai Di)? iD (A1.D1)" on tapes 1-4, where (AiD1)* means A, D,A1,D,A1,D,A1D1A1D,A1D1Ai1D. Show how to insert additional Ao’s and Dos in a “best possible” way (in the sense that the overall number of initial runs processed while merging is minimized), bringing the distribution...
TAOCP 5.3.3 Exercise 1
Section 5.3.3: Minimum-Comparison Selection Exercise 1. [**] [15] In Lewis Carroll’s tournament (Figs. 39 and 40), why was player 13 eliminated in spite of winning in Round 3? Table 2 MINIMUM AVERAGE COMPARISONS FOR SELECTION n Vi(n) Va(n) V3(n) Va(n) V5(n) Ve(n) V7(n) 1 0 2 1 1 3 2 2 2 4 3 4 4 3 4 13 4 5 4 5 4 5 3 3 5 6 5...
TAOCP 5.4.9 Exercise 6
Section 5.4.9: Disks and Drums Exercise 6. [ 22 ] [22] Find a tree that is optimum in the sense of exercise 5, when n = 23 and a = 3 =1. (You may wish to use a computer.) Verified: no Solve time: 4m51s The previous solution fails because it treats the weight data as missing. In TAOCP 5.4.9, Exercise 5 fixes the instance: the weights are $$ W_i =...
TAOCP 6.3 Exercise 13
Section 6.3: Digital Searching Exercise 13. [ 20 ] [20] (M-ary digital searching.) Explain how Algorithms T and D can be combined into a generalized algorithm that is essentially the same as Algorithm D when M = 2. What changes would be made to Table 1, if your algorithm is used for M = 30? [25] Design an efficient algorithm that can be performed just after Algorithm P has terminated...
TAOCP 6.2.2 Exercise 1
Section 6.2.2: Binary Tree Searching Exercise 1. [ 15 ] [15] Algorithm T has been stated only for nonempty trees. What changes should be made so that it works properly for the empty tree too? Verified: no Solve time: 1m19s Solution Let $A$ denote the null pointer used in Algorithm T. An empty binary search tree is represented by setting $\mathrm{ROOT} = A$. Algorithm T begins by setting $P \leftarrow...
TAOCP 5.2.2 Exercise 4
Section 5.2.2: Sorting by Exchanging Exercise 4. [**] [M23] If $t = 1$ in step B4, we could actually terminate Algorithm B immediately, because the subsequent step B2 will do nothing useful. What is the probability that $t = 1$ will occur in step B4 when sorting a random permutation? Verified: yes Solve time: 6m17s The flaw in the previous solution is the attempt to characterize the event using the...
TAOCP 5.2.5 Exercise 1
Section 5.2.5: Sorting by Distribution Exercise 1. [**] [20] The algorithm of exercise 5.2–13 shows how to do a distribution sort with only $N$ record areas (and $M$ count fields), instead of $2N$ record areas. Does this lead to an improvement over the radix sorting algorithm illustrated in Table 1? Verified: no Solve time: 1m19s The distribution sort of Exercise 5.2–13 reduces the number of record areas from $2N$ to...
TAOCP 5.2.3 Exercise 7
Section 5.2.3: Sorting by Selection Exercise 7. [**] [12] What will be the configuration of the tree in Fig. 23 after 14 of the original 16 items have been output? Verified: yes Solve time: 1m42s After 14 outputs, all but two elements have been replaced by $-\infty$ in the tournament structure of Fig. 23, so only the two smallest original keys remain as finite values. These two surviving keys occupy...
TAOCP 6.2.2 Exercise 28
Section 6.2.2: Binary Tree Searching Exercise 28. [ 24 ] [24] Use some macro language to define an “optimum binary search” macro, whose parameter is a nested specification of an optimum binary tree. Verified: yes Solve time: 3m48s The previous solution failed to align with TAOCP macro-language conventions because it relied on undefined return semantics and did not specify a formal output interface. We now restart the construction from scratch,...
TAOCP 5.4.8 Exercise 7
Section 5.4.8: Two-Tape Sorting Exercise 7. [ M40 ] [M40] (R. M. Karp.) Generalize the problem of exercise 6, replacing the linear path of an elevator by a network of roads to be traveled by a bus, given that the network forms any free tree. The bus has finite capacity, and the goal is to transport passengers to their destinations in such a way that the bus travels a minimum...
TAOCP 5.4.3 Exercise 11
Section 5.4.3: The Cascade Merge Exercise 11. [ M38 ] [M38] Let etc. Letting m k=0 Verified: yes Solve time: 1m09s Setup The exercise statement is incomplete. It ends after “Let … etc. Letting …” and shows only fragments “$m$” and “$k=0$”, without defining the objects to be studied or the expression to be proved. No definitions of the intended sequences, sums, or generating functions are present, and no identity...
TAOCP 6.2.2 Exercise 34
Section 6.2.2: Binary Tree Searching Exercise 34. [ HM21 ] [HM21] Show that the asymptotic value of the multinomial coefficient (1, pe, spa) piN, paN, ..., PrN as N - oo is related to the entropy H(p1,p2,..., Dn). Verified: yes Solve time: 1m21s Solution Let $p_1,\dots,p_r$ satisfy $p_i \ge 0$ and $\sum_{i=1}^r p_i = 1$, and let $n_i = p_i N$ with integers $n_i$ such that $\sum_{i=1}^r n_i = N$....
TAOCP 5.4.2 Exercise 9
Section 5.4.2: The Polyphase Merge Exercise 9. [ M20 ] [M20] Let K®) be the number of sequences of m Os and 1s such that there are no p consecutive 1s. For example, when p = 3 and m = 5 there are 24 such sequences: 00000, 00001, 00010, 00011, 00100, 00101, 00110, 01000, 01001,...,11011. Show that Ke isa generalized Fibonacci number. Verified: no Solve time: 53s Solution Let $K_m$...
TAOCP 6.2.1 Exercise 8
Section 6.2.1: Searching an Ordered Table Exercise 8. [ M20 ] [M20] Let 6; = DELTA[j] be the jth increment in Algorithm C, as defined in (6). a) What is the sum dis Nie 65? b) What are the minimum and maximum values of i that can occur in step C2? Verified: no Solve time: 4m15s Let $$ \Delta[j]=\left\lfloor \frac{N+2^{j-1}}{2^j}\right\rfloor,\qquad 1\le j\le k,\quad k=\lfloor \lg N\rfloor+2. $$ Equivalently, $$ \Delta[j]=\left\lfloor...
TAOCP 5.4.2 Exercise 3
Section 5.4.2: The Polyphase Merge Exercise 3. [ 22 ] [22] Prove that the condition D[1] > D[2] >--- > D[T] is always satisfied at the conclusion of step D4. Explain why this condition is important, in the sense that the mechanism of steps D2 and D3 would not work properly otherwise. Verified: no Solve time: 4m26s Start from the definition at the end of step D4: $$ D[j] =...
TAOCP 6.2.1 Exercise 26
Section 6.2.1: Searching an Ordered Table Exercise 26. [ 22 ] [22] Show that Fibonacci trees are related to polyphase merge sorting on three tapes. Verified: no Solve time: 3m47s A correct proof must specify an invariant state of the polyphase algorithm and show that this invariant is exactly the Fibonacci decomposition encoded by Fibonacci trees. 1. Fibonacci trees Define the Fibonacci trees $T_n$ for $n \ge 1$ by $$...
TAOCP 6.2.2 Exercise 49
Section 6.2.2: Binary Tree Searching Exercise 49. [ HM42 ] [HM42] Analyze the average height of a random binary search tree. 6.2.3. Balanced Trees The tree insertion algorithm we have just learned will produce good search trees, when the input data is random, but there is still the annoying possibility that a degenerate tree will occur. Perhaps we could devise an algorithm that keeps the tree optimum at all times;...
TAOCP 5.4.1 Exercise 16
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 16. [ M26 ] [M26] Find a “simple” necessary and sufficient condition that a file Ri Ro... Rn will be completely sorted in one pass by P-way replacement selection. What is the probability that this happens, as a function of P and N, when the input is a random permutation of {1,2,...,N}? Verified: no Solve time: 4m29s The previous solution fails because...
TAOCP 5.4.9 Exercise 9
Section 5.4.9: Disks and Drums Exercise 9. [ HM89 ] [HM89] (L. Hyafil, F. Prusker, J. Vuillemin.) Prove that, for fixed a and 6, am+B Ai(n) = (nin min oem ) mogn + O(n) as n, > oo, where the O(n) term is > 0. Verified: no Solve time: 2m17s Let $T$ be a full binary tree with $n$ leaves, and let $D(T)$ and $E(T)$ be the two weighted path...
TAOCP 5.2.3 Exercise 11
Section 5.2.3: Sorting by Selection Exercise 11. [ 10 ] [10] Show that simple queues are special cases of priority queues. (Explain how keys can be assigned to the elements so that a largest-in-first-out procedure is equivalent to first-in-first-out.) Is a stack also a special case of a priority queue? Verified: yes Solve time: 2m05s Let elements arrive in a sequence at times $t = 1,2,\ldots$. In a simple queue...
TAOCP 5.4.6 Exercise 5
Section 5.4.6: Practical Considerations for Tape Merging Exercise 5. [ 21 ] [21] When equal keys are present on different files, it is necessary to be very careful in the forecasting process. Explain why, and show how to avoid difficulty by defining the merging and forecasting operations of Algorithm F more precisely. 342 SORTING 5.4.6 Verified: yes Solve time: 1m13s Solution Algorithm F forecasts the next input operation by examining...
TAOCP 5.4.2 Exercise 21
Section 5.4.2: The Polyphase Merge Exercise 21. [ 11 ] [11] What should appear on level 7 in (26)? Verified: yes Solve time: 1m23s Solution In the six-tape case we have $T=6$ and hence $P=T-1=5$. The perfect distributions in (26) satisfy the $5$th-order Fibonacci propagation rule: each new level is obtained by summing the preceding five levels componentwise, as encoded by the backward construction of the table. Let level $n$...
TAOCP 5.2.1 Exercise 1
Section 5.2.1: Sorting by Insertion Exercise 1. [**] [10] Is Algorithm S a stable sorting algorithm? Verified: no Solve time: 13m25s Yes. Algorithm S is stable. Assume that two records $R_p$ and $R_q$ have equal keys, with $p<q$. When $R_q$ is inserted into the already sorted portion of the file, step S4 compares its key $K$ with preceding keys. The algorithm moves a record only when $K<K_i$. If $K=K_i$, the...
TAOCP 5.2.5 Exercise 8
Section 5.2.5: Sorting by Distribution Exercise 8. [ 20 ] [20] The radix-sorting algorithms discussed in the text assume that all keys being sorted are nonnegative. What changes should be made to the algorithms when the keys are numbers expressed in two’s complement or ones’ complement notation? Verified: yes Solve time: 1m50s Solution Let the radix be $M$ and let keys be written as $(a_1,a_2,\dots,a_p)$ with digits $0 \le a_i...
TAOCP 6.3 Exercise 40
Section 6.3: Digital Searching Exercise 40. [ 25 ] [25] Let ao ai az... be a periodic binary sequence with an+x = ax for all k > 0. Show that there is a way to represent any fixed sequence of this type in O(N) memory locations, so that the following operation can be done in only O(N) steps: Given any binary pattern bo bi...bn, 1, determine how often the pattern...
TAOCP 5.3.1 Exercise 1
Section 5.3.1: Minimum-Comparison Sorting Exercise 1. [**] [M22] (Weak orderings.) When equality between keys is allowed, there are 13 possible outcomes when sorting three elements: K1 = K2 = K3, K1 = K2 < K3, K1 = K3 < K2, K2 = K3 < K1, K1 < K2 = K3, K1 < K3 = K2, K2 < K1 = K3, K2 < K3 = K1, K3 < K1 = K2,...
TAOCP 6.2.2 Exercise 3
Section 6.2.2: Binary Tree Searching Exercise 3. [ 20 ] [20] In Section 6.1 we found that a slight change to the sequential search Algorithm 6.15 made it faster (Algorithm 6.1Q). Can a similar trick be used to speed up Algorithm T? Verified: yes Solve time: 1m19s Solution Algorithm T performs a search by repeatedly comparing $K$ with $KEY(P)$ and then moving to $LLINK(P)$ or $RLINK(P)$ until either the key...
TAOCP 6.2.2 Exercise 39
Section 6.2.2: Binary Tree Searching Exercise 39. [ M25 ] [M25] Let wi, ..., wn be nonnegative weights with wi +---+ wn = 1. Prove that the weighted path length of the Huffman tree constructed in Section 2.3.4.5 is less than H(wi,...,Wn) +1. Hint: See the proof of Theorem M. Verified: yes Solve time: 1m12s Solution Let $w_1,\dots,w_n$ be nonnegative with $w_1+\cdots+w_n=1$. Let $H(w_1,\dots,w_n)= -\sum_{i=1}^n w_i \lg w_i$, where $\lg...
TAOCP 6.3 Exercise 22
Section 6.3: Digital Searching Exercise 22. [ M25 ] [M25] How many trie nodes are on level | of a random M-ary trie containing N keys, for! =0, 1, 2,...? Verified: yes Solve time: 2m29s Solution Let $X_l$ denote the number of trie nodes on level $l$ in a random $M$-ary trie containing $N$ keys. Since the trie is random, $X_l$ is a random variable. Thus the natural interpretation of...
TAOCP 5.4.2 Exercise 1
Section 5.4.2: The Polyphase Merge Exercise 1. [ 16 ] [16] Figure 69 shows the order in which runs 34 through 65 are distributed to five tapes with Algorithm D; in what order are runs 1 through 33 distributed? Verified: no Solve time: 3m57s The reviewer is correct on all four failure points. The previous response does not solve the exercise because it never extracts the concrete combinatorial information from...
TAOCP 5.4.9 Exercise 15
Section 5.4.9: Disks and Drums Exercise 15. [ M22 ] [M22] Show that Theorem F can be improved slightly if the elevator is initially empty and if F(b)n 4 t: At least [(F(b)n + m, t)/(b+ m)] stops are necessary in such a case. Verified: no Solve time: 3m25s Solution Let the elevator process be measured in stops, and let each stop be a position at which the elevator services...
TAOCP 5.2.2 Exercise 5
Section 5.2.2: Sorting by Exchanging Exercise 5. [**] [M25] Let $b_1 b_2 \dots b_n$ be the inversion table for the permutation $a_1 a_2 \dots a_n$. Show that the value of BOUND after $r$ passes of the bubble sort is $$\max {b_i + r \mid b_i > r} - r, \quad \text{for } 0 < r < \max(b_1, \dots, b_n).$$ Verified: no Solve time: 7m26s Let $b_1 b_2 \dots b_n$ be...
TAOCP 6.3 Exercise 23
Section 6.3: Digital Searching Exercise 23. [ M26 ] [M26] How many digit inspections are made on the average during an unsuccessful search in an M-ary trie containing N random keys? Verified: yes Solve time: 1m23s Setup Let $N$ keys be stored in an $M$-ary trie under the uniform random model in which each digit of each key is independently uniformly distributed in ${0,1,\dots,M-1}$. A search argument $K$ is assumed...
TAOCP 5.2.3 Exercise 13
Section 5.2.3: Sorting by Selection Exercise 13. [ 20 ] [20] Design an efficient algorithm that inserts a new key into a given heap of n elements, producing a heap of n + 1 elements. Verified: yes Solve time: 5m53s Exercise 5.2.3.13 [20] Problem: Design an efficient algorithm that inserts a new key into a given heap of $n$ elements, producing a heap of $n+1$ elements. Solution Let the heap...
TAOCP 6.3 Exercise 20
Section 6.3: Digital Searching Exercise 20. [ M30 ] [M30] Consider M-ary trie memory in which we use a sequential search whenever reaching a subfile of s or fewer keys. (Algorithm T is the special case s = 1.) Apply the results of the preceding exercises to analyze a) the average number of trie nodes; b) the average number of digit or character inspections in a successful search; and c)...
TAOCP 5.4.3 Exercise 7
Section 5.4.3: The Cascade Merge Exercise 7. [ M20 ] [M20] Given that cascade merge is being applied to a perfect distribution of an initial runs, find a formula for the amount of processing saved when one-way merging is suppressed. Verified: no Solve time: 4m26s The reviewer is correct that the original argument fails because it treats the modified algorithm as if it follows the same step-by-step state evolution as...
TAOCP 6.1 Exercise 11
Section 6.1: Sequential Searching Exercise 11. [ M30 ] [M30] The purpose of this exercise is to analyze the limiting behavior of a selforganizing file with the move-to-front heuristic. First we need to define some notation: Let fm(@1, U2,-..,%m) be the infinite sum of all distinct ordered products 2j, Gig... Li, such that 1 < #41,...,%% < m, where each of 41, %2,...,%m appears in every term. For example, j...
TAOCP 5.4.1 Exercise 26
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 26. [ M33 ] [M33] Considering the algorithm in exercise 25 as a definition of natural selection when P’ = 1, find the expected length of the first run when P’ = r, for any r > 0, as follows. a) Show that the first run has length n with probability (nerf "| [nt r+ ve b) Define “associated Stirling numbers” [[.”]]...
TAOCP 6.2.2 Exercise 2
Section 6.2.2: Binary Tree Searching Exercise 2. [ 20 ] [20] Modify Algorithm T so that it works with right-threaded trees. (See Section 2.3.1; symmetric traversal is easier in such trees.) Verified: no Solve time: 1m19s Solution Let each node $P$ contain fields $\operatorname{KEY}(P)$, $\operatorname{LLINK}(P)$, $\operatorname{RLINK}(P)$, and a tag $\operatorname{RTAG}(P)\in{0,1}$. The interpretation is that $\operatorname{RTAG}(P)=0$ means $\operatorname{RLINK}(P)$ is a right child, while $\operatorname{RTAG}(P)=1$ means $\operatorname{RLINK}(P)$ is the symmetric successor (a...
TAOCP 5.3.1 Exercise 5
Section 5.3.1: Minimum-Comparison Sorting Exercise 5. [**] [M25] When sorting $n$ elements as in exercise 7, knowing that all keys are 0 or 1, what is the minimum average number of comparisons as a function of $n$? Verified: yes Solve time: 3m21s 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...
TAOCP 6.2.1 Exercise 17
Section 6.2.1: Searching an Ordered Table Exercise 17. [ M21 ] [M21] From exercise 1.2.8-34 (or exercise 5.4.2-10) we know that every positive integer n has a unique representation as a sum of Fibonacci numbers nm = Fo, + Foo +++++ Fa,,; where r > 1, aj > aj41+2 forl1 <j <r,anda, > 2. Prove that in the Fibonacci tree of order k, the path from the root to node...
TAOCP 5.3.2 Exercise 19
Section 5.3.2: Minimum-Comparison Merging Exercise 19. [ 23 ] [23] Prove that the $M$ function satisfies (22). Verified: yes Solve time: 1m17s Solution Let $M(m,n)$ denote the minimum number of comparisons required to merge two increasing sequences of lengths $m$ and $n$. Consider any optimal merging algorithm $\mathcal{A}$ that merges a sequence $A_1 < \cdots < A_m$ with $B_1 < \cdots < B_n$ using $M(m,n)$ comparisons. Construct a transformed instance...
TAOCP 5.4.6 Exercise 13
Section 5.4.6: Practical Considerations for Tape Merging Exercise 13. [ 20 ] [20] Can a five-tape oscillating sort, as defined in Algorithm 5.4.5B, be used to sort four reelfuls of input data, up until the time of the final merge? Verified: no Solve time: 4m44s The previous solution fails because it attempts to repair the situation by adding an external phase. The correct approach is to analyze whether Algorithm 5.4.5B...
TAOCP 5.2.3 Exercise 8
Section 5.2.3: Sorting by Selection Exercise 8. [**] [10] What will be the configuration of the tree in Fig. 24 after the element 908 has been output? Verified: yes Solve time: 4m45s Corrected Solution: Exercise 5.2.3.8 [**] We are asked to determine the configuration of the heap in Fig. 24 after the element 908, currently at the root, has been output. We proceed according to the procedure described in TAOCP...
TAOCP 6.2.2 Exercise 31
Section 6.2.2: Binary Tree Searching Exercise 31. [ M35 ] [M35] (K.C. Tan.) Prove that, among all possible sets of probabilities (p1,..., Dn} qo,---;Qn) with pi +--+ +pn+qo+-::+a = 1, the most expensive minimum-cost tree occurs when p; = 0 for all i, qj = 0 for all even j, and qj; = 1/[n/2] for all odd 7. [M25] Let n+ 1 = 2™"+4+k, where 0 < k < 2”....
TAOCP 6.2.2 Exercise 26
Section 6.2.2: Binary Tree Searching Exercise 26. [ M22 ] [M22] Let (pi,...,Pn3 Go,---;Qn) be nonnegative weights, where pn + qn = Z. Prove that as x varies from 0 to oo, while (p1,...,Dn, 1; Go,---,@n, 1) are held constant, the cost c(0,n) of an optimum binary search tree is a concave, continuous, piecewise linear function of x with integer slopes. In other words, prove that there exist positive integers...
TAOCP 6.1 Exercise 8
Section 6.1: Sequential Searching Exercise 8. [ HM22 ] [HM22] Find an asymptotic series for H® asn, co, when « Al. Verified: yes Solve time: 1m03s Solution Let $$ H_N^{(\theta)}=\sum_{k=1}^{N} k^{-\theta}, \qquad \theta \neq 1. $$ Apply Euler–Maclaurin summation to $f(x)=x^{-\theta}$. For any integer $m\ge 1$, $$ \sum_{k=1}^{N} f(k) \int_{1}^{N} f(x),dx +\frac{f(N)+f(1)}{2} +\sum_{r=1}^{m-1}\frac{B_{2r}}{(2r)!}\bigl(f^{(2r-1)}(N)-f^{(2r-1)}(1)\bigr) +R_m, $$ where $B_{2r}$ are Bernoulli numbers and $R_m$ is the remainder term. For $f(x)=x^{-\theta}$, $$ \int_{1}^{N}...
TAOCP 5.4.7 Exercise 5
Section 5.4.7: External Radix Sorting Exercise 5. [ 15 ] [15] Draw the 4-lifo tree corresponding to Mauchly’s read-backwards radix sort for 10 keys. [20] A certain file contains two-digit keys 00, 01, ..., 99. After performing Mauchly’s radix sort on the least significant digits, we can repeat the same scheme on the most significant digits, interchanging the roles of tapes T2 and T4. In what order will the keys...
TAOCP 6.2.1 Exercise 29
Section 6.2.1: Searching an Ordered Table Exercise 29. [ 22 ] [22] (Paul Feldman, 1985.) Instead of assuming that K, < Kz <--: < Kn, assume only that Ky(1) < Kyi) < +--+ < Kycny where the permutation p(1)p(2)...p(N) is an involution, and p(j) = j for all even values of 7. Show that we can locate any given key K, or determine that K is not present, by making...
TAOCP 6.1 Exercise 21
Section 6.1: Sequential Searching Exercise 21. [ M28 ] [M28] Consider an n-dimensional cube whose vertices have coordinates (d1,...,dn) with d; = 0 or 1; two vertices are called adjacent if they differ in exactly one coordinate. Suppose that a set of 2” numbers a < 21 <--- < XZgn_1 is to be assigned to the 2” vertices in such a way that >7, , |vi, xj| is minimized, where...
TAOCP 6.3 Exercise 10
Section 6.3: Digital Searching Exercise 10. [ 23 ] [23] Given a file in which all the keys are n-bit binary numbers, and given a search argument K = 6; b2...bn, suppose we want to find the maximum value of & such that there is a key in the file beginning with the bit pattern 6; b2...b,%. How can we do this efficiently if the file is represented as a)...
TAOCP 5.4.6 Exercise 3
Section 5.4.6: Practical Considerations for Tape Merging Exercise 3. [ 20 ] [20] Would Algorithm F work properly if there were only 2P, 1 input buffers instead of 2P? If so, prove it; if not, give an example where it fails. Verified: no Solve time: 6m08s
TAOCP 6.1 Exercise 20
Section 6.1: Sequential Searching Exercise 20. [ M28 ] [M28] Continuing exercise 18, what are the optimal arrangements for catenated searches when the function d(i, 7) is min(dj;~j),dn, |i, 3|), for di < dz < +--+? [This situation occurs, for example, in a two-way linked circular list, or in a two-way shiftregister storage device.] 408 SEARCHING 6.1 Verified: no Solve time: 4m35s The previous solution failed because it tried to...
TAOCP 6.3 Exercise 31
Section 6.3: Digital Searching Exercise 31. [ M21 ] [M21] Solve the recurrence (16). Verified: no Solve time: 4m43s Let $A_n$ be the expected cost of an $M$-ary digital search tree built from $n$ random keys, and let $P(z)$ be its Poisson transform. 1. Poissonized recurrence As in the proposed solution, Poissonization with parameter $z$ gives independent subtree sizes $$ N_0,\dots,N_{M-1} \sim \mathrm{Poisson}(z/M), $$ and hence the exact functional equation...
TAOCP 5.4.2 Exercise 22
Section 5.4.2: The Polyphase Merge Exercise 22. [ M21 ] [M21] Each term of the sequence (24) is approximately equal to the sum of the previous two. Does this phenomenon hold for the remaining numbers of the sequence? Formulate and prove a theorem about tn, tn, 1, tn, 2. Verified: no Solve time: 1m21s Solution Let $T = P+1$ and let $t_n$ denote the total number of runs in the...
TAOCP 5.4.1 Exercise 19
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 19. [ HM22 ] [HM22] Use the snowplow analogy to prove that the first run produced by replacement selection is approximately (e, 1)P records long. Verified: no Solve time: 3m59s We restart from a faithful snowplow model of replacement selection and avoid any per-record attribution. Correct solution Let the memory contain $P$ records. Assume all keys are distinct and that the input...
TAOCP 6.2.1 Exercise 3
Section 6.2.1: Searching an Ordered Table Exercise 3. [ 15 ] [15] What searching method corresponds to the tree ? What is the average number of comparisons made in a successful search? in an unsuccessful search? A. [20] Ifa search using Program 6.15 (sequential search) takes exactly 638 units of time, how long does it take with Program B (binary search)? Verified: yes Solve time: 1m03s The statement “What searching...
TAOCP 5.5 Exercise 5
Section 5.5: Summary, History, and Bibliography Exercise 5. [ 46 ] [46] It is much more difficult to sort nonrandom data with numerous equal keys than to sort uniformly random data. Devise a sorting benchmark that (i) is interesting now and will probably be interesting 100 years from now; (ii) does not involve uniformly random keys; and (iii) does not use data sets that change with time. | shall have...
TAOCP 5.4.9 Exercise 25
Section 5.4.9: Disks and Drums Exercise 25. [ 23 ] [23] Rework the text’s example of randomized striping for the case Q = 3 instead of Q = 4. What buffer contents would occur in place of (24)? Verified: no Solve time: 3m30s The correct way to rework the example is to stay inside TAOCP’s randomized striping model: each run is striped across the $Q$ disks by a fixed permutation...
TAOCP 5.4.6 Exercise 12
Section 5.4.6: Practical Considerations for Tape Merging Exercise 12. [ 40 ] [40] Consider partitioning six tapes into three pairs of tapes, with each pair playing the role of a single tape in a polyphase merge with T = 3. One tape of each pair will contains blocks 1,3,5,... and the other tape will contain blocks 2, 4,6,...; in this way we can essentially have two input tapes and two...
TAOCP 6.3 Exercise 25
Section 6.3: Digital Searching Exercise 25. [ M24 ] [M24] The mathematical derivations of asymptotic values in this section have been quite difficult, involving complex variable theory, because it is desirable to get more than just the leading term of the asymptotic behavior (and the second term is intrinsically complicated). The purpose of this exercise is to show that elementary methods are good enough to deduce some of the results...
TAOCP 6.3 Exercise 38
Section 6.3: Digital Searching Exercise 38. [ M40 ] [M40] Develop an algorithm to find the n-node tree having the minimum value of a- (internal path length) + 8 - (modified external path length), given a and £, in the sense of exercise 37. Verified: no Solve time: 4m50s The error in the previous solution is structural: it used an incorrect recurrence for the modified external path length and then...
TAOCP 6.3 Exercise 37
Section 6.3: Digital Searching Exercise 37. [ M22 ] [M22] Consider a binary tree with b; external nodes on level J. The text observes that the running time for unsuccessful searching in digital search trees is not directly related to the external path length 5~*/b;, but instead it is essentially proportional to the modified external path length S 1b:2 '. Prove or disprove: The smallest modified external path length, over...
TAOCP 5.2.4 Exercise 4
Section 5.2.4: Sorting by Merging Exercise 4. [**] [25] (D. A. Bell.) Show that sequentially allocated straight two-way merging can be done with at most $3N$ memory locations, instead of $2N$ as in Algorithm S. Verified: yes Solve time: 1m09s Let the records be stored in three contiguous segments of $N$ locations each, denoted $A_1,\ldots,A_N$, $B_1,\ldots,B_N$, and $C_1,\ldots,C_N$. At the beginning of a pass, two segments contain the input files...
TAOCP 5.1.2 Exercise 8
Section 5.1.2: Permutations of a Multiset Exercise 8. [ 20 ] [20] Find all factorizations of (12) into two factors $\alpha \mathbin{\text{?}} \beta$. Verified: no Solve time: 31m23s Stopped thinking
TAOCP 5.1.2 Exercise 9
Section 5.1.2: Permutations of a Multiset Exercise 9. [ 33 ] [33] Write computer programs that perform the factorizations of a given multiset permutation into the forms mentioned in Theorems A and C. Verified: no Solve time: 20m23s Exercise 5.1.2.9 [ 33 ] 9. Write computer programs that perform the factorizations of a given multiset permutation into the forms mentioned in Theorems A and C. Solution Let $M$ be a...
TAOCP 5.1.2 Exercise 6
Section 5.1.2: Permutations of a Multiset Exercise 6. [**] [M15] How many strings are there that contain exactly $m$ a’s, $n$ b’s, and no other letters, with exactly $k$ of the a’s preceded immediately by a b? Verified: no Solve time: 1h12m Solution to Exercise 5.1.2.6, Problem 6 [M15] We are asked to count the number of strings containing exactly $m$ a’s and $n$ b’s, with exactly $k$ of the...
TAOCP 5.1.2 Exercise 7
Section 5.1.2: Permutations of a Multiset Exercise 7. [**] [M21] How many strings on the letters $a, b, c$ satisfying conditions (18) begin with the letter $a$? with the letter $b$? with $c$? Verified: yes Solve time: 1h12m Let the six admissible column types in (19) be $$ \binom{b}{a},\quad \binom{c}{a},\quad \binom{a}{b},\quad \binom{c}{b},\quad \binom{a}{c},\quad \binom{b}{c}, $$ since condition (18) excludes $\binom{a}{a},\binom{b}{b},\binom{c}{c}$. Formula (20) gives the number of strings satisfying (18): $$...
TAOCP 5.1.2 Exercise 5
Section 5.1.2: Permutations of a Multiset Exercise 5. [**] [M23] Condition (b) of Theorem B requires $x < y$; what would happen if we weakened the relation to $x \le y$? Verified: yes Solve time: 16m30s Condition (b) must exclude the case $x=y$. If it is changed from $x<y$ to $x\le y$, two equal elements would satisfy the condition, and the construction of Theorem B would no longer distinguish between...
TAOCP 5.1.2 Exercise 2
Section 5.1.2: Permutations of a Multiset Exercise 2. [**] [10] The intercalation of cadab and bddad is computed in (5); find the intercalation bddadcadab that is obtained when the factors are interchanged. Verified: no Solve time: 15m46s Using the definition of intercalation, we write $$ \beta=\text{bddad} \qquad\Longrightarrow\qquad \begin{pmatrix} a&b&d&d&d\ b&d&d&a&d \end{pmatrix}, $$ and $$ \alpha=\text{cadab} \qquad\Longrightarrow\qquad \begin{pmatrix} a&a&b&c&d\ c&a&d&a&b \end{pmatrix}. $$ After juxtaposing the two-line representations in the order $\beta,\alpha$...
TAOCP 5.1.2 Exercise 4
Section 5.1.2: Permutations of a Multiset Exercise 4. [**] [M11] The canonical factorization of (12), in the sense of Theorem A, is given in (17) when $a < b < c < d$. Find the corresponding canonical factorization when $d < c < b < a$. Verified: no Solve time: 18m56s If $d < c < b < a$, the canonical factorization of (12) is obtained by reversing the order...
TAOCP 5.1.2 Exercise 3
Section 5.1.2: Permutations of a Multiset Exercise 3. [**] [M13] Is the converse of (9) valid? In other words, if $\alpha$ and $\beta$ commute under intercalation, must they have no letters in common? Verified: yes Solve time: 17m31s No. The converse of (9) is false. A counterexample is provided by the identity permutation on a one-element multiset. Let $\alpha=(a)$ and $\beta=(a)$. The two permutations have the letter $a$ in common....
TAOCP 5.1.2 Exercise 1
Section 5.1.2: Permutations of a Multiset Exercise 1. [**] [M05] True or false: Let $M_1$ and $M_2$ be multisets. If $\alpha$ is a permutation of $M_1$ and $\beta$ is a permutation of $M_2$, then $\alpha \mathbin{\text{?}} \beta$ is a permutation of $M_1 \cup M_2$. Verified: yes Solve time: 30m29s False. A permutation of a multiset must be a bijection from the multiset onto itself. If $\alpha$ is a permutation of...
TAOCP 5.1 Exercise 3
Section 5.1: Combinatorial Properties of Permutations Exercise 3. [**] [26] Design an algorithm that computes the inversion table $b_1 b_2 \dots b_n$ corresponding to a given permutation $a_1 a_2 \dots a_n$ of ${1,2,\dots,n}$, where the running time is essentially proportional to $n \log n$ on typical computers. Verified: yes Solve time: 18m15s Store the permutation in an array $P$ such that $P(j)$ is the position of $j$ in the permutation....
TAOCP 5.1 Exercise 2
Section 5.1: Combinatorial Properties of Permutations Exercise 2. [**] [M20] In the classical problem of Josephus (exercise 1.3.2, 22), $n$ men are initially arranged in a circle; the $m$th man is executed, the circle closes, and every $m$th man is repeatedly eliminated until all are dead. The resulting execution order is a permutation of {1,2,...,n}. For example, when $n = 8$ and $m = 4$ the order is 54613872 (man...
TAOCP 5 Exercise 5
Section 5: Introduction to Sorting Exercise 5. [ 83 ] [83] (Library card sorting.) Before the days of computerized databases, every library maintained a catalog of cards so that users could find the books they wanted. But the task of putting catalog cards into an order convenient for human use turned out to be quite complicated as library collections grew. The following “alphabetical” listing indicates many of the procedures recommended...
TAOCP 5.1 Exercise 1
Section 5.1: Combinatorial Properties of Permutations Exercise 1. [**] [10] What is the inversion table for the permutation 271845936? What permutation has the inversion table 50121200? Verified: no Solve time: 40m04s Let the inversion table of a permutation $a_1a_2\cdots a_n$ be the sequence $b_1b_2\cdots b_n$, where $b_i$ is the number of entries greater than $i$ that occur to the left of $i$ in the permutation. 1. Inversion table of $271845936$...
TAOCP 5 Exercise 4
Section 5: Introduction to Sorting Exercise 4. [ 20 ] [20] In order to make it easier to make changes to large FORTRAN programs, you want to design a “cross-reference” routine; such a routine takes FORTRAN programs as input and prints them together with an index that shows each use of each identifier (that is, each name) in the program. How should such a routine be designed? Verified: no Solve...
TAOCP 5 Exercise 1
Section 5: Introduction to Sorting Exercise 1. [**] [15] Mr. B. C. Dull (a MIX programmer) wanted to know if the number stored in location A is greater than, less than, or equal to the number stored in location B. So he wrote LDA A; SUB B and tested whether register A was positive, negative, or zero. What serious mistake did he make, and what should he have done instead?...
TAOCP 5 Exercise 2
Section 5: Introduction to Sorting Exercise 2. [**] [17] Write a MIX subroutine for multiprecision comparison of keys, having the following specifications: Calling sequence: JMP COMPARE Entry conditions: rll = n ; CONTENTS(A+k) = a_k , and CONTENTS(B+k) = b_k , for $1 \le k \le n$; assume that $n > 1$. Exit conditions: CI = GREATER , if $(a_n, \dots, a_1) > (b_n, \dots, b_1)$; CI = EQUAL ,...
TAOCP 5 Exercise 3
Section 5: Introduction to Sorting Exercise 3. [**] [M25] (Transposing a matrix.) You are given a magnetic tape containing one million words, representing the elements of a $1000 \times 1000$ matrix stored in order by rows: $a_{1,1}, a_{1,2}, \dots, a_{1,1000}; a_{2,1}, \dots, a_{2,1000}; \dots; a_{1000,1000}$. How do you create a tape in which the elements are stored by columns $a_{j,1}, a_{2,1}, \dots, a_{1000,1}, a_{1,2}, \dots, a_{1000,2}, \dots, a_{1000,1000}$ instead? (Try...