6.897: Advanced Data Structures (Spring'05)
[Home]
[Lectures]
[Assignments]
[Project]
[Erik's Notes]
[Accessibility]
Lectures are TR 2:30-4 in 32-141.
Scribing
- Use this template when scribing.
- Submissions must be via email to mip#at#mit.edu
and include a compiled PDF attachment, the LaTeX source, and whatever
figures you use.
- Please give real bibliographical citations for the papers that we
mention in class.
- Scribe notes are by 9pm on the day after lecture. They are posted
immediately without proofreading.
- Later on, we proofread the notes and may instruct scribers to make
some changes. Initial notes are marked "preliminary".
Scribe Notes
- Tuesday, Feb. 1 — dictionaries: worst-case queries, via
FKS and cuckoo hashing
Scribe: Pramook Khungurn. [PDF]
[TeX]
- Thursday, Feb. 3 — dictionaries: deterministic for
polynomial universes, via double displacement
Scribe: Catherine Miller.
[PDF] [TeX
+ tgz with figures]
- Tuesday, Feb. 8 — binary search trees: splay trees,
bounds, dynamic optimality conjecture
Scribe: Jeff Cohen.
[PDF] [TeX
+ tgz with figures]
- Thursday, Feb. 10 — binary search trees:
O(lglg n)-competitive, via Tango trees and Wilber bounds
Scribe: Mike Ebersol.
[PDF] [TeX]
- Tuesday, Feb. 15 — dynamic graphs: dynamic
trees, Euler tour trees
Scribe: Igor Ganichev.
[PDF] [TeX
+ an EPS figure]
- Thursday, Feb. 17 — dynamic graphs: overview, dynamic
connectivity in O(lg2 n)
Scribe: Jelani Nelson. [PDF]
[TeX]
- Thursday, Feb. 24 — dynamic graphs:
Ω(lg n) lower bound for dynamic connectivity
Scribe: Tim Abbott.
[PDF] [TeX
+ tgz with figure]
- Tuesday, Mar. 1 — dynamic graphs: overview for directed
graphs, dynamic reachability
Scribe: Vincent Yeung.
[PDF] [TeX]
- Thursday, Mar. 3 — integers: models, y-fast trees, van
Emde Boas
Scribe: Michael Lieberman.
[PDF] [TeX
+ tgz with auxiliary files]
- Tuesday, Mar. 8 — integers: fusion trees
Scribe: Daniel Kane.
[PDF] [TeX]
- Thursday, Mar. 10 — integers: predecessor lower bound via
round elimination
Scribe: Yoyo Zhou.
[PDF] [TeX]
- Tuesday, Mar. 15 — integers: tight bounds for predecessor
via Beame & Fich upper bounds, message compression
Scribe: Ilya Baran.
[PDF] [TeX]
- Thursday, Mar. 17 — integers: sorting in linear time for
w = Ω(lg2+&epsilon n)
Scribe: Brian Jacokes.
[PDF] [TeX
+ tgz with figures]
- Tuesday, Mar. 29 — integers: equivalence between sorting
and priority queues
This lecture was cancelled and a sketch of the material was given at
the beginning of the next lecture.
Scribe: Jelani Nelson.
[PDF] [TeX]
- Thursday, Mar. 31 — range queries and trees: static LCA,
RMQ
Scribe: Austin Clements.
[PDF] [TeX
+ tgz with figures]
- Tuesday, Apr. 5 — range queries and trees: marked
ancestor upper bound, decremental connectivity in trees
Scribe: Pramook Khungurn.
[PDF] [TeX
+ tgz with figures]
- Thursday, Apr. 7 — range queries and trees: marked
ancestor lower bound
Scribe: Tim Abbott.
[PDF] [TeX]
- Tuesday, Apr. 12 — strings: "3" suffix tree
construction, document retrieval
Scribe: Igor Ganichev.
[PDF] [TeX
+ tgz with figures]
- Thursday, Apr. 14 — strings: searching with wild
cards, level ancestor queries
Scribe: Vincent Yeung.
[PDF] [TeX
+ tgz with figures]
- Thursday, Apr. 21 — strings and geometry:
approximate nearest neighbor via locality sensitive hashing
Guest lecture by Piotr
Indyk. Slides (PDF): introduction,
technical part.
- Tuesday, Apr. 26 — succinct data structures: rank,
select, tries
Scribe: Yoyo Zhou.
[PDF] [TeX]
- Thursday, Apr. 28 — succinct data structures: compact
suffix trees
Scribe: Nick Harvey.
[PDF] [TeX]
- Tuesday, May 3 — external memory / cache-oblivious
Scribe: Dan Ports.
[PDF] [TeX]
- Thursday, May 5 — external memory / cache-oblivious
Scribe: Jeff Cohen.
[PDF] [TeX]
- Tuesday, May 10 — student presentations
Jeff Cohen and Daniel Kane; Igor Ganichev; Michael Lieberman.
A PDF with the abstracts of all projects
(including second day of presentations).
- Thursday, May 12 — student presentations; project due
Tim Abbott and Yoyo Zhou; Jelani Nelson and Vincent Yeung;
Pramook Khungurn; Austin Clements and Dan Ports; Brian Jacokes.