Finding a Hamiltonian path - a randomized aproach
The problem There is an international programming contest in Hungary held in every year. I like to participate, the problems are very entertaining. One of the problems in 2003 was an idealized DNA sequence assembly based on short reads. The sequences of course were generated by a computer (they weren't actually sequenced DNA data), and the input was very "clean": There were given N reads, each L long. The sequences overlapping exactly at five bases (five characters) There were no read errors, or any kind of noise That's it. It felt tempting to build a graph of that data. Doing it in Python, the adjacency dictionaries (one forward, one reversed) was built in a couple dozen seconds for the largest files. (Python dictionaries are hash maps, they're pretty fast, and scale well.)