Algorithms

https://www.khanacademy.org/computing/computer-science/algorithms/

by rsandhu • 9 years ago

624 155 9 years ago

khanacademy.org

Kimalsi• 9 years ago

as someone who doesn't know much about this and is trying to join the tech community, what will I achieve through this?

ludicast• 9 years ago

You will learn more about this, and that will make it easier to join the tech community.

--------------------------------------------

Also, to add some signal to my noise, Tom Cormen is apparently one of the designers of the course. He wrote the gigantic encyclopedia of algorithms, as well as a shorter, more-entry-level book on the subject. You'd be in good hands to learn the topic.

And the topic is one that teaches you how to reason about your programs in a way that works across languages and disciplines.

lebanon_tn• 9 years ago

Data structures and algorithms are foundational topics in computer science. While they can seem daunting to beginning programmers, they become very important as you progress into writing more advanced programs. Also, the interview process for software engineers at most companies ask about them almost exclusively.

throwaway2016a2• 9 years ago

they become very important as you progress into writing more advanced programs

As someone with a Computer Science degree I can say that the only times I have ever used any of the algorithms I learned directly was when writing low level C and GoLang. I'm willing to bet 90% of programmers... even those that right "advanced" programs do not use them day to day.

Every algorithm and data structure worth anything has been abstracted out into easy to use libraries years ago.

jeron• 9 years ago

you will learn algorithms and data structures

in all seriousness, algorithms and data structures are essential to computer science theory. When trying to get a job as a software engineer, technical interviews will mainly be problems about algos and data structures.

jingwen• 9 years ago

IDEs help you write correct syntaxes. Algorithms and data structures help you write correct programs.

happy-go-lucky2• 9 years ago

Data structures are ways of organizing and storing data.

Algorithms are recipes or instructions.

Usually it's learning algorithmic techniques for solving various computational problems and implementing algorithmic coding problems in a programming language.

Hope that helps.

SEJeff3• 9 years ago

Datastructures are akin to tools, and Algorithms are like plans. You need to use the tools to implement the plans for building your desired result.

Each "tool" you learn inside and out allows you to build something new. The better you learn them, the more you can build.

happy-go-lucky2• 9 years ago

It's a better explanation than mine.

mirekrusin• 9 years ago

Somewhere between 2-5x salary.

gspetr• 9 years ago

Programming is essentially working with data to solve some kind of real world problem.

When working with algorithms, you’re trying to solve problems efficiently. Your programs should be fast, the wait for a solution should be short.

a3n• 9 years ago

At some point the performance of your code (in time and or space) will really matter. Solid knowledge of algorithms and data structures are essential to getting that right.

Early in my career, actually before my career, I taught myself the available language on our department's mini-computer (don't remember the language or the computer), so I could automate parts of my and my colleagues' job.

I had to sort something, and I innocently "invented" bubble sort to do it. The system administrator visited me the day I first ran it, and told me to stop doing that.

Soon after, I quit and went to school. :)

stale20023• 9 years ago

You basically HAVE to learn this stuff, because it is all anyone every asks about in interviews.

So the answer is "you will become good at tech interviews and be able to get a job"

itsmemattchung• 9 years ago

Let's say you are writing a python program, and you want to simply check if an element is in a list. So, you build a list and then check if 'd' is in the list:

  mylist = ['a','b','c','d'].  
  if 'd' in mylist:
      ...

This works just fine, however, the time it takes, to find the item, grows proportional to the number of items in the list. If your list grows to 1000 items, and the item you are searching for is positioned last, python will check 1000 times. This is known as O(N).

Now, how does the performance compare, when using a set data structure?

  myset = ('a','b','c','d')
  if 'd' in myset:
    ...

Well, underneath the hood, the set stores the data in what's known as a hash. The time it takes to check if an item is (or isn't) in a list does not grow proportional to the number of items in the list—it's always constant: O(1).

ojr• 9 years ago

exposure to more solution techniques into programming problems that you might run into most likely in an interview session.

A lot will say learn this as it is the "core" of programming, but in industry practice I've seen using pure functions (functions that return the same result when the same parameter is passed in) is becoming more commonplace than having a trickier function that mutates a variable differently during each iteration, making it harder to reason about program state. Algorithmic problem solutions usually involve non-pure functions that are not intuitive until you've seen them before. Front-end UI is better built using several pure functions.

SEJeff3• 9 years ago

For anyone wanting to learn algorithms from one of the other heavyweights, not being a C developer, I found this series extremely beneficial:

https://www.amazon.com/Algorithms-Parts-1-4-Fundamentals-Str...

It also helps that Robert Sedgewick has been in compsci forever (got hit PHC in 1975) and is one of the subject matter experts in algorithms.

rajathagasthya• 9 years ago

Or the newer book with Java code.

https://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/03...

Robert Sedgewick also has fantastic algorithms courses on Coursera.

MaxLeiter• 9 years ago

My Data Structures & Algorithms class uses this book - it's fantastic. One nitpick is the "EASYQUESTION" sorting visualizations in the book; they aren't too easy to quickly understand (why use letters instead of numbers demonstrating sorting algorithms or trees?

shamino• 9 years ago

Best book on Algorithms I know of. Extremely pedagogical and clear explanations!

squeaky-clean• 9 years ago

Another vote here. I prefer this book to the CLRS.

sn9• 9 years ago

He's got a pair of Coursera courses that run frequently covering most of the books.

imakecomments5• 9 years ago

I don't like Sedgewick as much as CLRS. Sedgewick seems to assume knowledge in the physical sciences when explaining examples.

hal9000xp2• 9 years ago

It's strange they didn't cover dynamic programming at all. IMO every course should include at least one classical example of dynamic programming. For example:

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

https://en.wikipedia.org/wiki/Longest_common_subsequence_pro...

santaclaus• 9 years ago

They didn't get the memo(ization)...

nostrebored3• 9 years ago

Not being able to implement a DP solution to a problem has killed me in the last two Google interviews I've done. It's important to learn.

wopwopwop5• 9 years ago

I'd never heard of the expression "dynamic programming".

https://en.wikipedia.org/wiki/Dynamic_programming

Am I to understand that it is "just" recursion with caching?

hal9000xp2• 9 years ago

People often make such conclusions about dynamic programming that it's just caching (including myself several years ago).

I do recommend you to read this chapter:

https://people.eecs.berkeley.edu/~vazirani/algorithms/chap6....

After reading this chapter, you can try to understand why Dijkstra and Floyd-Warshall shortest path in graph algorithms work.

These classical and fundamental algorithms combine graph theory with dynamic programming.

snovv_crash3• 9 years ago

Sometimes it involves things like reversing nested loops so you can avoid the caching altogether, but that's the general idea.

Spotting where it can be successfully applied is the hard part.

joatmon-snoo2• 9 years ago

It's just caching.

Recursion not required, iterative DP solutions are things too.

sixstringtheory• 9 years ago

No, it's a way to avoid recursion that can grow exponentially by combinatorially comparing the inputs.

Groxx2• 9 years ago

You might call it a super-set of recursion-with-caching. It's a common technique, but it's not the whole field - you can also start at the "leaves" and summarize your way up to the "start" (and similar-ish things that don't involve recursive thinking at all). In many ways similar, but not actually the same. No call stack, for starters.

"just caching" is also hard to apply to e.g. the tower of hanoi problem.

egonschiele• 9 years ago

Dynamic programming is very similar to caching and memoization, but is not the same thing.

Cursuviam2• 9 years ago

MIT OCW Algorithms, 6.006, which is linked to elsewhere in the comments covers DP if I remember correctly.

vga805• 9 years ago

Another great resource I highly recommend: https://www.manning.com/books/grokking-algorithms

bogomipz3• 9 years ago

I didn't care for this book. I found though the use "doodle drawings" for visualization to be hard to look at and distracting. The book felt half-finished to me. For instance how does an algorithms book not include anything on trees?

I think a much better and free alternative is:

http://interactivepython.org/runestone/static/pythonds/index...

rapfaria• 9 years ago

About the alternative, you can learn about algorithms but be prepared to not learn them in a pythonic way.

chillaxdude2• 9 years ago

I'm currently referring this book to learn Python and Algorithms both in one go. Looks good so far.

PS: I'm an experienced programmer (Perl).

ofek• 9 years ago

Somewhat germane, https://github.com/patmorin/ods is a great resource for data structures.

tomwphillips3• 9 years ago

This is an excellent course and helped me get my current job.

My background is chemistry/chemical engineering. I had applied for a data scientist position. Phone interview included a problem where I was asked about my solution's complexity. I admitted I didn't know about it.

Still got called back for an interview on site, but the weekend before I powered through this course. Unsurprisingly, it came up in the on-site and they were really pleased I had learnt about it. I got the job.

I also found it useful to implement all the algorithms in Python.

michaelchisari2• 9 years ago

Python is the algorithm king as far as I'm concerned. It really gets out of your way and lets you focus on the abstract nature of what you're trying to accomplish.

koolba3• 9 years ago

If Python is the king, C is the court jester juggling knives.

Done well it looks amazing, elegant, and efficient, but in the wrong hands you'll lose your hands.

walshemj• 9 years ago

I would have said Fortran is still the King :-)

catnaroek2• 9 years ago

Hardly. How often is it that you can read an uncommented Python program that implements a tricky algorithm, and you can easily recover basic things like loop invariants?

kinkrtyavimoodh• 9 years ago

I'd disagree. Python abstracts a little too much away, and it's much easier to figure out loop ranges, invariants etc in an algorithm from say Java code.

Python works well when you have to convey your algorithm in a nice succinct functional manner, but that's optimizing for cuteness, not understanding.

GarvielLoken• 9 years ago

Common Lisp is the rebel leader, but is hampered by constant infighting.

ende• 9 years ago

Python is a fantastic language for learning algorithms. It's also a good interface for higher performance, lower level systems language libraries. That said, it is certainly worth the effort to learn one of those systems level languages to pair with python.

I always say that python is like the English of programming languages; it's an amalgamation of other languages, programming paradigms and a rich set of libraries, and often serves as a 'Common Tongue' to glue disparate processes together. There is an inherit risk to that, though. Because it's so easy to transition between object/procedural/functional modes, because it's so easy to tie together so many different interfaces, because it's so easy to `import everything`... it is often too easy to avoid a proper separation of concerns. The flexibility comes with a disincentive towards discipline.

All of the pedantry of systems level language performance and practices aside, even the context switch alone between 'algorithm language' and 'application language' is beneficial to promoting better discipline in both areas.

gech• 9 years ago

And now in your current job how often are you evaluating the complexity and implementing specialized algorithms?

tomwphillips3• 9 years ago

Implementing: never.

Evaluating: occasionally.

In my opinion, an understanding of data structures is _much_ more useful for a data scientist than algorithms.

Why should data scientists know about algorithms? Because data scientists are typically interviewed by computer scientists/software engineers, and that's what they tend to ask.

I recently conducted many phone and on site interviews for a data scientist position. I didn't ask about algorithms.

RandomOpinion• 9 years ago

Back in 2010, I was on a team with a intake of about 1 TB per day of mapping data, all of which needed to be integrated with previous data and condensed into processed output. I quite assure you that we cared a _lot_ about the runtime complexity of our algorithms.

All the really interesting jobs require knowing data structures, algorithms and discrete mathematics well.

imakecomments5• 9 years ago

As a follow up to this resource I recommend,

Algorithms unlocked: https://www.amazon.com/Algorithms-Unlocked-Press-Thomas-Corm...

CLRS: https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...

Both include the same author as the one in this article (Thomas Cormen).

bogomipz3• 9 years ago

I'm a big fan of Kahn and I like the addition of CS material to the site. I hope they continue to add CS material.

malloreon• 9 years ago

If you have the KA app installed this link opens in it!

Which is great, except it takes you to the main list of subject matters, and algorithms isn't in there.

So I'm not able to view this link on my iPad unless I uninstall KA?

lorenzhs2• 9 years ago

There should be a Safari action in the top right where usually you'd have the battery indicator

OJFord• 9 years ago

Am I the only one to think that, for anyone capable of making it through the course, the introduction is incredibly patronising?

Not just the everyday examples of what constitutes an algorithm, but the voice, presentation, etc.

koolba3• 9 years ago

It's hard to pick one thing to tell budding developers they have to learn but Big-O notation is definitely up there.

The follow up to that is understanding what you're counting and why, i.e. branches v.s. statements v.s. dereferences v.s. logical I/Os v.s. physical I/Os ...

bigdataanswers• 9 years ago

why python???? ... any language with functions will do. I mean just create a java class with all public static functions if you want it to work like python (global functions). Its really language agnostic. Your answer will be a number a string or a list of things. All languages can do that.

Im making an explicit opinion that python is no better than any other language for implementing algorithms. HN please prove me wrong in an objective way so we may all learn?

ambulancechaser• 9 years ago

why python???? ... any language with functions will do.

it will. and this person chose python.

HN please prove me wrong in an objective way so we may all learn?

no one cares about the choice of language. This is about learning algorithms.

skylark• 9 years ago

Significant whitespace is great for technical interviews - you don't need to worry about matching brackets and whatnot. No brackets also means you have some more vertical space to work with on the whiteboard.

Beyond that, if your interviewer is fluent in python, list comprehensions can greatly shorten the amount of boilerplate you have to write.

Bartweiss2• 9 years ago

Amusingly, significant whitespace is the one reason I don't like using Python in whiteboard interviews - my handwriting is far from excellent on a board, and I don't want any ambiguity when reading my control flow.

I'll definitely second the list comprehension point, though. Between that and pleasant string support, a lot of standard interview answers are maybe 50% as long in python as Java. Not easier, necessarily, but faster to write and cleaner to read.

tomwphillips3• 9 years ago

I'm not making a claim about Python being "best" for algorithms.

The course uses JavaScript. I recommend re-implementing the algorithms covered in the course in another language that you know well. It helped me really understand what's going on.

In my case, I'm most familiar with Python.

Godel_unicode• 9 years ago

One thing that I like about Python implementations of algorithms is less thinking about types. When I implement my sort algorithm, I just need to say > or < and assume the caller has given those terms meaning.

Not a Java expert, can you do something similar with Java? Maybe with generics?

lorenzhs2• 9 years ago

Yes, generics in Java or templates in C++ is how any algorithms library would handle this. Any type passed into such a function needs to possess the required operators and functions or it will fail to compile/run.

jwdunne• 9 years ago

I'm no expert but due to the language I think you need to specify types somewhere. It just offloads it to your test code as opposed to the algorithms.

With python, your algorithm will work with the primitives without specifying either in the algorithm or test code. You only need to specify type, i.e maybe a new class and definitely instantiation, if you want to use something more abstract.

This would be true of Ruby and other dynamically typed languages. For beginner algorithms courses at least, a dynamically typed languages makes more sense since the algorithms taught are only clouded by typing. Complexity theory still applies and what not.

Maybe if learning algorithms that do heavy crunching, a lower level language, probably with static types, may be used but by that point you're not going to mind type info.

morbidhawk• 9 years ago

I agree with this. For me, I'm using the language I'm currently using at work (C#) to learn them better. If I'm going to be tested (in tech interviews) in the language I know my bet is that it'd be better to know the C# way of doing it and knowing how to implement it using C# conventions. I haven't interviewed yet, but this is just the hunch I have if the goal is to do well in a tech interview

dang• 9 years ago

We detached this subthread from https://news.ycombinator.com/item?id=13654240 and marked it off-topic.

benchaney• 9 years ago

"HN please prove me wrong in an objective way so we may all learn?"

Your issue isn't so much being wrong as lacking a coherent and relevant point in the first place.

waynecolvin4• 9 years ago

I don't like Python either but it's out there and a fact of life. You use whatever a client requires.

Dictionaries, sets and lists can be nice though.

Go here( https://www.thecodingforums.com/threads/performance-sets-vs-... ) and search-find "Terry Reedy".

waynecolvin4• 9 years ago

You might be complaining about students being taught Python and it becoming their "blub" language. We all start somewhere, and you can indeed go far with Python in some fields. It's popular with scientists for instance.

http://www.paulgraham.com/avg.html

http://www.lessonsoffailure.com/tag/paul-graham/ <-- note "flamewar" in the title!

j2kun• 9 years ago

I understand that the focus on sorting is to have a simple application that everyone can understand. But I can't seriously expect people to get that excited about sorting. I sure didn't. It's not like we don't have tons of other applications that demonstrate the same principles.

evahop3• 9 years ago

Can anyone recommend an alternative introduction to asymptotic notation?

contravariant3• 9 years ago

Different in what way?

The general idea is that something takes O(f(n)) time if it takes at most C·f(n) time for some constant C and all but finitely many values of n. The 'all but finitely many values' is what makes this definition 'asymptotic'. Basically 'O(f(n))' ignores constant factors and the behaviour at 'small' n (i.e. small inputs), the reasoning behind this is that an algorithm in O(f(n)) is faster than any algorithm not in O(f(n)) provided you make the input big enough.

The little o, big Omega, big Theta are just small variations on this, which won't be too hard to understand if you get the general concept, and really the distinction isn't too important usually, just know that O(f(n)) gives an upper bound, not necessarily the best possible upper bound. To understand the big-O notation better it might help to have some basic knowledge of limits.

evahop3• 9 years ago

The information made intuitive sense to me. I just couldn't apply what was read directly to the exercises. It felt as though something crucial had been omitted. That something turns out to be calculus.

girzel• 9 years ago

My high-school-age daughter is using Khan Academy to learn about logarithms for her math class. She was telling me about it, and I thought "hmm, maybe I should finally figure out what Big-O actually means". Now here we are! I guess we'll both be on KA tonight.

contravariant3• 9 years ago

Odd choice to start with the iterative factorial before moving on to the recursive one. Usually it's the other way around, since the iterative algorithm is faster and uses less memory.

mildbow• 9 years ago

Recursive might be harder to grok to someone new because of the implied stack.

However, once you understand the iterative version, it's probably easier to understand how the recursion is actually working.

wopwopwop5• 9 years ago

Thanks for the link. However, it seems just a subset of Cormen et al.

fahimulhaq• 9 years ago

We at educative.io re-published this course as a free course with implementations in Java, C++ and Python (in addition to Javascript).

https://www.educative.io/collection/10370001/760001

One of the authors - Professor Balkcom is our advisor as well.

bhu1st• 9 years ago

Here is Princeton's Algorithm text I've found useful (The code is in JAVA though): http://algs4.cs.princeton.edu/home/

Pair this up with this excellent lecture by the authors Sedgewick and Wayne: https://www.coursera.org/learn/algorithms-part1/home/welcome

b3b0p2• 9 years ago

The Coursera Stanford [0] and Princeton [1] courses start again soon, February 20 to be exact. Not sure which one is better, but to refresh my atrophied CS skills of 10 years I've joined the Stanford course. Not sure how it compares to the Khan Algorithms course. Anyone have any feedback?

[0] https://www.coursera.org/learn/algorithm-design-analysis/

[1] https://www.coursera.org/learn/algorithms-part1/

bootload• 9 years ago

EdX as well,

- 6-00-1x https://www.edx.org/course/introduction-computer-science-mit... (started)

- 6.00.2x https://www.edx.org/course/introduction-computational-thinki... (March)

All are good and are pitched at various levels of complexity. The Princeton course uses Java. Okay if you're into that sort of language/thinking. MIT is using Python. Found one using lisp, "Systematic Program Design" ~ https://www.edx.org/xseries/how-code-systematic-program-desi...

imakecomments5• 9 years ago

This is just my opinion and I'm sure it differs from others...

Roughgarden's class is advance and expects mathematical maturity. You may find his course quite fast and rough if you are a beginner.

Sedgwick's class is much easier. He is a bit boring and tries to use "real life" examples (in some instances) from the physical sciences to make the material relatable. This in my opinion detracts from the material. Also, he doesn't always fully explain where he got some of the big ohs here and there.

My advice? Follow MIT's OCW course (it uses CLRS). Supplement it with Algorithms Unlocked, the Khan Academy link in OP and CLRS. If you use those 4 resources and put in the work you'll understand the material.

All 4 sources have Thomas C's DNA touch to it (he is the C in CLRS). So you'll find it consistent when you read from one source to the other. After reading/hearing the same thing about 4 different times in 4 different ways it'll begin to click.

Order of easiness is probably Khan Academy > Algorithms Unlocked > MIT Algorithms Course > CLRS.

Algorithms Unlocked is like "pre-CLRS" and Khan Academy's version is the TL;DR version of Algorithms Unlocked.

Hope this helps.

Below are the links,

https://www.amazon.com/Algorithms-Unlocked-Press-Thomas-Corm...

https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...

https://www.khanacademy.org/computing/computer-science/algor...

https://ocw.mit.edu/courses/electrical-engineering-and-compu...

b3b0p2• 9 years ago

Great feedback and insight. Appreciated. I'll checkout the MIT OCW and Khan Academy first. I'm hardly a beginner, but my skills feel a bit rusty and want to refresh them.

sua_3000• 9 years ago

I've taken both Stanford's and Princetons Coursera courses, and powered through the MIT OCW, and I would say this evaluation is spot on.

If you have to pick only one go with the MIT OCW, and snag a copy of CLRS. I got mine from my local lib. and it gave me more than enough time to work through the problem sets from the mooc.

40acres• 9 years ago

Great post, thanks for the resources.

I find there are a lot of online resources for those looking to learn algorithms and data structures but I've had trouble finding the same breadth and depth of resources surrounding the math behind CS (discrete math, probability, etc.). Any suggestions?

augusto2112• 9 years ago

I'm going through Sedgewick's class right now. Is the MIT OCW's course math heavy? It lists "Mathematics for Computer Scientists" as a prerequisite, I am somewhat familiar with the material, but not in a very deep level. Should I take that one before?

zumu• 9 years ago

Order of easiness is probably Khan Academy > Algorithms Unlocked > MIT Algorithms Course > CLRS.

Where does Roughgarden's course fit in to this?

dwdz• 9 years ago

Any particular reason that you linked MIT course from 2005 instead newer version from 2015?

awesomepantsm• 9 years ago

Talked to someone who wanted to work at one of the big megacorps as a software engineer, asked for advice to pass the interview. I asked them if they could implement quicksort. They said maybe, but they didn't really want to study algorithms. I guess they really didn't want the job after all.

uber1geek• 9 years ago

So what are some good resources for Data Structures out there, you can vouch for ?

oferzelig• 9 years ago

Unbelievable, a guy posts a link to some course and gets 458 HN upvotes (as of this writing).

ankurdhama2• 9 years ago

It is really sad that people still start the discussion about algorithms by telling it as a sequence of actions or operations to accomplish a task. How to go to airport is not an algorithm, how to cook food is not an algorithm.

ponco• 9 years ago

While I agree "following instructions" !== "algorithm", it does serve as a decent bit of context to people who are COMPLETELY unfamiliar with computing let alone programming.

ankurdhama2• 9 years ago

It provides them incorrect context, if you really want to provide context then start with long addition which everyone understands and tell them that it was the first algorithm they learned. Physical activities are not algorithms, algorithms are sequence of calculations on data and there are many many examples that people know about that they learned in elementary mathematics and that can serve as the proper context.

Apocryphon2• 9 years ago

The Algorithm Design Manual by Skiena is pretty great.

https://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena...

It's nearly a third of the length of CLRS, and half of Sedgwick. Much more precise, yet offers more in that it talks about common problem solving uses cases with data structures and algorithms, rather than writing going through the theoretical proofs behind them.

chillaxdude2• 9 years ago

I really love the war problems.

godmodus• 9 years ago

I have to applaud the attempt.

And I'm kind of smirking right now, because again asymptotic got butchered.

I've spent the good part of this semester trying to get my head around a very formal, very dense script of my own algorithms course. And I finally cracked asymptotic. Maybe I'm just dense. But If that's the case, I'm sharing a classroom with others who are equally dense.

We dealt with all 5 classes, big oh, small oh, theta, big omega and little omega. We're required to always give the "most exact" classification for best/avg/worst. Including "does not get as fast as" or "does not get as slow as"

I'm willing to write a "freshman friendly" write up if someone's willing to post it or use it. I'm shit at self publishing.

Algorithms

Related Stories