Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithms

khanacademy.org

Post reply on HN
Print view View original

71–80 of 163 posts

Re: Algorithms

#71

Post by snovv_crash »

joshwcomeau wrote: post #65
willhslade wrote: post #62

Earlier quoted context omitted.

For software engineers, algorithmic complexity is a good filter for, say, Javascript hackers vs people with a university education in computer science. Just saying.

And in your mind, "javascript hackers" are worse than "people with a university education in computer science" at doing modern front-end web development? In my experience, building performant web applications is much more about things like reducing bundle size, making sure animations are hardware-accelerated, being smart about _when_ you do complex work... The cost of using an O(n^2) algorithm over an O(n) algorithm…

If the 'javascript hacker' doesn't learn about the difference between iterating through a list and binary searching, and how/when one is better than the other, yes it is a problem.

I say this as a self taught programmer who studied a non-CS engineering well after learning about big-O.

Re: Algorithms

#72

Post by hal9000xp »

wopwopwop wrote: post #70
hal9000xp wrote: post #10

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

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?

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.

Re: Algorithms

#73

Post by snovv_crash »

wopwopwop wrote: post #70
hal9000xp wrote: post #10

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

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?

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.

Re: Algorithms

#75

Post by contravariant »

evahop wrote: post #60

Can anyone recommend an alternative introduction to asymptotic notation?

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.

Re: Algorithms

#76

Post by joatmon-snoo »

wopwopwop wrote: post #70
hal9000xp wrote: post #10

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

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?

It's just caching.

Recursion not required, iterative DP solutions are things too.

Re: Algorithms

#77

Post by stale2002 »

throwaway2016a wrote: post #45
stale2002 wrote: post #26

Earlier quoted context omitted.

Of course! But how are you going to know WHICH library function to use if you don't know what to look for in the first place? Knowing that a problem at hand requires a certain solution is important.

You use the one labeled "sort" and trust the standard library chose reasonable defaults. It's not like the standard lib is going to use bubble sort. If the reasonable defaults aren't good enough... you're in the 10%.

It is not about choosing "sort" it is about knowing if you need your data sorted in the first place.

Sure, in some situations it might be obvious, but maybe not obvious for others.

And things that are immediately, blindingly obvious to a 5 year experience programmer may not be obvious to a newbie.

Ex: imagine if you didn't know what a hashtable or a dictionary was and just used single variables for everything.

Re: Algorithms

#78

Post by [deleted] »

nostrebored wrote: post #41
hal9000xp wrote: post #10

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

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.

[deleted]

Re: Algorithms

#79

Post by sixstringtheory »

wopwopwop wrote: post #70
hal9000xp wrote: post #10

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

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?

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

Re: Algorithms

#80

Post by walshemj »

michaelchisari wrote: post #25
tomwphillips wrote: post #23

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…

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.

I would have said Fortran is still the King :-)
Post reply on HN