[Home] [General motivation] [Requirements] [Projects] [Scribe notes] [Erik's notes] [Email archive] [Accessibility]

`6897-students@theory.csail.mit.edu`

,
just in case you didn't receive or misplaced one.

- Thu, 9 Jan 2003 14:59:24 -- 6.897 scheduled
- Thu, 23 Jan 2003 08:59:59 -- First class on February 10
- Thu, 23 Jan 2003 09:47:24 -- Re: First class on February 10
- Sun, 9 Feb 2003 19:13:22 -- L1: van Emde Boas
- Tue, 11 Feb 2003 23:02:05 -- Class MOVED tomorrow
- Tue, 11 Feb 2003 23:08:47 -- Class MOVED tomorrow
- Wed, 12 Feb 2003 13:30:28 -- Tuesday is Monday; scribing
- Mon, 17 Feb 2003 19:00:15 -- Tomorrow's lecture; more on scribing
- Tue, 18 Feb 2003 06:47:48 -- Class canceled; enjoy snow!
- Sun, 23 Feb 2003 22:24:07 -- Tomorrow's lecture; more on scribing; notes
- Wed, 26 Feb 2003 09:05:29 -- Class today; projects & ideas; progress
- Sun, 2 Mar 2003 18:21:03 -- Tomorrow's lecture; choosing scribe dates & project
- Wed, 5 Mar 2003 09:43:03 -- Today's lecture; please sign up to scribe
- Mon, 10 Mar 2003 09:03:29 -- Class today
- Wed, 12 Mar 2003 09:57:56 -- Class today; project reminder
- Mon, 31 Mar 2003 08:23:36 -- Today's lecture: strings
- Wed, 2 Apr 2003 09:45:44 -- Today's lecture: LCAs & building suffix trees
- Mon, 7 Apr 2003 08:53:20 -- Today's lecture: succinct data structures
- Wed, 9 Apr 2003 09:36:32 -- Today's lecture: compression
- Sun, 13 Apr 2003 23:32:03 -- Tomorrow's class
- Tue, 15 Apr 2003 09:01:31 -- Scribes notes up for L1,2,3,4,6,9,10
- Tue, 15 Apr 2003 22:58:21 -- Class tomorrow
- Sun, 20 Apr 2003 11:47:50 -- Cache-oblivious lecture notes
- Wed, 23 Apr 2003 10:31:00 -- Class today
- Mon, 28 Apr 2003 10:40:42 -- Today's class: cache-oblivious sorting & priority queues
- Mon, 28 Apr 2003 16:05:34 -- Presentations
- Wed, 30 Apr 2003 08:35:38 -- Today's lecture: tree layout
- Mon, 5 May 2003 10:01:28 -- Today's class: fault tolerance
- Tue, 6 May 2003 16:27:53 -- Class presentations tomorrow
- Tue, 6 May 2003 21:59:42 -- Slides
- Sun, 11 May 2003 21:34:54 -- Class presentations tomorrow (round II)
- Wed, 14 May 2003 08:45:11 -- Final round of presentations today

Thanks for your interest in 6.897 (Advanced Data Structures)! Based on all your responses, the scheduled time for the class is Mondays and Wednesdays at 11:00am-12:30pm. I'll let you know once the room is scheduled. Cheers, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Dear Students, The first lecture of 6.897 (Advanced Data Structures) will be on February 10, because I'm at a conference the first week of the semester. The room is still being booked; I'll keep you posted. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

On Thu, 23 Jan 2003, Erik Demaine wrote: > The room is still being booked; I'll keep you posted. We have 26-168. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Tomorrow will be the first lecture in 6.897 (Advanced Data Structures), at 11-12:30 in 26-168. I'll start out with a bit of administrivia, but will quickly delve into the fun stuff. Both lectures this week will be about "search structures in a fixed universe". The problem is simple: you want to maintain a dynamic set of integers between 1 and u, and you want to be able to insert, delete, and find successors and predecessors. Unlike hash tables, you don't just want to tell whether a query element is in the set, but rather you want to know, if your query element isn't in the set, what are the two closest elements (next smallest and next largest). In other words, an unsuccessful search should report where that element would fit if it were there. We'll start out with one of my overall favorite data structures, designed by Peter van Emde Boas in 1975. This structure supports all operations in O(lg lg u) time. If u is subexponential in n, this is a big improvement over the usual O(lg n) binary search trees. Some of you may have seen the van Emde Boas data structure before, but I'll cover it cleaner and in more depth than usual, and it should be a lot of fun. See you then, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

We got a (somewhat) larger lecture room for the rest of the semester: 24-121. It's on the second floor of building 24, which you can get to e.g. by going above the big lecture room in building 34 (34-100?). Tomorrow's lecture will be about more fun topics related to van Emde Boas, the O(lg lg u) structure for insert/delete/successor: - Recap + Delete - Alternative view of the same structure as a (stratified) tree - Reducing the space to O(n) instead of Theta(u) - y-fast trees, a simple alternative that uses randomization + indirection - O(1)-time (!) insert/delete/successor in the "RAMBO" model I'll probably cover a couple of tools along the way, because they'll be necessary in some of these structures and at various times later on: - dynamic perfect hashing - some basic bit tricks: finding the least-significant 1 bit in a (lg n)-bit word - the "transdichotomous" model of computation See you then! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

We got a (somewhat) larger lecture room for the rest of the semester: 24-121. It's on the second floor of building 24, which you can get to e.g. by going above the big lecture room in building 34 (34-100?). Tomorrow's lecture will be about more fun topics related to van Emde Boas, the O(lg lg u) structure for insert/delete/successor: - Recap + Delete - Alternative view of the same structure as a (stratified) tree - Reducing the space to O(n) instead of Theta(u) - y-fast trees, a simple alternative that uses randomization + indirection - O(1)-time (!) insert/delete/successor in the "RAMBO" model I'll probably cover a couple of tools along the way, because they'll be necessary in some of these structures and at various times later on: - dynamic perfect hashing - some basic bit tricks: finding the least-significant 1 bit in a (lg n)-bit word - the "transdichotomous" model of computation See you then! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Dear Students, Next Monday (Feb. 17) is a holiday, and instead Tuesday (Feb. 18) plays the role of Monday classes. So your Tuesday classes are cancelled, and your Monday classes (like 6.897) move to Tuesday. (It's Tuesday's special week.) Scribes, let's try to keep a fast pace. I'd recommend scribing the same day as the class if you can, because then everything's still fresh. But as an upper bound, you should send me the notes by one week after the lecture you're scribing. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Assuming MIT classes aren't cancelled because of snow, there will be a 6.897 lecture tomorrow (Tuesday Feb. 18) at 11am in 24-121. Topics: - We'll first quickly finish up the van Emde Boas / fixed-universe successor topic by presenting a *constant-time* solution on a slightly different machine model, the RAMBO. If you're a fan of Sylvester Stallone, this may be exactly the action-packed lecture that you haven't been waiting for. The solution is nice & simple, given the intuition we have so far. - Along the way, we'll see our first "bit tricks": how to compute the least-significant 1-bit in a word of memory in constant time, on a (natural) transdichotomous RAM. This tool is really useful & practical; we'll use it all the time, as do various systems such as the Linux kernel. - Then we cover *fusion trees*, which solve a closely related problem, again successor queries, basically what normal search trees do, but without the fixed-universe assumption. I'll briefly mention why Theta(lg n) is the best you can do in the comparision model (or something more general called the decision-tree model). Then I'll show how fusion trees do better--Theta(sqrt(lg n))--on the transdichotomous RAM. This is very slick. Along the way, we see a bunch more bit tricks, and even use van Emde Boas as a subroutine! ------------------ I am a little behind on processing scribe notes. Meanwhile, I've prepared some general guidelines for scribing and what your notes should cover and how. See http://theory.lcs.mit.edu/classes/6.897/spring03/requirements.html Students enrolled in the class should read these over so that you know what's involved (because I was pretty vague about this before). Also, to move things along faster, I've changed the deadlines: you should now send me the first draft of your scribe notes by *2 days* after the lecture. Those who have scribed so far: after class, let's set up a meeting to discuss what you have. See you tomorrow! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

OK, I checked 617-253-SNOW, and MIT classes are canceled today. So Tuesday returns to being Tuesday, and 6.897 is canceled too. The fusion-tree lecture will be delayed to tomorrow (Wednesday), back to our usual schedule. Enjoy the feet of snow! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Tomorrow's 6.897 lecture (Monday Feb. 24 at 11am in 24-121) will continue on fusion trees. (We only scratched the surface on Wednesday, so you needn't worry if you missed the last lecture.) Fusion trees solve a closely related problem to van Emde Boas, again successor queries, basically what normal search trees do, but without the fixed-universe assumption. I'll show how fusion trees do better than lg n--Theta(sqrt(lg n))--on the transdichotomous RAM. This is very slick. Along the way, we see a bunch more bit tricks, and even use van Emde Boas as a subroutine! -------- I've posted a bit more information on the "requirements" webpage about scribe notes: - A LaTeX template which sets the style. - A sample set of scribe notes from another, related class. -------- I've started two webpages with two different sets of lecture notes: - Scribe notes: this is where scribe notes from students wil go, though currently none are complete (still working on it) - Erik's notes: my handwritten notes that I use to lecture. The idea is that these will help students catch up if they miss class, and if anyone wants to look back at recent lectures for which scribe notes aren't yet available. However, these notes are rough and incomplete, and do not serve as replacements to scribe notes or to attending lecture. http://theory.lcs.mit.edu/classes/6.897/spring03/ See you tomorrow! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

In today's class, we'll - Finish up fusion trees by making them dynamic and faster. - Start a rather different topic: self-organizing data structures. Here we'll mainly work in the comparison model, and try to exploit properties of the input distribution without actually knowing it. We'll start with the simplest version of this problem, searching in a linked list, which is already very interesting, and in which there are some open problems and some very recent progress. You may have seen Move-To-Front and related heuristics; we'll analyze those and compare them to several notions of the "optimal" strategy. My written notes for this lecture (#5) are up: http://theory.lcs.mit.edu/classes/6.897/spring03/erik_notes/ ------------------------------------------------------------------------------ I've started a new webpage whose main purpose is to collect ideas for open problems to work on for projects: http://theory.lcs.mit.edu/classes/6.897/spring03/projects.html I'll continue to add to this page as I think up or hear more problems. They vary in difficulty. You do not have to be taking the class for credit to work on these problems, but please let me know if you spend a nontrivial amount of time on a problem, so that I can add you to the list of "interested students" for the problem, so that we can all collaborate instead of working independently. ------------------------------------------------------------------------------ There has already been progress on the first problem, which I posed in the last lecture: speeding up planar point location in a strip through fusion trees. Ian Eslick and I came up with a couple of ideas which seem like they might work, but give us a few days to write it down (or get stuck again). If you don't mind, I'll use the class mailing list as a discussion list for open problems, so that multiple students can contribute. (Once we get the strip case, we'll need to reduce the space usage, and then adapt it to the general planar map case; so there is more to be done.) http://theory.lcs.mit.edu/classes/6.897/spring03/ Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Tomorrow I'll continue on with self-organizing data structures, specifically linear search: - I'll prove that Move-To-Front is not only statically optimal but *dynamically* optimal--as good as any dynamic list, up to a factor of 2. However, this is specific to Sleator & Tarjan's cost model. - I'll mention some open problems relating to improving the factor of 2 in the randomized context. ("Randomized self-organizing linear search" on the projects page.) - Then I'll prove that an omniscient algorithm Order-By-Next-Request is exponentially faster than Move-To-Front or any other online algorithm, for a particular request sequence (list the elements in order). - (If there's time,) I'll prove that the cost of Order-By-Next-Request is within a constant factor of the entropy of the "distribution" induced by the request sequence, which is pretty impressive for linear search. I also added a new open problem about this last algorithm; see "Offline self-organizing linear search" on the projects page. My written notes for this lecture (#6) are now on the webpage. ------------------------------------------------------------------------------ To make sure everyone gets a turn at scribing, I'd like to switch from ad-hoc volunteers to assigned scribing. I think we have more students than lectures, so we can start doubling up, two scribes per lecture. So, please check out http://theory.lcs.mit.edu/classes/6.897/spring03/scribe_notes/ and let me know a few dates during which you'll definitely be here and you'd like to sign up for scribing. (Sorry, I can't predict what topics will be covered when at this point.) ------------------------------------------------------------------------------ In particular, some advanced warning that I'll be away March 13-26, though I will be in email contact. Because of spring break, this only hits two lectures--March 17 & 19--which I'm tentatively canceling. During this time window, March 13-26, you should pick a project, so that we can discuss it when I return (either March 27 of spring break, or the following week). At that point, we are roughly half way through the semester, so you should be started on your project. http://theory.lcs.mit.edu/classes/6.897/spring03/ Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's lecture will finish up self-organizing lists by showing that Munro's Order-By-Next-Request strategy is not only better than all online algorithms, but amortized it achieves the "entropy" bound, which is the best possible for any comparison-based search structure in the stochastic model. Then we'll move on to trees, first optimal binary search trees (which play the role of "static OPT" but are much more interesting). Then we'll cover self-organizing trees and splay trees, how they work, and describe some of the bounds known about them. ------------------------------------------------------------------------------ I've updated the scribe page to sign up people who have sent me email so far (which is not very many). Please send me email about dates you can scribe. Thanks, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

This week's lectures are about recent work attacking the Dynamic Splay Conjecture. Today we'll cover something called the "unified structure", which has a property called the "unified property", both developed by Iacono in 2001. The unified property is stronger than both the dynamic finger property and the working set property (both obtained by splay trees), and in this sense simultaneously captures both spatial and temporal locality. Roughly, it says that it's cheap to access an element that's pretty close (in rank) to an element you've accessed recently. It's open whether splay trees also have the unified property. Along the way, we'll see a very simple way to get a "working set structure" with the working set property. The general idea in this data structure-- exponentially increasing substructures--is used in many other data structures. See you there, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's class will the last about results related to splay trees. We'll finish up the (rather complicated) unified structure. Then I'll describe some other recent and cool results (without proofs) and conjectures, leading to a couple more interesting (and relatively unstudied) open problems related to the dynamic splay conjecture. A reminder that I am going on a trip starting this afternoon, and there are no classes next week. When I get back (during spring break), I expect you all to have thought seriously about what you'd like to work on for your project. Then we can meet in the end of spring break, or the following week. I'll be in email contact throughout, so feel free to email me your ideas. It's important that you start working on your project now, so that there will be time for you to present your project in the final two weeks of the semester. Take a look at the open problems on the projects page; I add to it as I get new ideas. And if you are interested in a problem that another student has marked "interested", please talk to each other to avoid overlap and encourage collaboration. http://theory.lcs.mit.edu/classes/6.897/spring03/projects.html Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Welcome back from spring break. Today's lecture will be about string data structures: - I'll briefly mention what's known about normal substring searching. (Basically, time is linear in the text + substring.) - Then we'll see how this can be vastly improved if we can preprocess the text in which we want to do substring searches, using a *suffix tree*. (Basically, time becomes linear in just the substring.) - We'll see how to build suffix trees in linear time. (It's already cool that they take linear space--linear time is trickier!) - I'll talk about Muthukrishnan's recent related result about *document retrieval*: finding the set of (distinct) documents that contain a substring, even faster than normal suffix trees. - This will lead us into range minimum queries, which can be solved using least common ancestors. - If there's time, I'll show how to do (static) least common ancestors in a tree in constant time, linear space, and linear preprocessing. See you soon, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's lecture will get started by solving the (static) LCA problem in constant time per operation after linear preprocessing. As we saw last class, this result has several implications on range minimum queries, document retrieval, suffix trees, and various string operations. Then we'll cover how to build suffix trees in linear time (once you've sorted the alphabet). This is quite a sophisticated algorithm, and involves a lot of cool techniques involved in many string algorithms. See you there, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's class will be about "succinct data structures", typically static data structures that use the information-theoretic optimum amount of space up to lower-order terms, while still supporting the needed navigational operations quickly. In particular, we'll cover a couple of encodings of binary trees/tries, which use 2 n + o(n) bits of space, instead of the usual Theta(n) *words* of space occupied by child and/or parent pointers. These encodings still support left-child/right-child/parent navigation operations in constant time. The second encoding will also support subtree size, and computing the index of a particular external node, making it usable as a binary suffix trie. Along the way, we'll cover o(n)-size structures for computing the rank of a bit in a bitstring, i.e., the number of 1's to the left of that bit. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's class will be about compression. If I can squeeze it all in (ahem), I'll cover the following topics: - Huffman codes (to the extent you don't already know them). These are optimal prefix codes, and are within an additive constant of entropy, but can be far away from entropy in the multiplicative sense. - Arithmetic coding. Allows us to mix together codes from adjacent letters to get entropy plus an additive constant over the whole string, instead of letter by letter. For a long string, we basically get entropy. - Higher-order entropy. Suppose you consider the probability of a letter occuring given k previous letters of context. You can generalize entropy to capture this notion, and it gives a lower bound on compression schemes that use only k previous letters. - Burrows-Wheeler transform. One of the more recent & cool ideas for compression. I'll describe the algorithm, why it's so cool, and tell you about some brand new analysis that suggests why it's so good, connecting it to higher-order entropy. Along the way, we'll use linear-time suffix-tree construction, move-to-front, and arithmetic encoding! My apologies for being behind on (a) responding about project proposals and (b) posting scribe notes. I will get on top of these soon! http://theory.lcs.mit.edu/classes/6.897/spring03/ Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Tomorrow's class will start moving in the direction of external-memory and cache-efficient algorithms. We'll spend most of our time talking about the "ordered-file maintenance" problem, which asks you to maintain a bunch of elements in order in an array, subject to being able to insert and delete in the middle of the array. The naive solution does this in O(n) time per update, but it turns out that you can do it in O(lg^2 n) time per update! We'll see how this can solve the related problem of order queries (which element comes first?) in a linked list in O(1) time per update. Then, as time allows, I'll start discussing the external-memory model and the cache-oblivious model, which we'll cover in some depth during the next few classes. I have (finally) started putting up scribe notes; more to follow! http://theory.lcs.mit.edu/classes/6.897/spring03/scribe_notes/ Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

All scribe notes for which I have the final form from students (1,2,3,4,6,9,10) are now posted. Authors of these notes should look over the posted version to confirm they look OK. Everyone should let me know if they spot any bugs or have other comments on the notes. http://theory.lcs.mit.edu/classes/6.897/spring03/scribe_notes/ Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Tomorrow's lecture will be more about the external-memory and cache-oblivious models. We'll cover the following topics: - Specifics and justification of cache-oblivious model, in particular, block-replacement strategies and cache associativity. - The familiar "linked list" problem, but now in external memory. We can do inserts and deletes in O(1) memory transfers, and traversals of K elements in the list using O(1+K/B) memory transfers. - The familiar linked list problem, but now in the cache-oblivious model. - We can obtain the same bounds as above if they are both allowed to be amortized; in this case, the traversals "self-adjust" the data structure to fix what the updates broke. - Using the order-file-maintenance data structure, we can obtain the traversal bound worst-case, with an update cost of O((lg^2 N)/B). - Allowing the traversal bound to slide a little, we can reduce the update cost to O((lg lg N)^(2+epsilon) / B). Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

I've just posted a survey paper about cache-oblivious algorithms and data structures, which likely covers everything we will cover in class, and more, including references to the latest work in the area. These will hopefully serve as a useful reference in addition to my lecture notes and scribe notes. http://theory.lcs.mit.edu/~edemaine/papers/BRICS2002/ On the other side, I'd appreciate any comments you have on these notes (especially any bugs you spot), before they go to press in a volume of Lecture Notes in Computer Science. Thanks! Also, a reminder that tomorrow (Monday) is a holiday, so there is no class. http://theory.lcs.mit.edu/classes/6.897/spring03/ Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's class will continue on the cache-oblivious theme: - In general, we'll discuss divide-and-conquer as a tool for cache-oblivious design. - As a simple example, we'll see how to do cache-oblivious median/selection. - We'll see how to do "binary search" by way of a static search tree. (Normal binary search is *not* optimal.) - Building on this structure, we'll see how to do cache-oblivious B-trees. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's class will be about cache-oblivious sorting & priority queues. We'll start with an algorithm called Funnelsort, and then cover a dynamic version called Funnelheap. Both of these algorithms use a common assumption about B and M, called the tall-cache assumption: M = Omega(B^(1+gamma)) for some gamma > 0. The result is that each element can be handled in O((1/B) log_(M/B) (N/B)) amortized memory transfers, which is optimal. Notice that this amortized bound is strictly less than 1! A reminder about projects. Project presentations will be during the last 3 lectures, May 7, 12, and 14. Because there are many projects, you should plan to give one presentation for an entire group project, ideally divided among the members of the group. Please let me know if you are willing to present during the earlier days--May 7 or 12. Also, the project paper is due on the day of the last class, May 14. This deadline is imposed by MIT, because this class does not have a final exam, and the project should not conflict with other classes with final exams. This deadline is fast approaching! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Several people have asked me what equipment will be available for the project presentations. I will make available both an overhead projector and a data projector, so you can give your talk with either overhead transparencies or a laptop. If you want, you can email me PowerPoint or PDF slides and use my laptop, but be warned that PowerPoint presentations are not always portable (you should Include Fonts to minimize the risk). There won't be time for blackboard talks, so these are your options. I'll post who's speaking when, as they sign up, to the following webpage. http://theory.lcs.mit.edu/classes/6.897/spring03/scribe_notes/ Keep in mind that you needn't have as many results if you are presenting earlier (although it is only a matter of a week). All presentations must describe a good, clear problem and why it's interesting. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

The topic of Today's lecture will mix two topics we've seen: tries (as arise in string matching, etc.) and memory hierarchies (external memory & cache oblivious). Specifically, we'll look at the rather fundamental problem of *tree layout*: given a tree of fixed-topology (e.g., a trie), how should it be stored in memory so as to minimize the number of memory transfers required to follow a root-to-leaf path? This is a static data structure problem. There are two main subproblems here: - How do we minimize the maximum cost over all root-to-leaf paths? - How do we minimize the expected cost, given a stochastic distribution of the leaf accesses? Both problems can be solved optimally in polynomial time in the external memory model, and furthermore can be solved optimally up to constant factors in the cache-oblivious model. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's class (which is the last one where I'll be the lecturer) is about fault-tolerant data structures on a pointer machine. Most data structures we see are not tolerant to memory faults. For example, a linked list could be completely lost if the first node became faulty. The idea in fault-tolerant data structures is to contain the damage made by faults by as much as possible, without any replication. Specifically, up to a reasonable limit on faults, we can guarantee that f faults can cause only O(f) nodes to be lost, and the data structure can be recovered to a consistent state that preserves the desired properties of the structure. Such a result is possible for (at least) stacks, linked lists, and trees; I'll focus on the first two. Along the way, we'll get to use data structures for list labeling. See you there, Erik P.S. If you have not yet signed up for a presentation or are not listed on http://theory.lcs.mit.edu/classes/6.897/spring03/scribe_notes/ then send me email now! -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

I'd like to start the remaining classes right at 11am instead of the usual 11:05, to make a little more room in the (already tight) presentation schedule. I hope this isn't a problem for anyone. Tomorrow we'll have the following 6 groups presenting: * XML-related data structures -- David Malan * Partial-sum data structures -- Mihai Patrascu * RAMBO data structures -- Jonathan Brunsman and Sonia Garg * RAMBO data structures -- Loizos Michael * Offline linear search -- Ilya Baran, Denis Cebikins, and Lev Teytelman * Nearest-neighbor data structures -- Ray Jones Each presentation will be at most 15 minutes, including questions & switchover time. So try to keep the body of your presentation at most ~12 minutes. In each of the two classes next week, there are 7 presentations, so each presentation is less than 13 minutes including questions & switchover, so the body should be at most ~10 minutes. Please think hard about how to fit the problem description, motivation, intuition, and high-level descriptions of ideas/results into such a short presentation! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Dear Students, As part of the class requirements, please email me a copy of your presentation (unless it is not electronic, in which case please give me a photocopy). If you can email/bring me a copy *before* your presentation, that would be ideal. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

A reminder that classes this week will start at exactly 11am (not 11:05am), to give a few more minutes for presentations. Tomorrow we'll have the following 7 groups presenting in this order: * Amorphous data structures -- Jake Beal * Financial data structures -- William Kwong * Distributed data structures -- Ben Leong * Distributed data structures -- Rui Fan and Sayan Mitra * Higher-dimensional RAMBO data structures -- Chris Collier * Higher-dimensional van Emde Boas -- Sid Sen and Shantonu Sen * String data structures -- Alexandr Andoni and Cristian Cadar As I mentioned before, each presentation is less than 13 minutes including questions & switchover, so the body should be at most ~10 minutes. Please send me your slides if you haven't already. See you there! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Today's speakers will be * Minimum spanning hypertrees -- Percy Liang * Nearest-neighbor data structures -- Gautam Jayaraman * Dynamic text indexing -- Hans Robertson * Proximate point location -- Jeff Lindy * Fast and small text indexing -- Lance Anderson and Wayland Ni * Faster hashing -- Vladimir Kiriansky * Faster planar point location -- Glenn Eguchi and Hana Kim * Faster planar point location -- Alan Leung As in the previous round, each presentation is less than 13 minutes including questions & switchover, so the body should be at most ~10 minutes. However, today we have one last-minute signup for a presentation, which will run over the allotted time slot of 11-12:30. Those of you who can stay, please do; but I understand if you aren't able. Please send me your slides if you haven't already. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/