News for hackers. Stuff that matters.

Advanced Data Structures MIT

http://courses.csail.mit.edu/6.851/spring12/

Videos and lectures notes on the advanced data structures course (spring '12; graduate course) at MIT.

Prof. Erik Demaine (youngest MIT professor ever) is one of the most respected researchers in the field.

Topics include: persistent data structures, dynamic graphs, succinct d.s., dynamic optimality, geometry, integers, memory hierarchy, hashing and strings.

Lectures are twice a week (tue, thurs), videos uploaded on the same day.

( 31 comments | 293 points | on HN )
Re:Advanced Data Structures MIT by miggaiowski on Wednesday February 08, 2012 @08:22PM (#3569387)
This is awesome. I've asked professors at my university to have this class, but didn't happen. Couldn't be better to have Erik Demaine teaching it. The video has a great quality and the synced lecture notes are indeed impressive.
Re:Advanced Data Structures MIT by pork on Wednesday February 08, 2012 @10:54PM (#3569729)
Erik Demaine has some of the nicest algorithms lectures, and I would compare him to Gilbert Strang teaching linear algebra.

EDIT: and closer to here, cpercival talking about cryptography and security, or tptacek when he's not grumpy and actually writes an informative, detailed comment.

Re:Advanced Data Structures MIT by gammarator on Wednesday February 08, 2012 @05:32PM (#3568872)
Impressive: the video syncs with the lecture notes: http://courses.csail.mit.edu/6.851/spring12/lectures/L01.htm...
Re:Advanced Data Structures MIT by psykotic on Wednesday February 08, 2012 @08:04PM (#3569340)
He wrote that code for his earlier course on geometric folding algorithms:

http://courses.csail.mit.edu/6.849/fall10/lectures/

You'd enjoy it if you are into computational geometry.

Re:Advanced Data Structures MIT by zvrba on Thursday February 09, 2012 @03:08AM (#3570231)
Too bad that you can't easily judge upfront which of those data structures and algorithms are really usable in practice. For example, fusion trees may seem like a cool idea, but they're totally impractical, as also admitted by the authors (Fredman and Willard) in their original paper.
Re:Advanced Data Structures MIT by ot on Thursday February 09, 2012 @08:40AM (#3571048)
This is definitely true, and marks a strong detachment of asymptotic analysis and theoretical computation models from real-world computers, which are just too complex to reason about them abstractly.

In theoretical computer science, data structures like this are mostly theorems, proving what you can do in a given computation model. This doesn't mean that they have desirable properties in real-world implementations, compared to classical algorithms such as hash-tables, binary trees, tries, ...

However, they are not completely useless in practice, as they usually bring up new ideas that, if properly engineered, can improve on "classical" algorithms. I've been working in this field for the last couple of years and I've observed that in certain niche applications advanced algorithms can really be game-changers (think computational molecular biology).

For example I recently used succinct data structures to engineer a compressed trie that is fairly fast and has very good compression. For example if you have a big set of URLs you can compress it to a size around 12% of the original data and still do searches and retrievals in matter of microseconds. (paper http://siam.omnibooksonline.com/2012ALENEX/data/papers/018.p... , code https://github.com/ot/path_decomposed_tries ) [/shameless plug]

Re:Advanced Data Structures MIT by gritzko on Thursday February 09, 2012 @05:30AM (#3570530)
I don't really understand the point of fusion trees. log log N is a constant from the practical perspective. So, O(logN/loglogN) is simply O(logN). What was the point?
Re:Advanced Data Structures MIT by zvrba on Thursday February 09, 2012 @06:22AM (#3570672)
The point is that O(log N/log log N) is not O(log N): they have broken the informatic-theoretic bound of O(log N) in linear space using "ordinary" operations. (Previous such works used exotic machine models that had little to do with how modern CPUs actually operate.)

Even for N=2^16, you could (in theory) get a 4-fold speedup.

Re:Advanced Data Structures MIT by gritzko on Thursday February 09, 2012 @09:35AM (#3571238)
Aha... and for 2^32 I'll have 5-fold speedup. 6-fold for 2^64 entries, obviously. Frankly, those small-linear-factor improvements tend to be overshadowed by other factors (i.e. whether you hit the cache). I mean, they make sense as an optimization once everything is in place and works correctly. But, designing something ground up to have a small-constant-factor speedup... that reminds me one physics trick. Namely, that by standing next to an infinite wall and by turning a laser pointer fast you make the spot on the wall move faster than c.
Re:Advanced Data Structures MIT by jacobolus on Wednesday February 08, 2012 @05:39PM (#3568907)
Re:Advanced Data Structures MIT by JOnAgain on Wednesday February 08, 2012 @04:54PM (#3568695)
What's the message here? Is this course going to be online? or is just a CS course page from MIT?
Re:Advanced Data Structures MIT by splatterdash on Wednesday February 08, 2012 @04:57PM (#3568710)
The course seems to be online. Here's the page containing video links: http://courses.csail.mit.edu/6.851/spring12/lectures/
Re:Advanced Data Structures MIT by dhruvbird on Wednesday February 08, 2012 @10:12PM (#3569625)
VIDEO LECTURESSSSS!!!!!!!!!!!!!!!!!!!!!!!!!! http://courses.csail.mit.edu/6.851/spring12/lectures/L01.htm...
Re:Advanced Data Structures MIT by dhruvbird on Wednesday February 08, 2012 @10:22PM (#3569647)
That's just sheer excitement!!
Re:Advanced Data Structures MIT by perfunctory on Wednesday February 08, 2012 @05:29PM (#3568860)
This is great! Only one video seems to be available at the moment. Are other videos going to be released at some point?
Re:Advanced Data Structures MIT by vj44 on Wednesday February 08, 2012 @05:40PM (#3568911)
The videos are being released after each lecture (the first lecture was last Tuesday, so there's only 1 video available at this time).
Re:Advanced Data Structures MIT by why-el on Wednesday February 08, 2012 @06:45PM (#3569131)
They are following the same style as Stanford; they release a video each week. It personally helps me because I can set up time for it.
Re:Advanced Data Structures MIT by mprat on Wednesday February 08, 2012 @10:29PM (#3569672)
This isn't an online class at MIT - it is just a course webpage for a class that is offered at MIT this term.
Re:Advanced Data Structures MIT by jshen on Wednesday February 08, 2012 @10:39PM (#3569694)
With videos of the lectures.
Re:Advanced Data Structures MIT by Varun06 on Wednesday February 08, 2012 @04:58PM (#3568719)
Time to refresh data structure and learn some new things...I can see that they have a link for video there...
Re:Advanced Data Structures MIT by karamazov on Wednesday February 08, 2012 @05:06PM (#3568761)
This looks like it's going to be a great course, Prof. Demaine is an excellent lecturer.
Re:Advanced Data Structures MIT by MaxGabriel on Wednesday February 08, 2012 @11:58PM (#3569889)
His energy is just outstanding
Re:Advanced Data Structures MIT by javadyan on Wednesday February 08, 2012 @08:47PM (#3569435)
So, can "outsiders" like myself submit solved problemsets for grading?
Re:Advanced Data Structures MIT by karamazov on Thursday February 09, 2012 @12:04AM (#3569908)
No - this isn't an online class, it's an MIT course for which video lectures are being posted online.
Re:Advanced Data Structures MIT by nsomething on Wednesday February 08, 2012 @09:26PM (#3569520)
Must be typeset in LaTeX? That seems ridiculous.
Re:Advanced Data Structures MIT by bzbarsky on Wednesday February 08, 2012 @10:01PM (#3569590)
Depending on how many students you have and how many graders, it may be a choice of that or arbitrary "if I can't read your handwriting, you get a 0" requirements.

As a separate note, some people think that classes should teach more than just the narrow subject material, and a knowledge of LaTeX is somewhat useful for someone who plans to actually publish CS research.

Re:Advanced Data Structures MIT by karamazov on Thursday February 09, 2012 @12:03AM (#3569906)
Typesetting in LaTeX is a pretty common at MIT - for example, all majors have a technical communication requirement, and most courses that satisfy that requirement stipulate that problem sets be handed in in TeX. It's also not that difficult - TeX is easy to learn - and a helpful thing to be able to do if you plan to publish research.
Re:Advanced Data Structures MIT by cadr on Thursday February 09, 2012 @04:33PM (#3573195)
I don't remember what course I took for that (6-2), but I'm pretty sure I didn't have to use TeX.
Re:Advanced Data Structures MIT by willhunting on Wednesday February 08, 2012 @05:41PM (#3568913)
Hope they keep it up to date, looks great!
Re:Advanced Data Structures MIT by ricksta on Wednesday February 08, 2012 @09:44PM (#3569561)
are there any other classes like these with video made recently?
Re:Advanced Data Structures MIT by mcn on Wednesday February 08, 2012 @10:41PM (#3569702)
The MIT 2005 Introduction to Algorithms course is available.

http://ocw.mit.edu/courses/electrical-engineering-and-comput...