Algorithms on Khan Academy – a collaboration with Dartmouth College professors

http://cs-blog.khanacademy.org/2014/11/teaching-algorithms-on-khan-academy.html

by pamelafox • 12 years ago

360 43 12 years ago

cs-blog.khanacademy.org

pamelafox5• 12 years 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_5• 12 years 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-comput...?

jeresig5• 12 years 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-... Thanks for the offer :)

pamelafox5• 12 years 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-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!

bhaumik• 12 years 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...

[2] https://www.khanacademy.org/computing/computer-science

pamelafox5• 12 years 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/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.

devnonymous2• 12 years 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/0596...

chambo622• 12 years 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• 12 years ago

Thanks so much! :)

voltagex_5• 12 years ago

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

voltagex_5• 12 years ago

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

jeresig5• 12 years 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

It uses a real-time JavaScript editing framework that we're in the process of open sourcing: 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/

voltagex_5• 12 years ago

What's the difference between the editor on the course page and the one in the repo?

_nullandnull_• 12 years ago

Great work! I'm excited to mess around with these.

riprock• 12 years 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.

jeresig5• 12 years 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• 12 years ago

For what it's worth I would absolutely love a discrete math course from Khan academy.

vijaygj2• 12 years 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• 12 years ago

Berkley's Discrete Math class is solid. Lectures on Youtube: http://www.youtube.com/playlist?list=PL-XXv-cvA_iDTidF2dnVq_...

cbgb• 12 years 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-comput...

ern• 12 years ago

It seems like Khan Academy initially covered whatever Sal Khan found interesting, so there is Calculus, Linear Algebra and Differential Equations. Now that it's become more focused, a side effect is that there's a bigger concentration on grade school-level stuff.

It is a pity though. It would have been great to see KA covering Theoretical CS as well as Discrete Math.

CodeCube• 12 years 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 :)

egonschiele4• 12 years ago

Hey there, I'm working on an algorithms book myself: 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• 12 years 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.

egonschiele4• 12 years ago

Agreed! I snuck a small Haskell example into my book to show the advantages of pattern matching:)

rickdale• 12 years ago

I learned about those four sorting algorithms before ap comp sci in high school. And I know I covered them again in college at some point. Also, I remember talking about big o in the second level cs class in college. So I see them as appropriate curriculum. I am not a genius programmer that wants to figure out two algorithms cause I understand the other two so well. Show them all to me, I'll take in what I can. That being said, I am intrigued that you have a different perspective and I will check out your book to see what you have to say.

egonschiele4• 12 years ago

It is the typical curriculum. I'm curious about why it is appropriate. This should be about practical knowledge, not about "throw every algorithm at them and see what sticks"! That's why I only cover two sorting algorithms in my book. I cover selection sort to teach arrays, and I cover quicksort to teach recursion.

MaysonL• 12 years ago

Try the development of a recursive algorithm for permutations in lexicographical order.

EDIT: added recursive to make the purpose of the suggestion clearer.

pamelafox5• 12 years ago

Great feedback!

I think it helps to have both the sorts there, because it gives the students another opportunity to solidify their understanding of algorithms and because they are indeed expected in things like AP CS. Personally, I find them different enough that I need to spend time on each of them to grasp them- I always have to draw algorithms out when I'm learning them, so it helped me that we had the different diagrams and visualizations for each one.

When making KA content, we have to think both about the student that's going through the content from top to bottom and the student that's "snacking" on the content, like finding it via Google search. So if you knew that a student was going to do the whole thing, you could do more just-in-time teaching - but if you didn't know, then it'd be doing a disservice to the snacker to leave out something like Big O notation, because it'd sure be strange if someone learned Theta and Omega and came away not knowing that last one existed. We did spend a while restructuring asymptotic notation in particular, that was one of the topics we debated different approaches to.

We also debated the use cases for recursion, and if we should include the classic factorial challenge. We went for it in the end, as you saw. I think recursive art is my favorite, and works well in our ProcessingJS environment, but one could argue if that's real world :-) I believe that Devin is working on another tutorial with recursion and specifically on how students can come up with their own recursive algorithm. I'll suggest the looking through directory example to him.

Yep, we are working on a quick sort visualization. I am also quite a visual learner.

The neat thing about online curriculum is that we can get feedback from all the students that use it and improve it over time. We'll probably look at all the feedback in a few months, once it's been out there for a bit, see where the dropoff points are, see what the common questions are, and use that to decide what needs changing.

egonschiele4• 12 years ago

Hi Pamela, Thanks for the detailed response! It made me realize that Khan Academy does work a little differently than a book. You have a lot more readers "snacking" or looking for a reference. So it makes sense to group the Big-O discussion together, cover more algorithms, etc. I <3 KA, keep up the good work!

ashr2• 12 years ago

Towers of Hanoi problem (simple version with 3 towers) is a good practical recursion problem that is stimulating and good for visualization.

devnonymous2• 12 years ago

Just to address the recursion point that the GP brought up. Here is one of the best explanations I saw where the problem not only lends itself to a recursive solution but where the recursive solution is actually the more intuitive one rather than a loop. Also it explains with 'real-world' problems, albeit in the context of the material (game programming):

http://inventwithpython.com/blog/2011/08/11/recursion-explai...

findjashua• 12 years ago

These are all excellent points. As for practical example of recursion, I'd have to say anything implemented with a tree would be a good example.

cenhyperion• 12 years ago

This looks really useful!

Algorithms on Khan Academy – a collaboration with Dartmouth College professors

Related Stories