CSC482A/528 - Knuth 4A (Fall 2011)

Assignment 5

Due: November 23, 2011, at the beginning of class.

  • Let Z_n be the zig-zag poset, whose cover relations alternate a_1 < a_2 > a_3 < a_4 > ... What is the number of ideals of Z_n? What is the number of linear extensions of Z_n? In answering these questions it is ok to simply, compute the answers for small values of n, plug those numbers into OEIS and report about which A numbers come back from the OEIS.

  • From the book: Exercise 7.2.1.2.89. As usual, you are to elaborate on Knuth's solution. You may find it useful to do the actual implementation. Knuth's solution refers to Algorithm 2.2.3T. This is his version of topological sorting, except that he is now successively removing maximal elements (processed using a queue and not a stack). What does Knuth's version do on the bad example that I gave in class --- the one where the poset consists of a chain and an isolated element? Not required for the assignment, but I'd be interested if you come up with a natural way to incoporate Knuth's modifications into the recursive version of the Varol-Rotem algorithm.

  • In section 7.2.1.3 what is the "combinatorial number system" of degree 4 representation of 2011? See equation (20).

  • Develop a ranking algorithm for Algorithm P of Section 7.2.1.4. Your algorithm should be efficient (i.e., the number of elementary operations should be polynomial in n). What is the rank of 10+10+8+5+5+5+1+1?

  • Another question.

  • Let K(n) denote the set of sequences a_1 a_2 ... a_n with the properties that (a) 0 \le a_i < i and (b) there is no subsequence i-a_i < j-a_j \le i < j. Prove that |K(n)| is a Catalan number. HINT: Develop a pictorial way of representing the sequences as a linear array of dots, some of which are connected by arcs. Condition (b) is a ``non-crossing" condition. And then relate this pictorial view to binary trees somehow.

  • Develop a fast algorithm to generate the sequences K(n) from the previous exercise. Can you make your algorithm so that it does only a constant amount of computation, on average? Implement the algorithm and turn in a listing.