6 ms·

Simple algorithms

222 points by taylorbuley 16y ago

nikolaplejic 16y ago
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.
- latch 16y ago
  I can't believe I didn't think about comments. I've enabled disqus! Thanks for that, and the other, ideas.
  - nrbafna 16y ago
    Simple and no clutter. Do you plan to add more algorithms?
    - latch 16y ago
      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.
      - ggchappell 16y ago
        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. In any case, nice site.
        jules 16y ago
        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 (!).
        ggchappell 16y ago
        Nice. Never heard of that. 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).
      - taylorbuley 16y ago
        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.
  - bvi 16y ago
    Clear, concise explanations. Good job. 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.
tszming 16y ago
Just another wrong implementation of Binary Search, http://algorithms.openmymind.net/search/binarysearch http://algorithms.openmymind.net/search/binarysearch, see this: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
- jws 16y ago
  Yes, but if you are using binary search on a list with 2^52 elements…
  - maggit 16y ago
    Did you mean 2^32? That I could understand. 2^52 looks entirely random to me.
    - tsewlliw 16y ago
      the implementation on the site is in JavaScript, where everything is 64-bit floats. I'd guess 52 of those bits are mantissa.
      - jws 16y ago
        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.
- baddox 16y ago
  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.
nickconfer 16y ago
I had this same idea the other day. Glad to see someone made this. I hope you add more content in the future. From a teaching perspective I think it would be great to see the math behind this as well to get the worst case scenerio.
giltotherescue 16y ago
Yes! Thank you for putting this together.
jcampbell1 16y ago
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.
mfonda 16y ago
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.
Rickasaurus 16y ago
Oh look, it's 200 level CS algorithms.
- pavel_lishin 16y ago
  Oh no, not a free resource with controllable animations that show you step by step what's happening in the code!
thurn 16y ago
Is this open source? Nice visuals.
- latch 16y ago
  I'll probably post the source on github sometime over the weekend.
  - latch 16y ago
    https://github.com/karlseguin/Algorithms https://github.com/karlseguin/Algorithms
olragon 16y ago
you are my sunshine
phillijw 16y ago
From the 'arrays' page: A StringBuilder is nothing more than a dynamic arrays for strings with some extra buffer space. When it fills up, it too must be copied to a new, larger, memory block. Pretty sure that is false. The builder will create a new string only for additional characters. It shouldn't create a new string entirely.
baddox 16y ago
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.
- latch 16y ago
  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.
  - trobertson 16y ago
    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?
Apocryphon 16y ago
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.
f1gm3nt 16y ago
http://www.youtube.com/user/AlgoRythmics http://www.youtube.com/user/AlgoRythmics By far the best. Is it possible to implement something like this?
tcarnell 16y ago
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...
damncabbage 16y ago
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.

222 points by taylorbuley 16y ago

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.

latch 16y ago
I can't believe I didn't think about comments. I've enabled disqus! Thanks for that, and the other, ideas.
- nrbafna 16y ago
  Simple and no clutter. Do you plan to add more algorithms?
  - latch 16y ago
    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.
    - ggchappell 16y ago
      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. In any case, nice site.
      - jules 16y ago
        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 (!).
        ggchappell 16y ago
        Nice. Never heard of that. 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).
    - taylorbuley 16y ago
      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.
- bvi 16y ago
  Clear, concise explanations. Good job. 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.

tszming 16y ago

Just another wrong implementation of Binary Search, http://algorithms.openmymind.net/search/binarysearch http://algorithms.openmymind.net/search/binarysearch, see this: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-...

jws 16y ago
Yes, but if you are using binary search on a list with 2^52 elements…
- maggit 16y ago
  Did you mean 2^32? That I could understand. 2^52 looks entirely random to me.
  - tsewlliw 16y ago
    the implementation on the site is in JavaScript, where everything is 64-bit floats. I'd guess 52 of those bits are mantissa.
    - jws 16y ago
      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.
baddox 16y ago
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.

nickconfer 16y ago

I had this same idea the other day. Glad to see someone made this. I hope you add more content in the future. From a teaching perspective I think it would be great to see the math behind this as well to get the worst case scenerio.

giltotherescue 16y ago

Yes! Thank you for putting this together.

jcampbell1 16y ago

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.

mfonda 16y ago

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.

Rickasaurus 16y ago

Oh look, it's 200 level CS algorithms.

pavel_lishin 16y ago
Oh no, not a free resource with controllable animations that show you step by step what's happening in the code!

thurn 16y ago

Is this open source? Nice visuals.

latch 16y ago
I'll probably post the source on github sometime over the weekend.
- latch 16y ago
  https://github.com/karlseguin/Algorithms https://github.com/karlseguin/Algorithms

olragon 16y ago

you are my sunshine

phillijw 16y ago

From the 'arrays' page: A StringBuilder is nothing more than a dynamic arrays for strings with some extra buffer space. When it fills up, it too must be copied to a new, larger, memory block. Pretty sure that is false. The builder will create a new string only for additional characters. It shouldn't create a new string entirely.

baddox 16y ago

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.

latch 16y ago
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.
- trobertson 16y ago
  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?

Apocryphon 16y ago

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.

f1gm3nt 16y ago

http://www.youtube.com/user/AlgoRythmics http://www.youtube.com/user/AlgoRythmics By far the best. Is it possible to implement something like this?

tcarnell 16y ago

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...

damncabbage 16y ago

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.