#research
TAOCP 5.3.4 Exercise 62
Section 5.3.4: Networks for Sorting Exercise 62. [ 49 ] Study the largest $N$ for which $m$-head perfect sorters exist, given $m$. Is $N = O(m^2)$? Verified: no Solve time: 14m42s Setup A multihead sorter consists of $m$ read/write heads fixed at positions $1 = h_1 < h_2 < \dots < h_m = N$ on a tape of length $N$. The tape moves from left to right past the heads....
TAOCP 5.3.4 Exercise 47
Section 5.3.4: Networks for Sorting Exercise 47. [ 47 ] Is the function $T(n)$ of exercise 6 strictly less than $\hat{T}(n)$ for some $n$? Verified: no Solve time: 11m37s Setup Let (T(n)) be the minimum number of stages required to sort (n) numbers by an adaptive parallel algorithm that in each stage performs any set of disjoint comparisons (the choice of comparisons in a stage may depend on the outcomes...
TAOCP 5.3.4 Exercise 43
Section 5.3.4: Networks for Sorting Exercise 43. [ 48 ] Find an $(m, n)$-merging network with fewer than $C(m, n)$ comparators, or prove that no such network exists. Verified: no Solve time: 2m51s Setup An ((m,n))-merging network is a comparator network that accepts two sorted sequences (\langle x_1,\dots,x_m\rangle) and (\langle y_1,\dots,y_n\rangle) as inputs and produces the sorted merge of length (m+n) as output. The number of comparators used by Batcher’s...
TAOCP 5.3.4 Exercise 44
Section 5.3.4: Networks for Sorting Exercise 44. [ 50 ] Find the exact value of $\hat{S}(n)$ for some $n > 8$. Verified: no Solve time: 1m07s Setup Let (\hat{S}(n)) denote the minimum number of comparator modules required in a sorting network for (n) elements. A sorting network is an oblivious comparison-exchange network that correctly sorts every input sequence. The problem asks for the exact value of (\hat{S}(n)) for some (n...
TAOCP 5.2.4 Exercise 20
Section 5.2.4: Sorting by Merging Exercise 20. [ 47 ] In the notation of exercise 2.2.1–4, at most $a_N^n$ permutations of $N$ elements can be produced with an $n$-stack railway network; hence the number of stacks needed to obtain all $N!$ permutations is at least $\log N!/\log a_N \approx \log_4 N$. Exercise 19 shows that at most $\lceil \lg N \rceil$ stacks are needed. What is the true rate of...
TAOCP 7.2.2.2 Exercise 368
Section 7.2.2.2: Satisfiability Exercise 368. [ 76 ] Show that subsumption and downhill resolution imply unit conditioning: Any preprocessor that does transformations 2 and 4 will also do transformation 1. Verified: no Solve time: 3m52s Solution The information provided is not sufficient to derive the requested formulas. Exercise 7.2.2.2.357 depends on equation (155) and on the definition of the quantities $\pi_0$, $\pi_s$, the “field” of a variable $v$, and the...
TAOCP 7.2.2.2 Exercise 112
Section 7.2.2.2: Satisfiability Exercise 112. [ 46 ] [46] Exactly how many solutions does the tomography problem of Fig. 36 have? Verified: no Solve time: 2m04s Setup The tomography problem of Fig. 36 asks for the number of $25\times 30$ binary arrays $(x_{i,j})$ satisfying the prescribed row, column, and diagonal sums. The variables are $$ x_{i,j}\in{0,1},\qquad 1\leq i\leq25,\quad 1\leq j\leq30 . $$ The constraints are $$ r_i=\sum_{j=1}^{30}x_{i,j}, \qquad 1\leq i\leq25,...
TAOCP 7.2.2.1 Exercise 73
Section 7.2.2.1: Dancing Links Exercise 73. [ 46 ] [46] What's the maximum number of solutions to an instance of Dominosa? Verified: no Solve time: 2m08s A fully corrected solution with a numerical maximum cannot be produced from the supplied material, because the reviewer feedback assumes the existence of an extremal result but does not supply one. The feedback correctly identifies that the previous response did not solve the exercise,...
TAOCP 7.2.2.1 Exercise 56
Section 7.2.2.1: Dancing Links Exercise 56. [ 47 ] [47] What is the largest number of clues in a minimal sudoku puzzle? Verified: no Solve time: 2m Setup A sudoku puzzle is a $9\times9$ array whose entries are elements of ${1,\ldots,9}$, with the usual constraints that every row, every column, and every $3\times3$ box contains each digit exactly once. A clue is a specified entry of the puzzle. A set...
TAOCP 7.2.2.1 Exercise 297
Section 7.2.2.1: Dancing Links Exercise 297. [ 46 ] (P. Torbijn, 1989.) Can the 35 hexominoes be packed into six $6 \times 6$ squares? Verified: no Solve time: 2m04s Setup Exercise 7.2.2.1.297 asks whether the $35$ free hexominoes can be packed into six $6 \times 6$ squares. Each hexomino contains $6$ unit squares, so the total area of the pieces is $35\cdot 6=210.$ The six squares have total area $6\cdot...
TAOCP 7.2.1.6 Exercise 102
Section 7.2.1.6: Generating All Trees Exercise 102. [ 46 ] An oriented spanning tree of a directed graph $D$ on $n$ vertices, also known as a "spanning arborescence," is an oriented subtree of $D$ containing $n-1$ arcs. The matrix tree theorem (exercise 2.3.4.2–19) tells us that the oriented subtrees having a given root can readily be counted by evaluating an $(n-1) \times (n-1)$ determinant. Can those oriented subtrees be listed...
TAOCP 7.2.1.6 Exercise 101
Section 7.2.1.6: Generating All Trees Exercise 101. [ 46 ] Is there a simple revolving-door way to list all $n^{n-2}$ spanning trees of the complete graph $K_n$? (The order produced by Algorithm S is quite complicated.) 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...
TAOCP 7.2.1.4 Exercise 63
Section 7.2.1.4: Generating All Partitions Exercise 63. [ 47 ] [47] For which partitions λ and µ is there a Gray code through all partitions α such that λ ⪯α ⪯µ? Verified: no Solve time: 21m27s
TAOCP 7.2.1.4 Exercise 62
Section 7.2.1.4: Generating All Partitions Exercise 62. [ 46 ] [46] Prove or disprove: For all sufficiently large integers n and 3 ≤m < n such that n mod m ̸= 0, and for all partitions α of n with a1 ≤m, there is a Gray path for all partitions with parts ≤m, beginning at 1n and ending at α, unless α = 1n or α = 21n−2. Verified: no...
TAOCP 7.2.1.3 Exercise 67
Section 7.2.1.3: Generating All Combinations Exercise 67. [ 46 ] [46] Consider the Ising configurations of exercise 13 for which a0 = 0. Given n, t, and r, is there a Gray cycle for these configurations in which all transitions have the forms 0k1 ↔10k or 01k ↔1k0? For example, in the case n = 9, t = 5, r = 6, there is a unique cycle (010101110, 010110110, 011010110,...
TAOCP 7.2.1.2 Exercise 71
Section 7.2.1.2: Generating All Permutations Exercise 71. [ 48 ] [48] Does the Cayley graph with generators σ = (1 2 . . . n) and τ = (1 2) have a Hamiltonian cycle whenever n ≥3 is odd? Verified: no Solve time: 6m02s Setup Let the multiset be ${s_0 \cdot 0,; s_1 \cdot 1,; \ldots,; s_d \cdot d}, \qquad s_0 + s_1 + \cdots + s_d = n.$ Let...
TAOCP 7.2.1.1 Exercise 62
Section 7.2.1.1: Generating All n-Tuples Exercise 62. [ 46 ] [46] Does r(8) = 6? Verified: no Solve time: 4m14s Setup Let $\Gamma_n$ be an $n$-bit Gray cycle in the sense of Section 7.2.1.1, so consecutive vertices differ in exactly one bit. Write $g_i \in {1,\dots,n}$ for the coordinate flipped at step $i$ of the cycle, interpreted cyclically so that $g_{2^n}$ compares the last vertex back to the first. A...
TAOCP 7.1.4 Exercise 127
Section 7.1.4: Binary Decision Diagrams Exercise 127. [ 46 ] [46] Find a permutation π that minimizes B(hπ 100). Verified: no Solve time: 5m11s Setup Let $h_n(x_1,\ldots,x_n)$ be the hidden weighted bit function and let $h_n^\pi$ denote its permutation under $\pi$, evaluated in the fixed variable order $x_1,\ldots,x_n$. Let $B(h_n^\pi)$ be the number of nodes in the reduced ordered BDD, equivalently the number of beads of $h_n^\pi$ plus the two...
TAOCP 5.4.9 Exercise 8
Section 5.4.9: Disks and Drums Exercise 8. [ 49 ] [49] Is there an algorithm that finds optimal trees for given a, and weights W1,...,Wn, in the sense of exercise 7, taking only O(n°) steps for some c? Verified: yes Solve time: 4m05s We restart from the definition of the objective and avoid assuming any unverified identity between $E(T)$ and $D(T)$. 1. Setting and notation Let $T$ be a full...
TAOCP 5.5 Exercise 3
Section 5.5: Summary, History, and Bibliography Exercise 3. [ 87 ] [87] (Stable sorting in minimum storage.) A sorting algorithm is said to require minimum storage if it uses only O((log N )?) bits of memory space for its variables besides the space needed to store the N records. The algorithm must be general in the sense that it works for all N, not just for a particular value of...
TAOCP 5.5 Exercise 5
Section 5.5: Summary, History, and Bibliography Exercise 5. [ 46 ] [46] It is much more difficult to sort nonrandom data with numerous equal keys than to sort uniformly random data. Devise a sorting benchmark that (i) is interesting now and will probably be interesting 100 years from now; (ii) does not involve uniformly random keys; and (iii) does not use data sets that change with time. | shall have...
TAOCP 5 Exercise 5
Section 5: Introduction to Sorting Exercise 5. [ 83 ] [83] (Library card sorting.) Before the days of computerized databases, every library maintained a catalog of cards so that users could find the books they wanted. But the task of putting catalog cards into an order convenient for human use turned out to be quite complicated as library collections grew. The following “alphabetical” listing indicates many of the procedures recommended...
TAOCP 7.1.3 Exercise 61
Section 7.1.3: Bitwise Tricks and Techniques Exercise 61. [ 46 ] Is it NP-hard to decide whether a given permutation is realizable with at least one mask $\theta_j = 0$, using the recursive method of Fig. 12 as implemented in (71)? Verified: no Solve time: 3m44s The previous argument fails because it assumes that the recursion of Fig. 12 behaves like an arbitrary binary-choice system. In the actual TAOCP setting,...
TAOCP 7.1.1 Exercise 92
Section 7.1.1: Boolean Basics Exercise 92. [ 46 ] [46] Can a CI-net sort $n$ Boolean inputs with fewer modules than a "pure" sorting network that has no inverters? Verified: no Solve time: 4m34s The previous argument fails only at the treatment of outputs. Once this is repaired, the polarity-pushing idea does yield a correct elimination proof. Correct solution Let a CI-net be a finite acyclic Boolean circuit whose internal...
TAOCP 7.1.1 Exercise 91
Section 7.1.1: Boolean Basics Exercise 91. [ 46 ] [46] Can a retraction mapping for the labels of every median graph of dimension $t$ be computed by a CI-net that has only $O(\log t)$ levels of delay? [This question is motivated by the existence of asymptotically optimum sorting networks for the analogous problem of sorting; see M. Ajtai, J. Komlós, and E. Szemerédi, Combinatorica 3 (1983), 1–19.] Verified: no Solve...
TAOCP 7.1.3 Exercise 112
Section 7.1.3: Bitwise Tricks and Techniques Exercise 112. [ 46 ] [46] Can all occurrences of the pattern 1r0 be identified in O(1) broadword steps? Verified: no Solve time: 4m35s Corrected Solution We address the reviewer’s three critical points directly and restart from the correct interpretation of the pattern. 1. Correct interpretation of the pattern $1^r0$ The pattern $1^r0$ with variable $r \ge 1$ does not require tracking an unbounded...
TAOCP 7.1.1 Exercise 123
Section 7.1.1: Boolean Basics Exercise 123. [ 46 ] Determine the exact number of self-dual Boolean functions of ten variables that are threshold functions. Verified: no Solve time: 4m33s Start from the correct structural reduction and then fix the two issues raised in the review: duplication of hyperplanes and the unjustified use of a “general position” region count. 1. Correct structural form Let $f:{0,1}^{10}\to{0,1}$ be a threshold function. Then $$...
TAOCP 7.1.2 Exercise 24
Section 7.1.2: Boolean Evaluation Exercise 24. [ 47 ] [47] Does every symmetric function $f$ have $C_m(f) = C(f)$? Verified: no Solve time: 33m07s The previous solution fails at the only point where it matters: it does not establish a lower bound for tree complexity. A local observation about reuse inside one circuit does not imply a global separation between circuit and formula complexity. The argument must therefore be restarted....
TAOCP 7.1.2 Exercise 21
Section 7.1.2: Boolean Evaluation Exercise 21. [ 46 ] [46] For how many four-variable functions did the Harvard researchers discover an optimum vacuum-tube circuit in 1951? Verified: yes Solve time: 4m59s The key mistake in the previous solution is the assumption that the Harvard computation covered all $2^{16}$ Boolean functions. In fact, the 1951 Harvard optimal-circuit work did not treat every truth table separately. It exploited symmetry to reduce the...
TAOCP 7.1.1 Exercise 68
Section 7.1.1: Boolean Basics Exercise 68. [ 46 ] The just-barely-$Y$ configuration shown in the previous exercise has 52 black stones. What is the largest number of black stones possible in such a configuration? (That is, how many variables can there be in a prime implicant of the function $Y(t)$?) Verified: no Solve time: 4m12s The previous solution fails because it never produces a genuine upper bound. The correction must...
TAOCP 2.2.3 Exercise 25
Section 2.2.3: Linked Allocation Exercise 25. [ 47 ] Design as efficient an algorithm as possible for doing a topological sort of very large sets $S$ having considerably more nodes than the computer memory can contain. Assume that the input, output, and temporary working space are done with magnetic tape. [ Possible hint: A conventional sort of the input allows us to assume that all relations for a given node...
TAOCP 1.2.1 Exercise 14
Section 1.2.1: Mathematical Induction Exercise 14. [ 50 ] (R. W. Floyd.) Prepare a computer program that accepts, as input, programs in some programming language together with optional assertions, and that attempts to fill in the remaining assertions necessary to make a proof that the computer program is valid. (For example, strive to get a program that is able to prove the validity of Algorithm E, given only assertions A1...
Mochi-to-C Transpiler
Background research for Mochi MEP-45 : the deep-dive specification for the C-as-target AOT half of MEP-42 . The transpiler takes compiler3 IR, lowers it to ISO C23 plus a thin libmochi.a runtime, and ships a statically-linked single-file native binary for every tier-1 triple (x86_64-linux-{gnu,musl}, aarch64-linux-{gnu,musl}, aarch64-darwin, x86_64-darwin, x86_64-windows-msvc, x86_64-windows-gnu, wasm32-wasi). The master correctness gate is byte-equal stdout from the produced binary versus vm3 on the entire fixture corpus. Each file...
Native Code Emission
Background research for Mochi MEP-42 : the native-codegen positioning that pairs a copy-and-patch JIT (Xu+Kjolstad PLDI 2021, validated by CPython 3.13 in October 2024) for mochi run hot loops with a C-as-target AOT pipeline (Nim / V / Vala lineage) for mochi build distributables. Each subsection drills into one thread of the 2024-2026 native-codegen landscape. Every file has a §1 Provenance with canonical URLs, a §2 Mechanism, a §3 status...
Memory Management
Background research for Mochi MEP-41 : the memory-safety positioning that frames Mochi's vm3 runtime as a Vale generational reference machine, an MSWasm capability ABI, and a kalloc_type / xzone typed allocator, all under one roof. Each subsection drills into one thread of the 2023-2026 memory-safety landscape. Every file has a §1 Provenance with canonical URLs, a §2 Mechanism, a §3 status as of May 2026, an engineering-cost section, a Mochi...