#project
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.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 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 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....