Schedule and Lecture Notes
Class meets Tuesdays and Thursdays, 11:00-12:30, in 1131 Seibel Center. Visitors are welcome! Students are strongly encouraged to suggest specific topics for future lectures or discussion.
- Tue 17 Jan [Jeff's lecture notes]:
- Administrivia; the Bentley-Saxe logarithmic method [BS80]; local rebuilding; lazy deamortization [OL81a]; O(P(n)log n/n) worst-case insertion time.
- Thu 19 Jan [Jeff's lecture notes]:
- Weight-balanced B-trees [AV96]; weak deletions; (lazy) global rebuilding [OL81a]; O(P(n)log n/n) worst-case insertion time and O(P(n)/n + D(n)) worst-case deletion time
- Tue 24 Jan:
- No class—Jeff was at SODA
- Thu 26 Jan [Jeff's lecture notes]:
- Scapegoat trees [A89, A99,
GR93]: local and global rebuilding, O(log n)
worst-case search and amortized update time
Splay trees [ST85,T83]: rotations, roller-coasters and zig-zags, weighted amortized analysis, O(log n) amortized time, static optimality theorem, static finger theorem
- Tue 31 Jan [Jeff's lecture notes]:
-
Dynamic optimality and other splay tree conjectures [ST85, T83], Wilber's interleave lower bound for dynamic BSTs [W87, DHIP04]
- Thu 02 Feb [Jeff's lecture notes]:
-
Wilber's alternation bound [W87], key-independent optimality [I05], tango/multisplay trees [DHIP04, WDS06], rectangle cover bound [DSW05]
- Tue 07 Feb [Chris Obsorn's scribe notes]:
- Dynamic forest maintenance with link-cut trees [ST83, T83]: CUT, JOIN, and FINDROOT in O(log n) amortized time
- Thu 09 Feb [Joseph Elble's scribe notes]:
- More dynamic forest maintenance:
• Lazy propagation: MINPATHCOST,
ADDPATHCOST, and EVERT in O(log n) amortized time with link-cut trees
[ST83, T83]
• CUT, JOIN, FINDROOT, MINSUBTREECOST, ADDSUBTREECOST, and EVERT in O(log n) amortized time with Euler-tour trees [HK99]
• sketches of topology trees [F97], top trees [AHLT05], and rake-compress trees [TW05]
- Tue 14 Feb [David Klempner's scribe notes]:
- Dynamic graph connectivity: INSERT and DELETE in O(log2n) time, CONNECTED? in O(log n / log log n) time [HLT98]
- Thu 16 Feb [Reza Zamani's scribe notes]:
- Lower bounds for dynamic graph connectivity [PD06]: cell probe model [M99], little birdie principle, partial permutation sums
- Tue 21 Feb:
- Lower bounds for dynamic graph connectivity: set separators, the end [PD06]
Kinetic data structures: intro, desiderata (compact, responsive, local, efficient), some easy examples
[BGH99, G05]
- Thu 23 Feb [Tracy Grauman's scribe notes]:
- More kinetic data stuctures [G05]: kinetic heaps/heaters/hangers [BGR03, FF02], kinetic tournaments [BGH99]
- Tue 28 Feb-Thu 09 Mar:
- No class—Jeff was at Dagstuhl and Oberwolfach
- Tue 14 Mar:
- Range trees, multilevel data structures [AE99], fractional cascading [CG86a,CG86b], segment trees [BW80, EM81]
- Thu 16 Mar:
- Filtering search [C86]: hive graphs, window lists, interval trees [E83a,E83b], priority search trees [M85]
- Tue 21 Mar-Thu 23 Mar:
- No class—spring break
- Tue 28 Mar:
- Word-level parallelism: atomic pointer machine vs. integer RAM, PSPACE in polynomial time(!) [HS74], van Emde Boas structure [E75], y-fast trees [W83]
- Thu 30 Mar:
- Y-fast trees concluded [W83]; fusion trees [FW93]: overview, ingredients, sketches
- Tue 04 Apr:
- Fusion trees concluded [FW93]: approximate sketches
Lower bounds for predecessor queries [BF02]: colored predecessors, cell probe complexity = communication complexity, Round Elimination Lemma
- Thu 06 Apr:
- Lower bounds concluded [BF02]: Any colored predecessor protcol requires Ω(min{logaw, logbn}) rounds
- Tight cell probe bounds [BF02, PT06]: Θ(min{lg n/lg w, lg w/lg(a/lg n), lg w/lg lg w})
- Tue 11 Apr:
- Fast integer sorting: O(n log(w/log n)) time via range reduction
[KR84],
O(n) time for (w/lg n lg lg n)-bit integers via packed mergesort
[AH97]
- Wed 12 Apr:
- Fast integer sorting: O(n log log n) time for all w and O(n) time for w = Ω(log2+ε) [AHNR98]; equivalence between sorting and priority queues
- Thu 13 Apr:
- Lowest common ancestor queries in trees and 1-dimensional range-min queries in O(n) space and O(1) time.
Project overview
- Tue 18 Apr:
- Persistent data structures: version tree, fat nodes, path copying
- Wed 19 Apr:
- Full persistence: node splitting
- Thu 20 Apr:
- Confluently persistent concatenable lists
- Tue 25 Apr:
- Retroactive data structures