Name: Tim Daly Date: 05/19/04-07:31:30 PM Z
Kocay, William “The Hopcroft-Tarjan Planarity Algorithm”
http://bkocay.cs.umanitoba.ca/G&G/articles/Planarity.pdf
A readably clear explanation with pseudo-code.
A nearly-literate program.
Another nearly-literate program is
Agrawal, M., Kayal, N. and Saxena, N “PRIMES is in P”
http://www.cse.iitk.ac.in/primality.pdf
which contains not only the theory but also pseudo-code, a
time-complexity
analysis, loop termination proofs, and loop-invariant statements.
A near-perfect literate program. I have permission to make it into a
literate Axiom program and use it as a canonical example.
Both are beautiful pieces of work that tackle reasonably hard theory
yet get very close to practice. Unfortunately the very last step,
providing code, still needs to be done.
Tim