CS 573: Topics in Analysis of Algorithms (Spring 2006)
Advanced Data Structures

Main PageReferencesHomework and ProjectsAdministrivia


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

Main PageReferencesHomework and ProjectsAdministrivia