Dictionary of Algorithms and Data Structures(xlinux.nist.gov)
xlinux.nist.gov
Dictionary of Algorithms and Data Structures
https://xlinux.nist.gov/dads/
43 コメント
Always appreciate these historical references.
I want to love this but it is missing things that I know of:
- Fenwick tree
- union-find algorithm / data structures
Here is where I first saw Fenwick trees: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
I think this is where I saw union-find: https://www.youtube.com/watch?v=PGZ64ob440I Except I remember a dictionary/hashmap implementation, not a fixed size array.
- Fenwick tree
- union-find algorithm / data structures
Here is where I first saw Fenwick trees: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
I think this is where I saw union-find: https://www.youtube.com/watch?v=PGZ64ob440I Except I remember a dictionary/hashmap implementation, not a fixed size array.
It does seem to be missing quite a bit. I was sure Fenwick had to be there under another name, but I don't see it. Union-find is an even weirder miss, that's a _great_ data structure and very useful. I couldn't think of any other term it'd be hiding under.
The few I couldn't find off the top of my head: square-root decomposition, heavy-light decomposition and really anything at all on Range Minumum Query, one of my favorite general problems (IMO far more interesting than sorting as a group of techniques to focus some time on).
> I think this is where I saw union-find: https://www.youtube.com/watch?v=PGZ64ob440I Except I remember a dictionary/hashmap implementation, not a fixed size array.
I think you usually see ufds on fixed arrays because it makes the algorithm analysis a bit more interesting. If you have lookups cost more than O(1) I think you'll wash out the fun parts of the analysis.
The ds still works well of course regardless.
The few I couldn't find off the top of my head: square-root decomposition, heavy-light decomposition and really anything at all on Range Minumum Query, one of my favorite general problems (IMO far more interesting than sorting as a group of techniques to focus some time on).
> I think this is where I saw union-find: https://www.youtube.com/watch?v=PGZ64ob440I Except I remember a dictionary/hashmap implementation, not a fixed size array.
I think you usually see ufds on fixed arrays because it makes the algorithm analysis a bit more interesting. If you have lookups cost more than O(1) I think you'll wash out the fun parts of the analysis.
The ds still works well of course regardless.
“… was sure Fenwick had to be there under another name.”
Surely any ‘dictionary’ worth its salt would have cross references.
Surely any ‘dictionary’ worth its salt would have cross references.
It's a very finite collection, obviously almost everything will be missing. That's inevitable.
Eg they don't have a soft heap or a finger tree either. They are also missing many purely functional data structures that eg Okasaki talks about.
Eg they don't have a soft heap or a finger tree either. They are also missing many purely functional data structures that eg Okasaki talks about.
This is a great resource, but I wish data structures & algorithms courses would focus more on applications. I'm more interested in knowing why a data structure is useful and in what context I should reach for one, vs. simply knowing what it is.
https://www.redblobgames.com/ is a really good resource that gives a lot of context, and doesn't shy away from technical details.
I wrote something sort of adjacent to what you're talking about. It wasn't about applications persay but instead it was a guide / decision tree that took everything I learnt on how to make choices on what datastructure or algorithmic approaches applied to different problems (from doing the Blind 75 problem set).
It's not authoritative as I am not an expert yet but might still be of interest: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
It's not authoritative as I am not an expert yet but might still be of interest: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
Decision tree is an astute algorithm for the problem of knowing which algorithm to use.
Great resource, thanks!
In my experience they do.
It’s all about time and space complexity and analysis of given functions.
It’s all about time and space complexity and analysis of given functions.
There is an absolutely wild range in data structures courses. A lot of colleges merge data structures and algorithms and some do each separately. I went to one with them separate and we focused on the application because we had time to. I can't imagine that we could have actually covered complexity if we were doing both in one semester.
In my undergrad at University of Michigan it was combined. I do not remember if we covered it but I was already exposed to industry at that time and was far more advanced in the practical than the rest of the class.
The benefits of algorithm selection only really started to become apparent after years of experience and know-how in what _exactly_ an application requires or intends to be used as. Knowledge that is skipped at all levels of computer science education.
The benefits of algorithm selection only really started to become apparent after years of experience and know-how in what _exactly_ an application requires or intends to be used as. Knowledge that is skipped at all levels of computer science education.
I got it split over multiple units and years.
I think Skiena had a good course on it
His book, the Algorithm Design Manual, gets a lot of praise. But I found it far too fluffy, and lacking in rigor. And he doesn't even do a good job of talking about applications.
https://www.redblobgames.com/ is a really good resource that gives a lot of context, and doesn't shy away from technical details.
https://www.redblobgames.com/ is a really good resource that gives a lot of context, and doesn't shy away from technical details.
This looks like what the OP may want from the suggested reference: https://www.algorist.com/algorist.html ...
Are you referring to this? https://www3.cs.stonybrook.edu/~skiena/373/videos/
He was a great professor. Fun assignments that actually incentivized learning the material.
E.g. Write a platform agnostic backtrack algorithm, and fastest 3 in the course got extra credit.
E.g. Write a platform agnostic backtrack algorithm, and fastest 3 in the course got extra credit.
Knowing the context and history definitely makes it more interesting and usually helps in learning too.
Yeah, that would be a fantastic resource. Also implementations in various languages, and trade-offs between different designs.
> implementations in various languages
Rosetta Code is a good resource for that.
https://www.rosettacode.org/wiki/Rosetta_Code
Rosetta Code is a good resource for that.
https://www.rosettacode.org/wiki/Rosetta_Code
Ah I'd heard of this but didn't know what it was. Thank you!
One notable entry: Marlena
https://xlinux.nist.gov/dads/HTML/marlena.html
Does anyone know what it is about?
https://xlinux.nist.gov/dads/HTML/marlena.html
Does anyone know what it is about?
Probably just a guy who really loved his wife.
This one also references the name: https://xlinux.nist.gov/dads/HTML/antisymmetric.html
This one also references the name: https://xlinux.nist.gov/dads/HTML/antisymmetric.html
I don't know if an alphabetical list of algos is a good starting point for a learner. For someone who is either starting out or wants to confidently master the topic, this classic book is the way to go.[1]. I also think this is your best lever to leveling up as a dev and crushing faang coding interviews if that's your goal.
[1] https://books.google.com/books/about/Introduction_To_Algorit...
[1] https://books.google.com/books/about/Introduction_To_Algorit...
Probably not. But its wonderful for a reference.
I have a tangential question to this: how would one go about doing the reverse search of this list. For example I have this algorithm that I know about, I could describe how it works roughly but I don’t know its name and want to know if it’s in the list. Maybe nowadays write a pseudo code version of it, give it to chatGPT and ask for the name of it… otherwise I don’t know
You go on a discord and ask, someone will tell you.
/dads/
Somethin about this just makes me smile. Nice site
Somethin about this just makes me smile. Nice site
I wish they took pull requests. "Acceleration structure" is a basic one that's missing.
I wonder if they have any good random numbers I could use for my encryption algorithm?
This is just awesome … I hope it survives all the budget cut etc. let’s archive it.
I like don't care.
For those unaware (inc the down voters): don't care[1] is a condition used in an output cell in
karnaugh maps.
The parent comment is my attempt at a play on words.
1. https://xlinux.nist.gov/dads/HTML/dontcare.html
The parent comment is my attempt at a play on words.
1. https://xlinux.nist.gov/dads/HTML/dontcare.html
You’ll typically get downvoted for a comment like that even by people who catch the reference. HN tries hard not to be Reddit.
Don't worry about silly numbers on the internet; self-respect is infinitely more valuable
Ha ha. If you have to explain it, the audience isn't worth your time! :)
Or you haven’t given the audience enough to infer your point.
NIST is a treasure trove. Thanks gballan for posting!
Wow, this is pretty useful, thanks!
Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - Oct 2016 (18 comments)
Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - Jan 2015 (4 comments)
Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - April 2013 (15 comments)
Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - April 2011 (16 comments)
Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - March 2011 (1 comment)