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

Advanced Data Structures (2017)

courses.csail.mit.edu

Post reply on HN
Print view View original

81–89 of 89 posts

Re: Advanced Data Structures (2017)

#81

Post by 0x445442 »

joebergeron wrote: post #10

Hey! I’m a coauthor with this guy :^). Incredibly fascinating (and extremely smart) dude. His interest in origami is what drew me to MIT in the first place, since I was interested in it as well from a young age. A few years ago I took his class on the computability/complexity theory of folding, and we ended up solving an open problem in the field and published a paper out of it [0]. If you had told highschool me some…

The first 17 minutes of the Time Travel lecture is the best introduction to Git I've seen and he didn't even mention Git.

Re: Advanced Data Structures (2017)

#83

Post by Mijka »

joebergeron wrote: post #10

Hey! I’m a coauthor with this guy :^). Incredibly fascinating (and extremely smart) dude. His interest in origami is what drew me to MIT in the first place, since I was interested in it as well from a young age. A few years ago I took his class on the computability/complexity theory of folding, and we ended up solving an open problem in the field and published a paper out of it [0]. If you had told highschool me some…

Recognized his face and name instantly ! I know him by reputation from his origami work and appearance in a documentary, seems to be a very cool guy.

Re: Advanced Data Structures (2017)

#84

Post by elevenoh »

chrisweekly wrote: post #70
dcolkitt wrote: post #63

Earlier quoted context omitted.

> As a busy self-learner, when is it time to learn data structures in depth? From a practical perspective... The best sign is if you're spending a lot of time trying to wrangle performance or scalability and most of the bottleneck is inside the standard data structures. E.g. if you're spending too much time or memory doing dictionary lookups, then it may be worth looking into Bloom filters. But if dictionary lookups…

> "Effectively that means something like being able to translate between business requirements and academic language. "Oh, I need something that works on directed graphs, handles cycles, logarithmic in space, linear in average case time, resistant to adversaries, respects cache locality during lookup, and behaves deterministically." Excellent comment! I'd love to see a catalog of data structures that documented those…

Would also like to know if there's a resource like this out there.

Re: Advanced Data Structures (2017)

#85

Post by amrx431 »

pfdietz wrote: post #78
amrx431 wrote: post #59

Earlier quoted context omitted.

Hi there. What would you suggest to a person who loves these kind of stuff (data structures and algorithms) but finds it hard to develop the underlying intuitions for coming up with these data-structure and algorithm? I personally just hammer down on deliberate practice to recognise patterns and underlying concepts to solve as many problems as I can on my own. I was wondering apart from general DS and Algo what topic…

I recently had someone ask me about a problem in machine learning. The algorithm for it turned out to be something I had read about 30 years earlier, where it was being used to accelerate the simulation of the motion of stars in galaxies. I had never expected to use that algorithm, but its existence, if not details, was there in my long term memory, waiting to surface. So, I suggest you just read everything you can,…

Few questions:

1. Where can I find that algorithm you are talking about?

2. The algorithm which you stated seems a bit complex from the algos taught in the undergrad level, so what are the pre-requisites for understanding it that I must be aware of?

3. What books or papers you would suggest for reading?

4. How the hell you remember something you read decades ago :)?

Re: Advanced Data Structures (2017)

#86

Post by pfdietz »

amrx431 wrote: post #85
pfdietz wrote: post #78

Earlier quoted context omitted.

I recently had someone ask me about a problem in machine learning. The algorithm for it turned out to be something I had read about 30 years earlier, where it was being used to accelerate the simulation of the motion of stars in galaxies. I had never expected to use that algorithm, but its existence, if not details, was there in my long term memory, waiting to surface. So, I suggest you just read everything you can,…

Few questions: 1. Where can I find that algorithm you are talking about? 2. The algorithm which you stated seems a bit complex from the algos taught in the undergrad level, so what are the pre-requisites for understanding it that I must be aware of? 3. What books or papers you would suggest for reading? 4. How the hell you remember something you read decades ago :)?

The ML problem involved, for a set of points on a line, computing the sum (over all the pairs of distinct points) of a function d(x_i,x_j) that is, in some sense, well behaved. The purpose was to compute the similarity of two sets of real numbers.

It turns out this can be done (to sufficient accuracy) in nearly linear time using something called the fast multipole method.

http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/publications/F...

I wouldn't consider the "O(log n) chunks" trick all that complex, btw, although Tarjan did have to point it out to me when I should have used it.

Re: Advanced Data Structures (2017)

#87

Post by dcolkitt »

chrisweekly wrote: post #70
dcolkitt wrote: post #63

Earlier quoted context omitted.

> As a busy self-learner, when is it time to learn data structures in depth? From a practical perspective... The best sign is if you're spending a lot of time trying to wrangle performance or scalability and most of the bottleneck is inside the standard data structures. E.g. if you're spending too much time or memory doing dictionary lookups, then it may be worth looking into Bloom filters. But if dictionary lookups…

> "Effectively that means something like being able to translate between business requirements and academic language. "Oh, I need something that works on directed graphs, handles cycles, logarithmic in space, linear in average case time, resistant to adversaries, respects cache locality during lookup, and behaves deterministically." Excellent comment! I'd love to see a catalog of data structures that documented those…

Unfortunately, I don't have any great suggestions for a single book or resource. (Doesn't mean something good isn't out there, just not anything I've come across.)

For me personally, the best resource has been simply to work through famous papers in the space. Blogs like the Morning Paper, centered around breaking down papers, are also helpful.

Re: Advanced Data Structures (2017)

#88

Post by amrx431 »

pfdietz wrote: post #86
amrx431 wrote: post #85

Earlier quoted context omitted.

Few questions: 1. Where can I find that algorithm you are talking about? 2. The algorithm which you stated seems a bit complex from the algos taught in the undergrad level, so what are the pre-requisites for understanding it that I must be aware of? 3. What books or papers you would suggest for reading? 4. How the hell you remember something you read decades ago :)?

The ML problem involved, for a set of points on a line, computing the sum (over all the pairs of distinct points) of a function d(x_i,x_j) that is, in some sense, well behaved. The purpose was to compute the similarity of two sets of real numbers. It turns out this can be done (to sufficient accuracy) in nearly linear time using something called the fast multipole method. http://www.umiacs.umd.edu/labs/cvl/pirl/vikas…

> Tarjan did have to point it out to me when I should have used it.

Wow, you worked with Tarjan. How cool!!!.

Re: Advanced Data Structures (2017)

#89

Post by pfdietz »

amrx431 wrote: post #88
pfdietz wrote: post #86

Earlier quoted context omitted.

The ML problem involved, for a set of points on a line, computing the sum (over all the pairs of distinct points) of a function d(x_i,x_j) that is, in some sense, well behaved. The purpose was to compute the similarity of two sets of real numbers. It turns out this can be done (to sufficient accuracy) in nearly linear time using something called the fast multipole method. http://www.umiacs.umd.edu/labs/cvl/pirl/vikas…

> Tarjan did have to point it out to me when I should have used it. Wow, you worked with Tarjan. How cool!!!.

Not directly, but he did point out the improvement.
Post reply on HN