September 2013

S M T W T F S
1 234567
891011121314
15161718192021
22232425262728
2930     

Custom Text

Most Popular Tags

I've come across a rather interesting CS problem during work that I thought I'd throw out there. The problem is this: given a finite lattice (L, ⊑) (our problem has a lattice that is also distributive, so you may presume that) and a node x in that lattice, efficiently compute the set SL = { yL : xy ∧ ∄ z xzy }. This is well defined, and starting from ⊥ it is possible to walk the entire lattice easily (which is why we care). If you precompute the lattice you can do this trivially. Is it possible to do so without considering every node in the lattice?

Failing that, can you give me an efficient algorithm for computing the structure of the lattice from a set L and a partial order ⊑ ?

Tags:

(no subject)

Sep. 20th, 2008 06:41 pm
From Talk is talk, kill is kill:
Knuth, 4.5.2, theorem D: If u and v are integers chosen at random, the probability that gcd(u,v)=1 is 6/pi^2

So if you give someone an infinite amount of random integers, they can use those to calculate pi by checking how many of those are prime to one another.

Yet another demonstration of the unreasonable rationality of the universe.
Tags:

Syndicate

RSS Atom

Expand Cut Tags

No cut tags

Style Credit