6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford

[Home] [Lectures] [Assignments] [Project] [Open Problems] [Piazza] [Accessibility]

Class 5 Video     [previous] [next] [completion form]

[+] Memory hierarchy (L07 + L08): new results on dynamically changing M (instruction-aligned and time-aligned models) and tight bounds on ordered files and list labeling. Problems: O(lg3 n) for label space exactly n, cache-oblivious search trees supporting efficient bulk insert/delete.

This class will focus on describing two exciting new results related to memory hierarchies:

  1. The open problem about cache-oblivious algorithms running on machines with changing cache size has been largely solved. [SODA 2014]
  2. The open problem about optimality of e.g. ordered file maintenance has been solved. [STOC 2012]

Then we'll have solved and open problems as usual. The open problems are already posted, but feel free to continue on old open problems too (e.g. I still think we can make the suggested progress on C04: BST Lower Bound).

[The video still needs to be recorded or encoded. Stay tuned!]

Lecture notes, page 1/4 • [previous page] • [next page] • [PDF]

Lecture notes, page 1/4 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.