The post on applying GPU to finding Eulerian path mentioned a stumbling block: partitioning a very specific kind of graph. In general, partitioning is a hard problem, NP-hard actually. The graphs we are dealing with are very specific, though, and may be partitioned in $latex O(|E|)$ time (E - the set of graph edges). Our … Continue reading HashSet, Graph, Cognac
Tag: algorithm
Look-and-say: F#
This holiday season my brief indulgence was solving the Advent of Code puzzles. One was about the look-and-say sequence. It starts with "1" and grows as follows: 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" … Continue reading Look-and-say: F#