O'Reilly logo

Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1 by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 z1 z2 . . . zn of (8) instead of the parenthesis strings a1 a2 . . . a2n.

Image    3. [23] Prove that (11) converts z1 z2 . . . zn to the inversion table c1 c2 . . . cn.

4. [20] True or false: If the strings a1 . . . a2n are generated in lexicographic order, so are the corresponding strings d1 . . . dn, z1 . . . zn, p1 . . . pn, and c1 . . . cn.

5. [15] What tables d1 . . . dn, z1 . . . zn, p1 . . . pn, and c1 . . . cn correspond to the nested parenthesis ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required