#hard
TAOCP 4.6.4 Exercise 3
Section 4.6.4: Evaluation of Polynomials Exercise 3. [ 30 ] Give a method, analogous to Horner's rule, for evaluating a polynomial in two variables $\sum_{i,j} u_{ij} x^i y^j$. (This polynomial has $(n+1)(n+2)/2$ coefficients, and its "total degree" is $n$.) Count the number of additions and multiplications you use. Verified: yes Solve time: 1m18s Setup Let $$ u(x,y)=\sum_{i+j\le n}u_{ij}x^iy^j $$ be a polynomial of total degree $n$ in two variables. The...
TAOCP 4.4 Exercise 6
Section 4.4: Radix Conversion Exercise 6. [ 30 ] Discuss using Methods 1a, 1b, 2a, and 2b when $b$ or $B$ is $-2$. Verified: yes Solve time: 5m29s Setup Methods 1a, 1b, 2a, and 2b are defined for conversion between positional systems of radix $b$ and radix $B$. The exercise asks for a discussion of these methods when one of the radices is $-2$. A radix-$(-2)$ representation of an integer...
TAOCP 4.3.2 Exercise 4
Section 4.3.2: Modular Arithmetic Exercise 4. [ 29 ] Continue the process shown in (13); what would $m_5, m_6, m_9, \ldots$ be? Verified: yes Solve time: 4m40s Equation (13) is obtained by choosing successively the largest odd integer below the preceding modulus that is relatively prime to every modulus already chosen. The first four terms are $$ m_1=99,\qquad m_2=97,\qquad m_3=95,\qquad m_4=91. $$ We continue the process. Since $$ 99=3^2\cdot11,\qquad 95=5\cdot19,\qquad...
TAOCP 4.3.1 Exercise 25
Section 4.3.1: The Classical Algorithms Exercise 25. [ 26 ] Write a MIX routine for step D1, which is needed to complete Program D. Verified: yes Solve time: 3m12s Exercise 4.3.1.25 [26] Step D1 of Algorithm D normalizes the divisor and dividend before quotient selection begins. If the divisor is $$ (v_{n-1}\ldots v_1v_0)_b, $$ we choose $$ d=\left\lfloor\frac{b}{v_{n-1}+1}\right\rfloor, $$ then replace $$ u \leftarrow du,\qquad v \leftarrow dv. $$ After...
TAOCP 4.2.2 Exercise 17
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 17. [ 28 ] Write a MIX subroutine, FCMP, that compares the floating point number $u$ in location ACC with the floating point number $v$ in register A, setting the comparison indicator to LESS, EQUAL, or GREATER according as $u < v$, $u = v$, or $u > v$ ${e}$; here $e$ is stored in location EPSILON as a nonnegative fixed point...
TAOCP 4.2.1 Exercise 15
Section 4.2.1: Single-Precision Calculations Exercise 15. ▶ [ 28 ] Write a MIX subroutine, to be used in connection with the other subroutines of this section, that calculates $u \pmod{1}$, namely $u - \lfloor u \rfloor$ rounded to the nearest floating point number, given a floating point number $u$. Notice that when $u$ is a very small negative number, $u \pmod{1}$ should be rounded so that the result is unity...
TAOCP 4.2.1 Exercise 7
Section 4.2.1: Single-Precision Calculations Exercise 7. [ 27 ] Discuss floating point arithmetic using balanced ternary notation. Verified: yes Solve time: 9m56s Balanced ternary uses radix $b=3$ and digits $$ \bar 1=-1,\qquad 0,\qquad 1. $$ A real number is represented in normalized floating-point form as $$ x=\pm m,3^e, $$ where the significand (mantissa) $$ m=.d_1d_2\cdots d_p $$ is a balanced ternary fraction with digits $d_i\in{\bar1,0,1}$, and normalization requires $d_1\neq0$. Since...
TAOCP 4.2.1 Exercise 13
Section 4.2.1: Single-Precision Calculations Exercise 13. [ 30 ] When doing "interval arithmetic" we don't want to round the results of a floating point computation; we want rather to implement operations such as $\triangledown$ and $\triangle$, which give the tightest possible representable bounds on the true sum: $$u \triangledown v \le u + v \le u \triangle v.$$ How should the algorithms of this section be modified for such a...
TAOCP 4.1 Exercise 3
Section 4.1: Positional Number Systems Exercise 3. [ 29 ] Express $-49 + i$ in the quarter-imaginary system. Verified: yes Solve time: 13m Exercise 4.1.3, Problem 3 [29] Express $-49+i$ in the quarter-imaginary system, that is, in base $2i$. Solution Let $$ -49+i=\sum_{k} d_k(2i)^k, \qquad d_k\in{0,1,2,3}. $$ A standard property of the quarter-imaginary system is that the even and odd powers separate: $$ (2i)^{2k}=(-4)^k, \qquad (2i)^{2k+1}=2i(-4)^k. $$ Hence $$ \sum_k...
TAOCP 3.5 Exercise 43
Section 3.5: What Is a Random Sequence? Exercise 43. [ 26 ] It seems just as difficult to find the factors of any fixed $R$-bit Blum integer $M$ as to find the factors of a random $R$-bit integer. Why then is Theorem P stated for random $M$ instead of fixed $M$? Verified: yes Solve time: 1m48s Setup Let Theorem P be the result asserting that a prediction algorithm for the...
TAOCP 3.4.2 Exercise 15
Section 3.4.2: Random Sampling and Shuffling Exercise 15. ▶ [ 30 ] (Ole-Johan Dahl.) If $X_k = k$ for $1 \le k \le t$ at the start of Algorithm P, and if we terminate the algorithm when $j$ reaches the value $t - n$, the sequence $X_{t-n+1}, \ldots, X_t$ is a random permutation of a random combination of $n$ elements. Show how to simulate the effect of this procedure using...
TAOCP 2.3.3 Exercise 10
Section 2.3.3: Other Representations of Trees Exercise 10. [ 28 ] In the worst case, Algorithm E may take order n^2 steps to process n equivalences. Show how to modify the algorithm so that the worst case is not this bad. Verified: yes Solve time: 1m24s Setup Algorithm E constructs a forest whose nodes are the elements $1,\ldots,n$. Each tree represents one equivalence class. The PARENT field of a root...
TAOCP 2.3.2 Exercise 13
Section 2.3.2: Binary Tree Representation of Trees Exercise 13. [ 26 ] Write a MIX program for the COPY subroutine (which fits in the program of the text between lines 063-104 ). [ Hint: Adapt Algorithm 2.3.1C to the case of right-threaded binary trees, with suitable initial conditions.] Verified: yes Solve time: 1m40s Exercise 2.3.2.13 The previous solution does not address the exercise. The problem is not to describe a...
TAOCP 2.3.3 Exercise 18
Section 2.3.3: Other Representations of Trees Exercise 18. [ 28 ] Design an algorithm that, given the two tables INFO1[j] and RLINK[j] for 1 <= j <= n corresponding to preorder sequential representation, forms tables INFO2[j] and DEGREE[j] for 1 <= j <= n , corresponding to postorder with degrees. For example, according to (3) and (9) , your algorithm should transform $$ \begin{array}{c|cccccccccc} j & 1 & 2 &...
TAOCP 2.3.1 Exercise 33
Section 2.3.1: Traversing Binary Trees Exercise 33. [ 30 ] There is more than one way to thread a tree! Consider the following representation, using three fields LTAG, LLINK, RLINK in each node: LTAG(P): defined the same as in a threaded binary tree; LLINK(P): always equal to P* ; RLINK(P): defined the same as in an unthreaded binary tree. Discuss insertion algorithms for such a representation, and write out the...
TAOCP 2.3.1 Exercise 27
Section 2.3.1: Traversing Binary Trees Exercise 27. [ 28 ] Design an algorithm that tests two given trees T and T' to see whether T \prec T' , T \succ T' , or T is equivalent to T' , in terms of the relation defined in exercise 25 , assuming that both binary trees are right-threaded. Assume that each node has the fields LLINK, RLINK, RTAG, INFO; use no auxiliary...
TAOCP 2.3.1 Exercise 19
Section 2.3.1: Traversing Binary Trees Exercise 19. [ 27 ] Design an algorithm analogous to Algorithm S for the calculation of P‡ in (a) a right-threaded binary tree; (b) a fully threaded binary tree. If possible, the average running time of your algorithm should be at most a small constant, when P is a random node of the tree. Verified: yes Solve time: 1m41s Setup Exercise 19 asks for an...
TAOCP 2.3.1 Exercise 21
Section 2.3.1: Traversing Binary Trees Exercise 21. [ 33 ] Design an algorithm that traverses an unthreaded binary tree in inorder without using any auxiliary stack . It is permissible to alter the LLINK and RLINK fields of the tree nodes in any manner whatsoever during the traversal, subject only to the condition that the binary tree should have the conventional representation illustrated in (2) both before and after your...
TAOCP 2.2.2 Exercise 17
Section 2.2.2: Sequential Allocation Exercise 17. [ 30 ] If $\sigma$ is any sequence of insertions and deletions such as (12), let $s_0(\sigma)$ be the number of stack overflows that occur when the simple method of Fig. 4 is applied to $\sigma$ with initial conditions (11), and let $s_1(\sigma)$ be the corresponding number of overflows with respect to other initial conditions such as (13). Prove that $s_0(\sigma) \le s_1(\sigma) +...
TAOCP 2.2.3 Exercise 23
Section 2.2.3: Linked Allocation Exercise 23. [ 27 ] When the topological sort algorithm cannot proceed because it has detected a loop in the input (see step T8 ), it is usually of no use to stop and say, "There was a loop." It is helpful to print out one of the loops, thereby showing part of the input that was in error. Extend Algorithm T so that it will...
TAOCP 2.2.3 Exercise 26
Section 2.2.3: Linked Allocation Exercise 26. [ 29 ] ( Subroutine allocation. ) Suppose that we have a tape containing the main subroutine library in relocatable form, for a 1960s-style computer installation. The loading routine wants to determine the amount of relocation for each subroutine used, so that it can make one pass through the tape to load the necessary routines. The problem is that some subroutines require others to...
TAOCP 2.2.2 Exercise 8
Section 2.2.2: Sequential Allocation Exercise 8. [ 26 ] Explain how to modify (9), (10), and the repacking algorithms for the case that one or more of the lists is a queue being handled circularly as in (6a) and (7a). Verified: no Solve time: - Setup We are asked to extend the sequential allocation scheme for multiple stacks, as described by equations (9) and (10) and the repacking algorithm (Algorithm...
TAOCP 2.2.2 Exercise 5
Section 2.2.2: Sequential Allocation Exercise 5. [ 35 ] The extension of MIX suggested in exercise 3 has an unfortunate restriction that " 7:7 " is not allowed in an indirectly addressed location. a) Give an example to indicate that, without this restriction, it would probably be necessary for the MIX hardware to be capable of maintaining a long internal stack of three-bit items. (This would be prohibitively expensive hardware,...
TAOCP 1.4.4 Exercise 16
Section 1.4.4: Input and Output Exercise 16. [ 29 ] Formulate the "green-yellow-red-purple" algorithm, suggested by Fig. 26, in the manner of the algorithms for multiple buffering given in the text, using three coroutines (one to control the input device, one for the output device, and one for the computation). Verified: no Solve time: - Setup We are asked to formulate the "green-yellow-red-purple" algorithm, illustrated in Fig. 26, in the...
TAOCP 1.4.4 Exercise 18
Section 1.4.4: Input and Output Exercise 18. [ 30 ] A proposed extension of MIX allows its computations to be interrupted, as explained below. Your task in this exercise is to modify Algorithms and Programs A, R, and B of the text so that they use these interrupt facilities instead of the JRED instructions. The new MIX features include an additional 3999 memory cells, locations $-3999$ through $-0001$. The machine...
TAOCP 2.2.1 Exercise 14
Section 2.2.1: Stacks, Queues, and Deques Exercise 14. [ 26 ] Suppose you are allowed to use only stacks as data structures. How can you implement a queue efficiently with two stacks? The simplest and most natural way to keep a linear list inside a computer is to put the list items in consecutive locations, one node after the other. Then we will have $$ \operatorname{LOC}(X[j+1]) = \operatorname{LOC}(X[j]) + c,...
TAOCP 1.4.3.2 Exercise 5
Section 1.4.3.2: Trace Routines Exercise 5. [ 28 ] In a manner similar to that used to solve the previous exercise, consider the situation in which two copies of the trace routine are placed in different places in memory, and each is set up to trace the other. What would happen? Verified: yes Solve time: 49s Setup Let trace routines $T_A$ and $T_B$ occupy disjoint regions of memory. Each routine...
TAOCP 1.3.3 Exercise 36
Section 1.3.3: Applications to Permutations Exercise 36. [ 27 ] Write a MIX subroutine for the algorithm in the answer to exercise 35, and analyze its running time. Compare it with the simpler method that goes from $\alpha\beta\gamma$ to $(\alpha\beta\gamma)^R = \gamma^R\beta^R\alpha^R$ to $\gamma\beta\alpha$, where $\sigma^R$ denotes the left-right reversal of the string $\sigma$. Verified: yes Solve time: 3m13s Exercise 1.3.3.36, Corrected Solution Problem Let an array $X[0 \dots l+m+n-1]$...
TAOCP 1.4.3.1 Exercise 7
Section 1.4.3.1: A MIX Simulator Exercise 7. [ 32 ] Modify the solutions of the previous exercise in such a way that execution of IN or OUT does not cause I/O transmission immediately; the transmission should take place after approximately half of the time required by the simulated devices has elapsed. (This will prevent a frequent student error, in which IN and OUT are used improperly.) Verified: no Solve time:...
TAOCP 1.4.3.2 Exercise 2
Section 1.4.3.2: Trace Routines Exercise 2. [ 26 ] Modify the trace routine of the text so that before executing each program step it writes the following information on tape unit 0. Word 1, (0:2) field: location. Word 1, (4:5) field: register J (before execution). Word 1, (3:3) field: 2 if comparison is greater, 1 if equal, 0 if less; plus 8 if overflow is not on before execution. Word...
TAOCP 1.4.3.1 Exercise 6
Section 1.4.3.1: A MIX Simulator Exercise 6. [ 28 ] Write programs for the input-output operators JBUS , IOC , IN , OUT , and JRED , which are missing from the program in the text, allowing only units 16 and 18. Assume that the operations "read-card" and "skip-to-new-page" take $T = 10000u$, while "print-line" takes $T = 7500u$. [ Note: Experience shows that the JBUS instruction should be simulated...
TAOCP 1.3.1 Exercise 22
Section 1.3.1: Description of MIX Exercise 22. [ 28 ] Location 2000 contains an integer number, X . Write two programs that compute X^{13} and halt with the result in register A . One program should use the minimum number of MIX memory locations; the other should require the minimum execution time possible. Assume that X^{13} fits into a single word. Verified: no Solve time: 2m49s Program 1: minimum memory...
TAOCP 1.3.1 Exercise 26
Section 1.3.1: Description of MIX Exercise 26. [ 32 ] This problem is to write a card-loading routine. Every computer has its own peculiar "bootstrapping" problems for getting information initially into the machine and for starting a job correctly. In MIX's case, the contents of a card can be read only in character code, and the cards that contain the loading program itself must meet this restriction. Not all possible...
TAOCP 1.3.1 Exercise 17
Section 1.3.1: Description of MIX Exercise 17. [ 26 ] This is the same as the previous exercise, except that locations 0000 through N , inclusive, are to be set to zero, where N is the current contents of rI2 . Your programs (a) and (b) should work for any value 0 \le N \le 2999 ; they should start in location 3000 . Verified: yes Solve time: 1m55s The...
TAOCP 1.3.1 Exercise 25
Section 1.3.1: Description of MIX Exercise 25. [ 30 ] Suppose that the manufacturer of MIX wishes to come out with a more powerful computer ("Mixmaster"?), and he wants to convince as many as possible of those people now owning a MIX computer to invest in the more expensive machine. He wants to design this new hardware to be an extension of MIX, in the sense that all programs correctly...
TAOCP 1.3.1 Exercise 23
Section 1.3.1: Description of MIX Exercise 23. [ 27 ] Location 0200 contains a word + a b c d e write two programs that compute the "reflected" word + e d c b a and halt with the result in register A . One program should do this without using MIX's ability to load and store partial fields of words. Both programs should take the minimum possible number of...
TAOCP 1.2.8 Exercise 38
Section 1.2.8: Fibonacci Numbers Exercise 38. [ 35 ] Write a computer program that plays the game described in the previous exercise and that plays optimally. Verified: no Solve time: - Setup Exercise 37 defines the following game. A pile initially contains $n$ chips. On the first move, the first player may remove any positive number of chips except all $n$ chips. Thereafter, if the preceding player removed $m$ chips,...