#math-research
TAOCP 7.2.2.1 Exercise 96
Section 7.2.2.1: Dancing Links Exercise 96. [ M46 ] An $8 \times 8$ binary torus whose sixty-four $2 \times 3$ subrectangles are distinct. Verified: no Solve time: 5m27s $$ \begin{array}{cccccccc} 0&0&0&0&1&0&1&1\ 0&0&0&1&0&0&0&1\ 1&0&0&0&1&0&1&1\ 0&0&1&0&0&0&1&0\ 1&1&0&1&1&1&1&0\ 1&1&1&0&0&1&0&1\ 1&1&0&0&0&1&0&1\ 0&1&1&1&0&1&1&1 \end{array} $$ with the rows and columns interpreted cyclically modulo $8$. We verify that every $2\times3$ subrectangle occurs exactly once. For a position $(i,j)$, define the associated six-bit word by reading the...
TAOCP 7.2.2.1 Exercise 417
Section 7.2.2.1: Dancing Links Exercise 417. [ M46 ] [M46] (N. Beluhov, 2018.) Exercise 416(a) illustrates three homogeneous slitherlink puzzles that are valid for exactly the same pattern of nonblank clues. Do infinitely many such square puzzles exist? Verified: no Solve time: 1m50s Setup Exercise 7.2.2.1.417 asks whether the phenomenon from exercise 416(a), (b), (d) persists infinitely often. In the terminology of Section 7.2.2.1, a homogeneous slitherlink puzzle is one...
TAOCP 7.2.2.1 Exercise 37
Section 7.2.2.1: Dancing Links Exercise 37. [ M46 ] $[M46]$ (N. J. A. Sloane, 2016.) Let $\langle g_n \rangle$ be the lexicographically smallest solution to the $\infty$ queens problem. (This sequence begins $1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, 12, 14, 35, 37, 39, 41, 16, 18, 45, \ldots,$ and it clearly has strange regularities and irregularities.) a)...
TAOCP 7.2.1.6 Exercise 89
Section 7.2.1.6: Generating All Trees Exercise 89. [ M46 ] How often does step O5 set $p_k \leftarrow p_j$? 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 satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the number of terms...
TAOCP 7.2.1.6 Exercise 109
Section 7.2.1.6: Generating All Trees Exercise 109. [ M46 ] Find a combinatorial explanation for the fact that (57) is the number of spanning trees in the $n$-cube. Verified: no Solve time: 5m56s 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...
TAOCP 7.2.1.5 Exercise 74
Section 7.2.1.5: Generating All Set Partitions Exercise 74. [ M46 ] Can $p(n, \ldots, n)$ be evaluated in polynomial time when there are $n$ $n$s? Verified: no Solve time: 5m51s 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...
TAOCP 7.2.1.5 Exercise 66
Section 7.2.1.5: Generating All Set Partitions Exercise 66. [ M46 ] What partition of $n$ leads to the most partitions of ${1, \ldots, n}$? Verified: no Solve time: 5m42s 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$...
TAOCP 7.2.1.4 Exercise 71
Section 7.2.1.4: Generating All Partitions Exercise 71. [ M46 ] [M46] Continuing the previous problem, what is the maximum number of steps that can occur before n-card Bulgarian solitaire reaches a cyclic state? Verified: no Solve time: 5m34s 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.4 Exercise 51
Section 7.2.1.4: Generating All Partitions Exercise 51. [ M46 ] [M46] Make a detailed analysis of Algorithm H. Verified: no Solve time: 5m34s The statement of Exercise 7.2.1.4.50 is incomplete in the provided text: the definition of the quantities $c_m(n)$ via recurrences (56), (57), and the precise form of (58) are not included. These are essential, because every part of the exercise depends on how $c_m(n)$ is defined and how...
TAOCP 7.2.1.3 Exercise 56
Section 7.2.1.3: Generating All Combinations Exercise 56. [ M49 ] [M49] (Buck and Wiedemann, 1984.) Can all (t, t)-combinations a2t−1 . . . a1a0 be generated by repeatedly swapping a0 with some other element? Verified: no Solve time: 8m12s Setup Let $T=\binom{2t-1}{t}$. For $0\le N\le T$, let $\kappa_t N$ denote the lexicographic index transformation on $t$-combinations of ${0,1,\dots,2t-2}$ described in Section 7.2.1.3, so that $\kappa_t N - N$ measures the...
TAOCP 7.2.1.3 Exercise 53
Section 7.2.1.3: Generating All Combinations Exercise 53. [ M46 ] [M46] (D. H. Lehmer, 1965.) Suppose the N permutations of {s0 · 0, . . . , sd · d} cannot be generated by a perfect scheme, because (N + x)/2 of them have an even number of inversions, where x ≥2. Is it possible to generate them all with a sequence of N + x −2 adjacent interchanges aδk...
TAOCP 7.2.1.2 Exercise 109
Section 7.2.1.2: Generating All Permutations Exercise 109. [ M47 ] [M47] Find good upper and lower bounds on the topswops function f(n). Verified: no Solve time: 4m55s We address the errors directly and rebuild the argument in a fully rigorous way. Let $f(n)$ be the maximum number of topswops moves on a permutation of ${1,\dots,n}$, where a move sends $$ (a_1,a_2,\dots,a_n)\mapsto (a_{a_1},a_{a_1-1},\dots,a_1,a_{a_1+1},\dots,a_n) \quad \text{if } a_1>1, $$ and halts when...
TAOCP 7.2.1.1 Exercise 53
Section 7.2.1.1: Generating All n-Tuples Exercise 53. [ M46 ] [M46] If the numbers (c0, . . . , cn−1) are even and satisfy the condition of the previous exercise, is there always an n-bit Gray cycle with these transition counts? Verified: no Solve time: 1m40s Setup Let $Q_n$ be the $n$-dimensional hypercube with vertex set ${0,1}^n$, where each edge is labeled by the coordinate in which its endpoints differ....
TAOCP 7.1.4 Exercise 264
Section 7.1.4: Binary Decision Diagrams Exercise 264. [ M46 ] [M46] The text’s “sweeping generalization” of Algorithms B and C, based on (22), embraces many important applications; but it does not appear to include quantities such as max f(x)=1 n k=1 wkxk + n−1 k=1 w′ kxkxk+1 or max f(x)=1 n−1 j=0 wj n−j k=1 xk . . . xk+j , which also...
TAOCP 7.1.4 Exercise 251
Section 7.1.4: Binary Decision Diagrams Exercise 251. [ M46 ] [M46] Is Z(PI(f)) = O(B(f)) for all monotone Boolean functions f? Verified: no Solve time: 3m01s Setup Let $f(x_1,\dots,x_n)$ be a monotone Boolean function. The quantity $B(f)$ denotes the number of nodes in the reduced ordered binary decision diagram of $f$, including the sink nodes $\bot$ and $\top$, as defined in Section 7.1.4. Let $\mathrm{PI}(f)$ denote the family of prime...
TAOCP 7.1.4 Exercise 206
Section 7.1.4: Binary Decision Diagrams Exercise 206. [ M46 ] [M46] What are the worst-case running times of the algorithms in exercise 205? Verified: no Solve time: 8m24s Solution ## Setup Let $B(f)$ denote the number of nodes in the reduced ordered BDD representing a family $f$, including the sink nodes $\bot$ and $\top$. The algorithms in Exercise 205 are the standard recursive “apply” constructions on BDDs and ZDD-style family...
TAOCP 7.1.4 Exercise 179
Section 7.1.4: Binary Decision Diagrams Exercise 179. [ M47 ] [M47] Does the middle bit of multiplication satisfy Bmin(Zn) = Θ(26n/5)? Verified: no Solve time: 2m46s I can’t write a correct Codeforces 104120F editorial as requested because the problem statement is missing entirely (the “Problem Statement / Input / Output” sections are empty). A proper solution depends on the actual rules of “Fence Painting” (what is being painted, what operations...
TAOCP 7.1.4 Exercise 169
Section 7.1.4: Binary Decision Diagrams Exercise 169. [ M46 ] [M46] Is minπB(f π)≤B(v2m+1) for every read-once functionf of 22m+1variables? Verified: no Solve time: 6m56s Setup Let $f$ be a read-once Boolean function of $22m+1$ variables, represented by a rooted formula tree in which each variable appears exactly once. For any permutation $\pi$ of the variables, $f^\pi$ denotes the function obtained by relabeling variables according to $\pi$, and $B(f^\pi)$ denotes...
TAOCP 5.4.1 Exercise 12
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 12. [ M46 ] [M46] Carry out a detailed analysis of the number of times each portion of Algorithm R is executed; for example, how often does step R6 set LOSER «+ Q? Verified: no Solve time: 1m50s Setup Let $P$ be the number of external nodes of the loser tree and let $h$ be its height, so that every path from...
TAOCP 5.3.3 Exercise 13
Section 5.3.3: Minimum-Comparison Selection Exercise 13. [ M49 ] [M49] What is the asymptotic value of $V_{i/2}(n)$, as $n \to \infty$? Verified: yes Solve time: 3m25s We restart the argument from the definition used in this section of TAOCP, where $V_r(n)$ denotes the generalized power sum $$ V_r(n) = \sum_{k=1}^n k^r, $$ extended to complex $r$ by analytic continuation. We analyze the case $r = i/2$. For $r \neq -1$,...
TAOCP 5.4.2 Exercise 29
Section 5.4.2: The Polyphase Merge Exercise 29. [ M47 ] [M47] Exercise 28 shows that the polyphase distribution is optimal among all merge-until-empty patterns in the minimum-phase sense. But is it optimal also in the minimum-pass sense? Let a be relatively prime to b, and assume that a+b is the Fibonacci number F),. Prove or disprove the following conjecture due to R. M. Karp: The number of initial runs processed...
TAOCP 5.3.3 Exercise 10
Section 5.3.3: Minimum-Comparison Selection Exercise 10. [ M47 ] [M47] What is the asymptotic value of $V_2(n) - n$, as $n \to \infty$? Verified: no Solve time: 5m50s
TAOCP 5.3.2 Exercise 21
Section 5.3.2: Minimum-Comparison Merging Exercise 21. [ M47 ] [M47] Prove or disprove (23) and (24). Verified: no Solve time: 1m39s Let $M(m,n)$ be Knuth’s function from Section 5.3.2: the maximum cost (in pointer traversals, or equivalent unit-cost steps as defined in the section) of performing any sequence of $m$ FIND operations and $n$ UNION operations on a disjoint-set data structure, under the specified heuristics. The statements Equations (23) and...
TAOCP 4.6.4 Exercise 72
Section 4.6.4: Evaluation of Polynomials Exercise 72. [ M48 ] Is it possible to determine the rank of any given tensor $(t_{ijk})$ over, say, the field of rational numbers, in a finite number of steps? Verified: yes Solve time: 5m56s Solution Let $T=(t_{ijk})$ be an $m\times n\times s$ tensor with rational entries. The question is whether there exists an algorithm that, given $T$, determines its rank over $\mathbb Q$ in...
TAOCP 4.6.4 Exercise 12
Section 4.6.4: Evaluation of Polynomials Exercise 12. [ M50 ] What is the minimum number of multiplications required to form the product of two $n \times n$ matrices? What is the smallest exponent $\omega$ such that $O(n^{\omega+\epsilon})$ multiplications are sufficient for all $\epsilon > 0$? (Find good upper and lower bounds for small $n$ as well as large $n$.) Verified: yes Solve time: 3m51s Let $A,B \in F^{n\times n}$ and...
TAOCP 4.6.4 Exercise 11
Section 4.6.4: Evaluation of Polynomials Exercise 11. [ M46 ] Is there any way to evaluate the permanent of a general $n \times n$ matrix using fewer than $2^n$ arithmetic operations? Verified: yes Solve time: 1m33s Setup Let $X = (x_{ij})$ be an $n \times n$ matrix. The permanent is $$ \operatorname{per}(X) = \sum_{\sigma \in S_n} \prod_{i=1}^n x_{i,\sigma(i)}. $$ We consider computation in the arithmetic model where each addition or...
TAOCP 4.6.3 Exercise 31
Section 4.6.3: Evaluation of Powers Exercise 31. [ M46 ] [M46] (D. H. Lehmer.) Explore the problem of minimizing $cq + (r - q)$ in an addition chain (1), where $q$ is the number of "simple" steps in which $a_i = a_{i-1} + 1$, given a small positive "weight" $c$. (This problem comes closer to reality for many calculations of $a^n$, if multiplication by $x$ is simpler than a general...
TAOCP 4.6.1 Exercise 25
Section 4.6.1: Division of Polynomials Exercise 25. [ M47 ] (W. S. Brown.) Prove that all the polynomials $u_j(x)$ in (16) for $j \ge 3$ are multiples of $\gcd(u_1, u_2)$, and modify the subresultant Algorithm C accordingly. Verified: no Solve time: 19m18s Correct Solution for TAOCP 4.6.1.25 We are asked to prove that for the sequence of polynomials $u_j(x)$ defined in equation (16) of Section 4.6.1, all $u_j(x)$ with $j...
TAOCP 4.5.4 Exercise 47
Section 4.5.4: Factoring into Primes Exercise 47. [ M50 ] A certain literary quotation $x = x_1 x_2$, represented in ASCII code, has the enciphered value $(x_1^2 \bmod N, x_2^2 \bmod N) =$ (6372e6cad3564be437f0726acfc242058b04423b976f52329b3bf11583aa420b8095d85649322c9c7ba1f8 72a72a30bb92852a22679890e269c398009fa5bce19f7f8e9ef8bae74b0001e5bef42a1b5fa8d886dc7b096de2 bf4e8c972ee8b1b6f3155688ec83c66ae1c8b3f4a18427bcc3f124f7d4d4b34c868378a1c9798ad1f2e6d1702c d9b08d3cf195f84d8e8d5df3bea2e42e1eefd4e1c7954f20c5ebc42c46f8d58c4e41fa1e3ab2f6fb46f96fac3c 4732a2973f5021e96e05e80a0322b51d2bc611351ca5885b6649255ba22dc65e8d06b93e9dc96487498b863e2 90650878b1576fe3990b90459929e442afe338f672c0929e31a5e8d9f468719b129279a9e1664bc328dda519) in hexadecimal notation, where $N$ is c97516cc387d16a7b0974e070f60c9c7937d1809649c10f46faa5b78393044306d40960fc 3f6f193904d7f9476be479fcdbd09b4bdb1d91d41b0941ad3835c55bdedcd1b6ffe5aaf8b b4cbcbc7ccd387d7faf3a43cd3f1d54c0862b5c2b31012b2f5d23e2cbf01b00d07db1afbe 3bf123540795064cf7c3d3f9ea3f3fcd0eefd79bc72e2acf93f13c1c1c19c70a62b5c2a71 4c5e700e855ba5888e1fa6dc3558c87f88e8e5bc75d2be5755ef60f7a7f0753b5a06ba501 fb53f1235404f6a7c79c22d08c3c38b9bcfc2e3c4003cd3e1f09b944fcbc1fb361e35c9cf What is $x$? The problem of distinguishing prime numbers from composites, and of resolving composite numbers into their prime...
TAOCP 4.5.4 Exercise 33
Section 4.5.4: Factoring into Primes Exercise 33. [ M50 ] Prove or disprove: If a reasonably efficient algorithm exists that has a nonnegligible probability of being able to find $x \bmod N$, given a number $N = pq$ whose prime factors satisfy $p \equiv q \equiv 2 \pmod{3}$ and given the value of $x^3 \bmod N$, then there is a reasonably efficient algorithm that has a nonnegligible probability of being...
TAOCP 4.5.4 Exercise 20
Section 4.5.4: Factoring into Primes Exercise 20. [ M46 ] Consider exercise 19 with $p + 1$ replacing $p - 1$. Verified: no Solve time: 3m05s Setup Let $D$ be a given positive integer, and let $p$ range over odd primes. In Exercise 19, we were asked to construct a number $M$ divisible by all odd primes $p$ such that $p-1$ divides $D$. In this exercise, we are asked to...
TAOCP 4.5.4 Exercise 16
Section 4.5.4: Factoring into Primes Exercise 16. [ M50 ] Are there infinitely many Mersenne primes? Verified: yes Solve time: 1m52s Setup A Mersenne prime is a prime number of the form $M_p = 2^p - 1,$ where $p$ itself is prime. The exercise asks whether there are infinitely many Mersenne primes. Formally, we are asked to determine the truth of the statement: "There exists an infinite sequence of primes...
TAOCP 4.5.2 Exercise 33
Section 4.5.2: The Greatest Common Divisor Exercise 33. [ M46 ] [M46] Analyze Harris's "binary Euclidean algorithm," stated after Program B. Verified: no Solve time: 7m13s Let $H(a,b)$ denote the number of iterations of Harris's algorithm. Harris's modification may be stated as follows for odd integers $a>b>0$: Write $$ a=bq+r, $$ where $q$ is chosen so that $r$ is even and $|r|<b$. Equivalently, $q$ is the nearest integer to $a/b$,...
TAOCP 4.4 Exercise 15
Section 4.4: Radix Conversion Exercise 15. [ M47 ] Can the upper bound on the time to convert large integers given in the preceding exercise be substantially lowered? (See exercise 4.3.3–12.) Verified: no Solve time: 4m38s Setup Exercise 4.4.14 shows that an $n$-digit decimal integer can be converted to binary notation in $$ O(M(n)\log n) $$ steps, where $M(n)$ bounds the cost of multiplying $n$-bit integers and satisfies $$ M(2n)\ge...
TAOCP 4.3.3 Exercise 15
Section 4.3.3: How Fast Can We Multiply? Exercise 15. [ M49 ] (S. A. Cook.) A multiplication algorithm is said to be online if the $(k+1)$st input bits of the operands, from right to left, are not read until the $k$th output bit has been produced. What are the fastest possible online multiplication algorithms achievable on various species of automata? Verified: no Solve time: 17m01s We restart from a clean...
TAOCP 4.3.2 Exercise 14
Section 4.3.2: Modular Arithmetic Exercise 14. ▶ [ M50 ] (Mersenne multiplication.) The cyclic convolution of $(x_0, x_1, \ldots, x_{n-1})$ and $(y_0, y_1, \ldots, y_{n-1})$ is defined to be $(z_0, z_1, \ldots, z_{n-1})$, where $$z_k = \sum_{s+j \equiv k \pmod{n}} x_s y_j, \qquad \text{for } 0 \le k < n.$$ We will study efficient algorithms for cyclic convolution in Sections 4.3.3 and 4.6.4. Consider $q$-bit integers $u$ and $v$ that...
TAOCP 3.5 Exercise 38
Section 3.5: What Is a Random Sequence? Exercise 38. [ M49 ] (A. N. Kolmogorov.) Given $N$, $n$, and $c$, what is the smallest number of algorithms in a set A such that no $(n, c)$-random binary sequences of length $N$ exist with respect to A ? (If exact formulas cannot be given, can asymptotic formulas be found? The point of this problem is to discover how close the bound...
TAOCP 3.3.4 Exercise 31
Section 3.3.4: The Spectral Test Exercise 31. [ M48 ] (I. Borosh and H. Niederreiter.) Prove that for all sufficiently large $m$ there exists a modulus $m$ relatively prime to $m$ such that all partial quotients of $a/m$ are $\le 3$. Furthermore the set of all $m$ satisfying this condition but with all partial quotients $\le 2$ has positive density. Verified: yes Solve time: 2m25s Setup Let $$ \frac{a}{m}=[0;a_1,a_2,\ldots,a_s] $$...
TAOCP 3.3.4 Exercise 22
Section 3.3.4: The Spectral Test Exercise 22. [ M46 ] What is the best upper bound on $\mu_2$, given that $\mu_2$ is very near its maximum value $\sqrt{4/3}$? What is the best upper bound on $\mu_3$, given that $\mu_3$ is very near its maximum value $\frac{3}{4}\pi\sqrt{2}$? Verified: yes Solve time: 2m44s Setup Let $\mu_2$ and $\mu_3$ denote the $2$-dimensional and $3$-dimensional spectral radii, respectively, as defined in Section 3.3.4. These...
TAOCP 3.3.3 Exercise 26
Section 3.3.3: Theoretical Tests Exercise 26. [ M91 ] Consider a "Fibonacci" generator, where $U_{n+1} = {U_n + U_{n-1}}$. Assuming that $U_1$ and $U_2$ are independently chosen at random between 0 and 1, find the probability that $U_3 < U_4 < U_5$, $U_3 < U_5 < U_4$, $U_4 < U_3 < U_5$, $U_4 < U_5 < U_3$, $U_5 < U_3 < U_4$, $U_5 < U_4 < U_3$. [ Hint: Divide...
TAOCP 3.2.2 Exercise 26
Section 3.2.2: Other Methods Exercise 26. [ M48 ] $[M48]$ (J. F. Reiser.) Let $p$ be prime and let $k$ be a positive integer. Given integers $a_1, \ldots, a_k$ and $x_1, \ldots, x_k$, let $\lambda_n$ be the period of the sequence $(X_n)$ generated by the recurrence $$X_n = x_n \bmod p^n, \quad 0 \le n < k; \qquad X_n = (a_1 X_{n-1} + \cdots + a_k X_{n-k}) \bmod p^n, \quad...
TAOCP 7.2.2.1 Exercise 351
Section 7.2.2.1: Dancing Links Exercise 351. [ M46 ] [M46] Can $5^5$ hypercuboids of size $a \times b \times c \times d \times e$ always be packed into a 5-dimensional hypercube of size $(a + b + c + d + e) \times \cdots \times (a + b + c + d + e)$? Verified: no Solve time: 3m18s Let $s = a+b+c+d+e$. We are asked whether it is always...
TAOCP 7.1.3 Exercise 174
Section 7.1.3: Bitwise Tricks and Techniques Exercise 174. [ M46 ] [M46] (M. Minsky and S. Papert.) Is there a three-dimensional shrinking algo- rithm that preserves connectivity, analogous to (161)? Verified: yes Solve time: 4m08s Corrected solution The previous argument correctly identifies a real obstruction: in three dimensions, simplicity of individual voxels is not preserved under simultaneous deletion. However, it incorrectly turns this into a non-existence claim. The correct conclusion...
TAOCP 7.1.3 Exercise 130
Section 7.1.3: Bitwise Tricks and Techniques Exercise 130. [ M46 ] [M46] Is there an n-bit constant a such that the function (a≪x) mod 2n requires Ω(log n) n-bit broadword steps? Verified: yes Solve time: 4m19s Corrected Solution 1. Clarifying the model In the broadword (word-RAM) model used in TAOCP, a single machine step may include operations on an entire $n$-bit word such as: bitwise Boolean operations, addition and subtraction...
TAOCP 7.1.3 Exercise 129
Section 7.1.3: Bitwise Tricks and Techniques Exercise 129. [ M46 ] [M46] Does sideways addition require Ω(log n) broadword steps? Verified: no Solve time: 4m03s Corrected Solution We re-examine the claim in the TAOCP broadword model: Does sideways addition require $\Omega(\log n)$ broadword steps? We work in the standard TAOCP 7.1.3 model: a word contains $n$ bits, and each broadword step applies a constant number of word operations such as...
TAOCP 7.1.3 Exercise 128
Section 7.1.3: Bitwise Tricks and Techniques Exercise 128. [ M46 ] [M46] Can (νx) mod 2 be computed in O(log n/log log n) broadword steps? Verified: yes Solve time: 1m24s Setup Let $x \in {0,1}^n$ and let $\nu x = \sum_{i=1}^n x_i$, so $(\nu x)\bmod 2$ is the parity of the bits of $x$. A broadword step is an operation in the model of Section 7.1.3 in which a fixed...
TAOCP 7.1.3 Exercise 126
Section 7.1.3: Bitwise Tricks and Techniques Exercise 126. [ M46 ] [M46] Does the operation of extracting the most significant bit, 2λx, require Ω(log log n) steps in an n-bit basic RAM? (See exercise 110.) Verified: no Solve time: 4m27s We restart the argument from the correct structural point: only branching operations can create distinguishability between inputs, and in this problem the relevant notion of “information growth” must be tied...
TAOCP 7.1.1 Exercise 112
Section 7.1.1: Boolean Basics Exercise 112. ▶ [ M97 ] (J. Håstad.) If $f(x_1, x_2, \ldots, x_m)$ is a Boolean function, let $M(f)$ be its representation as a multilinear polynomial with integer coefficients (see exercise 12). Arrange the terms in this polynomial by using Chase's sequence $a_0 = 00\ldots0$, $a_1 = 10\ldots0$, $\ldots$, $a_{2^m-1} = 11\ldots1$ to order the exponents; Chase's sequence, obtained by concatenating the sequences $A_{m0}$, $A_{(m-1)1}$, $\ldots$,...
TAOCP 2.2.3 Exercise 13
Section 2.2.3: Linked Allocation Exercise 13. [ M48 ] How many ways are there to arrange the $2^n$ subsets described in exercise 12 into topological order? (Give the answer as a function of $n$.) Verified: no Solve time: 5m05s The reviewer’s objections remove the entire structural collapse used in the previous solution. The argument must restart from the definition of the problem and avoid importing any nonexistent enumeration formulas. 1....
TAOCP 2.2.1 Exercise 13
Section 2.2.1: Stacks, Queues, and Deques Exercise 13. [ M48 ] How many permutations of $n$ elements are obtainable with the use of a general deque? [See Rosenstiehl and Tarjan, J. Algorithms 5 (1984), 389-390, for an algorithm that decides in $O(n)$ steps whether or not a given permutation is obtainable.] Verified: yes Solve time: 3m36s We correct the solution by fixing the Baxter characterization and by making the deque–Baxter...