Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1

Exercises

1. [15] If a worm crawls around the binary tree (4), how could it easily reconstruct the parentheses of (1)?

2. [20] (S. Zaks, 1980.) Modify Algorithm P so that it produces the combinations z₁ z₂ . . . z_n of (8) instead of the parenthesis strings a₁ a₂ . . . a_2n.

    3. [23] Prove that (11) converts z₁ z₂ . . . z_n to the inversion table c₁ c₂ . . . c_n.

4. [20] True or false: If the strings a₁ . . . a_2n are generated in lexicographic order, so are the corresponding strings d₁ . . . d_n, z₁ . . . z_n, p₁ . . . p_n, and c₁ . . . c_n.

5. [15] What tables d₁ . . . d_n, z₁ . . . z_n, p₁ . . . p_n, and c₁ . . . c_n correspond to the nested parenthesis ...