Prof is a super nice guy - actually had the opportunity to shake his hand and thank him for being such a great lecturer and putting up the videos. Truly a nice guy that just wants to help students learn what he teaches.
It's so impresses me that MIT has not only 2 TAs for an advanced class but also a scribe. They are serious about teaching ... sadly unlike the majority of colleges today.
I'm not 100% certain, but usually scribes are students taking the class, and being a scribe for a certain number of lectures is part of the assessments
Thanks so much for sharing this. As a suggestion, perhaps in the future (given that this material is so interesting and important) give a research oriented MOOC...? Like one from stanford like a year ago. I didn't attend it, but when I found out it existed I thought it is really good idea
Around 38:13 (this ties in to several points before wherein the professor mentions backpointers and recursive updating of them): Why do we have potentially 2p updates? - If this's referring to updating fields that are themselves pointers to other nodes, well, why is there any updating to do? - If this's referring to updating the backpointers: we have only max p of them. I think there's a bit that's vague, confusing, or missing, and I'm not sure because I don't know where it should be: Backpointers only point to nodes, not fields (duh), so the update algo must go through the fields of the nodes backpointed to in order to update all fields whose contents is a pointer pointing to the node executing the update. This still would mean at most p*n updates (i.e. only one level of recursion is possible) where every backpointer points to one node with 1 to n updates possible (where n is the max number of fields in a node; I must've missed the part where that's specified, if it is; but the important part is that it's one level of recursion). What am I missing?
I think you’ve forgot the part that, when updating the fields of the nodes pointed by the backpointers, it’s actually another field update, which might trigger another recursion if the mods are full. I think this answers the recursion part, but I didn’t understand why it’s 2p instead of just p.
A question regarding the Partial Persistence Data Structure. In the event a read is needed, an entity is required go through
7 лет назад
I believe there is a mistake in the way he does full persistence. He assumes that he can find a vertex in the tree such that its subtree has size roughly one half. But this is only true for trees of bounded degree. For example, it cannot be done for a star. Please correct me if I'm wrong, but I think his way of splitting nodes does not work.
I had the same question! I think maybe he assumes that every version tree can be converted into an equivalent bounded degree version tree. Not sure exactly how though.
YES SUCCINCT!!! python recently changed how they store dicts in cpython and it's both succinct AND preserves insertion order it was VERY clever of them
I can see that maybe github might use something like the first algorithm ... .... but I wonder how many of these algorithms are actually in use outside of theory?
I feel the same. The way I see it is: Commit is an implementation of partial persistence(updating the last commit) Fork matches with the idea of full persistence(creating an entirely new branch) Confluent persistence seems applicable when you're merging two branches.
I think nodes also need a back pointer to older version parent nodes, when the mods are migrated to the fields of a new node, so that search a new node for a version older than the migration, can propogate back to the original node. e.g. if a node with a full mods list at version 10 splits, it gets copied, but if someone searches for version 5 of a field, the new copy needs to know that versions
No, fortunately that's not needed. As he mentions in the lecture, a "version" in this model is really a (root pointer, version id) tuple, so if an older version is accessible you know its root pointer and everything relevant to that version is reachable from that root; when an existing root node splits, the new version is associated with the new root pointer. If you had a shared root pointer for all versions then you'd indeed need something like what you're suggesting, but that would ruin the running time to access old versions from the latest version since you'd have to chase through the entire version chain.
Question about *full persistence*: In 57:40 the prof said there are at most 2d+2p+1 pointer updates after the split. But my problem is: if node N was pointed by another node (M.field=N), then after N split into N’ and N2, what value should we set to M.field? Is it the old node (original tree) or the new one (subtree)? The requirement says that one can browse any version in the history, but when browsing node M, who gets to decide the value of M.field?
We've tested both links- the one in the description (ocw.mit.edu/6-851S12), and the one in our comments on this video (ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012). If you need to, you can manually go to our site (ocw.mit.edu) and use the Course Finder to find the course number 6.851 Spring 2012. If you can't get to our site, it is being blocked by your connection. We have many mirrors of our content, if need be you can search for those. Good luck!
At 23:45, how does prof Erik decide on 2p modifications? what is the rationale? Doesn't putting a bound on the size of mod indirectly say we can only store constant number of versions?
I am interested in developing models to track data for marketing. There's a connection here although it is just a seed at this point. For instance, can this sort of thing move me from aggregate data to specific data that results in greater analytical effectiveness?
would anyone tell me what are the prerequisites for the course?? i have been through "introduction to algorithms" and "Introduction to computer science and programming" both...Any suggestions??
+Mithil Leua From the syllabus, "The prerequisite for this course is 6.046, Design and Analysis of Algorithms, or an equivalently thorough undergraduate algorithms class from another school (e.g., covering much of CLRS). I recommend that you take 6.854, Advanced Algorithms, the broad entry-level graduate course in Theory / Algorithms-it normally makes sense to start there before jumping into deeper graduate courses. If you haven't taken 6.854, you must have a strong understanding of algorithms at the undergraduate level, such as receiving an A in 6.046, having done relevant research, involvement in computer competitions, etc." See the course on MIT OpenCourseWare for more information and course materials at ocw.mit.edu/6-851S12.
You know, I understand the focus on "pure O()" thinking, but at the same time, sooner or later one needs to actually work out the details of how they implement these things, and one wants a faster implementation rather than a slower one. Those constant factors DO MATTER. SOMEONE needs to talk about those details. The engineering aspects of the problems do actually matter. So, let's just pay a little attention to the quantity of things we just wave away as "irrelevant." Just in general it feels like you're glossing over quite a lot of details that are likely to be very subtle. You're only giving a very vague idea about how one might do this work.
Erik demain the professor walk like sheldon cooper of big bang theory. Very detailed lecture but professor haven't mentioned any example of persistence data structures
What if #mods is 1, there are N nodes in chain spanning from the root to the leaf and the leaf is updated continuously? Would't time complexity be Θ(N/2) or simply Θ(N) in this case? Each even update is amortized, but each odd is not
I am looking at your Computer Science and Engineering degree (Course 6-3) on the degree chart ( goo.gl/sYm0bI ). I am trying to decipher where to start and sort out my path for the Bachelor degree. I just have basic / intermediate knowledge of introductory computer science and .NET programming through my college courses.. Any pointers on where to start?? Or an order of the most important courses from beginning to finish possibly? That would be very nice.
Does anyone knows whether the mit professors lectured on Fibonacci Heap or not? really want some insight to this data structure, also to prepare for my exam...... Plz and thanks a lot
This isn't video, but might help: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/lecture-notes/lec1.pdf. There are also a number of courses that touch upon it: ocw.mit.edu/search/ocwsearch.htm?q=%22Fibonacci%20Heap%22. Best wishes on your exam!
Is there any context as to why I care about this lecture? Not trying to be negative I actually dont know where these data structures are used. Maybe I dont understand
I like the approach to this. I am by far no expert in this field although I have a basic understanding. It is very user friendly to the novice. Good job.
From the syllabus: "The prerequisite for this course is 6.046, Design and Analysis of Algorithms, or an equivalently thorough undergraduate algorithms class from another school..." See the course on MIT OpenCourseWare for more information and materials at: ocw.mit.edu/6-851S12. Best wishes on your studies!
Prerequisites are listed on the Syllabus page of the OCW course site: ocw.mit.edu/6-851S12, in this case 6.046, Design and Analysis of Algorithms ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/, or an equivalently thorough undergraduate algorithms class from another school (e.g., covering much of the CLRS book mitpress.mit.edu/9780262533058) and 6.854, Advanced Algorithms ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/index.htm, the broad entry-level graduate course in Theory / Algorithms.
+Abdullah Ali MIT OpenCourseWare is not a degree-granting or credit-bearing initiative. For a certificate, you should check out the MITx offerings (www.edx.org/school/mitx).
Sorry, we don't have any Chinese versions of this content. Here's a list of courses that have been translated: ocw.mit.edu/courses/translated-courses/traditional-chinese/
This is really old style teaching. One doesn't know what all the stuff is good for. Not a single example what all these types of persistence are good for. Good teaching is putting oneself into the student role and asking oneself: Do my students understand me. Do they know what I want them to learn. etc
Teaching theory without practical examples can still be extremely useful. If you want practical knowledge that you can apply immediately, go do a bootcamp, or learn from tutorials on the internet.
You're asking to be spoonfed, whereas if you wanted applications, you should be thinking of ways to apply them yourself. Plus, that's what the problem sets are for.
that is good education for 10 year olds. good uni students can understand concepts somewhat independent of any other data point in their minds. in other words you dont need to know a particular use for an information to learn that well once your brain develops enough
From my experience, this is very true. You excel way faster if you can make as much connections as possible with things you are learning and things you already know. And real life examples, events, objects, etc. that are already strongly imprinted in your brain can make that process much easier.
