Given a fnite partial order as input, it is a well known hard problem to compute the number of linear extensions of the partial order. Interestingly, however, it is known that one can approximate the count to within a arbitrarily small multiplicative error in polynomial time. The known algorithms are based on sampling random linear extensions by simulating a simple random walk in the space of linear extensions. A particularly simple and elegant treatment is given in

Russ Bubley, Martin E. Dyer: Faster random generation of linear extensions. Discrete Mathematics 201(1-3): 81-88 (1999).

However, as the viewpoint in the literature has been largely theoretical, there apparently is no implementation currently available. The task of the master's thesis is to produce an implementation. To this end, the thesis work should expand the mathematical proofs underlying the algorithms, and in particular, reveal some of the hidden constant factors of the asymptotic complexity bounds.

Prerequisites: mathematical maturity and basic programming skills.