I like the writing style and simplicity of presentation. I would recommend putting some thought into the order and organization of the articles. Perhaps you should have "main" articles about data structures, then sub-articles about the algorithms that are relevant to them (e.g. "binary search" could be under "arrays," "heapsort" and "priority queue" operations under "heaps," etc.). Obviously, it's a challenge to choose the order and organization of topics and subtopics—it's essentially the task of developing a curriculum.
If you plan on doing some tree/graph algorithms, perhaps you could have a brief introduction to the topic by talking about trees and graphs in general, then proceeding by discussing heaps, simple binary trees (which can branch off into more advanced topics like the various balanced binary trees), and so forth.
As a side note, I think binary trees are a great visual way to introduce the concept of asymptotic running time in a more accessible/pragmatic (albeit less rigorous) way, by showing that the more balanced a binary tree is, the fewer steps it will take on average to find an element (approaching the best-case of log base 2 of n). You can show how a worst-case unbalanced binary tree degrades to a linked list.
I struggled with the ordering. I wanted to do linear searching first, because i thought it was the most fundamental and important to understand for the other stuff. And then I didn't want to do binary search right away because it's more complex.
I'd like to add more, but as I said in another comment, when I started doing quicksort, it didn't feel right. I'd likely need to build a different UI paradigm to represent more complicated algorithms. Same with a btree, I really want to go over it, but that seemed like a ball of UI hurt. Might still try to tackle it though.
One thing I noticed was that you use an array in your linear search example. The example is good, but assumes that the reader knows what an array is. Perhaps you should switch the linear search and array positions, so that you know the reader will know what an array is before using it in your examples?
I really like the simplicity and the choice of language. I think a comments / discussion section would be useful, for people to ask questions, talk about the ways to make the articles even better and perhaps translate the code to other languages.
All in all - I hope you keep up the good work, solid tutorials like these make it more compelling to keep up with the basics and learn new things from the "CS 101" department.
A tip: It would be better if you could expand on the "Real World" section, especially when it comes to specific examples (e.g. dictionaries etc). That way, more students would relate to understanding exactly how those data structures are used in practical applications.
I started doing a quicksort, but I didn't feel it was turning out very good. It felt just a bit too complex for the paradigm I was using.
But, I might try again, or find a different approach to represent some slightly more complicated algorithms. Quicksort and some type of Btree would likely be next on my list, if I feel I can do them justice.
I'd do Merge Sort before Quicksort. There's less to say about it, and these days it seems to be edging out Quicksort in the behind-the-scenes-implementation-of-standard-library department.
And, yes, including some kind of self-balancing tree would seem to be a good idea. But how the heck does one discuss such things concisely and simply? I couldn't say.
Another amazing algorithm (or data structure really) is the pairing heap. I just wrote this down, so it's possible that it's not correct, but here he goes:
data Heap k v = Empty | Heap k v [Heap k v]
merge Empty h = h
merge (Heap k1 v hs) h@(Heap k2 _ _) | k1 <= k2 = Heap k1 v (h:hs)
merge a b = merge b a
extractmin (Heap k v hs) = (v, foldr merge Empty hs)
insert h k v = merge h (Heap k v [])
These 6 lines of code provide a heap data structure with amortized logarithmic time for extractmin and constant time insertion and merging (!).
Honestly, though, I don't think such a thing is what this website is aiming at. It seems to be more for the established, widely used stuff.
Still nice, though. (It's cute how, for so many of the "heap" data structures, the merge operation is really all you need to give much thought to. See also Binomial Heap, etc.)
> These 6 lines of code provide a heap data structure with amortized logarithmic time for extractmin and constant time insertion and merging (!).
Hmmm ... maybe. We need to be exceptionally careful in our reasoning about time complexity, when the code uses lazy evaluation (perhaps more careful than people know how to be, yet).
I'm new to this stuff, and trying to learn fast. This is hands down the best explanation of these concepts I've seen. I suspect you'd do just fine Karl. Keep up the great work.
A fantastic set of articles. I do think that tutorials in general obsess over sorting too much. Rather than expanding this with dozens of sorting algos, it would be nice to see a treatment of trees and graphs. Lay the foundation for someone to understand search trees, huffman coding, A*, etc.
Does the author ever claim what language the code is in? Sure, it looks like JavaScript, but he could easily have just borrowed JavaScript's function syntax (which is easily readable to anyone who's used virtually any imperative programming language) for his pseudocode.
The potential "bug" you pointed out has nothing to do with the algorithm being taught, and is an implementation detail that's irrelevant for this application.
Alert! There is an error on the internet. The source I used for Javascript mantissa size was wrong. It said 53 bits, I knocked one off to avoid the addition overflow, but that source must have counted the sign bit.
IEEE doubles only have a 52 bit mantissa, so you need to keep that array under 2^51 elements. Call it 2 quadrillion to be safe.
I've seen many of these "intro to algo" presentations and I have to say this is one of the best. I suppose the Web 2.0 minimalist style helps to facilitate understanding very well. Perhaps there could be sites that could provide math tutorials in the same way.
I really like this idea, thanks for putting this up. I think it would be nice to additionally split it up into a data structures section and an algorithms section.
This site is great! I love the way latch has presented the examples with each concept. (I would've begged for something like this ten years ago when I was still in highschool.)
I would love if he could take this further and, say, cover graph algorithms in the same way the Linked List was done here.
Nice! Great idea for a site - actually, I kinda had a similar idea when I registered "algolution.com" - the idea being to have a library of algorithms AND people can add implementations in different languages and of course vote up which are the best.
In addiation I had thought to add a 'live run' feature so that you could actually run 1 or more algorithms together and compare performance/memory usage etc!
hmmm... if we defined an API for running a piece of code and returning results, we could build a series of independant web applications that could run sandboxed code in different languages live on the web...
If you plan on doing some tree/graph algorithms, perhaps you could have a brief introduction to the topic by talking about trees and graphs in general, then proceeding by discussing heaps, simple binary trees (which can branch off into more advanced topics like the various balanced binary trees), and so forth.
As a side note, I think binary trees are a great visual way to introduce the concept of asymptotic running time in a more accessible/pragmatic (albeit less rigorous) way, by showing that the more balanced a binary tree is, the fewer steps it will take on average to find an element (approaching the best-case of log base 2 of n). You can show how a worst-case unbalanced binary tree degrades to a linked list.