Haskell

372 readers

1 users here now

founded 1 year ago

MODERATORS

[email protected]

Competitive Programming in Haskell: Union-Find (byorgey.github.io)

submitted 1 week ago by [email protected] to c/[email protected]

4 comments fedilink hide all child comments

you are viewing a single comment's thread
view the rest of the comments

[–] solrize 2 points 1 week ago (1 children)

The Wikipedia article discusses some applications. One amazing thing I remembered about the algorithm is its running time, which is infinitesimally slower than linear, by which I mean that the growth factor above linear is the inverse Ackermann function! I've never studied the analysis but I found the result to be mind boggling.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

[–] [email protected] 1 points 1 week ago

Thanks, I did look at the Wikipedia page, but the Applications section is pretty difficult to read. The applications it lists are themselves quite abstract problems.