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

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

- Use this template when scribing.
- Submissions must be via email to
and include a compiled PDF attachment, the LaTeX source, and whatever figures you use.`mip#at#mit.edu` - 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".

- 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(lg^{2}*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*= Ω(lg^{2+&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.