6 ms·

Algorithms on Khan Academy – a collaboration with Dartmouth College professors

360 points by pamelafox 12y ago

pamelafox 12y ago
I'm Pamela, from Khan Academy. I worked with Cormen and Balkcom on the curriculum over the summer, and learned a lot myself while creating it (I don't remember my uni ever talking about Big-Theta!). I hope that this curriculum will be useful for the range of people interested in algorithms, from high schoolers to engineers studying for interviews. If you have feedback on any of the coding challenges, please click "Report a problem". The automated graders start off strict, and I adjust those based on student feedback. If you have feedback about other parts, please email compsci-feedback at khanacademy.org or pamela @.
- voltagex_ 12y ago
  Will a transcript or text alternative be available for these videos? (or can I help in creating one?) How does this course compare with http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...?
  - jeresig 12y ago
    There will be one! Although there's only a single video (the introduction) - everything else is text or an interactive program. The intro video is being fed to our translators/transcribers now and should be up soon! Oh - and as a comparison to the MIT course, probably the biggest differences is that (upon a quick review): There are no lectures and no textbooks. Everything is available online and there are tons of interactive projects to complete. Edit: If you are interested in providing transcription or translation of the single video this is where you can help! http://www.amara.org/en/videos/muCpy2w3ZIH5/info/what-is-an-algorithm-and-why-should-you-care/ http://www.amara.org/en/videos/muCpy2w3ZIH5/info/what-is-an-... Thanks for the offer :)
    - voltagex_ 12y ago
      Oops! I misunderstood - I'm used to the video-heavy maths tutorials. Thanks for letting me know.
  - pamelafox 12y ago
    There is only one video, everything else is in article format, with embedded diagrams and visualizations. From looking at the video list (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...), that one looks like it focuses a lot on data structures - which we don't talk much about, at least not in what we've released so far. The professors hope to add more over the coming months. I'd say they're complimentary, do them both!
    - psbp 12y ago
      What is the Khan Academy approach to article vs. video formats? IMO, lessons with video introductions then a hybrid of text with interactive exercises as the bulk of the lesson would be ideal. Is KA working towards an ideal combination of methods or are you guys experimenting depending on the topic?
      - jeresig 12y ago
        It really depends upon the subject matter - we're experimenting! For Computer Science/programming education we've been pushing more towards the text/interactive exercise direction. Art History is almost all text and videos (with little interaction). Math is almost all video and exercises (no text). We also have pieces like Cryptography and Information Theory which are video heavy and have some interactive portions: https://www.khanacademy.org/computing/computer-science/cryptography https://www.khanacademy.org/computing/computer-science/crypt... https://www.khanacademy.org/computing/computer-science/informationtheory https://www.khanacademy.org/computing/computer-science/infor... Hope you find some of them interesting!
        ashr 12y ago
        This summer my kids (elementary & middle school) did the Intro to JS and Advanced JS courses. They really got hooked due to interactive creativity and video lessons. The audio narrative was really fun and kept them interested. Therefore, videos and especially the audio narrative style in Intro to JS is something I would vote for and hope that Khan academy continues that even (and especially) for CS courses.
- bhaumik 12y ago
  YES! Thanks so much for helping put this together. I've spent a lot of time looking for valuable resources on Algorithms, Data Structures, and other CS theory concepts. CLRS was highly recommended but without a technical background, I wasn't able to dive in as quickly as I hoped. A few days ago, I purchased a copy of Algorithms Unlocked [1] which was described as a "prequel" to CLRS. This review in particular grabbed my attention: "The people who will get the most out of this book are self-taught programmers who have never taken a course in algorithms but who nevertheless need to know this material." Hopefully there isn't too much overrlap :) BTW, the crytopgraphy & information theory units [2] also look promising. [1] http://www.amazon.com/Algorithms-Unlocked-Thomas-H-Cormen/dp/0262518805 http://www.amazon.com/Algorithms-Unlocked-Thomas-H-Cormen/dp... [2] https://www.khanacademy.org/computing/computer-science https://www.khanacademy.org/computing/computer-science
  - pamelafox 12y ago
    Yes, Cormen thinks that Algorithms Unlocked is actually a much better book for the crowd that would likely use this content. I put more links in this article at the end, with recommendations from someone who runs an Algorithms study group for mostly self-taught programmers: https://www.khanacademy.org/computing/computer-science/algorithms/algorithms-more-learning/a/where-to-go-from-here https://www.khanacademy.org/computing/computer-science/algor... The crypto one has a lot of well done videos by Brit Cruise, I've been going through that one personally myself. The info theory is also done by Brit and likely just as cool. There is no programming in either of those, though you can see how they programmed a few visualizations.
  - devnonymous 12y ago
    Just a note I thought might be useful. I am a self-taught programmer as well and personally, I found the O'reilly 'Algorithms in a nutshell'[1] book excellent as both a learning resource as well as reference. Also, it is a /much/ smaller book with a '...focus on application, rather than theory...' and /complete/ working code. [1] http://www.amazon.com/Algorithms-Nutshell-In-OReilly/dp/059651624X http://www.amazon.com/Algorithms-Nutshell-In-OReilly/dp/0596...
- chambo622 12y ago
  This is awesome, as someone going through the interview process this will be my go-to for reviewing. Also, thanks for coming to HackSC! Your talk was great and I think it really inspired a lot of people who were new to the hackathon scene.
- odonnellryan 12y ago
  Thanks so much! :)
voltagex_ 12y ago
The editor for the exercises is based on ProcessingJS - http://processingjs.org/ http://processingjs.org/.
voltagex_ 12y ago
The interactive editor is really cool. Playing around with the drawing functions can create some cool visualisations of the algorithms.
- jeresig 12y ago
  Yeah! We have full curriculum around it, as well (Intro to JavaScript, Game development, and Natural Simulations): https://www.khanacademy.org/computing/computer-programming https://www.khanacademy.org/computing/computer-programming It uses a real-time JavaScript editing framework that we're in the process of open sourcing: https://github.com/Khan/live-editor https://github.com/Khan/live-editor A technical talk on the editor (a bit dated at this point, but most of the points still hold) can be found here: http://ejohn.org/blog/talk-khan-academy-computer-science/ http://ejohn.org/blog/talk-khan-academy-computer-science/
  - deleted 12y ago
    [deleted]
  - voltagex_ 12y ago
    What's the difference between the editor on the course page and the one in the repo?
    - jeresig 12y ago
      None - other than on the course page you can save your progress. A simple demo of the open source editor can be found here: https://khan.github.io/live-editor/demos/simple/ https://khan.github.io/live-editor/demos/simple/
  - _nullandnull_ 12y ago
    Great work! I'm excited to mess around with these.
riprock 12y ago
Just curious, but any chance of Khan Academy adding Discrete Mathematics? Correct me if I am wrong but I don't think coursera/udemy have a course either. The only free online course I am aware of for Discrete Mathematics is MIT OCW 6.042J.
- jeresig 12y ago
  I don't think we have any immediate plans for Discrete math - we are still filling in gaps in our K-12 curriculum. We'll see, maybe someday!
  - mhoad 12y ago
    For what it's worth I would absolutely love a discrete math course from Khan academy.
- vijaygj 12y ago
  Descrete Math is so important to understand the analysis of the algorithms (esp. a new problem). However, I did not find any useful course except the one you mentioned.
  - mikemajzoub 12y ago
    Berkley's Discrete Math class is solid. Lectures on Youtube: http://www.youtube.com/playlist?list=PL-XXv-cvA_iDTidF2dnVq_8lqoigCNSEL http://www.youtube.com/playlist?list=PL-XXv-cvA_iDTidF2dnVq_...
    - vijaygj 12y ago
      This looks latest (fall 2014). Thanks :) Will try it out, I was looking for descrete mathematics course almost 2 years back and could find only MIT one. Good to see some options now.
  - cbgb 12y ago
    MIT also has a pretty solid discrete math course on OCW (I admit, I only watched the lectures, but they were a good refresher for me going into interviews). http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...
CodeCube 12y ago
Just wanted to say thanks, and keep on doing the great work you're doing. KA is one of those places doing good in the world :)
egonschiele 12y ago
Hey there, I'm working on an algorithms book myself: http://www.manning.com/bhargava/ http://www.manning.com/bhargava/ It is meant to be an easier read than CLRS, so I'm excited to see that Khan Academy is thinking along the same lines! I have been thinking about how to make algorithms easier to understand for the last year, so I have some feedback. Some of it is critical, so first I want to say how much I LOVE that Khan Academy is doing this. I really like the interactive nature of this, and I really like that you have comments. I think that's one advantage of e-books vs traditional books: you can't comment on a paper book. I like the sequencing too (it is very similar to my table of contents, which is cool to see). What I don't like: I don't understand why you have four sorting algorithms here. What does insertion sort add over selection sort? I chose to only include selection sort and quicksort in my book. I think once you know those two, you can figure out insertion sort and merge sort if needed. It doesn't add a lot for the reader...I would rather they spend mental effort learning something new. Similarly, why include big-omega notation? I use a writing principle called "just-in-time" vs "just-in-case". It feels like Big-Omega notation was included "just in case" the reader needs to know it for a later section. I would rather it be taught "just-in-time", i.e. right when the reader needs to know big-omega notation to proceed. I struggled with the recursion section. My challenge was: - come up with a real-world example that uses recursion. - come up with an example where the recursive solution is more elegant than a while loop. Otherwise, why use recursion? It looks like you had the same challenges. I wish you guys would swap out the factorial example for something that solves a real problem: looking through a directory for a file, for example. It would be great to see more interactivity in the harder sections too. For example, in "overview of quicksort", I would like to see an animation of the sorting (I am a visual learner). Overall this is still amazing. Algorithms are such a core topic, and there are no good resources for beginners out there. Very happy to see Khan Academy take this step.
- tikhonj 12y ago
  I think a lot of tree code is good for practical recursive examples. Of course, it really helps to have algebraic types and pattern matching because they more clearly expose the recursive structure of both trees and tree-based algorithms. I've also found that writing things out in a patter-matching style, case by case, really helps convey how to think recursively. Instead of trying to run a recursive algorithm in my head, having the separate cases separate makes it easier to consider them one by one.
cenhyperion 12y ago
This looks really useful!

360 points by pamelafox 12y ago

I'm Pamela, from Khan Academy. I worked with Cormen and Balkcom on the curriculum over the summer, and learned a lot myself while creating it (I don't remember my uni ever talking about Big-Theta!). I hope that this curriculum will be useful for the range of people interested in algorithms, from high schoolers to engineers studying for interviews. If you have feedback on any of the coding challenges, please click "Report a problem". The automated graders start off strict, and I adjust those based on student feedback. If you have feedback about other parts, please email compsci-feedback at khanacademy.org or pamela @.

voltagex_ 12y ago
Will a transcript or text alternative be available for these videos? (or can I help in creating one?) How does this course compare with http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...?
- jeresig 12y ago
  There will be one! Although there's only a single video (the introduction) - everything else is text or an interactive program. The intro video is being fed to our translators/transcribers now and should be up soon! Oh - and as a comparison to the MIT course, probably the biggest differences is that (upon a quick review): There are no lectures and no textbooks. Everything is available online and there are tons of interactive projects to complete. Edit: If you are interested in providing transcription or translation of the single video this is where you can help! http://www.amara.org/en/videos/muCpy2w3ZIH5/info/what-is-an-algorithm-and-why-should-you-care/ http://www.amara.org/en/videos/muCpy2w3ZIH5/info/what-is-an-... Thanks for the offer :)
  - voltagex_ 12y ago
    Oops! I misunderstood - I'm used to the video-heavy maths tutorials. Thanks for letting me know.
- pamelafox 12y ago
  There is only one video, everything else is in article format, with embedded diagrams and visualizations. From looking at the video list (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...), that one looks like it focuses a lot on data structures - which we don't talk much about, at least not in what we've released so far. The professors hope to add more over the coming months. I'd say they're complimentary, do them both!
  - psbp 12y ago
    What is the Khan Academy approach to article vs. video formats? IMO, lessons with video introductions then a hybrid of text with interactive exercises as the bulk of the lesson would be ideal. Is KA working towards an ideal combination of methods or are you guys experimenting depending on the topic?
    - jeresig 12y ago
      It really depends upon the subject matter - we're experimenting! For Computer Science/programming education we've been pushing more towards the text/interactive exercise direction. Art History is almost all text and videos (with little interaction). Math is almost all video and exercises (no text). We also have pieces like Cryptography and Information Theory which are video heavy and have some interactive portions: https://www.khanacademy.org/computing/computer-science/cryptography https://www.khanacademy.org/computing/computer-science/crypt... https://www.khanacademy.org/computing/computer-science/informationtheory https://www.khanacademy.org/computing/computer-science/infor... Hope you find some of them interesting!
      - ashr 12y ago
        This summer my kids (elementary & middle school) did the Intro to JS and Advanced JS courses. They really got hooked due to interactive creativity and video lessons. The audio narrative was really fun and kept them interested. Therefore, videos and especially the audio narrative style in Intro to JS is something I would vote for and hope that Khan academy continues that even (and especially) for CS courses.
bhaumik 12y ago
YES! Thanks so much for helping put this together. I've spent a lot of time looking for valuable resources on Algorithms, Data Structures, and other CS theory concepts. CLRS was highly recommended but without a technical background, I wasn't able to dive in as quickly as I hoped. A few days ago, I purchased a copy of Algorithms Unlocked [1] which was described as a "prequel" to CLRS. This review in particular grabbed my attention: "The people who will get the most out of this book are self-taught programmers who have never taken a course in algorithms but who nevertheless need to know this material." Hopefully there isn't too much overrlap :) BTW, the crytopgraphy & information theory units [2] also look promising. [1] http://www.amazon.com/Algorithms-Unlocked-Thomas-H-Cormen/dp/0262518805 http://www.amazon.com/Algorithms-Unlocked-Thomas-H-Cormen/dp... [2] https://www.khanacademy.org/computing/computer-science https://www.khanacademy.org/computing/computer-science
- pamelafox 12y ago
  Yes, Cormen thinks that Algorithms Unlocked is actually a much better book for the crowd that would likely use this content. I put more links in this article at the end, with recommendations from someone who runs an Algorithms study group for mostly self-taught programmers: https://www.khanacademy.org/computing/computer-science/algorithms/algorithms-more-learning/a/where-to-go-from-here https://www.khanacademy.org/computing/computer-science/algor... The crypto one has a lot of well done videos by Brit Cruise, I've been going through that one personally myself. The info theory is also done by Brit and likely just as cool. There is no programming in either of those, though you can see how they programmed a few visualizations.
- devnonymous 12y ago
  Just a note I thought might be useful. I am a self-taught programmer as well and personally, I found the O'reilly 'Algorithms in a nutshell'[1] book excellent as both a learning resource as well as reference. Also, it is a /much/ smaller book with a '...focus on application, rather than theory...' and /complete/ working code. [1] http://www.amazon.com/Algorithms-Nutshell-In-OReilly/dp/059651624X http://www.amazon.com/Algorithms-Nutshell-In-OReilly/dp/0596...
chambo622 12y ago
This is awesome, as someone going through the interview process this will be my go-to for reviewing. Also, thanks for coming to HackSC! Your talk was great and I think it really inspired a lot of people who were new to the hackathon scene.
odonnellryan 12y ago
Thanks so much! :)

voltagex_ 12y ago

The editor for the exercises is based on ProcessingJS - http://processingjs.org/ http://processingjs.org/.

voltagex_ 12y ago

The interactive editor is really cool. Playing around with the drawing functions can create some cool visualisations of the algorithms.

jeresig 12y ago
Yeah! We have full curriculum around it, as well (Intro to JavaScript, Game development, and Natural Simulations): https://www.khanacademy.org/computing/computer-programming https://www.khanacademy.org/computing/computer-programming It uses a real-time JavaScript editing framework that we're in the process of open sourcing: https://github.com/Khan/live-editor https://github.com/Khan/live-editor A technical talk on the editor (a bit dated at this point, but most of the points still hold) can be found here: http://ejohn.org/blog/talk-khan-academy-computer-science/ http://ejohn.org/blog/talk-khan-academy-computer-science/
- deleted 12y ago
  [deleted]
- voltagex_ 12y ago
  What's the difference between the editor on the course page and the one in the repo?
  - jeresig 12y ago
    None - other than on the course page you can save your progress. A simple demo of the open source editor can be found here: https://khan.github.io/live-editor/demos/simple/ https://khan.github.io/live-editor/demos/simple/
- _nullandnull_ 12y ago
  Great work! I'm excited to mess around with these.

riprock 12y ago

Just curious, but any chance of Khan Academy adding Discrete Mathematics? Correct me if I am wrong but I don't think coursera/udemy have a course either. The only free online course I am aware of for Discrete Mathematics is MIT OCW 6.042J.

jeresig 12y ago
I don't think we have any immediate plans for Discrete math - we are still filling in gaps in our K-12 curriculum. We'll see, maybe someday!
- mhoad 12y ago
  For what it's worth I would absolutely love a discrete math course from Khan academy.
vijaygj 12y ago
Descrete Math is so important to understand the analysis of the algorithms (esp. a new problem). However, I did not find any useful course except the one you mentioned.
- mikemajzoub 12y ago
  Berkley's Discrete Math class is solid. Lectures on Youtube: http://www.youtube.com/playlist?list=PL-XXv-cvA_iDTidF2dnVq_8lqoigCNSEL http://www.youtube.com/playlist?list=PL-XXv-cvA_iDTidF2dnVq_...
  - vijaygj 12y ago
    This looks latest (fall 2014). Thanks :) Will try it out, I was looking for descrete mathematics course almost 2 years back and could find only MIT one. Good to see some options now.
- cbgb 12y ago
  MIT also has a pretty solid discrete math course on OCW (I admit, I only watched the lectures, but they were a good refresher for me going into interviews). http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/ http://ocw.mit.edu/courses/electrical-engineering-and-comput...

CodeCube 12y ago

Just wanted to say thanks, and keep on doing the great work you're doing. KA is one of those places doing good in the world :)

egonschiele 12y ago

Hey there, I'm working on an algorithms book myself: http://www.manning.com/bhargava/ http://www.manning.com/bhargava/ It is meant to be an easier read than CLRS, so I'm excited to see that Khan Academy is thinking along the same lines! I have been thinking about how to make algorithms easier to understand for the last year, so I have some feedback. Some of it is critical, so first I want to say how much I LOVE that Khan Academy is doing this. I really like the interactive nature of this, and I really like that you have comments. I think that's one advantage of e-books vs traditional books: you can't comment on a paper book. I like the sequencing too (it is very similar to my table of contents, which is cool to see). What I don't like: I don't understand why you have four sorting algorithms here. What does insertion sort add over selection sort? I chose to only include selection sort and quicksort in my book. I think once you know those two, you can figure out insertion sort and merge sort if needed. It doesn't add a lot for the reader...I would rather they spend mental effort learning something new. Similarly, why include big-omega notation? I use a writing principle called "just-in-time" vs "just-in-case". It feels like Big-Omega notation was included "just in case" the reader needs to know it for a later section. I would rather it be taught "just-in-time", i.e. right when the reader needs to know big-omega notation to proceed. I struggled with the recursion section. My challenge was: - come up with a real-world example that uses recursion. - come up with an example where the recursive solution is more elegant than a while loop. Otherwise, why use recursion? It looks like you had the same challenges. I wish you guys would swap out the factorial example for something that solves a real problem: looking through a directory for a file, for example. It would be great to see more interactivity in the harder sections too. For example, in "overview of quicksort", I would like to see an animation of the sorting (I am a visual learner). Overall this is still amazing. Algorithms are such a core topic, and there are no good resources for beginners out there. Very happy to see Khan Academy take this step.

tikhonj 12y ago
I think a lot of tree code is good for practical recursive examples. Of course, it really helps to have algebraic types and pattern matching because they more clearly expose the recursive structure of both trees and tree-based algorithms. I've also found that writing things out in a patter-matching style, case by case, really helps convey how to think recursively. Instead of trying to run a recursive algorithm in my head, having the separate cases separate makes it easier to consider them one by one.

cenhyperion 12y ago

This looks really useful!