The same introductory remarks as taocp-ch1-solutions.txt apply. 2.2.1-8 -------------------- If n>=5, then any permutation starting with n13... works. If n1 can be output from the deque, that means right before n is output (when all n elements are in the deque), either 1. n and 1 appear at both ends of the deque, or 2. n1.. in the left end or ..1n in the right end. Thus the only possible arrangements are 123..n n..321 n123.. ..321n, and in each case 3 is stuck in the middle after n1 is output. 2.2.2-9 -------------------- Let xk be the stack of the kth insertion. The basic observation is that the number of moves caused by this insertion is equal to the number of previous insertion whose stack is > xk. Let Xk be the random variable denoting the number of moves caused by the kth insertion. We have E(total moves) = sum(1km) E(Xk) = sum(1km) sum(1in) E(Xk|k=i) P(k=i) = sum(1km) sum(1in) [(n-i)/n * (k-1)] 1/n ^ expected number of values > i if sampled uniformly k times from 1 to n = 1/n [sum(1km) (k-1)] [sum(1in) 1-i/n] = 1/n (m 2) (n - 1/n * n(n+1)/2) = 1/2 (1-1/n) (m 2). 2.2.2-10 -------------------- The method of 2.2.2-9 is easily adapted. 2.2.2-11 -------------------- Similar to 2.2.2-9, E(total moves) = sum(1km) E(Xk) = sum(1km) sum(1in) E(Xk|k=i) P(k=i) = sum(1km) sum(1in) sum(1lk) E(Xk|k=i, lth occurrence of i) P(lth occurrence of i) P(k=i) ^ 1/n We have P(lth occurrence of i) = P(l-1 occurrences of i in x1,...,x(k-1)) = (k-1 l-1) (n-1)^(k-l) / n^(k-1) and E(Xk|k=i, lth occurrence of i) = (n-i)(k-t)/(n-1) if t>T, 0 otherwise. Plugging these in, the inner most sum sum(1lk) E(Xk|k=i, lth occurrence of i) P(lth occurrence of i) evaluates to 0 if k=1, (n-i)/n^(k-1) sum(t+1 l k) (k-1 l-1) (k-l) (n-1)^(k-l-1) = (n-i)/n^(k-1) sum(t+1 l k) (k-2 l-1) (k-1) (n-1)^(k-2-(l-1)) = (n-i)(k-1)/n^(k-1) sum(t l k-1) (k-2 l) (n-1)^(k-2-l) otherwise. Denote the final sum by A(k-2); it represents the number of (k-2)-tuples of {1,...,n} with >= t occurrences of a given number; A1=0 as well. Apparently there is no simpler closed form. Finally, the big sum evaluates to 1/n sum(1in) sum(2km) (n-i)(k-1)/n^(k-1) A(k-2) = [sum(1in) (1-i/n)] [sum(2km) A(k-2) k-1 / n^(k-1)]. = (n-1)/2 [sum(2km) A(k-2) k-1 / n^(k-1)]. In the special case t=0, we have A(k-2)=n^(k-2), thus the expressionq evaluates to (n-1)/2 sum(2km) k-1 / n = 1/2(1-1/n) sum(1 k m-1) k = 1/2(1-1/n) (m 2), which is the solution to 2.2.2-9. 2.2.2-12 -------------------- If n is even, the expectation is equal to 2^-n times n/2 (n n/2) + 2 sum(0 k n/2-1) (n-k)(n k) = n/2 (n n/2) + 2 sum(0 k n/2-1) n(n-1 k) (recall (n n-k) = n/(n-k) (n-1 n-k-1)) = n/2 (n n/2) + 2n sum(0 k n/2-1) (n-1 k) (sum over left half of (n-1)th row of Pascal's triangle) = n/2 (n n/2) + 2^(n-1) n. = n (n-1 n/2-1) + 2^(n-1) n. = n (n-1 n/2) + 2^(n-1) n. If n is odd, the expectation is equal to 2^-n times 2 sum(0 k (n-1)/2) (n-k) (n k) = 2n sum(0 k (n-1)/2) (n-1 k) (sum over left half of (n-1)th row, including middle term) = 2n 1/2 [2^(n-1) + (n-1 (n-1)/2)] = n 2^(n-1) + n (n-1 (n-1)/2) In general, the answer is n/2 + n 2^-n (n-1 floor(n/2)), the difference from n/2 grows with n, since (n n/2) ~ sqrt(2) 2^n/sqrt(pi n). 2.2.2-16 -------------------- I was initially tempted to say yes: perhaps we could use the circular queue idea. However, there are complications with the idea. Suppose at some point, a certain amount of memory is allocated for the queue (which implies an allocation of memory to the other structure, say a stack). If the stack is full but the F and R pointers of the queue are well off the end of the list, then we would be wasting a lot of space: [ F...R ][......................] One might say, we could dynamically adjust the size of the queue so that this doesn't happen. But that leads to more complications: if the stack is always empty, do we let the queue grow to the right (thus leaving less room for the stack to grow in the future), or do we force it to wrap around at some point? Without an idea of the distribution of insertions and deletions, it is hard to decide on an efficient allocation scheme a priori. 2.2.2-18 -------------------- The idea is to spread out the cost of each expensive repacking operation across the subsequent run of insertions and deletions. Let bji denotes the fraction of memory used by stack i during the jth repacking operation; thus if the repacking occurred on move k, then ak = sum(i)bji. After the repacking, stack i is allowed to grow by A(1-ak)N/n + (1-A)(1-ak)N * bji/ak (where A=0.1 in Knuth's description of Algorithm R). Therefore, the minimum number of moves to the next repacking is equal to the minimum of these quantities, which is at least A(1-ak)N/n. Thus, the cost of the jth repacking operation (which is C ak N), is at most C/A n sum(k l k'-1) al N / (1-al)N, where the jth and (j+1)th repackings occur at moves k and k'. Summing over all repackings, and taking into account the cost of each insertion/deletion, we get the desired bound O(m + n sum(1km) ai/(1-ai)). (Pedantry: the repacking operation also includes costs from iterating through the stacks to find which ones to move upward/downward, and this contributes at most O(nm), which can be subsumed in the sum.) 2.2.3-21 -------------------- The situation is easy to visualise if we draw an arrow for each relation j= some term in poly(Q), thus each term is processed exactly once. Thus if poly(M)=t1+...+tn then the effective result is the series of assignments poly(Q) <- poly(Q) + t1*poly(Q), poly(Q) <- poly(Q) + t2*poly(Q), ... poly(Q) <- poly(Q) + tn*poly(Q), or equivalently poly(Q) <- (1+t1)...(1+tn) poly(Q). Q=M in Algorithm M is ok, because for each term t in poly(M), every term of t*poly(P) is > t, so they all get added behind M. The exception is when poly(P) contains a constant term, but the constant term is already the last node in P, so we don't ever read from the dirty node. 2.2.4-10,11 -------------------- My implementation below, which takes (24p+27)u where p is the number of terms in poly(P). Not quite as good as Knuth's (21p+31)u but still an improvement over (27p+13)u with Program A. * Steps: * 1. Set P1<-P, Q0<=AVAIL, COEF(Q0)<-COEF(P1), ABC(Q0)<-ABC(P1), Q<-Q0. * 2. P1<-LINK(P1). If P1=sentinel, set LINK(Q)<-Q0 and terminate. * 3. Set Q1<-Q, Q<=AVAIL, COEF(Q)<-COEF(P1), ABC(Q)<-ABC(P), * LINK(Q1)<-Q, and goto 2. * Registers: * rI2=Q0, rI3=Q, rI4=Q1, rI5=P1, rI6=tmp COPY STJ 9F 2 ENT5 0,1 1 P1 <- P. LD2 AVAIL 2 Q0 <= AVAIL. J2Z OVERFLOW 1 LD6 1,2(LINK) 2 ST6 AVAIL 2 LDA 0,5 2 COEF(Q0) <- COEF(P1). STA 0,2 2 LDA 1,5(ABC) 2 ABC(Q0) <- ABC(PQ). STA 1,2(ABC) 2 ENT3 0,2 1 Q <- Q0. 2H LD5 1,5(LINK) 2(p+1) P1 <- LINK(P1). LDA 1,5(ABC) 2(p+1) JANN 3F p+1 P1 = sentinel? ST2 1,3(LINK) 2 LINK(Q) <- Q0. 9H JMP * 1 3H ENT4 0,3 p Q1 <- Q. LD3 AVAIL 2p Q <= AVAIL. J3Z OVERFLOW p LD6 1,3(LINK) 2p ST6 AVAIL 2p LDA 0,5 2p COEF(Q) <- COEF(P1). STA 0,3 2p LDA 1,5(ABC) 2p ABC(Q) <- ABC(P1). STA 1,3(ABC) 2p ST3 1,4(LINK) 2p LINK(Q1) <- Q. JMP 2B p