9 ms·

Khan Academy: Algorithms

358 points by lobo_tuerto 12y ago

jzelinskie 12y ago
It's about time; this is great progress. it seems like they've updated a lot of their computer science stuff -- it used to just be a basic introduction to JS and not really anything theoretical.
RMarcus 12y ago
For others who may be confused (as I was), note in the sidebar that this course is for "introductory computer science algorithms." While I suppose it is most certainly a collection of algorithms, I would generally expect such topics to be listed under "data structures" or "discrete math" at most universities. In my experience, "algorithms" denotes a higher level, more advanced course (OBSTs, flows, stable marriage, ILP/LP...)
- gt565k 12y ago
  That was my thought exactly! My data structures & algorithms course covered most of these topics and more and that was the 3rd CS class required in the curriculum. The 3000 level algorithms course I took as part of my CS program, included Big O notation, NP completeness, P vs NP, advanced uses of graph algorithms, dynamic programming, reducability.
- quonn 12y ago
  While the algorithm course at my university consisted mostly of calculating complexities and was much more difficult in general, there is also Sedgewicks' Algorithms book, which covers many of the topics in this course. So "algorithms" is certainly the correct term.
wodenokoto 12y ago
When I first tried this course a few month ago, the little helpers (think clippy) were driving me nuts! Half way through writing a line of code they would pop up and tell me that my code couldn't execute, maybe I should add a semi colon. It's really distracting and of course code can't execute when you are in the middle of typing an if-statement. It is not helpful at all. On top of that there's no "submit" button (because it is supposed to test continuously) so sometimes when I was done it wouldn't test the code and made it impossible to get a "completion" on parts.
- fafner 12y ago
  Yes, that's truly annoying. I have a few code examples that are complete but it refuses to accept them without giving any reason. If I try to step forward it says I have to go back. Also in the first example it complained when I was using Math.round for the index calculation and only wanted to accept Math.floor. (although not applicable in this case, I think Math.floor is not the best choice since it won't behave like ints in negative cases)
symlinkk 12y ago
I'm in college right now and I've been wondering...do professional programmers actually think about sorting algorithms on a day-to-day basis? How relevant is this knowledge when it comes to actually making something?
- patio11 12y ago
  Ask a simple question, get a simple answer: no. While there are some programmers who develop libraries, the majority will just consume well-understood sorting algorithms which are baked into their languages/standard libraries/etc of choice. If you find yourself coding mergesort and you are not in a job interview, a nightmare, or a nightmare of a job interview, you are probably doing something wrong. That said, most of the reason we teach sorting algorithms is to teach algorithms in general, and particularly the consequential lesson that "There are often many methods to doing something that work; these methods are often different in extraordinarily consequential ways; the right method for certain problems -- even ones which look trivial on the outside! --may require literally years of R&D to develop."
  - aninhumer 12y ago
    Even ones that look trivial on the inside might take years of R&D to develop.
    - throwaway43 12y ago
      Any examples ?
      - CoreDumpling 12y ago
        http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
      - danieldk 12y ago
        http://mumble.net/~campbell/2014/04/28/uniform-random-float http://mumble.net/~campbell/2014/04/28/uniform-random-float
eliben 12y ago
Taught by Cormen, no less
edem 12y ago
For some reason when I read "Khan Academy" somewhere I instantly associate it with Star Trek and I can't take it seriously.
- rm445 12y ago
  Well done, you've noticed a tremendous character flaw and now you can strive to correct it. Honestly, how are you going to live life if any reminder of pop culture can distract you from a serious subject? And how are you going to interact with people if noticing such a thing (even if it's tremendously obvious) makes you feel the need to shout about it? Best to knock it on the head now.
  - benihana 12y ago
    Jesus dude. It was just an anecdote. It's a hell of a thing to call that a "tremendous character flaw" based on like, literally no evidence other than your assumptions.
    - rm445 12y ago
      Just for clarity, genuinely being incapable of taking anything seriously which sounded like a pop culture reference, would indeed be a tremendously damaging flaw. Of course I don't really believe parent poster has that problem: it was making a little fun as mild chastisement for the terrible comment. I honestly think you could have interpreted it correctly if you hadn't been so quick to take offence.
      - randomnumber53 12y ago
        If you don't actually believe the poster has that problem, why respond the way that you did? Doesn't that make your comment at least as terrible?
  - edem 12y ago
    Dude you need to get something for your soreness. I don't take everything seriously and comments on the internet are definitely one of those things. You are like a loser klingon captain whose ship is about to blow up because the Enterprise is firing its photon torpedoes at him. And no I don't care about you downvoting either.
graycat 12y ago
Gee, I saw quicksort but not heap sort! Heap sort is O( n log(n) ) in all cases including worst, and quicksort is O( n^2 ) worst case. O( n log(n) ) is the Gleason bound, the fastest sort there can be on average from comparing pairs of keys so that in that sense heap sort is asymptotically the fastest possible. Dropping the technique of comparing pairs lets us consider radix sort which can be faster, still. The lecture does cover merge sort; good. For graphs, the min cost network flow problem is linear programming, and it turns out that if the arc capacities are integers and start with a basic integer feasible solution, then the simplex algorithm maintains integer solutions and, if merely an optimal solution exists, will find an optimal integer solution. It turns out that this fact is in practice one of the best tools for linear integer programming which generally is in NP-complete. This progress on integer programming is worth noting. For cycling in the simplex algorithm for the min cost flow problem on networks, W. Cunningham, long at Waterloo, has a nice solution based on what he calls strongly feasible basic solutions. For the simplex algorithm for the network flow problem, there are, compared with the simplex algorithm in general, some enormous simplifications -- e.g,. a feasible basis corresponds to a spanning tree of arcs -- and, thus, astoundingly high performance on astoundingly large problems -- this fact should be noted. Maybe I missed it, but I didn't see trees mentioned. Both AVL trees and red-black trees are good examples, that is, balanced binary trees good for collection classes. And B-trees, multi-way branched balanced trees, long important on hard disk (and likely now on solid state disks) for database should also be mentioned. Since need to teach heap sort, should also mention that the heap data structure is good for an easy implementation of fast priority queues, e.g., look at 1 billion numbers one at a time, in any order, and end up with the 100 largest, efficiently. Also there is a modification of the heap data structure that has good locality of reference when doing a lot of virtual memory paging. And for hashing, the clean solution is Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong, Extendible hashing-a fast access method for dynamic files', "ACM Transactions on Database Systems", ISSN 0362-5915, Volume 4, Issue 3, September 1979, Pages: 315 - 344. I'm not thrilled with recursion since in practice it can strain implementations of the call stack. Course over. Hope you enjoyed it!
stevebot 12y ago
Edit: Why the downvote? Disagree? I would love to hear more about why this attitude is helpful. I love algorithms, AND I think they are necessary in interviews, but I feel like the tech community has become ridiculous in how they interview for them lately. Example problem: Given two words in a dictionary, transform one word into another, changing one character at a time, using only words in the dictionary. A good interview would recognize most people have no clue how to solve this, give hints and still pass candidates who make a reasonable attempt but fail. Now it seems to be that most places will just fail you, if you don't know the most optimal answer and can't write it out without any syntax mistakes. This is ridiculous, and I have experienced it and this attitude around major tech companies. What this has resulted in is Algorithm trivia. Your ability to succeed is your ability to memorize every algorithm question and approach in existence.
- cloakandswagger 12y ago
  It's easy to see why: algorithms are foundational, and they're the kind of right or wrong test that give binary, merit-based substance to the nebulous process of assessing a candidate. Still, I agree that they're overused. The truth is, the vast majority of modern programming doesn't even involve intensive algorithm writing and is more focused on the design and construction of apps that are nothing more than CRUD operations and business logic.
  - perdunov 12y ago
    I think this is actually not a problem of overusing algorithms, but a problem of correctly separating the job titles related to software development. There are software developers whose work actually requires no knowledge of algorithms, mathematics, or even CS besides their language, framework, and some architectural concepts. On the other hand, there are "software developers" whose primary work is to develop algorithms and computational methods. For historical reasons those roles are not always properly and clearly separated. This can be one of the reasons why we have intimidating algorithmic interviews that are irrelevant to the actual work of the developers who are being interviewed.
- jimmaswell 12y ago
rfrey 12y ago
graycat: you may be hellbanned. (I don't see anything obnoxious in your comment history which is why I mention it.)

358 points by lobo_tuerto 12y ago

It's about time; this is great progress. it seems like they've updated a lot of their computer science stuff -- it used to just be a basic introduction to JS and not really anything theoretical.

RMarcus 12y ago

For others who may be confused (as I was), note in the sidebar that this course is for "introductory computer science algorithms." While I suppose it is most certainly a collection of algorithms, I would generally expect such topics to be listed under "data structures" or "discrete math" at most universities. In my experience, "algorithms" denotes a higher level, more advanced course (OBSTs, flows, stable marriage, ILP/LP...)

gt565k 12y ago
That was my thought exactly! My data structures & algorithms course covered most of these topics and more and that was the 3rd CS class required in the curriculum. The 3000 level algorithms course I took as part of my CS program, included Big O notation, NP completeness, P vs NP, advanced uses of graph algorithms, dynamic programming, reducability.
quonn 12y ago
While the algorithm course at my university consisted mostly of calculating complexities and was much more difficult in general, there is also Sedgewicks' Algorithms book, which covers many of the topics in this course. So "algorithms" is certainly the correct term.

wodenokoto 12y ago

When I first tried this course a few month ago, the little helpers (think clippy) were driving me nuts! Half way through writing a line of code they would pop up and tell me that my code couldn't execute, maybe I should add a semi colon. It's really distracting and of course code can't execute when you are in the middle of typing an if-statement. It is not helpful at all. On top of that there's no "submit" button (because it is supposed to test continuously) so sometimes when I was done it wouldn't test the code and made it impossible to get a "completion" on parts.

fafner 12y ago
Yes, that's truly annoying. I have a few code examples that are complete but it refuses to accept them without giving any reason. If I try to step forward it says I have to go back. Also in the first example it complained when I was using Math.round for the index calculation and only wanted to accept Math.floor. (although not applicable in this case, I think Math.floor is not the best choice since it won't behave like ints in negative cases)

symlinkk 12y ago

I'm in college right now and I've been wondering...do professional programmers actually think about sorting algorithms on a day-to-day basis? How relevant is this knowledge when it comes to actually making something?

patio11 12y ago
Ask a simple question, get a simple answer: no. While there are some programmers who develop libraries, the majority will just consume well-understood sorting algorithms which are baked into their languages/standard libraries/etc of choice. If you find yourself coding mergesort and you are not in a job interview, a nightmare, or a nightmare of a job interview, you are probably doing something wrong. That said, most of the reason we teach sorting algorithms is to teach algorithms in general, and particularly the consequential lesson that "There are often many methods to doing something that work; these methods are often different in extraordinarily consequential ways; the right method for certain problems -- even ones which look trivial on the outside! --may require literally years of R&D to develop."
- aninhumer 12y ago
  Even ones that look trivial on the inside might take years of R&D to develop.
  - throwaway43 12y ago
    Any examples ?
    - CoreDumpling 12y ago
      http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
    - danieldk 12y ago
      http://mumble.net/~campbell/2014/04/28/uniform-random-float http://mumble.net/~campbell/2014/04/28/uniform-random-float

eliben 12y ago

Taught by Cormen, no less

edem 12y ago

For some reason when I read "Khan Academy" somewhere I instantly associate it with Star Trek and I can't take it seriously.

rm445 12y ago
Well done, you've noticed a tremendous character flaw and now you can strive to correct it. Honestly, how are you going to live life if any reminder of pop culture can distract you from a serious subject? And how are you going to interact with people if noticing such a thing (even if it's tremendously obvious) makes you feel the need to shout about it? Best to knock it on the head now.
- benihana 12y ago
  Jesus dude. It was just an anecdote. It's a hell of a thing to call that a "tremendous character flaw" based on like, literally no evidence other than your assumptions.
  - rm445 12y ago
    Just for clarity, genuinely being incapable of taking anything seriously which sounded like a pop culture reference, would indeed be a tremendously damaging flaw. Of course I don't really believe parent poster has that problem: it was making a little fun as mild chastisement for the terrible comment. I honestly think you could have interpreted it correctly if you hadn't been so quick to take offence.
    - randomnumber53 12y ago
      If you don't actually believe the poster has that problem, why respond the way that you did? Doesn't that make your comment at least as terrible?
- edem 12y ago
  Dude you need to get something for your soreness. I don't take everything seriously and comments on the internet are definitely one of those things. You are like a loser klingon captain whose ship is about to blow up because the Enterprise is firing its photon torpedoes at him. And no I don't care about you downvoting either.

graycat 12y ago

Gee, I saw quicksort but not heap sort! Heap sort is O( n log(n) ) in all cases including worst, and quicksort is O( n^2 ) worst case. O( n log(n) ) is the Gleason bound, the fastest sort there can be on average from comparing pairs of keys so that in that sense heap sort is asymptotically the fastest possible. Dropping the technique of comparing pairs lets us consider radix sort which can be faster, still. The lecture does cover merge sort; good. For graphs, the min cost network flow problem is linear programming, and it turns out that if the arc capacities are integers and start with a basic integer feasible solution, then the simplex algorithm maintains integer solutions and, if merely an optimal solution exists, will find an optimal integer solution. It turns out that this fact is in practice one of the best tools for linear integer programming which generally is in NP-complete. This progress on integer programming is worth noting. For cycling in the simplex algorithm for the min cost flow problem on networks, W. Cunningham, long at Waterloo, has a nice solution based on what he calls strongly feasible basic solutions. For the simplex algorithm for the network flow problem, there are, compared with the simplex algorithm in general, some enormous simplifications -- e.g,. a feasible basis corresponds to a spanning tree of arcs -- and, thus, astoundingly high performance on astoundingly large problems -- this fact should be noted. Maybe I missed it, but I didn't see trees mentioned. Both AVL trees and red-black trees are good examples, that is, balanced binary trees good for collection classes. And B-trees, multi-way branched balanced trees, long important on hard disk (and likely now on solid state disks) for database should also be mentioned. Since need to teach heap sort, should also mention that the heap data structure is good for an easy implementation of fast priority queues, e.g., look at 1 billion numbers one at a time, in any order, and end up with the 100 largest, efficiently. Also there is a modification of the heap data structure that has good locality of reference when doing a lot of virtual memory paging. And for hashing, the clean solution is Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong, Extendible hashing-a fast access method for dynamic files', "ACM Transactions on Database Systems", ISSN 0362-5915, Volume 4, Issue 3, September 1979, Pages: 315 - 344. I'm not thrilled with recursion since in practice it can strain implementations of the call stack. Course over. Hope you enjoyed it!

stevebot 12y ago

Edit: Why the downvote? Disagree? I would love to hear more about why this attitude is helpful. I love algorithms, AND I think they are necessary in interviews, but I feel like the tech community has become ridiculous in how they interview for them lately. Example problem: Given two words in a dictionary, transform one word into another, changing one character at a time, using only words in the dictionary. A good interview would recognize most people have no clue how to solve this, give hints and still pass candidates who make a reasonable attempt but fail. Now it seems to be that most places will just fail you, if you don't know the most optimal answer and can't write it out without any syntax mistakes. This is ridiculous, and I have experienced it and this attitude around major tech companies. What this has resulted in is Algorithm trivia. Your ability to succeed is your ability to memorize every algorithm question and approach in existence.

cloakandswagger 12y ago
It's easy to see why: algorithms are foundational, and they're the kind of right or wrong test that give binary, merit-based substance to the nebulous process of assessing a candidate. Still, I agree that they're overused. The truth is, the vast majority of modern programming doesn't even involve intensive algorithm writing and is more focused on the design and construction of apps that are nothing more than CRUD operations and business logic.
- perdunov 12y ago
  I think this is actually not a problem of overusing algorithms, but a problem of correctly separating the job titles related to software development. There are software developers whose work actually requires no knowledge of algorithms, mathematics, or even CS besides their language, framework, and some architectural concepts. On the other hand, there are "software developers" whose primary work is to develop algorithms and computational methods. For historical reasons those roles are not always properly and clearly separated. This can be one of the reasons why we have intimidating algorithmic interviews that are irrelevant to the actual work of the developers who are being interviewed.
jimmaswell 12y ago

rfrey 12y ago

graycat: you may be hellbanned. (I don't see anything obnoxious in your comment history which is why I mention it.)