6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford

[Home] [Lectures] [Assignments] [Project] [Open Problems] [Piazza]

Class 10 Video     [previous] [next] [completion form]

[+] Succinct (L17 + L18)

This class will review succinct suffix trees via compact suffix trees via compact suffix arrays via rank + select data structures, this time top down instead of bottom up (for variety). I've culled down the details to the essentials so that it's not too long.

(I also corrected a bug on the last page of Lecture 18, so if you've read that (it wasn't covered much in the video), you may want to reread it.)

Unfortunately I am out of town this week, so I will be video conferencing in to give the lecture. I guess you're used to watching me on video so it won't be so different — but this time, it will be live, so you can raise your hand if you have a question and the TAs will shepherd. Also, after the review and Q&A material, I'll be available to talk to you individually about your solved/unsolved progress/ideas — just come up to the laptop in the front of class.

[The video still needs to be recorded or encoded. Stay tuned!]

Lecture notes, page 1/5[previous page][next page][PDF]

Lecture notes, page 1/5[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.