News for hackers. Stuff that matters.

A comment on Ask HN: What's your favorite elegant/beautiful algorithm?.

Re:Ask HN: What's your favorite elegant/beautiful algorithm? by KerrickStaley on Wednesday October 17, 2018 @03:14AM (#18236834)
Union-find data structure: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by emmanueloga_ on Wednesday October 17, 2018 @05:05AM (#18237375)
I was gonna mention this one as well! So simple and clever.

I like the explanation in the case study in Sedgewick's Algorithms [1].

Compare its simplicity to connected-components [2], another elegant algorithm but with a perhaps a bit more involved implementation.

1: https://algs4.cs.princeton.edu/15uf/

2: https://algs4.cs.princeton.edu/41graph/CC.java.html

[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by OskarS on Wednesday October 17, 2018 @03:53AM (#18237028)
Yeah, this is one of my absolute favorites as well. Such a neat idea. The analysis is also fun, where the complexity of operations is O(alpha(n)), where alpha(n) is the Inverse Ackermann Function. That function is just fun to contemplate.

You wanna flex your muscles with this data structure, this is a fun Project Euler problem: https://projecteuler.net/problem=186

[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by jedimastert on Friday October 19, 2018 @11:22AM (#18257315)
I was recently in a coding interview where I had heard of the original problem (a version of "transform one word to another one letter at a time, making sure that each step is a real word") so instead of just skipping the question, we went straight to the "extra credit" question of "can you tell that there is a path from one word to another faster than just calculating the answer?"

After hearing the word "memoization" go through my head (part of "Hacking the Coding Interview." which I recommend at least for the wealth of example questions for practice), I basically walked my way through making a disjoint-set data structure using the words as keys and the set number as values. I'm prettyy sure that making that up on the spot is what got me the job.

[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by tomp on Wednesday October 17, 2018 @06:26AM (#18237725)
I love this algorithm (I like implementing type systems) but I always feel a bit naughty when I implement it, as AFAIK it can't be implemented with immutable data structures (not efficiently, at least).
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by mattyw on Wednesday October 17, 2018 @06:54AM (#18237849)
I like implementing type systems

Could you expand on this? This is something I've just started reading about. I'd be interested in good resources to use to get started. At the moment I've just started reading TAPL.

[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by tomp on Wednesday October 17, 2018 @08:42AM (#18238377)
Check out https://github.com/tomprimozic/type-systems there's been a few HN threads about it as well. I can also answer any specific questions you have, or if you want further resources I can try and find them... (there's a good online book I have in mind, but I've no idea how to find it right now!)
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by mattyw on Wednesday October 17, 2018 @11:23AM (#18239953)
Some great stuff in this repo thanks. I'm particularly interested in resources that build a type system up step by step, from very simple and working towards Hindley-Milner
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by tomp on Wednesday October 17, 2018 @11:35AM (#18240062)
Hm... I'm not sure it works that way. Type systems are quite fragile beasts, if you change one thing you can easily break the rest. Especially when it comes to type inference! Although I'd say that HM is quite simple, especially if you don't consider polymorphism (i.e. if you require that every function parameter has a concrete type like int or bool).

In fact, that might be a good starting point - first implement something with the above 2 types, and where every variable and function parameter has a type annotation. From then, you could (1) add more complex types, like function types, tuples or lists, (2) implement type propagation where each variable has the type of the value it's assigned (like auto in modern C++), and then (3) go full HM type inference.

TAPL definitely sounds like a good resource. The next book might be this one: Advanced Topics in Types and Programming Languages https://www.cis.upenn.edu/~bcpierce/attapl/frontmatter.pdf

[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by DonaldPShimoda on Wednesday October 17, 2018 @02:16PM (#18241898)
Have you read TAPL? I'm curious how you think that stacks up to readily-available online resources.
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by tomp on Wednesday October 17, 2018 @02:25PM (#18242018)
No, I've just skimmed over some of its chapters to clarify some concepts. I've mostly learned by reading code and then trying to implement my own type systems. Algorithm W is really quite simple and basic.

Another good resource could be Programming Language Zoo http://plzoo.andrej.com/ that covers different evaluation techniques as well.

In general, I've been "involved" in PL design for quite some time, so I've no idea where I've gained all the knowledge I have... but in recent years, there have been quite a few modern resources, even a few on HN IIRC!

e.g.

http://craftinginterpreters.com/

http://createyourproglang.com/

(disclaimer: I haven't read them)

[ Parent | on HN ]