TAOCP 2.1 Exercise 4
We wish to design an algorithm analogous to Algorithm A, but instead of placing a new card on top of the pile, we place it _face down_ at the _bottom_ of the pile.
Exercise 4. [18] Give an algorithm analogous to Algorithm A, except that it puts the new card face down at the bottom of the pile. (The pile may be empty.)
Verified: no
Solve time: -
Solution
We wish to design an algorithm analogous to Algorithm A, but instead of placing a new card on top of the pile, we place it face down at the bottom of the pile. Let us denote the pile by a linked list with TOP pointing to the top card and NEXT(X) giving the card immediately above X (or undefined if there is none). The pile may be empty, in which case TOP = 0. The new card is represented by the address NEWCARD. We assume, as in Algorithm A, that the card has a field NEXT that can be set.
The invariant we wish to maintain is that TOP always points to the top of the pile, and NEXT pointers correctly chain all cards down to the bottom. Placing a card at the bottom requires traversing to the last card and linking the new card there.
Algorithm B (Put new card face down at the bottom of the pile).
B1. [Check for empty pile.] If TOP = 0, then set TOP \leftarrow NEWCARD and NEXT(NEWCARD) \leftarrow 0. Terminate the algorithm.
B2. [Traverse to bottom.] Set X \leftarrow TOP. While NEXT(X) \ne 0, set X \leftarrow NEXT(X). Upon termination, X points to the bottom card.
B3. [Attach new card.] Set NEXT(X) \leftarrow NEWCARD and NEXT(NEWCARD) \leftarrow 0. Terminate the algorithm.
Correctness. Step B1 handles the empty-pile case directly; the invariant is maintained trivially because TOP now points to the single card, and NEXT(NEWCARD) = 0. For a non-empty pile, step B2 traverses the chain of cards starting from TOP until reaching the last card. Since NEXT(X) = 0 for the bottom card, X correctly identifies the bottom. Step B3 attaches the new card to the bottom by setting NEXT(X) \leftarrow NEWCARD and NEXT(NEWCARD) \leftarrow 0. After this operation, the pile remains a single linked list from TOP to the new bottom, preserving the invariant. Each NEXT assignment counts as one replacement; thus step B1 performs one replacement if the pile is empty, and step B3 performs two replacements if the pile is non-empty. Step B2 performs no replacements, only pointer traversals.
This completes the construction. The algorithm correctly places NEWCARD face down at the bottom of the pile regardless of whether the pile is initially empty. ∎