Advanced Data Structures
Lecture Notes
Scribe notes for selected lectures are available below. These notes are courtesy of anonymous MIT students unless otherwise noted, and are used with permission.
Handwritten notes by Prof. Demaine and Dr. Schulz are available on the 6.851 class site.
|
LEC # |
TOPICS |
LECTURE NOTES |
|
1 |
Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm |
(PDF) |
|
2 |
Dynamic optimality: independent rectangle, Wilber, and Signed Greedy lower bounds; key-independent optimality; O(lg lg n)-competitive Tango trees |
(PDF) |
|
3 |
Geometric data structures: orthogonal range queries, range trees, fractional cascading |
(PDF) |
|
4 |
Geometric data structures: stabbing queries, interval trees, segment trees, priority search trees, windowing |
(PDF) (PDF) |
|
5 |
Geometric data structures: kinetic data structures and ray shooting (1) |
(PDF) |
|
6 |
Geometric data structures: ray shooting (2), partition trees |
(PDF) |
|
7 |
Strings: suffix tree, suffix array, document retrieval |
(PDF) (Courtesy of Mark Chen. Used with permission.) |
|
8 |
Strings: level ancestor, static LCA (part 1) |
(PDF) |
|
9 |
Strings: static LCA (part 2) Integers: van Emde Boas, y-fast trees |
(PDF) |
|
10 |
Integers: fusion trees |
(PDF) |
|
11 |
Integers: predecessor lower bound via round elimination |
(PDF) |
|
12 |
Integers: sorting in linear time for w = O(lg2+ε n), priority queues |
(PDF) |
|
13 |
Integers: tree decompositions, marked ancestor upper bound, decremental connectivity in trees |
(PDF) |
|
14 |
Dictionaries: FKS and cuckoo hashing |
(PDF) |
|
15 |
Dictionaries: deterministic dictionaries |
|
|
16 |
Dynamic graphs: dynamic trees (link-cut trees) |
(PDF) |
|
17 |
Dynamic graphs: overview, Euler tour trees, dynamic connectivity in O(lg2n) |
(PDF) |
|
18 |
Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity |
(PDF) |
|
19 |
Temporal data structures: persistence, retroactivity |
(PDF) |
|
20 |
External memory / cache-oblivious: models, B-trees |
(PDF) |
|
21 |
External memory / cache-oblivious: ordered-file maintenance, list labeling, order queries, priority queues |
(PDF) |
|
22 |
Succinct data structures: rank, select, tries |
(PDF) |
|
23 |
Succinct data structures: compact suffix arrays and trees |
(PDF) |
Assignments
Policies
- There will be a weekly one-page assignment, up to 9 assignments in total.
- You may skip any one problem, or we will ignore the problem with the lowest grade. If you volunteered to scribe twice, we will ignore the lowest two grades.
- The answers must be typeset in LaTeX. The answersmustfit in one page, or your solution will not be read. Use at least 10 pt font and 1 inch margins. This rule is meant to prepare you for writing research publications: one often has to explain great ideas in a very limited number of pages.
- Solutions do not need to include all calculations, trivial details etc. Just prove to us that you found the solution, and you understand it well.
- Problems will be graded on a 0-2 scale:
- o0 = You didn't get it. Filling one page to the brim does not mean you can't get zero. Please don't write stuff you know is wrong.
- o1 = Your solution was ultimately a good one, but the write-up contained significant errors or omissions.
- o2 = (We think) you got it.
Assignments
Solutions are courtesy of the course TA, Aleksandar Zlateski, and are used with permission.
|
ASSN # |
TOPICS |
ASSIGNMENTS |
SOLUTIONS |
|
1 |
Transposing a matrix, logarithmic redux |
(PDF) |
(PDF) |
|
2 |
Query time kd-trees, segment stabbing |
(PDF) |
(PDF) |
|
3 |
Ray shooting in simple polygons |
(PDF) |
(PDF) |
|
4 |
Analysis partition trees, speed up with LCP array |
(PDF) |
(PDF) |
|
5 |
Cartesian trees in linear time, space requirements for integer data structures |
(PDF) |
(PDF) |
|
6 |
Dynamizing static search structures |
(PDF) |
(PDF) |
|
7 |
Finding the most significant 1 bit |
(PDF) |
(PDF) |
|
8 |
Cuckoo hashing, conditional expectations |
(PDF) |
(PDF) |
|
9 |
Link-cut tree analysis, dynamic partition of [n] into intervals |
(PDF) |
(PDF) |