6.897: Advanced Data Structures (Spring'05)

Prof. Erik Demaine     TA: Mihai Patrascu

[Home] [Lectures] [Assignments] [Project] [Erik's Notes]

Lectures are TR 2:30-4 in 32-141.


Scribe Notes

  1. Tuesday, Feb. 1 — dictionaries: worst-case queries, via FKS and cuckoo hashing
    Scribe: Pramook Khungurn. [PDF] [TeX]

  2. Thursday, Feb. 3 — dictionaries: deterministic for polynomial universes, via double displacement
    Scribe: Catherine Miller. [PDF] [TeX + tgz with figures]

  3. Tuesday, Feb. 8 — binary search trees: splay trees, bounds, dynamic optimality conjecture
    Scribe: Jeff Cohen. [PDF] [TeX + tgz with figures]

  4. Thursday, Feb. 10 — binary search trees: O(lglg n)-competitive, via Tango trees and Wilber bounds
    Scribe: Mike Ebersol. [PDF] [TeX]

  5. Tuesday, Feb. 15 — dynamic graphs: dynamic trees, Euler tour trees
    Scribe: Igor Ganichev. [PDF] [TeX + an EPS figure]

  6. Thursday, Feb. 17 — dynamic graphs: overview, dynamic connectivity in O(lg2 n)
    Scribe: Jelani Nelson. [PDF] [TeX]

  7. Thursday, Feb. 24 — dynamic graphs: Ω(lg n) lower bound for dynamic connectivity
    Scribe: Tim Abbott. [PDF] [TeX + tgz with figure]

  8. Tuesday, Mar. 1 — dynamic graphs: overview for directed graphs, dynamic reachability
    Scribe: Vincent Yeung. [PDF] [TeX]

  9. Thursday, Mar. 3 — integers: models, y-fast trees, van Emde Boas
    Scribe: Michael Lieberman. [PDF] [TeX + tgz with auxiliary files]

  10. Tuesday, Mar. 8 — integers: fusion trees
    Scribe: Daniel Kane. [PDF] [TeX]

  11. Thursday, Mar. 10 — integers: predecessor lower bound via round elimination
    Scribe: Yoyo Zhou. [PDF] [TeX]

  12. Tuesday, Mar. 15 — integers: tight bounds for predecessor via Beame & Fich upper bounds, message compression
    Scribe: Ilya Baran. [PDF] [TeX]

  13. Thursday, Mar. 17 — integers: sorting in linear time for w = Ω(lg2+&epsilon n)
    Scribe: Brian Jacokes. [PDF] [TeX + tgz with figures]

  14. 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]

  15. Thursday, Mar. 31 — range queries and trees: static LCA, RMQ
    Scribe: Austin Clements. [PDF] [TeX + tgz with figures]

  16. Tuesday, Apr. 5 — range queries and trees: marked ancestor upper bound, decremental connectivity in trees
    Scribe: Pramook Khungurn. [PDF] [TeX + tgz with figures]

  17. Thursday, Apr. 7 — range queries and trees: marked ancestor lower bound
    Scribe: Tim Abbott. [PDF] [TeX]

  18. Tuesday, Apr. 12 — strings: "3" suffix tree construction, document retrieval
    Scribe: Igor Ganichev. [PDF] [TeX + tgz with figures]

  19. Thursday, Apr. 14 — strings: searching with wild cards, level ancestor queries
    Scribe: Vincent Yeung. [PDF] [TeX + tgz with figures]

  20. Thursday, Apr. 21 — strings and geometry: approximate nearest neighbor via locality sensitive hashing
    Guest lecture by Piotr Indyk. Slides (PDF): introduction, technical part.

  21. Tuesday, Apr. 26 — succinct data structures: rank, select, tries
    Scribe: Yoyo Zhou. [PDF] [TeX]

  22. Thursday, Apr. 28 — succinct data structures: compact suffix trees
    Scribe: Nick Harvey. [PDF] [TeX]

  23. Tuesday, May 3 — external memory / cache-oblivious
    Scribe: Dan Ports. [PDF] [TeX]

  24. Thursday, May 5 — external memory / cache-oblivious
    Scribe: Jeff Cohen. [PDF] [TeX]

  25. 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).

  26. 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.