#simple
TAOCP 5.4.4 Exercise 6
Section 5.4.4: Reading Tape Backwards Exercise 6. [ 07 ] What is the vector representation of the merge pattern whose tree representation is (8)? Verified: no Solve time: 3m34s The tree representation (8) illustrates the balanced merge on four tapes with eight initial runs, as summarized in the tableau of the section. The merge steps, in chronological order, are: Merge one run from T1 and one from T2 → T3...
TAOCP 5.3.1 Exercise 25
Section 5.3.1: Minimum-Comparison Sorting Exercise 25. [ 11 ] If there were a sorting procedure for seven elements that achieves the minimum average number of comparisons predicted by the use of Eq. (34), how many external nodes would there be on level 13? Verified: no Solve time: 1m50s Solution The minimum average number of comparisons for sorting (n) distinct elements is achieved by a comparison tree (a full binary tree)...
TAOCP 5.3.1 Exercise 23
Section 5.3.1: Minimum-Comparison Sorting Exercise 23. [ 10 ] The text proves that the average number of comparisons made by any sorting method for $n$ elements must be at least $\lceil \lg n! \rceil \approx n \lg n$. But multiple list insertion (Program 5.2.1M) takes only $O(n)$ units of time on the average. How can this be? Verified: no Solve time: 52s The information-theoretic lower bound (\lceil \lg n! \rceil)...
TAOCP 5.2.5 Exercise 17
Section 5.2.5: Sorting by Distribution Exercise 17. [ 15 ] In the two-level distribution sort proposed by Tamminen (see Theorem T), why is a MacLaren-like method used for the second level of distribution but not the first level? Verified: no Solve time: 1m41s Solution In Tamminen's two-level distribution sort (Theorem T), the first level partitions the $N$ records into $M$ buckets according to their most significant digit. This is done...
TAOCP 5.2.2 Exercise 33
Section 5.2.2: Sorting by Exchanging Exercise 33. ▶ [ 15 ] Design an algorithm that rearranges all the numbers in a given table so that all negative values precede all nonnegative ones. (The items need not be sorted completely, just separated between negative and nonnegative.) Your algorithm should use the minimum possible number of exchanges. Verified: no Solve time: 54s Solution We are given a table $A[1 \ldots N]$ of...
TAOCP 5.2.2 Exercise 19
Section 5.2.2: Sorting by Exchanging Exercise 19. [ 15 ] Would Algorithm Q still work properly if a queue (first-in-first-out) were used instead of a stack (last-in-first-out)? Verified: no Solve time: 38s Solution Yes, Algorithm Q would still work properly if a queue (FIFO) were used instead of a stack (LIFO). Reason. Algorithm Q is an iterative implementation of quicksort. It maintains a collection of subarray intervals ((l, r)) that...
TAOCP 5.2.2 Exercise 13
Section 5.2.2: Sorting by Exchanging Exercise 13. [ 10 ] Is Batcher's method a stable sorting algorithm? Verified: no Solve time: 4m16s Yes, Batcher's merge exchange sort is stable. Every compare-exchange operation in the algorithm is defined to swap two records only when their keys are in strictly decreasing order (i.e., (K_i > K_j)). Equal keys are therefore never interchanged directly. Moreover, because all operations are of this form, two...
TAOCP 5.2.1 Exercise 32
Section 5.2.1: Sorting by Insertion Exercise 32. [ 10 ] What would be the final contents of $L_0, L_1 \ldots L_{16}$ if the list insertion sort in Table 8 were carried through to completion? Verified: no Solve time: 4m23s The list insertion sort (Algorithm L) applied to the 16 keys from Table 1 (503, 087, 512, 061, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703) produces...
TAOCP 5.2.1 Exercise 28
Section 5.2.1: Sorting by Insertion Exercise 28. [ 15 ] Which sequence of increments shown in Table 6 is best from the standpoint of Program D, considering the average total running time? Verified: no Solve time: 1m48s Solution Table 6 in Section 5.2.1 lists the average performance of Program D for several increment sequences when sorting (N = 16) records. The table gives the average number of comparisons, moves, and...
TAOCP 5 Exercise 10
Section 5: Introduction to Sorting Exercise 10. [ 15 ] You are given a tape containing one million words of data. How do you determine how many distinct words are present on the tape? Verified: yes Solve time: 10m07s Solution We are given a tape containing (N = 10^6) words and have at most a few thousand words of internal memory (say (M) words, where (M \ll N)) and about...
TAOCP 5 Exercise 6
Section 5: Introduction to Sorting Exercise 6. [ 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...
TAOCP 1.2.5 Exercise 4
Section 1.2.5: Permutations and Factorials Exercise 4. ▶ [ 13 ] Given the fact that $\log_{10} 1000! = 2567.60464\ldots$, determine exactly how many decimal digits are present in the number $1000!$. What is the most significant digit? What is the least significant digit? Verified: yes Solve time: 7m12s Solution Let [ L=\log_{10}(1000!)=2567.60464\ldots. ] For every positive integer (N), the number of decimal digits of (N) is [ \lfloor \log_{10}N\rfloor+1, ]...
TAOCP 7.2.2.2 Exercise 88
Section 7.2.2.2: Satisfiability Exercise 88. [ 15 ] Satisfy (41) and (42) for $0 \le t < 6$, and the $20 \times 6$ additional binary clauses that exclude multiple states, along with the "embarrassing" unit clauses $(A3_6) \land (B3_6)$. Verified: no Solve time: 3m43s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and...
TAOCP 7.2.2.2 Exercise 52
Section 7.2.2.2: Satisfiability Exercise 52. [ 15 ] $[15]$ What clauses correspond to (29) and (30) when the second case on the left of Table 2, $f(1, 0, 1, 0, \ldots, 1) = 1$, is taken into account? Verified: no Solve time: 3m47s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le...
TAOCP 7.2.2.2 Exercise 490
Section 7.2.2.2: Satisfiability Exercise 490. [ 15 ] [15] Does Theorem E hold also when $p_1 p_2 \ldots p_n$ is any signed permutation? Verified: no Solve time: 3m45s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses...
TAOCP 7.2.2.2 Exercise 454
Section 7.2.2.2: Satisfiability Exercise 454. [ 15 ] $[15]$ If $\tau$ is an endomorphism for the solutions of $f$, show that $f(x) = f(x\tau)$ for every cyclic element $x$ (every element that's in a cycle of $\tau$). Verified: no Solve time: 3m43s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le...
TAOCP 7.2.2.2 Exercise 422
Section 7.2.2.2: Satisfiability Exercise 422. [ 11 ] What does unit propagation deduce when the additional clause $(x_1)$ or $(\bar{x}_2)$ is appended to (a) $F$ in (175)? (b) $G$ in (176)? Verified: no Solve time: 3m58s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain has size...
TAOCP 7.2.2.2 Exercise 40
Section 7.2.2.2: Satisfiability Exercise 40. [ 01 ] $[01]$ Is the factorization problem (22) unsatisfiable whenever $x$ is a prime number? Verified: no Solve time: 4m Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses forcing each...
TAOCP 7.2.2.2 Exercise 323
Section 7.2.2.2: Satisfiability Exercise 323. [ 10 ] [10] What trace precedes $ccb$ in the list (135)? Verified: no Solve time: 3m51s Solution No. Theorem J and Theorem L concern different probability estimates for Algorithm W, and the hypotheses of Theorem L do not imply the statement of Theorem J. Theorem J gives a bound under the specific assumption that the current assignment is at Hamming distance $d$ from a...
TAOCP 7.2.2.2 Exercise 32
Section 7.2.2.2: Satisfiability Exercise 32. [ 15 ] [15] A list coloring is a graph coloring in which the color belongs to a given list $L(v)$, for each vertex $v$. Express list coloring as a SAT problem. Verified: no Solve time: 3m55s Solution No. Theorem J and Theorem L concern different probability estimates for Algorithm W, and the hypotheses of Theorem L do not imply the statement of Theorem J....
TAOCP 7.2.2.2 Exercise 236
Section 7.2.2.2: Satisfiability Exercise 236. [ 8 ] Is the chain in the previous exercise as short as possible? Verified: no Solve time: 6m04s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly from ${0,1}$. For each clause $C$ of $F$, define the bad event $A_C$ to be the event that all literals of $C$ are false. Since $C$ has seven literals,...
TAOCP 7.2.2.1 Exercise 362
Section 7.2.2.1: Dancing Links Exercise 362. [ 10 ] $[10]$ A reduced pattern is called strictly reduced if each of its subrectangles $[a \ldots b) \times [c \ldots d)$ has $(a, b) \ne (0, m)$ and $(c, d) \ne (0, n)$, in other words, if no subrectangle "cuts all the way across." Modify the construction of exercise 360 so that it produces only strictly reduced solutions. How many $3 \times...
TAOCP 7.2.2.2 Exercise 174
Section 7.2.2.2: Satisfiability Exercise 174. [ 15 ] What's an easy way to accomplish (i) in the previous exercise? Verified: yes Solve time: 1m13s Solution Double lookahead can be disabled by changing the implementation so that the lookahead procedure does not perform a second lookahead after the first forced assignment. In Algorithm L, ordinary lookahead tests a candidate literal $l$ by temporarily assigning $l$ and applying the forced consequences produced...
TAOCP 7.2.2.2 Exercise 158
Section 7.2.2.2: Satisfiability Exercise 158. [ 15 ] [15] If $l$ is a pure literal, will Algorithm X discover it? Verified: no Solve time: 2m23s Solution Yes. Algorithm X will discover every pure literal that occurs in the current formula. Let $l$ be a pure literal of $F$. By definition, $\bar l$ occurs in no clause of $F$. Consider the exploration of $l$ in Algorithm X. When $l$ is assumed...
TAOCP 7.2.2.2 Exercise 157
Section 7.2.2.2: Satisfiability Exercise 157. [ 10 ] [10] Give an example of an autarky that is not a pure literal. Verified: no Solve time: 1m57s Take the formula $$ F={ab,\ \bar a\bar b}. $$ The set of literals $L={a,\bar b}$ is an autarky, because the clause $ab$ contains $a$, which is true under $L$, and the clause $\bar a\bar b$ contains $\bar b$, which is true under $L$. Hence...
TAOCP 7.2.2.2 Exercise 156
Section 7.2.2.2: Satisfiability Exercise 156. [ 05 ] [05] Why is a pure literal a special case of an autarky? Verified: yes Solve time: 1m14s A pure literal $l$ is a special case of an autarky because the partial assignment that sets $l=1$ and leaves all other variables unset satisfies every clause containing the variable $|l|$. Since $l$ is pure, no clause contains $\bar{l}$, so every clause touched by this...
TAOCP 7.2.2.2 Exercise 147
Section 7.2.2.2: Satisfiability Exercise 147. [ 05 ] [05] Evaluate $C_{\max}$ in (66) for $d = 0, 1, 10, 20, 30$, using the default $C_0$ and $C_1$. Verified: yes Solve time: 1m46s By equation (66), the cutoff value is $$ C_{\max}=C_0+C_1d . $$ Using the default values $C_0=1000$ and $C_1=100$, we substitute each requested value of $d$. For $d=0$, $$ C_{\max}=1000+100(0)=1000 . $$ For $d=1$, $$ C_{\max}=1000+100(1)=1100 . $$ For...
TAOCP 7.2.2.2 Exercise 144
Section 7.2.2.2: Satisfiability Exercise 144. [ 15 ] [15] True or false: If $l$ doesn't appear in any clause, $h'(l) = 0.1$ in (65). Verified: no Solve time: 2m09s Solution The statement is true. By equation (65), the refined heuristic value is $$ h'(l)=0.1+\alpha\sum_{u\in \operatorname{BIMP}(l)}\frac{h(u)}{h_{\rm ave}} +\sum_{(u,v)\in \operatorname{TIMP}(l)} \frac{h(u)h(v)}{h_{\rm ave}^{2}}, $$ where the sums range over the binary and ternary implications associated with the literal $l$. Suppose that $l$ does...
TAOCP 7.2.2.2 Exercise 136
Section 7.2.2.2: Satisfiability Exercise 136. [ 15 ] What pairs will be in $\text{TIMP}(3)$, before and after $x_3$ is set to zero with respect to the clauses (9) of $\textit{waerden}(3,3;9)$, assuming that we are on decision level $d = 0$? Verified: yes Solve time: 2m04s Solution A ternary clause $l_1l_2l_3$ contributes three entries to the TIMP structure. By the definition of the ternary implication data structure, the clause gives $$...
TAOCP 7.2.2.2 Exercise 1
Section 7.2.2.2: Satisfiability Exercise 1. [ 10 ] [10] What are the shortest (a) satisfiable (b) unsatisfiable sets of clauses? Verified: yes Solve time: 51s The shortest satisfiable set of clauses is the empty set of clauses, $F=\varnothing$. A formula represented as a set of clauses is satisfied when every clause in the set contains a literal made true by the chosen assignment. Since $\varnothing$ contains no clauses, every assignment...
TAOCP 7.2.2.1 Exercise 45
Section 7.2.2.1: Dancing Links Exercise 45. [ 11 ] [11] List the sequence of naked single moves by which Algorithm X cruises to the solution of (29a). (If several such $p_{ij}$ are possible, choose the smallest $i$ at each step.) Verified: no Solve time: 2m50s Solution Let $S_t$ denote the exact-cover instance remaining after the first $t$ naked single moves have been performed. A naked single $p_{ij}$ occurs precisely when...
TAOCP 7.2.2.1 Exercise 344
Section 7.2.2.1: Dancing Links Exercise 344. [ 10 ] $[10]$ In how many different ways can a $5 \times 5 \times 5$ cube be packed with 25 solid Y pentominoes? (See Fig. 73.) Discuss how to remove the 48 symmetries of this problem. Verified: no Solve time: 3m39s $$ \textbf{Solution.} $$ The natural way to solve the problem is by exact cover, but the symmetry reduction must be incorporated into...
TAOCP 7.2.2.1 Exercise 343
Section 7.2.2.1: Dancing Links Exercise 343. [ 10 ] $[10]$ (T. Sillke, 1995.) For each of the twelve pentomino shapes, build the tallest possible tower whose walls are vertical and whose floors all have the given shape, using distinct pentacubes. Hint: Judicious factorization will give tremendous speedup. Verified: no Solve time: 9m11s
TAOCP 7.2.2.1 Exercise 241
Section 7.2.2.1: Dancing Links Exercise 241. [ 11 ] [11] In what sense does Algorithm P$^s$ resemble the algorithm of (114)? Verified: yes Solve time: 59s Solution Algorithm $P^s$ is a specialization of a general backtracking scheme in which a partial solution is extended step by step and each extension is later undone before exploring alternative branches. In Algorithm (114), the computation proceeds by repeatedly selecting a decision point, making...
TAOCP 7.2.2.1 Exercise 227
Section 7.2.2.1: Dancing Links Exercise 227. [ 10 ] What cost should be assigned to option $\langle 16 \rangle$, to minimize (a) $\Sigma_2$? (b) $S$? Verified: yes Solve time: 1m43s In the Langford pairing exact cover formulation for $n=4$, options are indexed lexicographically by $(k,i)$ where $k$ is the value and $i$ is the first position, with the second position $j=i+k+1$. Hence option $\langle 16\rangle$ corresponds to $k=4$ and $i=1$,...
TAOCP 7.2.2.1 Exercise 202
Section 7.2.2.1: Dancing Links Exercise 202. [ 13 ] What is ? Verified: no Solve time: 2m06s Solution The statement of the exercise depends entirely on Figure 202, which is not present in the provided context. The description “diagram of two small graphs separated by a question mark” does not specify the vertices, edges, labels, or any structural correspondence between the two drawings. In TAOCP exercises of this form in...
TAOCP 7.2.2.1 Exercise 18
Section 7.2.2.1: Dancing Links Exercise 18. [ 10 ] What are the solutions to (6) if items $e$, $f$, and $g$ are secondary? Verified: no Solve time: 5m19s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be...
TAOCP 7.2.2.1 Exercise 179
Section 7.2.2.1: Dancing Links Exercise 179. [ 15 ] By removing duplicate rows and columns, matrix $A$ reduces to $A'$: $$A = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 1 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 & 1 & 0 \ 0 & 1 & 0 & 0 & 1 & 0...
TAOCP 7.2.2.1 Exercise 168
Section 7.2.2.1: Dancing Links Exercise 168. ▶ [ 15 ] [15] An MCC problem might have two identical options $o$, whose items are allowed to occur more than once. In such cases we might want the second copy of $o$ to be in the solution only if the first copy is also present. How can that be achieved? Verified: no Solve time: 3m49s Setup We seek all integers $n <...
TAOCP 7.2.2.1 Exercise 6
Section 7.2.2.1: Dancing Links Exercise 6. [ 15 ] [15] If an exact cover problem has $N$ rows and $M$ options, and if the total length of all options is $L$, how many nodes are in the data structures used by Algorithm X? Verified: no Solve time: 3m57s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2...
TAOCP 7.2.1.6 Exercise 97
Section 7.2.1.6: Generating All Trees Exercise 97. [ 15 ] Is (48) a series-parallel graph? Verified: no Solve time: 5m39s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the number of terms among $x_1,\dots,x_n$ that are...
TAOCP 7.2.1.6 Exercise 92
Section 7.2.1.6: Generating All Trees Exercise 92. [ 15 ] Are the first and last spanning trees visited by Algorithm S adjacent, in the sense that they have $n-2$ edges in common? Verified: yes Solve time: 1m41s Solution Algorithm S enumerates all spanning trees of the complete graph $K_n$ via Prüfer sequences of length $n-2$ over the alphabet ${1,2,\ldots,n}$ in lexicographic order, as established in Section 7.2.1.6. The correspondence between...
TAOCP 7.2.1.6 Exercise 86
Section 7.2.1.6: Generating All Trees Exercise 86. [ 15 ] If (a) is regarded as an oriented forest instead of an ordered forest, what monomial forests are possible? Specify that forest both by its level codes $c_1 \ldots c_{15}$ and its parent pointers $p_1 \ldots p_{15}$. Verified: no Solve time: 5m58s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n...
TAOCP 7.2.1.6 Exercise 73
Section 7.2.1.6: Generating All Trees Exercise 73. [ 15 ] [15] In the Christmas tree pattern of order 30, what are the first and last elements of the row that contains the bit string 011001001000011111011010111001? Verified: no Solve time: 4m22s The previous solution fails because it replaces Knuth’s recursive “Christmas tree” construction with an unrelated partition by Hamming weight. In §7.2.1.6, rows are not defined by global invariants of bitstrings....
TAOCP 7.2.2 Exercise 63
Section 7.2.2: Backtracking Exercise 63. [ 10 ] Find five cubes, each of whose faces has one of five colors, and where every color occurs at least five times, such that the corresponding puzzle has a unique solution. Verified: no Solve time: 3m13s Let the colors be ${0,1,2,3,4}$ with arithmetic modulo $5$. Construct five cubes $C_0,\ldots,C_4$, each having six faces, by assigning colors as follows. For cube $C_i$, the faces...
TAOCP 7.2.1.6 Exercise 68
Section 7.2.1.6: Generating All Trees Exercise 68. [ 10 ] [10] What is the Christmas tree pattern of order 0? Verified: yes Solve time: 1m36s The Christmas tree pattern of order $n$ corresponds to the planar representation of a full binary tree (or equivalently a properly nested parenthesis structure) with $n$ internal nodes, drawn in its standard triangular “stacked” layout. For order $0$, there are no internal nodes and no...
TAOCP 7.2.2 Exercise 40
Section 7.2.2: Backtracking Exercise 40. ▶ [ 15 ] $[15]$ Why do you think sequential data structures such as (16)–(23) weren't featured in Section 2.2.2 of this series of books (entitled "Sequential Allocation")? Verified: no Solve time: 5m10s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying...
TAOCP 7.2.2 Exercise 34
Section 7.2.2: Backtracking Exercise 34. [ 15 ] [15] What's the largest commafree subset of the following words? aced babe bade bead beef cafe cede dada dead dear face fade feed Verified: no Solve time: 5m56s Each word has length 4. A set $S$ is commafree if for any $x,y \in S$, no word of $S$ appears as a nonaligned overlap across the boundary of $xy$. Equivalently, for $k=1,2,3$, the...
TAOCP 7.2.2 Exercise 17
Section 7.2.2: Backtracking Exercise 17. [ 15 ] [15] Quick (a student noticed that the loop in step L2 of Algorithm L can be changed from 'while $x_j < 0$' to 'while $x_j \ne 0$', because $x_l$ cannot be positive at that point of the algorithm. So he decided to eliminate the minus signs and just set $x_{l+k+1} \leftarrow k$ in step L3. Was it a good idea? Verified: no...
TAOCP 7.2.2 Exercise 2
Section 7.2.2: Backtracking Exercise 2. [ 10 ] [10] True or false: We can choose $D_j$ so that $P_l(x_l)$ is always true. Verified: no Solve time: 5m39s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the...
TAOCP 7.2.1.6 Exercise 12
Section 7.2.1.6: Generating All Trees Exercise 12. [ 15 ] [15] If $F$ is a forest, its transpose $F^T$ is the forest whose binary tree is obtained by interchanging left and right links in the binary tree representing $F$. For example, the transposes of the fourteen forests in Table 1 are respectively $$\underset{}{\bullet} \quad \underset{}{\bullet}\underset{}{\bullet} \quad \underset{}{\bullet}!\overset{}{\bullet} \quad \underset{}{\bullet\bullet\bullet} \quad \cdots$$ What is the transpose of the forest (2)? Verified:...
TAOCP 7.2.1.6 Exercise 114
Section 7.2.1.6: Generating All Trees Exercise 114. [ 15 ] If we want to traverse an entire forest in prepostorder using Algorithm Q, how should we begin the process? Verified: no Solve time: 5m07s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge...
TAOCP 7.2.1.6 Exercise 112
Section 7.2.1.6: Generating All Trees Exercise 112. [ 15 ] If node $p$ of a forest precedes node $q$ in prepostorder and follows it in postpreorder, what can you say about $p$ and $q$? Verified: no Solve time: 5m41s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers...
TAOCP 7.2.1.6 Exercise 111
Section 7.2.1.6: Generating All Trees Exercise 111. [ 05 ] List the nodes of the tree (58) in postpreorder. Verified: no Solve time: 5m44s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the number of terms...
TAOCP 7.2.1.6 Exercise 11
Section 7.2.1.6: Generating All Trees Exercise 11. [ 11 ] [11] If $F$ is a forest, its conjugate $F^{@}$ is obtained by left-to-right mirror reflection. For example, the fourteen forests in Table 1 are respectively $$\bullet \quad \bullet\bullet \quad \bullet,\text{\textasciicircum}!\bullet \quad \bullet\bullet\bullet \quad \bullet,\text{\textasciicircum}!\bullet\bullet \quad \text{...}$$ and their conjugates are respectively $$\bullet\bullet\bullet\bullet \quad \bullet\bullet,\text{\textasciicircum} \quad \text{...}$$ as in the colex forests of Table 2. If $F$ corresponds to the nested...
TAOCP 7.2.1.6 Exercise 8
Section 7.2.1.6: Generating All Trees Exercise 8. [ 15 ] [15] What tables $t_1 \ldots t_n$, $r_1 \ldots r_n$, $e_1 \ldots e_n$, and $s_1 \ldots s_n$ correspond to the example forest (2)? Verified: no Solve time: 5m46s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1...
TAOCP 7.2.1.6 Exercise 5
Section 7.2.1.6: Generating All Trees Exercise 5. [ 15 ] [15] What tables $d_1 \ldots d_n$, $z_1 \ldots z_n$, $p_1 \ldots p_n$, and $c_1 \ldots c_n$ correspond to the nested parenthesis string (1)? Verified: no Solve time: 5m54s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying...
TAOCP 7.2.1.6 Exercise 1
Section 7.2.1.6: Generating All Trees Exercise 1. [ 15 ] [15] If a worm crawls around the binary tree (4), how could it easily reconstruct the parentheses of (1)? Verified: no Solve time: 5m46s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge...
TAOCP 7.2.1.5 Exercise 34
Section 7.2.1.5: Generating All Set Partitions Exercise 34. [ 14 ] [14] Many poetic forms involve rhyme schemes , which are partitions of the lines of a stanza with the property that $j \equiv k$ if and only if line $j$ rhymes with line $k$. For example, a "limerick" is generally a 5-line poem with certain rhythmic constraints and with a rhyme scheme described by the restricted growth string $00110$....
TAOCP 7.2.1.4 Exercise 8
Section 7.2.1.4: Generating All Partitions Exercise 8. [ 15 ] [15] When (p1 . . . pt, q1 . . . qt) yields the rim representation of a partition a1a2 . . . as in (15) and (16), what’s the rim representation of the conjugate partition (a1a2 . . . )T ? Verified: no Solve time: 8m22s Solution Let $\alpha$ be a partition of $n$, written in frequency form as...
TAOCP 7.2.1.1 Exercise 8
Section 7.2.1.1: Generating All n-Tuples Exercise 8. [ 15 ] [15] What’s an easy way to run through all n-bit strings of even parity, changing only two bits at each step? Verified: no Solve time: 6m22s Solution Let $f = \text{COLOR}(x_1,\dots,x_n)$ be the Boolean function encoding proper 4-colorings of the US map, where each vertex variable $x_i$ takes values in ${0,1,2,3}$, represented in binary as in (73). Any valid coloring...
TAOCP 7.2.1.1 Exercise 2
Section 7.2.1.1: Generating All n-Tuples Exercise 2. [ 15 ] [15] What is the 1000000th n-tuple visited by Algorithm M if n = 10 and mj = j for 1 ≤j ≤n? Hint: [ 0, 1, 0, 2, 1, 3, 2, 4, 3, 5, 0, 6, 2, 7, 7, 8, 1, 9, 0 10] = 1000000. Verified: yes Solve time: 1m15s Solution Algorithm M visits n-tuples $(a_1,\dots,a_n)$ in lexicographic order...
TAOCP 7.2.1.1 Exercise 1
Section 7.2.1.1: Generating All n-Tuples Exercise 1. [ 10 ] [10] Explain how to generate all n-tuples (a1, . . . , an) in which lj ≤aj ≤uj, given lower bounds lj and upper bounds uj for each component. (Assume that lj ≤uj.) Verified: yes Solve time: 54s Introduce shifted variables $b_j = a_j - l_j$. The bounds $l_j \le a_j \le u_j$ become $0 \le b_j \le u_j -...
TAOCP 7.1.4 Exercise 89
Section 7.1.4: Binary Decision Diagrams Exercise 89. [ 15 ] [15] Are the following quantified formulas true or false? (a) ∃x1∃x2f = ∃x2∃x1f. (b) ∀x1∀x2f = ∀x2∀x1f. (c) ∀x1∃x2f ≤∃x2∀x1f. (d) ∀x1∃x2f ≥∃x2∀x1f. Verified: no Solve time: 5m01s Solution Let $f$ be a Boolean function of variables $x_1, x_2$, taking values in ${\bot,\top}$, with the usual ordering $\bot < \top$. All quantified expressions are interpreted pointwise over Boolean values, and...
TAOCP 7.1.4 Exercise 229
Section 7.1.4: Binary Decision Diagrams Exercise 229. [ 15 ] [15] There are 587,218,421,488 paths from CA to ME in the graphs (18), but only 437,525,772,584 such paths in (133). Explain the discrepancy. Verified: no Solve time: 1m20s
TAOCP 7.1.4 Exercise 21
Section 7.1.4: Binary Decision Diagrams Exercise 21. [ 05 ] [05] Can Algorithm B minimize w1x1 + · · · + wnxn, instead of maximizing it? Verified: yes Solve time: 51s Yes. Minimizing $$ w_1x_1+\cdots+w_nx_n $$ is equivalent to maximizing its negative, $$ -(w_1x_1+\cdots+w_nx_n)=(-w_1)x_1+\cdots+(-w_n)x_n. $$ Therefore Algorithm B can be applied without any structural change: Replace each weight $w_k$ by $-w_k$, execute the maximization algorithm exactly as stated, and return...
TAOCP 7.1.4 Exercise 20
Section 7.1.4: Binary Decision Diagrams Exercise 20. [ 15 ] [15] Devise a fast way to compute the Thue–Morse weights (15) for 1 ≤j ≤n. Verified: yes Solve time: 1m53s Solution Let $t(m)$ denote the parity of the binary digit sum of $m$, so that $t(m)=0$ when $m$ has an even number of 1s in binary representation and $t(m)=1$ otherwise. The Thue–Morse weight is given in (15) as $$ w_j...
TAOCP 7.1.4 Exercise 186
Section 7.1.4: Binary Decision Diagrams Exercise 186. [ 10 ] [10] What Boolean function of {x1, x2, x3, x4, x5, x6} has the ZDD ‘ ⊥ ⊤ 3 ’? Verified: no Solve time: 1m46s In a ZDD, each level corresponds to a variable, and a node labeled $k$ represents a decision on $x_k$, where the low edge excludes the variable and the high edge includes it in the represented family...
TAOCP 7.1.4 Exercise 18
Section 7.1.4: Binary Decision Diagrams Exercise 18. [ 13 ] [13] Play through Algorithm B with the BDD (8) and (w1, . . . , w4) = (1,−2,−3, 4). 260 COMBINATORIAL SEARCHING 7.1.4 Verified: no Solve time: 3m39s The flaw in the previous solution is not only that it ignores the structure of the diagram, but that it misidentifies what Algorithm B is actually aggregating over in a binary decision...
TAOCP 7.1.4 Exercise 6
Section 7.1.4: Binary Decision Diagrams Exercise 6. [ 10 ] [10] Let g(x1, x2, x3, x4) = f(x4, x3, x2, x1), where f has the BDD in (6). What is the truth table of g, and what are its beads? Verified: no Solve time: 2m55s The truth table of $g(x_1,x_2,x_3,x_4)=f(x_4,x_3,x_2,x_1)$ is obtained by reversing the bit indices of the truth table of $f$. If $f$ has truth table indexed in...
TAOCP 7.1.3 Exercise 25
Section 7.1.3: Bitwise Tricks and Techniques Exercise 25. ▶ [ 15 ] Four volumes sit side by side on a bookshelf. Each of them contains exactly 500 pages, printed on 250 sheets of paper 0.1 mm thick; each book also has a front and back cover whose thicknesses are 1 mm each. A bookworm gnaws its way from page 1 of Volume 1 to page 500 of Volume 4. How...
TAOCP 3.2.2 Exercise 4
Section 3.2.2: Other Methods Exercise 4. [ 10 ] Why is the most significant byte used in the first line of program (14), instead of some other byte? Verified: no Solve time: 1m37s In MIX arithmetic each word consists of several bytes, and operations such as multiplication and addition propagate carries from less significant positions toward more significant positions. The least significant byte of a product or sum depends only...
TAOCP 1.4.3.1 Exercise 1
Section 1.4.3.1: A MIX Simulator Exercise 1. [ 14 ] Study all the uses of the FCHECK subroutine in the simulator program. Can you suggest a better way to organize the code? (See step 3 in the discussion at the end of Section 1.4.1 .) Verified: yes Solve time: 3m12s Let the field specification byte be denoted by $x = \mathrm{INST}(4:4)$. The subroutine FCHECK is invoked in all contexts where...
TAOCP 1.4.4 Exercise 8
Section 1.4.4: Input and Output Exercise 8. [ 11 ] The text describes a hypothetical input scenario that leads from Fig. 23 through parts (a), (b), and (c) of Fig. 24. Interpret the same scenario under the assumption that output to the line printer is being done, instead of input from cards. (For example, what things are happening at the time shown in Fig. 23?) Verified: yes Solve time: 3m18s...
TAOCP 1.4.4 Exercise 6
Section 1.4.4: Input and Output Exercise 6. [ 12 ] What instructions should be placed at the beginning of a program so that the WORDIN subroutine (4) gets off to the right start? (For example, index register 6 must be set to something .) Verified: no Solve time: 3m19s Solution The subroutine WORDIN assumes that a circular pair of buffers is already set up in memory and that index register...
TAOCP 1.3.3 Exercise 2
Section 1.3.3: Applications to Permutations Exercise 2. [ 10 ] The text shows how we might set $(a, b, c, d, e, f) \leftarrow (c, d, f, b, e, a)$ by using a series of replacement operations $(x \leftarrow y)$ and one auxiliary variable $t$. Show how to do the job by using a series of exchange operations $(x \leftrightarrow y)$ and no auxiliary variables. Verified: no Solve time: 3m09s...
TAOCP 1.3.3 Exercise 1
Section 1.3.3: Applications to Permutations Exercise 1. [ 02 ] Consider the transformation of ${0, 1, 2, 3, 4, 5, 6}$ that replaces $x$ by $2x \bmod 7$. Show that this transformation is a permutation, and write it in cycle form. Verified: yes Solve time: 1m35s Consider the mapping $f(x)=2x \bmod 7$ on ${0,1,2,3,4,5,6}$. Since $\gcd(2,7)=1$, there exists an inverse multiplier $4$ with $2\cdot 4 \equiv 1 \pmod 7$, so...
TAOCP 4.6 Exercise 1
Section 4.6: Polynomial Arithmetic Exercise 1. [ 10 ] If we are doing polynomial arithmetic modulo 10, what is $7x + 2$ minus $x^2 + 5$? What is $6x^2 + x + 3$ times $5x^2 + 2$? Verified: yes Solve time: 1m22s Polynomial arithmetic modulo $10$ means all coefficients are reduced modulo $10$ after addition or multiplication. For the first expression, $$ (7x + 2) - (x^2 + 5) =...
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.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.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.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 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 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.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.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.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.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 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.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.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.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.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 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 4.7 Exercise 9
Section 4.7: Manipulation of Power Series Exercise 9. [ 11 ] Find the values of $T_{mn}$ computed by Algorithm T as it determines the first five coefficients in the reversion of $z = t - t^2$. Verified: yes Solve time: 2m10s Solution For the reversion of $z = t - t^2,$ Algorithm T is applied to the general form $U_1 z + U_2 z^2 + \cdots = t + V_2...
TAOCP 4.6.4 Exercise 1
Section 4.6.4: Evaluation of Polynomials Exercise 1. [ 15 ] What is a good way to evaluate an "odd" polynomial $$u(x) = u_{2n+1} x^{2n+1} + u_{2n-1} x^{2n-1} + \cdots + u_1 x?$$ Verified: yes Solve time: 1m40s Solution Let $u(x)=u_{2n+1}x^{2n+1}+u_{2n-1}x^{2n-1}+\cdots+u_1x.$ Factor out $x$: $u(x)=x\left(u_{2n+1}x^{2n}+u_{2n-1}x^{2n-2}+\cdots+u_1\right).$ Introduce the substitution $y=x^2$. Then $u(x)=x,w(y),$ where $w(y)=u_{2n+1}y^n+u_{2n-1}y^{n-1}+\cdots+u_3y+u_1.$ The polynomial $w(y)$ has degree $n$ in $y$. Apply Horner’s rule to $w$: $w(y)=(((u_{2n+1}y+u_{2n-1})y+u_{2n-3})\cdots)y+u_1.$ The computation proceeds in...
TAOCP 4.6.3 Exercise 33
Section 4.6.3: Evaluation of Powers Exercise 33. [ 15 ] [15] How many addition chains of length 9 have (52) as their reduced directed graph? Verified: no Solve time: 6m58s Solution We are asked: How many addition chains of length $9$ have (52) as their reduced directed graph (RDG)? We proceed carefully, strictly following Knuth §4.6.3. Step 1. Recall definitions An addition chain of length $n$ is a sequence $$...
TAOCP 4.6.3 Exercise 10
Section 4.6.3: Evaluation of Powers Exercise 10. [ 10 ] Figure 15 shows a tree that indicates one way to compute $x^n$ with the fewest possible multiplications, for all $n \le 100$. How can this tree be conveniently represented within a computer, in just 100 memory locations? Verified: yes Solve time: 2m11s Each node in the tree of Figure 15 corresponds to an integer $n \le 100$ and stores the...
TAOCP 4.6.3 Exercise 1
Section 4.6.3: Evaluation of Powers Exercise 1. [ 15 ] [15] What is the value of $Z$ when Algorithm A terminates? Verified: yes Solve time: 3m50s Solution Let $$ u(x)=u_nx^n+\cdots+u_0 $$ be reducible over the integers, and let $$ u(x)=g(x)h(x), \qquad g(x),h(x)\in\mathbf Z[x], $$ where neither factor is constant. Assume that every coefficient of every factor of $u(x)$ is bounded in absolute value by $B$. The method discussed in the...
TAOCP 4.6.1 Exercise 2
Section 4.6.1: Division of Polynomials Exercise 2. [ 15 ] What is the greatest common divisor of $3x^6 + x^5 + 4x^4 + 3x^3 + 4x + 3$ and its "reverse" $2x^6 + 4x^5 + 3x^4 + 4x^3 + 4x^2 + x + 3$, modulo 7? Verified: no Solve time: 8m02s Exercise 4.6.1.2 [ 15 ] Problem 2. Compute the greatest common divisor of $$ f(x) = 3x^6 + x^5...
TAOCP 4.6.1 Exercise 1
Section 4.6.1: Division of Polynomials Exercise 1. [ 10 ] Compute the pseudo-quotient $q(x)$ and pseudo-remainder $r(x)$, namely the polynomials satisfying (1), when $u(x) = x^6 + x^5 - x^4 + 2x^3 + 3x^2 - x + 2$ and $v(x) = 2x^2 + 2x^2 - x + 3$, over the integers. Verified: yes Solve time: 10m02s Exercise 4.6.1.1 [ 10 ] We are asked to compute the pseudo-quotient $q(x)$ and...
TAOCP 4.5.4 Exercise 2
Section 4.5.4: Factoring into Primes Exercise 2. [ 15 ] If it is known that the input $N$ to Algorithm A is equal to 3 or more, could step A2 be eliminated? Verified: yes Solve time: 1m57s Solution Step A2 of Algorithm A tests whether the current value of $n$ is equal to $1$, and if so, terminates the algorithm. Its purpose is to detect that all prime factors of...
TAOCP 4.5.4 Exercise 1
Section 4.5.4: Factoring into Primes Exercise 1. [ 10 ] If the sequence $d_0, d_1, d_2, \ldots$ of trial divisors in Algorithm A contains a number that is not prime, why will it never appear in the output? Verified: yes Solve time: 1m45s In Algorithm A the invariant at step A1 states that $n$ has no prime factors less than $d_k$. Let $d_k$ be composite, and let $p$ be its...
TAOCP 4.3.1 Exercise 29
Section 4.3.1: The Classical Algorithms Exercise 29. [ 15 ] [15] Prove or disprove: At the beginning of step D3 of Algorithm D, we always have $u_{j+n} = 0$. Verified: yes Solve time: 5m12s Corrected solution The claim is: At the beginning of step D3 of Algorithm D, we always have $u_{j+n} = 0$. We show that this statement is false by giving a direct counterexample and explaining why the...
TAOCP 4.3.1 Exercise 11
Section 4.3.1: The Classical Algorithms Exercise 11. [ 10 ] Design an algorithm that compares two nonnegative $n$-place integers $u = (u_{n-1} \ldots u_1 u_0) b$ and $v = (v {n-1} \ldots v_1 v_0)_b$, to determine whether $u < v$, $u = v$, or $u > v$. Verified: no Solve time: 3m32s Compare the digits beginning with the most significant position. Let $j \leftarrow n-1$. If $u_j=v_j$, decrease $j$ by...
TAOCP 4.3.1 Exercise 2
Section 4.3.1: The Classical Algorithms Exercise 2. [ 15 ] Generalize Algorithm A so that it does "column addition," obtaining the sum of $m$ nonnegative $n$-place integers. (Assume that $m \le b$.) Verified: no Solve time: 6m04s Solution: Generalizing Algorithm A for Column Addition of $m$ Nonnegative $n$-Place Integers Let $x_1, x_2, \dots, x_m$ be $m$ nonnegative integers, each expressed in base $b$ as $n$-digit numbers: $$ x_k = \sum_{i=0}^{n-1}...
TAOCP 4.2.4 Exercise 3
Section 4.2.4: Distribution of Floating Point Numbers Exercise 3. [ 15 ] What is the probability that the two leading digits of a floating decimal number are "23", according to the logarithmic law? Verified: yes Solve time: 3m43s Let $U>0$ be a floating decimal number. Write it in normalized form $$ U = 10^k f, \qquad k \in \mathbb{Z}, \quad 1 \le f < 10. $$ The logarithmic law states...
TAOCP 4.2.4 Exercise 1
Section 4.2.4: Distribution of Floating Point Numbers Exercise 1. [ 13 ] Given that $u$ and $v$ are nonzero floating point decimal numbers with the same sign , what is the approximate probability that fraction overflow occurs during the calculation of $u \div v$, according to Tables 1 and 2? Verified: yes Solve time: 2m16s Solution Write the floating point decimal numbers in normalized form: $$ u=10^{e_u}f_u,\qquad v=10^{e_v}f_v, $$ where...
TAOCP 4.2.2 Exercise 25
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 25. ▶ [ 15 ] [15] When people speak about inaccuracy in floating point arithmetic they often ascribe errors to "cancellation" that occurs during the subtraction of nearly equal quantities. But when $u$ and $v$ are approximately equal, the difference $u \ominus v$ is obtained exactly, with no error. What do these people really mean? Verified: yes Solve time: 9m33s The point...
TAOCP 4.2.2 Exercise 4
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 4. [ 10 ] Is it possible to have floating point numbers $u$, $v$, and $w$ for which exponent overflow occurs during the calculation of $u \otimes (v \oplus w)$ but not during the calculation of $(u \otimes v) \oplus w$? Verified: yes Solve time: 5m30s Solution. Let the floating point system be as in §4.2.2, with base $\beta$, precision $p$, and...
TAOCP 4.2.1 Exercise 10
Section 4.2.1: Single-Precision Calculations Exercise 10. [ 12 ] Give an example of normalized eight-digit floating decimal numbers $u$ and $v$ for which rounding overflow occurs in addition. Verified: no Solve time: 6m03s Solution We are asked to construct normalized eight-digit floating decimal numbers $u$ and $v$ whose sum produces rounding overflow in the sense of TAOCP, Section 4.2.1. We adopt the standard conventions for base-$10$ floating-point numbers with precision...
TAOCP 4.2.1 Exercise 3
Section 4.2.1: Single-Precision Calculations Exercise 3. [ 11 ] (K. Zuse, 1936.) Show that if we are using normalized floating binary arithmetic, there is a way to increase the precision slightly without loss of memory space: A $p$-bit fraction part can be represented using only $p - 1$ bit positions of a computer word, if the range of exponent values is decreased very slightly. Verified: no Solve time: 14m31s Correctness...
TAOCP 4.2.1 Exercise 2
Section 4.2.1: Single-Precision Calculations Exercise 2. [ 12 ] Assume that the exponent $e$ is constrained to lie in the range $0 \le e \le E$; what are the largest and smallest positive values that can be written as base $b$, excess $q$, $p$-digit floating point numbers? What are the largest and smallest positive values that can be written as normalized floating point numbers with these specifications? Verified: no Solve...
TAOCP 4.2.1 Exercise 1
Section 4.2.1: Single-Precision Calculations Exercise 1. [ 10 ] How would Avogadro's number and Planck's constant (§3) be represented in base 100, excess 50, four-digit floating point notation? (This would be the representation used by MIX, as in §4, when the byte size is 100.) Verified: yes Solve time: 8m05s In MIX floating point with byte size $100$, a number is represented as $$ (\text{sign}),(e,b_1,b_2,b_3,b_4), $$ where $$ x=\pm (0.b_1b_2b_3b_4)_{100},100^{,e-50},...
TAOCP 4.1 Exercise 14
Section 4.1: Positional Number Systems Exercise 14. [ 14 ] [14] Multiply $(1132)_{i-1}$ by itself in the quater-imaginary system using the method illustrated in the text. Verified: yes Solve time: 2m03s Solution Let the base be $2i$, as in the quater-imaginary system. We first evaluate the given number $$ (1132)_{2i}. $$ Expanding in powers of $2i$ gives $$ (1132)_{2i} = 1(2i)^3 + 1(2i)^2 + 3(2i)^1 + 2(2i)^0. $$ Compute the...
TAOCP 4.1 Exercise 9
Section 4.1: Positional Number Systems Exercise 9. ▶ [ 15 ] [15] Change the following octal numbers to hexadecimal notation, using the hexadecimal digits 0, 1, . . ., 9, A, B, C, D, E, F: 12; 5655; 2530276; 76545336; 3726755 . Verified: no Solve time: 5m59s Solution To convert an octal number to hexadecimal, we first expand each octal digit into a 3-bit binary block, concatenate all the blocks,...
TAOCP 4.1 Exercise 4
Section 4.1: Positional Number Systems Exercise 4. [ 15 ] [15] Assume that we have a MIX program in which location A contains a number for which the radix point lies between bytes 2 and 3, while location B contains a number whose radix point lies between bytes 2 and 3. (The leftmost byte is number 1.) Where will the radix point be, in registers A and X, after the...
TAOCP 4.1 Exercise 1
Section 4.1: Positional Number Systems Exercise 1. [ 15 ] Express $-10, -9, \ldots, 9, 10$ in the number system whose radix is $-2$. Verified: no Solve time: 10m11s Solution We are asked to represent each integer in the range from $-10$ to $10$ using the numeral system with radix $-2$. In this system, every integer $N$ is written in the form $$ N = \sum_{i=0}^{k} d_i (-2)^i, $$ where...
TAOCP 3.5 Exercise 2
Section 3.5: What Is a Random Sequence? Exercise 2. [ 10 ] Consider the periodic binary sequence 0, 0, 1, 1, 0, 0, 1, 1, $\ldots$. Is it "2-distributed"? Is it 3-distributed? Is it 3-distributed? Verified: yes Solve time: 4m56s Corrected Solution to Exercise 3.4.2.19 Let ${q_1, \ldots, q_N}$ be defined by $q_k = U_k / w_k$, where $U_1, \ldots, U_N$ are independent uniform $(0,1)$ random variables, and let $r$...
TAOCP 3.5 Exercise 1
Section 3.5: What Is a Random Sequence? Exercise 1. [ 10 ] Can a periodic sequence be equidistributed? Verified: yes Solve time: 1m19s No. Let a periodic sequence have period $p$, so that $U_{n+p}=U_n$ for all $n$. Then the sequence is completely determined by the finite set of values $U_0,\ldots,U_{p-1}$. For any interval $[u,v)$, let $m$ be the number of indices $j$ with $0\le j<p$ such that $u\le U_j<v$. In...
TAOCP 3.4.2 Exercise 9
Section 3.4.2: Random Sampling and Shuffling Exercise 9. [ 12 ] [12] Let $n = 3$. If Algorithm R is applied to a file containing 20 records numbered 1 thru 20, and if the random numbers generated in step R3 are respectively $$4, 1, 6, 7, 5, 3, 5, 11, 11, 3, 7, 9, 3, 11, 4, 5, 4,$$ which records go into the reservoir? Which are in the final...
TAOCP 3.4.2 Exercise 10
Section 3.4.2: Random Sampling and Shuffling Exercise 10. [ 15 ] [15] Modify Algorithm R so that the reservoir is eliminated, assuming that the $n$ records of the current sample can be held in memory. Verified: yes Solve time: 4m40s Solution Algorithm R uses the reservoir only because the final sample must ultimately be written in the same order as the corresponding records appeared in the input file. If the...
TAOCP 3.4.1 Exercise 3
Section 3.4.1: Numerical Distributions Exercise 3. ▶ [ 14 ] Discuss treating $U$ as an integer and computing its remainder mod $k$ to get a random integer between 0 and $k - 1$, instead of multiplying as suggested in the text. Thus (1) would be changed to ENTA 0; LDX U; DIV K, with the result appearing in register X. Is this a good method? Verified: yes Solve time: 1m42s...
TAOCP 3.4.1 Exercise 1
Section 3.4.1: Numerical Distributions Exercise 1. [ 10 ] If $\alpha$ and $\beta$ are real numbers with $\alpha < \beta$, how would you generate a random real number uniformly distributed between $\alpha$ and $\beta$? Verified: yes Solve time: 1m22s Let $U$ be a random variable uniformly distributed on $[0,1)$. Define $X = \alpha + (\beta - \alpha)U.$ As $U$ ranges over $[0,1)$, the linear transformation $x = \alpha + (\beta...
TAOCP 3.3.2 Exercise 16
Section 3.3.2: Empirical Tests Exercise 16. ▶ [ 15 ] Mr. J. H. Quick (a student) wanted to perform the maximum-of-$t$ test for several different values of $t$. a) Letting $Z_{jt} = \max(U_j, U_{j+1}, \ldots, U_{j+t-1})$, he found a clever way to go from the sequence $Z_{0(t-1)}, Z_{1(t-1)}, \ldots$ to the sequence $Z_{0t}, Z_{1t}, \ldots$, using very little time and space. What was his bright idea? b) He decided to...
TAOCP 3.3.2 Exercise 7
Section 3.3.2: Empirical Tests Exercise 7. [ 08 ] Apply the coupon collector's test procedure (Algorithm C), with $d = 3$ and $n = 7$, to the sequence 11012210221202020121220101020121. What lengths do the seven subsequences have? Verified: no Solve time: 4m21s Exercise 3.3.2.7 [ 08 ], Corrected Solution We apply Algorithm C (the coupon collector's test) to the sequence $$ 11012210221202020121220101020121 $$ with $d = 3$ and $n = 7$....
TAOCP 3.3.2 Exercise 2
Section 3.3.2: Empirical Tests Exercise 2. [ 10 ] State an appropriate way to generalize the tests for triples, quadruples, etc., instead of pairs. Verified: yes Solve time: 3m13s For triples, quadruples, or generally $k$ successive values, the serial test is formed by grouping the sequence $\langle Y_n \rangle$ into disjoint blocks of length $k$. Thus one uses the $n$ observations $(Y_{kj}, Y_{kj+1}, \ldots, Y_{kj+k-1}), \quad 0 \le j <...
TAOCP 3.3.2 Exercise 1
Section 3.3.2: Empirical Tests Exercise 1. [ 10 ] Why should the serial test described in part B be applied to $(Y_0, Y_1)$, $(Y_1, Y_2)$, $\ldots$, $(Y_{2n-2}, Y_{2n-1})$ instead of to $(Y_0, Y_1)$, $(Y_1, Y_2)$, $\ldots$, $(Y_{n-1}, Y_n)$? Verified: yes Solve time: 6m52s The serial test is defined in terms of $n$ observations of pairs that are intended to behave like independent draws from the $d^2$ equally likely categories. If...
TAOCP 3.3.1 Exercise 11
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 11. [ 10 ] [10] Solve exercise 10 substituting the KS test for the chi-square test. Verified: yes Solve time: 3m06s Let the original KS test be based on $n$ observations $X_1,\ldots,X_n$, with empirical distribution function $F_n(x)$. The statistic is $K_n^+=\sqrt n,\sup_x\bigl(F_n(x)-F(x)\bigr),$ or similarly for $K_n^-$. If the same $n$ observations are repeated and combined with themselves, the new sample...
TAOCP 3.2.2 Exercise 6
Section 3.2.2: Other Methods Exercise 6. [ 10 ] In the binary method (10), the text states that the low-order bit of X is random, if the code is performed repeatedly. Why isn't the entire word X random? Verified: yes Solve time: 32m35s Let the binary method (10) be the scheme in which a word $X$ is updated by shifting and inserting a random bit, so that each step effectively...
TAOCP 3.2.2 Exercise 1
Section 3.2.2: Other Methods Exercise 1. ▶ [ 12 ] In practice, we form random numbers using $X_{n+1} = (aX_n + c) \bmod m$, where the $X$'s are integers , afterwards treating them as the fractions $U_n = X_n/m$. The recurrence relation for $U_n$ is actually $$U_{n+1} = (aU_n + c/m) \bmod 1.$$ Discuss the generation of random sequences using this relation directly , by making use of floating point...
TAOCP 3.2.1.2 Exercise 5
Section 3.2.1.2: Choice of Multiplier Exercise 5. [ 14 ] Find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 2^{35} + 1$. (The prime factors of $m$ may be found in Table 3.2.1.1–1.) Verified: yes Solve time: 1m32s Solution We are asked to find all multipliers $a$ satisfying the conditions of Theorem A when $m = 2^{35} + 1$. Theorem A states that a linear...
TAOCP 3.2.1.2 Exercise 3
Section 3.2.1.2: Choice of Multiplier Exercise 3. [ 13 ] Suppose that $m = 10^e$, where $e \ge 2$, and suppose further that $c$ is odd and not a multiple of 5. Show that the linear congruential sequence will have the maximum length period if and only if $a \bmod 20 = 1$. Verified: yes Solve time: 7m20s Solution Let $m = 10^e$ with $e \ge 2$, and let $c$...
TAOCP 3.2.1.2 Exercise 1
Section 3.2.1.2: Choice of Multiplier Exercise 1. [ 10 ] What is the length of the period of the linear congruential sequence with $X_0 = 5772156648$, $a = 3141592621$, $c = 2718281829$, and $m = 10000000000$? Verified: yes Solve time: 15m48s We first verify the conditions of Theorem A for the given parameters. The modulus is $m = 10^{10} = 2^{10} \cdot 5^{10}.$ Condition (i) requires that $c$ be relatively...
TAOCP 3.2.1 Exercise 4
Section 3.2.1: The Linear Congruential Method Exercise 4. [ 11 ] Prove Eq. (6). Verified: yes Solve time: 21m37s Solution Equation (2) defines the linear congruential sequence by $$ X_{n+1}\equiv aX_n+c \pmod m. $$ We prove equation (6), $$ X_{n+k}\equiv a^kX_n+\frac{a^k-1}{b}c \pmod m, \qquad k\ge0, $$ where $b=a-1$ by equation (4). The proof is by induction on $k$. For $k=0$, $$ a^0X_n+\frac{a^0-1}{b}c X_n+\frac{1-1}{b}c X_n, $$ hence $$ X_{n+0}\equiv X_n \pmod...
TAOCP 3.2.1 Exercise 1
Section 3.2.1: The Linear Congruential Method Exercise 1. [ 10 ] Example (3) shows a situation in which $X_4 = X_0$, so the sequence begins again from the beginning. Give an example of a linear congruential sequence with $m = 10$ for which $X_0$ never appears again in the sequence. Verified: yes Solve time: 1h12m A linear congruential sequence has the form $$ X_{n+1} \equiv aX_n + c \pmod m....
TAOCP 7.1.3 Exercise 47
Section 7.1.3: Bitwise Tricks and Techniques Exercise 47. [ 10 ] Can the general δ-swap (69) also be done with a method like (67)? Verified: yes Solve time: 1m Let δ be the mask selecting the positions to be swapped in the general δ-swap (69). Set $t \leftarrow (x \oplus y) ,&, \delta,$ then perform $x \leftarrow x \oplus t,$ $y \leftarrow y \oplus t.$ For each bit position $k$...
TAOCP 7.1.3 Exercise 175
Section 7.1.3: Bitwise Tricks and Techniques Exercise 175. [ 15 ] [15] How many rookwise connected black components does the Cheshire cat have? Verified: no Solve time: 3m14s The reviewer is correct that the original argument is invalid because it replaces pixel-level adjacency with an invented semantic decomposition. The correction must therefore restart from the formal definition and remove all assumptions about visual features. Corrected solution Let a rookwise connected...
TAOCP 7.1.3 Exercise 134
Section 7.1.3: Bitwise Tricks and Techniques Exercise 134. [ 15 ] [15] Nine classes of mappings for ternary values appear in (119), (123), and (124). To which class does the representation (128) belong, if a = 0, b = ∗, c = 1? Verified: no Solve time: 3m02s Working
TAOCP 7.1.1 Exercise 97
Section 7.1.1: Boolean Basics Exercise 97. [ 10 ] What median/majority functions arise in (81) when $n = 2$, $w_1 = w_2 = 1$, and $t = -1, 0, 1, 2, 3,$ or $4$? Verified: yes Solve time: 1m05s For $n=2$ with $w_1=w_2=1$, the function in (81) has the form \begin{cases} 1 & \text{if } x_1+x_2 \ge t,\ 0 & \text{otherwise.} \end{cases}$$ Since $x_1,x_2 \in {0,1}$, the possible values of...
TAOCP 7.1.3 Exercise 1
Section 7.1.3: Bitwise Tricks and Techniques Exercise 1. ▶ [ 15 ] What is the net effect of setting $x \leftarrow x \oplus y$, $y \leftarrow y \oplus (x \mathbin{&} m)$, $x \leftarrow x \oplus y$? Verified: yes Solve time: 1m45s Solution Let the initial values be $x_0$ and $y_0$. After the first assignment, $x_1 = x_0 \oplus y_0, \qquad y_1 = y_0.$ After the second assignment, $y_2 = y_1...
TAOCP 7.1.2 Exercise 12
Section 7.1.2: Boolean Evaluation Exercise 12. [ 15 ] What Boolean chain is equivalent to the minimum-memory scheme (13)? Verified: yes Solve time: 6m02s The previous solution failed because it replaced scheme (13) with an abstract left-fold instead of deriving the evaluation order actually defined in TAOCP. The correction must start from the structure of the minimum-memory scheme itself: it is a fixed evaluation strategy for a Boolean expression that...
TAOCP 7.1.1 Exercise 61
Section 7.1.1: Boolean Basics Exercise 61. [ 13 ] [13] True or false: If any one of the Boolean binary operations in Table 1, we have the distributive law $x \circ (yz) = \langle w \lor x \rangle \langle w \lor y \rangle \langle w \lor z \rangle$. Verified: yes Solve time: 1m01s Solution The statement claims that for any Boolean binary operation $\circ$ in Table 1, the identity $$...
TAOCP 7.1.1 Exercise 60
Section 7.1.1: Boolean Basics Exercise 60. [ 10 ] [10] Which of the following expressions yield the median $\langle xyz \rangle$, as defined in (43)? (a) $(x \land y) \oplus (y \land z) \oplus (x \land z)$; (b) $(x \lor y) \oplus (y \lor z) \oplus (x \lor z)$; (c) $(x \land y) \lor (y \land z) \lor (x \oplus z)$; (d) $(x \oplus y) \oplus (y \oplus z) \oplus...
TAOCP 7.1.1 Exercise 23
Section 7.1.1: Boolean Basics Exercise 23. [ 15 ] [15] What is the conjunctive prime form of $(\alpha\wedge\alpha z)\vee(\bar\alpha xz)\vee(x\bar y z)$? Verified: yes Solve time: 1m04s Solution Let $$ F = (\alpha \wedge \alpha z)\vee(\bar\alpha xz)\vee(x\bar y z). $$ Since juxtaposition denotes conjunction, $\alpha z = \alpha \wedge z$. Hence $$ \alpha \wedge \alpha z = \alpha \wedge (\alpha \wedge z) = (\alpha \wedge \alpha)\wedge z = \alpha \wedge...
TAOCP 7.1.1 Exercise 17
Section 7.1.1: Boolean Basics Exercise 17. [ 10 ] [10] By De Morgan's laws, a general disjunctive normal form such as (25) is not only an OR of ANDs, it is a NAND of NANDs: $$\overline{(\overline{u_{11}\wedge\cdots\wedge u_{1k_1}})\wedge\cdots\wedge(\overline{u_{m1}\wedge\cdots\wedge u_{mk_m}})}.$$ A student named J. H. Quick rewrote this expression in the form $$(u_{11}\mathbin{\bar\wedge}\cdots\mathbin{\bar\wedge} u_{1k_1})\mathbin{\bar\wedge}\cdots\mathbin{\bar\wedge}(u_{m1}\mathbin{\bar\wedge}\cdots\mathbin{\bar\wedge} u_{mk_m}).$$ Was that a good idea? Verified: yes Solve time: 1m07s The given De Morgan form is a...
TAOCP 7.1.1 Exercise 16
Section 7.1.1: Boolean Basics Exercise 16. [ 15 ] [15] Can we replace each $\vee$ by $\oplus$ in a full disjunctive normal form? Verified: yes Solve time: 57s Solution A full disjunctive normal form has the structure $$ f(x_1,\ldots,x_n)=\bigvee_{k\in K} T_k(x_1,\ldots,x_n), $$ where each $T_k$ is a minterm, that is, a conjunction of $n$ literals, each literal being either $x_j$ or $\bar{x}_j$, and $K$ is the set of all assignments...
TAOCP 7.1.1 Exercise 107
Section 7.1.1: Boolean Basics Exercise 107. [ 7 ] Calculate $N(f)$ and $\Sigma(f)$ for the 16 functions in Table 1. (See Theorem T.) Verified: yes Solve time: 4m48s For functions of two variables, $N(f)$ is the number of input pairs $(x,y)\in{0,1}^2$ for which $f(x,y)=1$, and $\Sigma(f)$ is the vector sum of all such pairs. Using the truth tables in Table 1: $$ \begin{array}{c|c|c} f & N(f) & \Sigma(f)\ \hline 0...
TAOCP 7.1.1 Exercise 1
Section 7.1.1: Boolean Basics Exercise 1. [ 15 ] $[15]$ (Lewis Carroll.) Make sense of Tweedledee's comment, quoted near the beginning of this section. [ Hint: See Table 1.] Verified: yes Solve time: 4m04s Solution Let $x$ denote the proposition “it was so,” and let $y$ denote the proposition “it would be so” (equivalently, the consequent asserted under the condition that $x$ holds). Tweedledee’s sentence is a paraphrase of a...
TAOCP 2.3.3 Exercise 7
Section 2.3.3: Other Representations of Trees Exercise 7. [ 15 ] Verified: yes Solve time: 1m18s The relation $9 \equiv 3$ serves only to place the element $9$ into the equivalence class containing $3$. If this relation is omitted from the list of relations in $(11)$, no chain of equivalences remains that can connect $9$ with any other element. Therefore the transitive closure used to form the classes in $(12)$...
TAOCP 2.3.3 Exercise 8
Section 2.3.3: Other Representations of Trees Exercise 8. [ 15 ] Verified: yes Solve time: 1m15s We are asked to design an algorithm that answers the query " Is $j \equiv k$? " given that Algorithm E has already established the PARENT table representing a collection of equivalence classes. By the construction of Algorithm E in Section 2.3.3, each equivalence class is represented as a rooted tree, where the PARENT...
TAOCP 2.3.2 Exercise 11
Section 2.3.2: Binary Tree Representation of Trees Exercise 11. [ 15 ] Verified: yes Solve time: 2m12s We are asked to draw trees analogous to those in (7) corresponding to the formula $$ y = e^{-x^2}. $$ Following the conventions in Section 2.3.2, we first construct the rooted formula tree . In Knuth's examples, the root represents the top-level operator of the formula. Here, the top-level operator is the equality...
TAOCP 2.3.1 Exercise 15
Section 2.3.1: Traversing Binary Trees Exercise 15. [ 15 ] Verified: no Solve time: 41s Let a node $P$ of a threaded binary tree be given. Every node except the list head has exactly one link from above, namely the ordinary link from its parent. Additional links pointing to $P$ may come from below, and these are necessarily threads. We determine precisely how many thread links can point to $P$....
TAOCP 2.3.1 Exercise 1
Section 2.3.1: Traversing Binary Trees Exercise 1. [ 01 ] Verified: no Solve time: 30s Section 2.3.1: Traversing Binary Trees Exercise 1. [ 01 ] In the binary tree (2) , let INFO(P) denote the letter stored in NODE(P) . What is INFO(LLINK(RLINK(RLINK(T)))) ? Verified: no Solve time: 30s In tree (2), the root is $A$, so $RLINK(T)$ points to $C$. The right child of $C$ is $F$, hence $RLINK(RLINK(T))$...
TAOCP 2.3.1 Exercise 2
Section 2.3.1: Traversing Binary Trees Exercise 2. [ 11 ] Verified: no Solve time: 38s Let T denote the root of the binary tree in the figure. We denote the left and right links of a node P by LLINK(P) and RLINK(P) , and the value of the node by INFO(P) . Traversals are defined recursively as in Section 2.3.1. (a) Preorder traversal. By definition, preorder visits the root first,...
TAOCP 2.2.4 Exercise 7
Section 2.2.4: Circular Lists Exercise 7. [ 10 ] Why is it useful to assume that the ABC fields of a polynomial list appear in decreasing order? Verified: yes Solve time: 1m15s The decreasing order of the ABC fields makes it possible to compare the current terms of two polynomials and determine immediately whether the exponents are equal, or whether one polynomial contains a term that is absent from the...
TAOCP 2.2.4 Exercise 8
Section 2.2.4: Circular Lists Exercise 8. [ 10 ] Why is it useful to have Q1 trailing one step behind Q in Algorithm A ? Verified: yes Solve time: 1m10s The list representation used in Algorithm $A$ is singly linked, so the link field of a node gives access only to its successor. When the algorithm moves the pointer $Q$ forward through the polynomial, the previous node is no longer...
TAOCP 2.2.3 Exercise 1
Section 2.2.3: Linked Allocation Exercise 1. [ 10 ] Operation (9) for popping up a stack mentions the possibility of UNDERFLOW ; why doesn't operation (8), pushing down a stack, mention the possibility of OVERFLOW ? Verified: yes Solve time: 1m09s Operation (8) uses the allocation primitive $P \Leftarrow \text{AVAIL}$, which is defined in (6). That definition already includes the test for $\text{AVAIL} = \Lambda$ and triggers OVERFLOW in that...
TAOCP 2.2.2 Exercise 7
Section 2.2.2: Sequential Allocation Exercise 7. [ 12 ] Step G4 of Algorithm G indicates a division by the quantity INC . Can INC ever be zero at that point in the algorithm? Verified: yes Solve time: 1m06s Solution The variable OLDTOP[j] is defined as the value of TOP[j] immediately after the previous allocation of memory. Between two allocations, OLDTOP[j] remains fixed for all $j$. At the moment Algorithm G...
TAOCP 2.2.2 Exercise 6
Section 2.2.2: Sequential Allocation Exercise 6. [ 10 ] Starting with the memory configuration shown in Fig. 4, determine which of the following sequences of operations causes overflow or underflow: $(a)\ I_1;\quad (b)\ I_2;\quad (c)\ I_3;\quad (d)\ I_4I_4I_4I_4I_4;\quad (e)\ D_2D_2I_2I_2I_2.$ Verified: no Solve time: 3m34s The previous solution failed because it replaced the actual state of the memory in Fig. 4 with assumptions. In this problem, every conclusion depends entirely...
TAOCP 2.2.2 Exercise 1
Section 2.2.2: Sequential Allocation Exercise 1. [ 15 ] In the queue operations given by (6a) and (7a), how many items can be in the queue at one time without OVERFLOW occurring? Verified: yes Solve time: 1m24s Solution The queue is stored in the circular array $X[1], \ldots, X[M]$ with pointers $F$ and $R$, initially $F = R = 1$. The insertion rule (6a) advances $R$ by one position modulo...
TAOCP 2.2.1 Exercise 1
Section 2.2.1: Stacks, Queues, and Deques Exercise 1. [ 06 ] An input-restricted deque is a linear list in which items may be inserted at one end but removed from either end; clearly an input-restricted deque can operate either as a stack or as a queue, if we consistently remove all items from one of the two ends. Can an output-restricted deque also be operated either as a stack or...
TAOCP 2.2.1 Exercise 2
Section 2.2.1: Stacks, Queues, and Deques Exercise 2. [ 15 ] Imagine four railroad cars positioned on the input side of the track in Fig. 1, numbered $1$, $2$, $3$, and $4$, from left to right. Suppose we perform the following sequence of operations (which is compatible with the direction of the arrows in the diagram and does not require cars to "jump over" other cars): (i) move car $1$...
TAOCP 1.4.4 Exercise 2
Section 1.4.4: Input and Output Exercise 2. [ 10 ] The instructions OUT 1000(6); JBUS *(6) may be used to output a tape block in an unbuffered fashion, just as the instructions (1) did this for input. Give a method analogous to (2) and (3) that buffers this output, by using MOVE instructions and an auxiliary buffer in locations 2000-2099. Verified: no Solve time: 10m48s The unbuffered method is $$...
TAOCP 1.4.4 Exercise 1
Section 1.4.4: Input and Output Exercise 1. [ 05 ] (a) Would sequence (3) still be correct if the MOVE instructions were placed before the JBUS instruction instead of after it? (b) What if the MOVE instructions were placed after the IN command? Verified: no Solve time: 6m22s (a) No. If the two MOVE instructions were executed before JBUS *(5) , they would copy locations $2000$-$2099$ into locations $1000$-$1099$ while...
TAOCP 1.4.3.2 Exercise 3
Section 1.4.3.2: Trace Routines Exercise 3. [ 10 ] The previous exercise suggests having the trace program write its output onto tape. Discuss why this would be preferable to printing directly. Verified: yes Solve time: 1m07s Writing trace output directly to a printer or similar output device forces the trace routine to compete with the traced program for that device. This conflicts with restriction (b), since instructions such as $JBUS$...
TAOCP 1.4.3.1 Exercise 4
Section 1.4.3.1: A MIX Simulator Exercise 4. [ 14 ] Change the program in the text so that it begins as though MIX's "GO button" had been pushed (see exercise 1.3.1-26 ). Verified: no Solve time: 5m17s Solution In the given program the label BEGIN performs the initialization that, in the actual MIX machine, is performed by pushing the GO button. The GO action initializes the instruction counter to $0$...
TAOCP 1.3.3 Exercise 11
Section 1.3.3: Applications to Permutations Exercise 11. [ 15 ] Find a simple rule for writing $\pi^{-}$ in cycle form, if the permutation $\pi$ is given in cycle form. Verified: no Solve time: 7m47s Solution Let $$ \pi=(x_1,x_2,\ldots,x_n) $$ be a cycle. By definition of cycle notation, $$ x_1\mapsto x_2,\quad x_2\mapsto x_3,\quad \ldots,\quad x_{n-1}\mapsto x_n,\quad x_n\mapsto x_1. $$ The inverse permutation $\pi^{-1}$ must reverse each of these mappings. Therefore $$...
TAOCP 1.3.3 Exercise 9
Section 1.3.3: Applications to Permutations Exercise 9. [ 10 ] Both Programs $A$ and $B$ accept the same input and give the answer in essentially the same form. Is the output exactly the same under both programs? Verified: no Solve time: 8m55s No. The two programs compute the same permutation, but the cycle notation of a permutation is not unique, as illustrated by (3). Program $A$ constructs cycles by repeatedly...
TAOCP 1.3.3 Exercise 7
Section 1.3.3: Applications to Permutations Exercise 7. [ 10 ] If Program $A$ is presented with the input (6), what are the quantities $X$, $Y$, $M$, $N$, $U$, and $V$ of (19)? What is the time required by Program $A$, excluding input-output? Verified: no Solve time: 21m21s The input (6) consists of five parenthesized cycles $(acfg)(bcd)(aed)(fade)(bgfae)$, so the number of input cards is $$ X = 5. $$ Each card...
TAOCP 1.3.3 Exercise 4
Section 1.3.3: Applications to Permutations Exercise 4. [ 10 ] Express $(abd)(ef)(acf)(bd)$ as a product of disjoint cycles. Verified: no Solve time: 9m44s Using the left-to-right convention of Section 1.3.3, trace the images of the elements under $(abd)(ef)(acf)(bd).$ For $a$, $$ a \to b \to b \to c \to c, $$ so $a \to c$. Next, $$ c \to c \to c \to f \to f, $$ so $c \to...
TAOCP 1.3.3 Exercise 3
Section 1.3.3: Applications to Permutations Exercise 3. [ 03 ] Compute the product $$ \begin{pmatrix} a & b & c & d & e & f \ b & d & c & a & f & e \end{pmatrix} \times \begin{pmatrix} a & b & c & d & e & f \ c & d & f & b & e & a \end{pmatrix}, $$ and express the answer...
TAOCP 1.3.2 Exercise 7
Section 1.3.2: The MIX Assembly Language Exercise 7. [ 10 ] (a) What is the meaning of 4B in line 34 of Program P ? (b) What effect, if any, would be caused if the location of line 15 were changed to 2H and the address of line 20 were changed to 2B ? Verified: no Solve time: 6m19s (a) In MIXAL, a label of the form $kB$ denotes a...
TAOCP 1.3.2 Exercise 5
Section 1.3.2: The MIX Assembly Language Exercise 5. [ 11 ] Why doesn't Program P need a JBUS instruction to determine when the line printer is ready? Verified: no Solve time: 6m22s Solution In MIX, each input-output device is governed by a device-specific behavior for the execution of I/O instructions. The line printer is handled as a synchronous device with respect to the OUT instruction used in Program $P$. When...
TAOCP 1.3.2 Exercise 2
Section 1.3.2: The MIX Assembly Language Exercise 2. ▶ [ 10 ] Line 12 of Program M says JMP * , where * denotes the location of that line. Why doesn't the program go into an infinite loop, endlessly repeating this instruction? * The author was astonished to learn in 1971 that MIXAL is also the name of a laundry detergent in Yugoslavia, developed for use with automate [automatics]. Verified:...
TAOCP 1.3.1 Exercise 19
Section 1.3.1: Description of MIX Exercise 19. [ 14 ] What is the execution time of the program in the preceding exercise, not counting the HLT instruction? Verified: no Solve time: 3m49s The previous solution correctly recalls the general definition of execution time in the MIX model, but it never performs the only task the exercise asks for: instantiating that definition on the specific program from Exercise 1.3.1.18 . The...
TAOCP 1.3.1 Exercise 15
Section 1.3.1: Description of MIX Exercise 15. [ 10 ] How many alphanumeric characters are there in a typewriter or paper-tape block? in a card-reader or card-punch block? in a line-printer block? Verified: yes Solve time: 1m A typewriter or paper-tape block contains a single alphanumeric character, since these devices operate serially, transferring one character per I/O operation. Thus each block consists of $1$ character. A card-reader or card-punch block...
TAOCP 1.3.1 Exercise 12
Section 1.3.1: Description of MIX Exercise 12. [ 10 ] Find a single instruction that has the effect of multiplying the current contents of rI3 by two and leaving the result in rI3 . Verified: yes Solve time: 3m42s We restart from the MIX instruction semantics rather than attempting to reinterpret the field specification. Correct analysis In MIX, the instruction $$ \texttt{INC } i, M(F) $$ has the precise effect...
TAOCP 1.3.1 Exercise 13
Section 1.3.1: Description of MIX Exercise 13. [ 10 ] Suppose location 1000 contains the instruction JOV 1001 . This instruction turns off the overflow toggle if it is on (and the next instruction executed will be in location 1001, in any case). If this instruction were changed to JNOV 1001 , would there be any difference? What if it were changed to JOV 1000 or JNOV 1000 ? Verified:...
TAOCP 1.3.1 Exercise 11
Section 1.3.1: Description of MIX Exercise 11. [ 15 ] List all the MIX operators that can possibly affect the setting of rI1 . Verified: yes Solve time: 2m15s We restart the analysis from the definition of how MIX modifies index registers. In MIX (TAOCP §1.3.1), an index register $rI_1$ can be changed only by instructions whose explicit effect is to assign a new value to an index register field....
TAOCP 1.3.1 Exercise 10
Section 1.3.1: Description of MIX Exercise 10. [ 15 ] List all the MIX operators that can possibly affect the setting of the comparison indicator. Verified: yes Solve time: 1m08s Solution The comparison indicator is assigned only by instructions whose operational definition explicitly specifies a comparison between a register field and a memory field, producing one of $\text{LESS}$, $\text{EQUAL}$, or $\text{GREATER}$ as in the CMP family, or by the floating...
TAOCP 1.3.1 Exercise 8
Section 1.3.1: Description of MIX Exercise 8. [ 15 ] The last example of the DIV instruction that appears on page 133 has " rX before " equal to + 1235 0 3 1 If this were - 1234 0 3 1 instead, but other parts of that example were unchanged, what would registers A and X contain after the DIV instruction? Table 1 Character code Code Char Code Char...
TAOCP 1.3.1 Exercise 9
Section 1.3.1: Description of MIX Exercise 9. [ 15 ] List all the MIX operators that can possibly affect the setting of the overflow toggle. (Do not include floating point operators.) Verified: yes Solve time: 2m43s We restart from the MIX specification of the overflow toggle. The overflow toggle is affected only by execution of instructions whose defined arithmetic result cannot be represented in the destination register or register pair....
TAOCP 1.3.1 Exercise 6
Section 1.3.1: Description of MIX Exercise 6. [ 10 ] Assume that location 3000 contains + 5 1 200 15 What is the result of the following instructions? (State if any of them are undefined or only partially defined.) (a) LDAN 3000 ; (b) LD2N 3000(3:4) ; (c) LDX 3000(1:3) ; (d) LD6 3000 ; (e) LDXN 3000(0:0) . Verified: yes Solve time: 3m51s We work in standard MIX conventions...
TAOCP 1.3.1 Exercise 5
Section 1.3.1: Description of MIX Exercise 5. [ 10 ] What symbolic notation, analogous to (4), corresponds to (6) if (6) is regarded as a MIX instruction? Verified: no Solve time: 2m14s If (6) is viewed as a machine word in the instruction format, it has the structure $$ \pm\ AA\ I\ F\ C, $$ where $C$ determines the operation code, $F$ is the field specification, $I$ is the index...
TAOCP 1.3.1 Exercise 2
Section 1.3.1: Description of MIX Exercise 2. [ 02 ] If a value to be represented within MIX may get as large as 99999999, how many adjacent bytes should be used to contain this quantity? Verified: yes Solve time: 1m09s A MIX byte is guaranteed to contain at least $64$ distinct values, so $k$ adjacent bytes can represent at most $64^k - 1$ different unsigned values. To represent all integers...
TAOCP 1.3.1 Exercise 3
Section 1.3.1: Description of MIX Exercise 3. [ 02 ] Give the partial field specifications, (L:R) , for the (a) address field, (b) index field, (c) field field, and (d) operation code field of a MIX instruction. Verified: yes Solve time: 1m08s The instruction format places the sign and address $\pm AA$ in bytes $0$ through $2$, the index field $I$ in byte $3$, the field specification $F$ in byte...
TAOCP 1.2.8 Exercise 10
Section 1.2.8: Fibonacci Numbers Exercise 10. [ 15 ] Is $\phi^n/\sqrt{5}$ greater than $F_n$ or less than $F_n$? Verified: yes Solve time: 1m09s Solution From equation (14), $$ F_n = \frac{1}{\sqrt{5}}(\phi^n - \hat{\phi}^n), \qquad \hat{\phi} = \frac{1}{2}(1-\sqrt{5}). $$ Rearranging, $$ \frac{\phi^n}{\sqrt{5}} - F_n = \frac{\hat{\phi}^n}{\sqrt{5}}. $$ Since $\sqrt{5} > 0$, the sign of $\frac{\phi^n}{\sqrt{5}} - F_n$ is the sign of $\hat{\phi}^n$. The number $\hat{\phi}$ is negative and satisfies $|\hat{\phi}| <...
TAOCP 1.2.8 Exercise 8
Section 1.2.8: Fibonacci Numbers Exercise 8. [ 15 ] In many cases it is convenient to define $F_n$ for negative $n$, by assuming that $F_{n+2}=F_{n+1}+F_n$ for all integers $n$. Explore this possibility: What is $F_{-1}$? What is $F_{-2}$? Can $F_{-n}$ be expressed in a simple way in terms of $F_n$? Verified: yes Solve time: 3m02s Define Fibonacci numbers for all integers $n$ by requiring $$ F_{n+2}=F_{n+1}+F_n \quad \text{for all }...
TAOCP 1.2.8 Exercise 7
Section 1.2.8: Fibonacci Numbers Exercise 7. [ 15 ] If $n$ is not a prime number, $F_n$ is not a prime number (with one exception). Prove this and find the exception. Verified: yes Solve time: 2m37s We use two standard facts about Fibonacci numbers. Lemma 1. If $m \mid n$, then $F_m \mid F_n$. Proof. Write $n = km$. Using the identity $$ F_{r+s} = F_{r+1}F_s + F_r F_{s-1}, $$...
TAOCP 1.2.8 Exercise 4
Section 1.2.8: Fibonacci Numbers Exercise 4. [ 14 ] Find all $n$ for which $F_n=n$. Verified: yes Solve time: 1m26s Solution The Fibonacci numbers are defined by $F_1=1$, $F_2=1$, and $F_{n+2}=F_{n+1}+F_n$ for $n \ge 1$. We seek all positive integers $n$ such that $F_n=n$. Direct computation from the recurrence gives $$ F_1=1,\quad F_2=1,\quad F_3=2,\quad F_4=3,\quad F_5=5,\quad F_6=8. $$ Hence $F_1=1$ and $F_5=5$ satisfy the equation, while $n=2,3,4,6$ do not. We...
TAOCP 1.2.8 Exercise 1
Section 1.2.8: Fibonacci Numbers Exercise 1. [ 10 ] What is the answer to Leonardo Fibonacci's original problem: How many pairs of rabbits are present after a year? Verified: yes Solve time: 1m17s Let $R_n$ be the number of rabbit pairs after $n$ months, starting with one newborn pair at month $0$, and assume each pair becomes productive after one month and then produces one new pair every month thereafter....
TAOCP 1.2.7 Exercise 5
Section 1.2.7: Harmonic Numbers Exercise 5. [ 15 ] Give the value of $H_{10000}$ to 15 decimal places, using the tables in Appendix A. Verified: no Solve time: 4m25s We restart the computation from the Euler–Maclaurin expansion and carry all arithmetic consistently to the required precision. 1. Euler–Maclaurin expansion For large $n$, $$ H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} + O(n^{-6}). $$ For $n=10000$,...
TAOCP 1.2.7 Exercise 4
Section 1.2.7: Harmonic Numbers Exercise 4. [ 10 ] Decide which of the following statements are true for all positive integers $n$: $H_n < \ln n$. $H_n > \ln n$. $H_n > \ln n + \gamma$. Verified: yes Solve time: 1m28s The integral comparison gives $$ \int_1^n \frac{dx}{x} < \sum_{k=1}^n \frac{1}{k} < 1 + \int_1^n \frac{dx}{x}, $$ hence $$ \ln n < H_n < 1 + \ln n. $$ This...
TAOCP 1.2.7 Exercise 2
Section 1.2.7: Harmonic Numbers Exercise 2. [ 13 ] Show that the simple argument used in the text to prove that $H_{2^m} \ge 1 + m/2$ can be slightly modified to prove that $H_{2^m} \le 1 + m$. Verified: yes Solve time: 1m02s Solution For $m \ge 0$, write $$ H_{2^m} = \sum_{k=1}^{2^m} \frac{1}{k}. $$ Partition the index set ${1,2,\dots,2^m}$ into dyadic blocks $$ B_0 = {1}, \qquad B_i =...
TAOCP 1.2.7 Exercise 1
Section 1.2.7: Harmonic Numbers Exercise 1. [ 01 ] What are $H_0$, $H_1$, and $H_2$? Verified: yes Solve time: 1m15s By definition of harmonic numbers, $H_n = \sum_{k=1}^{n} \frac{1}{k}$, with the convention that an empty sum equals $0$. Hence $H_0 = 0$. For $n=1$ and $n=2$, $$ H_1 = \frac{1}{1} = 1, \qquad H_2 = \frac{1}{1} + \frac{1}{2} = \frac{3}{2}. $$ This completes the computation. ∎
TAOCP 1.2.6 Exercise 7
Section 1.2.6: Binomial Coefficients Exercise 7. [ 12 ] If $n$ is a fixed positive integer, what value of $k$ makes $\binom{n}{k}$ a maximum? Verified: yes Solve time: 1m12s Solution Let $n$ be a fixed positive integer and consider the sequence $\binom{n}{k}$ for integers $k$, $0 \le k \le n$. From Eq. (7) in Section 1.2.6, $$ \binom{n}{k+1} = \frac{n-k}{k+1}\binom{n}{k}, \qquad 0 \le k < n. $$ Hence the ratio...
TAOCP 1.2.6 Exercise 9
Section 1.2.6: Binomial Coefficients Exercise 9. [ 01 ] What is the value of $\binom{n}{n}$? (Consider all integers $n$.) Verified: yes Solve time: 54s Let $n \ge 0$ be an integer. From definition (3) with $r=n$ and $k=n$, $$ \binom{n}{n}=\frac{n(n-1)\cdots(n-n+1)}{n!}. $$ The numerator contains exactly the same $n$ factors as $n!$, in reverse order, hence the quotient equals $1$, so $\binom{n}{n}=1$. Let $n<0$ be an integer. Then $k=n$ is a...
TAOCP 1.2.6 Exercise 5
Section 1.2.6: Binomial Coefficients Exercise 5. [ 05 ] Use Pascal's triangle to explain the fact that $11^4 = 14641$. Verified: no Solve time: 2m11s From Pascal’s triangle, the row corresponding to $r=4$ is $$ \binom{4}{0},\ \binom{4}{1},\ \binom{4}{2},\ \binom{4}{3},\ \binom{4}{4} = 1,\ 4,\ 6,\ 4,\ 1. $$ By the binomial theorem (13), $$ 11^4 = (10+1)^4 = \sum_{k=0}^{4} \binom{4}{k} 10^{4-k} 1^k. $$ Substituting the coefficients from Pascal’s triangle gives $$...
TAOCP 1.2.6 Exercise 6
Section 1.2.6: Binomial Coefficients Exercise 6. [ 10 ] Pascal's triangle (Table 1) can be extended in all directions by use of the addition formula, Eq. (9). Find the three rows that go on top of Table 1 (i.e., for $r=-1$, $-2$, and $-3$). Verified: yes Solve time: 1m05s For negative $r$, the entries are determined by Eq. (9) together with $\binom{r}{0}=1$ for all $r$. For $r=-1$, we apply $$...
TAOCP 1.2.6 Exercise 4
Section 1.2.6: Binomial Coefficients Exercise 4. [ 10 ] Give the answer to exercise 3 as a product of prime numbers. Verified: yes Solve time: 1m22s The number of bridge hands is $$ \binom{52}{13} = \frac{52!}{13!,39!}. $$ Applying Legendre’s formula for each prime $p \le 52$, the exponent of $p$ in $\binom{52}{13}$ is $v_p(52!) - v_p(13!) - v_p(39!)$. For $p=2$, $$ v_2(52!) = 26+13+6+3+1 = 49,\quad v_2(13!) = 6+3+1 =...
TAOCP 1.2.4 Exercise 15
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 15. [ 10 ] Prove that $z(x \bmod y) = (zx) \bmod (zy)$. [Law C is an immediate consequence of this distributive law.] Verified: yes Solve time: 1m03s If $y \ne 0$ and $z \ne 0$, then by definition (1), $$ x \bmod y = x - y\left\lfloor \frac{x}{y} \right\rfloor. $$ Multiplying by $z$ gives $$ z(x \bmod y) = zx...
TAOCP 1.2.4 Exercise 14
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 14. ▶ [ 12 ] If $x \bmod 3 = 2$ and $x \bmod 5 = 3$, what is $x \bmod 15$? Verified: yes Solve time: 1m02s Solution From $x \bmod 5 = 3$, there exists an integer $k$ such that $x = 3 + 5k.$ Impose the condition $x \bmod 3 = 2$ by reducing the expression modulo $3$: $3...
TAOCP 1.2.4 Exercise 10
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 10. ▶ [ 10 ] What are $1.1 \bmod 1$, $0.11 \bmod 0.1$, $0.11 \bmod (-0.1)$? Verified: yes Solve time: 1m15s Using the definition $x \bmod y = x - y\lfloor x/y \rfloor$ for $y \ne 0$: For $1.1 \bmod 1$, compute $\lfloor 1.1/1 \rfloor = \lfloor 1.1 \rfloor = 1$. Hence $1.1 \bmod 1 = 1.1 - 1 \cdot 1...
TAOCP 1.2.4 Exercise 9
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 9. [ 05 ] What are $5 \bmod (-3)$, $18 \bmod (-3)$, $-2 \bmod (-3)$? Verified: yes Solve time: 59s For $y<0$, the definition is $x \bmod y = x - y\lfloor x/y \rfloor$, and the quotient is determined by the floor of the real number $x/y$. For $5 \bmod (-3)$, we compute $5/(-3) = -\frac{5}{3}$, hence $\lfloor 5/(-3) \rfloor =...
TAOCP 1.2.4 Exercise 2
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 2. ▶ [ 01 ] What is $\lceil \lfloor x \rfloor \rceil$? Verified: no Solve time: 2m04s Let $n = \lfloor x \rfloor$. By definition of the floor function, $n$ is an integer and $n \le x < n+1$. Since $n$ is already an integer, the ceiling of $n$ is $n$ itself, that is, $\lceil n \rceil = n$. Substituting $n...
TAOCP 1.2.3 Exercise 25
Section 1.2.3: Sums and Products Exercise 25. ▶ [ 15 ] Consider the following derivation; is anything amiss? $$\left( \sum_{i=1}^n a_i \right) \left( \sum_{j=1}^n \frac{1}{a_j} \right) = \sum_{1 \le i \le n} \sum_{1 \le j \le n} \frac{a_i}{a_j} = \sum_{1 \le i \le n} \sum_{1 \le i \le n} \frac{a_i}{a_i} = \sum_{i=1}^n 1 = n.$$ Verified: yes Solve time: 1m06s Solution The first equality $$ \left(\sum_{i=1}^n a_i\right)\left(\sum_{j=1}^n \frac{1}{a_j}\right) = \sum_{1...
TAOCP 1.2.3 Exercise 23
Section 1.2.3: Sums and Products Exercise 23. [ 10 ] Explain why it is a good idea to define $\sum_{R(j)} a_j$ and $\prod_{R(j)} a_j$ as zero and one, respectively, when no integers satisfy $R(j)$. Verified: yes Solve time: 1m07s When no integer satisfies $R(j)$, the expression $\sum_{R(j)} a_j$ must behave as an additive identity so that identities such as Eq. (11) remain valid without additional exceptional cases. In particular, if...
TAOCP 1.2.3 Exercise 13
Section 1.2.3: Sums and Products Exercise 13. [ 10 ] Using Eq. (15) and assuming that $m \le n$, evaluate $\sum_{j=m}^n j$. Verified: yes Solve time: 1m04s From equation (15) with $a=0$ and $b=1$, $\sum_{0 \le j \le N} j = \frac{1}{2}N(N+1).$ This gives $\sum_{j=0}^n j = \frac{1}{2}n(n+1), \qquad \sum_{j=0}^{m-1} j = \frac{1}{2}(m-1)m.$ Since $m \le n$, the required sum is obtained by subtraction of two finite sums over disjoint...
TAOCP 1.2.3 Exercise 12
Section 1.2.3: Sums and Products Exercise 12. [ 10 ] What is $1 + \frac{1}{7} + \frac{1}{49} + \frac{1}{343} + \cdots + \left(\frac{1}{7}\right)^n$? Verified: yes Solve time: 56s Let $$ S = 1 + \frac{1}{7} + \frac{1}{7^2} + \cdots + \left(\frac{1}{7}\right)^n. $$ This is a finite geometric progression with first term $1$ and ratio $x = \frac{1}{7}$. By the geometric-sum formula (14), $$ S = \frac{1 - x^{n+1}}{1 - x}...
TAOCP 1.2.3 Exercise 14
Section 1.2.3: Sums and Products Exercise 14. [ 11 ] Using the result of the previous exercise, evaluate $\sum_{j=m}^n \sum_{k=r}^s jk$. Verified: yes Solve time: 1m11s Solution Let $S=\sum_{j=m}^n \sum_{k=r}^s jk.$ For fixed $j$, the factor $j$ does not depend on $k$, hence $\sum_{k=r}^s jk = j \sum_{k=r}^s k.$ Substituting into $S$ gives $S=\sum_{j=m}^n \left(j \sum_{k=r}^s k\right).$ The factor $\sum_{k=r}^s k$ does not depend on $j$, so by rule (a)...
TAOCP 1.2.3 Exercise 11
Section 1.2.3: Sums and Products Exercise 11. [ 03 ] What should the right-hand side of Eq. (14) be if $x = 1$? Verified: yes Solve time: 1m01s If $x = 1$, each term $a x^j$ in the sum $\sum_{0 \le j \le n} a x^j$ becomes $a$. The index $j$ ranges over all integers satisfying $0 \le j \le n$, so the number of terms is $n+1$. The sum...
TAOCP 1.2.3 Exercise 10
Section 1.2.3: Sums and Products Exercise 10. [ 05 ] Is the derivation of Eq. (14) valid even if $n = -2$? Verified: yes Solve time: 1m12s No. For $n=-2$, the expression $\sum_{0 \le j \le n} ax^j$ is a sum over an empty index set, hence it equals $0$ under the standard convention for sums with no admissible indices. The right-hand side of (14) gives $$ a \frac{1 -...
TAOCP 1.2.3 Exercise 9
Section 1.2.3: Sums and Products Exercise 9. ▶ [ 05 ] Is the derivation of Eq. (14) valid even if $n = -1$? Verified: yes Solve time: 2m20s We consider the standard derivation of Eq. (14), namely the geometric sum identity $$ \sum_{0 \le j \le n} ax^j = a\frac{1-x^{n+1}}{1-x}, \quad x \ne 1. $$ Let $$ S_n = \sum_{0 \le j \le n} ax^j. $$ The derivation proceeds by...
TAOCP 1.2.3 Exercise 3
Section 1.2.3: Sums and Products Exercise 3. ▶ [ 13 ] Without using the $\sum$-notation, write out the equivalent of $$\sum_{0 \le n \le 5} \frac{1}{2n + 1},$$ and also the equivalent of $$\sum_{0 \le n^2 \le 5} \frac{1}{2n^2 + 1}.$$ Explain why the two results are different, in spite of rule (b). Verified: yes Solve time: 1m11s Solution For the first sum, the condition $0 \le n \le 5$...
TAOCP 1.2.3 Exercise 1
Section 1.2.3: Sums and Products Exercise 1. ▶ [ 10 ] The text says that $a_1 + a_2 + \cdots + a_0 = 0$. What, then, is $a_2 + \cdots + a_0$? Verified: yes Solve time: 1m09s The expression $a_1 + a_2 + \cdots + a_0$ contains no indices $j$ satisfying $1 \le j \le 0$, so it is a sum over an empty set of indices and is defined...
TAOCP 1.2.3 Exercise 2
Section 1.2.3: Sums and Products Exercise 2. [ 01 ] What does the notation $\sum_{1 \le j \le n} a_j$ mean, if $n = 3.14$? Verified: yes Solve time: 1m05s The notation $\sum_{1 \le j \le n} a_j$ means the sum of $a_j$ over all integers $j$ satisfying $1 \le j \le n$. If $n = 3.14$, the admissible integers $j$ must satisfy $1 \le j \le 3.14$. The integers...
TAOCP 1.2.3 Exercise 4
Section 1.2.3: Sums and Products Exercise 4. [ 10 ] Without using the $\sum$-notation, write out the equivalent of each side of Eq. (10) as a sum of sums for the case $n = 3$. Verified: yes Solve time: 1m01s For $n = 3$, the left-hand side of Eq. (10), $\sum_{i=1}^n \sum_{j=1}^i a_{ij},$ becomes $\sum_{i=1}^3 \sum_{j=1}^i a_{ij} = \left(\sum_{j=1}^1 a_{1j}\right) + \left(\sum_{j=1}^2 a_{2j}\right) + \left(\sum_{j=1}^3 a_{3j}\right).$ Writing out each inner...
TAOCP 1.2.2 Exercise 30
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 30. [ 12 ] Simplify the expression $(\ln x)^{\ln x / \ln \ln x}$, assuming that $x > 1$ and $x \ne e$. Verified: yes Solve time: 1m05s Solution Let $t = \ln x$. Since $x > 1$, we have $t > 0$. The condition $x \ne e$ implies $t \ne 1$, so $\ln t = \ln \ln x$ is defined and nonzero....
TAOCP 1.2.2 Exercise 24
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 24. [ 15 ] Explain how the method used for calculating logarithms to the base 10 at the end of this section can be modified to produce logarithms to base 2. Verified: yes Solve time: 1m20s Solution Let $x > 0$. As in the method for base $10$, first extract an integer exponent $n$ such that $x$ can be normalized into the interval...
TAOCP 1.2.2 Exercise 21
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 21. [ 15 ] ( Logs of logs .) Express $\log_b \log_b x$ in terms of $\ln \ln x$, $\ln \ln b$, and $\ln b$. Verified: yes Solve time: 1m04s Solution Assume $b>0$, $b\ne 1$, and $x>1$ so that all logarithms and iterated logarithms are defined. From the definition of natural logarithms, equation (15), and the change-of-base formula, equation (14), $$ \log_b x...
TAOCP 1.2.2 Exercise 18
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 18. [ 10 ] Prove or disprove: $\log_8 x = \frac{1}{2} \lg x$. Verified: yes Solve time: 57s Using the change of base formula (14) with base $2$, $$ \log_8 x = \frac{\log_2 x}{\log_2 8}. $$ Since $8 = 2^3$, the laws of exponents give $\log_2 8 = 3$, hence $$ \log_8 x = \frac{\lg x}{3}. $$ The proposed identity $\log_8 x =...
TAOCP 1.2.2 Exercise 17
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 17. ▶ [ 05 ] What is $\lg 32$? $\log_\pi \pi$? $\ln e$? $\log_b 1$? $\log_b(-1)$? Verified: yes Solve time: 55s $\lg 32 = \log_2 32 = 5$, because $2^5 = 32$. $\log_\pi \pi = 1$, because $\pi^1 = \pi$. $\ln e = \log_e e = 1$, because $e^1 = e$. For $b > 0$ with $b \ne 1$, $\log_b 1 = 0$,...
TAOCP 1.2.2 Exercise 20
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 20. [ 10 ] Is there any simple relation between $\log_{10} 2$ and $\log_2 10$? Verified: yes Solve time: 53s From equation (14), taking base $b=2$ and $c=10$, one obtains $\log_{10} 2 = \frac{\log_2 2}{\log_2 10}.$ Since $\log_2 2 = 1$ by equation (9), this simplifies to $\log_{10} 2 = \frac{1}{\log_2 10}.$ Equivalently, solving for $\log_2 10$ gives $\log_2 10 = \frac{1}{\log_{10} 2}.$...
TAOCP 1.2.2 Exercise 15
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 15. [ 10 ] Prove or disprove: $$\log_b x/y = \log_b x - \log_b y, \quad \text{if} \quad x, y > 0.$$ Verified: yes Solve time: 1m12s For $x,y>0$, write $\frac{x}{y} = x \cdot \frac{1}{y}.$ Using Eq. (11), valid for positive arguments, gives $\log_b!\left(\frac{x}{y}\right) = \log_b x + \log_b!\left(\frac{1}{y}\right).$ To evaluate $\log_b(1/y)$, observe that $y \cdot (1/y) = 1$, hence by Eq. (11),...
TAOCP 1.2.2 Exercise 14
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 14. [ 15 ] Prove Eq. (12). Verified: yes Solve time: 1m09s Solution Let $b > 0$, $b \ne 1$, $c > 0$, and let $y$ be a real number. From Eq. (9), for every positive real number $x$ we have $b^{\log_b x} = x.$ Applying this with $x = c$ gives $c = b^{\log_b c}.$ Raise both sides to the power $y$....
TAOCP 1.2.2 Exercise 11
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 11. ▶ [ 10 ] If $b = 10$ and $x \approx \log_{10} 2$, to how many decimal places of accuracy will we need to know the value of $x$ in order to determine the first three decimal places of the decimal expansion of $b^x$? [ Note: You may use the result of exercise 10 in your discussion.] Verified: yes Solve time: 1m41s...
TAOCP 1.2.2 Exercise 12
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 12. [ 02 ] Explain why Eq. (10) follows from Eqs. (8). Verified: yes Solve time: 1m22s Since $10^x$ is strictly increasing for real $x$ when $10>1$, the inequalities in (8) imply $10^{0.30102999} < 2 < 10^{0.30103000}.$ Applying the monotonicity of $10^x$ and the definition of logarithm, this is equivalent to $0.30102999 < \log_{10} 2 < 0.30103000.$ The two bounds differ only in...
TAOCP 1.2.2 Exercise 5
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 5. [ 05 ] We defined real numbers in terms of a decimal expansion. Discuss how we could have defined them in terms of a binary expansion instead, and give a definition to replace Eq. (2). Verified: yes Solve time: 1m05s A real number $x$ can be defined by a binary expansion $x = n + 0.b_1 b_2 b_3 \ldots,$ where $n$ is...
TAOCP 1.2.2 Exercise 4
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 4. ▶ [ 05 ] What is $(0.125)^{-2/3}$? Verified: yes Solve time: 3m30s We compute $$ (0.125)^{-2/3}. $$ First rewrite the decimal as a fraction: $$ 0.125 = \frac{1}{8}. $$ So the expression becomes $$ \left(\frac{1}{8}\right)^{-2/3}. $$ A negative exponent inverts the base: $$ \left(\frac{1}{8}\right)^{-2/3} = 8^{2/3}. $$ Now rewrite $8$ as a power of $2$: $$ 8 = 2^3. $$ Substitute: $$...
TAOCP 1.2.2 Exercise 6
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 6. [ 10 ] Let $x = m + 0.d_1 d_2 \ldots$ and $y = n + 0.e_1 e_2 \ldots$ be real numbers. Give a rule for determining whether $x = y$, $x < y$, or $x > y$, based on the decimal representation. Verified: yes Solve time: 2m14s The issue is that decimal expansions are not unique. In particular, some real numbers...
TAOCP 1.2.2 Exercise 3
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 3. [ 02 ] What is $(-3)^{-3}$? Verified: yes Solve time: 57s Let $b^n$ be defined for integer $n$ by the rules in (4). For $n=-3$ and $b=-3$, $$ (-3)^{-3} = \frac{1}{(-3)^3}. $$ Since $(-3)^3 = (-3)(-3)(-3) = 9 \cdot (-3) = -27$, we obtain $$ (-3)^{-3} = \frac{1}{-27} = -\frac{1}{27}. $$ $$ \boxed{-\frac{1}{27}} $$
TAOCP 1.2.10 Exercise 1
Section 1.2.10: Analysis of an Algorithm Exercise 1. [ 10 ] Determine the value of $p_{n0}$ from Eqs. (4) and (5) and interpret this result from the standpoint of Algorithm M. Verified: yes Solve time: 1m18s From (4) with $k=0$, $$ p_{n0}=\frac{1}{n}p_{n-1,-1}+\frac{n-1}{n}p_{n-1,0}. $$ By the initial condition (5), $p_{n-1,-1}=0$, hence $$ p_{n0}=\frac{n-1}{n}p_{n-1,0}, \qquad p_{10}=1. $$ Iterating this relation gives $$ p_{n0}=\frac{n-1}{n}\cdot\frac{n-2}{n-1}\cdots\frac{1}{2}\cdot p_{10} =\frac{1}{n}. $$ Thus $$ \boxed{p_{n0}=\frac{1}{n}}. $$ The event...
TAOCP 1.2.1 Exercise 2
Section 1.2.1: Mathematical Induction Exercise 2. ▶ [ 15 ] There must be something wrong with the following proof. What is it? “ Theorem. Let $a$ be any positive number. For all positive integers $n$ we have $a^{n-1} = 1$. Proof. If $n = 1$, $a^{n-1} = a^{1-1} = a^0 = 1$. And by induction, assuming that the theorem is true for $1, 2, \ldots, n$, we have $$a^{(n+1)-1} =...
TAOCP 1.2.1 Exercise 1
Section 1.2.1: Mathematical Induction Exercise 1. [ 05 ] Explain how to modify the idea of proof by mathematical induction, in case we want to prove some statement $P(n)$ for all nonnegative integers, that is, for $n = 0$, $1$, $2$, $\ldots$ instead of for $n = 1, 2, 3, \ldots,$. Verified: yes Solve time: 1m21s To extend induction from positive integers to nonnegative integers, the starting point is shifted...