#project
TAOCP 4.5.4 Exercise 39
Section 4.5.4: Factoring into Primes Exercise 39. [ 40 ] Many primes $p$ have the property that $2p + 1$ is also prime; for example, $5 \to 11 \to 23 \to 47$. More generally, say that $q$ is a successor of $p$ if $p$ and $q$ are both prime and $q = 2^k p + 1$ for some $k \ge 0$. For example, $2 \to 3 \to 7 \to 29...
TAOCP 4.4 Exercise 16
Section 4.4: Radix Conversion Exercise 16. [ 41 ] Construct a fast linear iterative array for radix conversion from decimal to binary (see Section 4.3.3E). Verified: yes Solve time: 5m09s Setup Section 4.3.3E defines a fast linear iterative array as a systolic network in which data move through a linear sequence of cells, each cell performs a fixed local operation, and the total running time is proportional to the number...
TAOCP 4.3.2 Exercise 1
Section 4.3.2: Modular Arithmetic Exercise 1. [ 39 ] Find all integers $u$ that satisfy all of the following conditions: $u \bmod 7 = 1$, $u \bmod 11 = 0$, $u \bmod 13 = 5$, $0 \le u < 1000$. Verified: yes Solve time: 4m13s Setup Find all integers $u$ such that $$ u \bmod 7 = 1,\qquad u \bmod 11 = 0,\qquad u \bmod 13 = 5, $$ with...
TAOCP 4.3.1 Exercise 16
Section 4.3.1: The Classical Algorithms Exercise 16. [ 39 ] ( Short division. ) Design an algorithm that divides a nonnegative $n$-place integer $(.u_1 u_2 \ldots u_n) b$ by $v$, where $v$ is a single-precision number (that is, $0 < v < b$), producing the quotient $(.w {n-1} \ldots w_1 w_0)_b$ and remainder $r$. Verified: yes Solve time: 1m29s Setup Let $$ U=(.u_1u_2\cdots u_n)_b, \qquad 0<v<b, $$ where each digit...
TAOCP 4.2.1 Exercise 17
Section 4.2.1: Single-Precision Calculations Exercise 17. [ 40 ] (John Cocke.) Explore the idea of extending the range of floating point numbers by defining a single-word representation in which the precision of the fraction decreases as the magnitude of the exponent increases. Verified: yes Solve time: 1m41s Setup A floating point number is represented by a single word containing a fraction and exponent. Exercise 17 asks for an exploration of...
TAOCP 3.2.2 Exercise 29
Section 3.2.2: Other Methods Exercise 29. ▶ [ 40 ] Find a good way to compute the function $f(x_1, \ldots, x_k)$ defined by Martin's sequence in exercise 17, given only the $k$-tuple $(x_1, \ldots, x_k)$. Verified: yes Solve time: 1m19s Exercise 3.2.2.29 29. [ 40 ] Find a good way to compute the function $f(x_1, \ldots, x_k)$ defined by Martin's sequence in exercise 17, given only the $k$-tuple $(x_1, \ldots,...
TAOCP 3.2.2 Exercise 28
Section 3.2.2: Other Methods Exercise 28. [ 40 ] (A. G. Waterman.) Experiment with linear congruential sequences with $m$ the square or cube of the computer word size, while $a$ and $c$ are single-precision numbers. Verified: yes Solve time: 1m27s Setup Exercise 28 asks for an experimental investigation of linear congruential sequences when the modulus is much larger than the machine word size, while the multiplier and increment remain single-precision...
TAOCP 2.3.3 Exercise 15
Section 2.3.3: Other Representations of Trees Exercise 15. [ 40 ] Design an algorithm to compute the product of two polynomials represented as in Fig. 28. Verified: yes Solve time: 2m39s Exercise 2.3.3.15 [ 40 ] Problem restatement. Let two polynomials be represented in the linked-tree sequential form of Fig. 28. That is, each polynomial is a tree in which a node contains fields: COEFF , the coefficient of the...
TAOCP 2.3.3 Exercise 14
Section 2.3.3: Other Representations of Trees Exercise 14. [ 40 ] Give a formal proof (or disproof) of the validity of Algorithm A . Verified: yes Solve time: 3m14s Exercise 2.3.3.14 [ 40 ] Problem: Give a formal proof (or disproof) of the validity of Algorithm A . Corrected Solution We prove formally that Algorithm A correctly computes the sum of two polynomials represented as described in Section 2.3.2. Let...
TAOCP 2.3.1 Exercise 35
Section 2.3.1: Traversing Binary Trees Exercise 35. [ 40 ] Define a ternary tree (and, more generally, a t -ary tree for any t \ge 2 ) in a manner analogous to our definition of a binary tree, and explore the topics discussed in this section (including topics found in the exercises above) that can be generalized to t -ary trees in a meaningful way. Verified: no Solve time: 47s...
TAOCP 2.2.5 Exercise 10
Section 2.2.5: Doubly Linked Lists Exercise 10. [ 40 ] It is perhaps significant to note that although the author had used the elevator system for years and thought he knew it well, it wasn't until he attempted to write this section that he realized there were quite a few facts about the elevator's system of choosing directions that he did not know. He went back to experiment with the...
TAOCP 2.2.3 Exercise 28
Section 2.2.3: Linked Allocation Exercise 28. [ 40 ] The following construction shows how to "solve" a fairly general type of two-person game, including chess, nim, and many simpler games: Consider a finite set of nodes, each of which represents a possible position in the game. For each position there are zero or more moves that transform that position into some other position. We say that position $x$ is a...
TAOCP 2.2.2 Exercise 15
Section 2.2.2: Sequential Allocation Exercise 15. [ 40 ] Using a Monte Carlo method, simulate the behavior of Algorithm G under varying distributions of insertions and deletions. What do your experiments imply about the efficiency of Algorithm G ? Compare its performance with the algorithm given earlier that shifts up and down one node at a time. Verified: no Solve time: - Setup The exercise asks for an empirical evaluation...
TAOCP 1.4.3.2 Exercise 6
Section 1.4.3.2: Trace Routines Exercise 6. [ 40 ] Write a trace routine that is capable of tracing itself, in the sense of exercise 4: It should print out the steps of its own program at slower speed, and that program will be tracing itself at still slower speed, ad infinitum, until memory capacity is exceeded. Verified: no Solve time: 2m41s The previous submission failed because it attempted a high-level...
TAOCP 1.4.4 Exercise 17
Section 1.4.4: Input and Output Exercise 17. [ 40 ] Adapt the multiple-buffering algorithm to pooled buffers; build in methods that keep the process from slowing down, due to too much anticipated input. Try to make the algorithm as elegant as possible. Compare your method to nonpooling methods, applied to real-life problems. Verified: yes Solve time: 2m06s Corrected solution We model the system as a pool of $N$ indistinguishable buffers....