The material seems to be for this course: http://web.stanford.edu/class/cs166/ There are more slides and info on that site :)
It's a pity there are no video lectures. Are there lectures out there for a similar algorithms class?
Topics in Advanced Data Structures [pdf]
51–60 of 89 posts
Re: Topics in Advanced Data Structures [pdf]
#52> Traditional data structures assume a single-threaded execution model and break if multiple operations canbe performed at once. (Just imagine how awful it would be if you tried to access a splay tree with multiplethreads.) Can you design data structures that work safely in a parallel model – or, better yet, take maxi-mum advantage of parallelism? In many cases, the answer is yes, but the data structures look nothing…
The Art of Multiprocessor Programming by Herlihy and Shavit have many examples, including stacks, queues, skip lists, and hash tables. There's plenty of papers out there too that have parallel implementations of vectors, various tree structures and more.
Re: Topics in Advanced Data Structures [pdf]
#53Hm, where else are Lowest Common Ancestors in tree-structures useful? Storing for instance ORDPATH/DeweyIDs allows to simply check for a common prefix (they are hierarchical node labels). I think maybe for locking in a storage system with multiple read/write transactions or to determine which of two given nodes is the firs one in preorder, which is useful for XQuery/XPath processing (to determine the so caslled docum…
Error-boundaries in VDOM frameworks. If you have an asynchronous diff cycle, you might get multiple errors from more than one node in a single diff cycle. One option is to bubble up errors to the nearest LCA that is an error-boundary. In general if you have marked two nodes in a tree and need to modify the smallest subtree that contains those nodes, then you will probably need to know the LCA.
Re: Topics in Advanced Data Structures [pdf]
#54awesome topics.
just leaving this here:
https://coincircle.com/l/50VVxbObg3
Re: Topics in Advanced Data Structures [pdf]
#55The material seems to be for this course: http://web.stanford.edu/class/cs166/ There are more slides and info on that site :)
It's a pity there are no video lectures. Are there lectures out there for a similar algorithms class?
MIT 6.851 Advanced Data Structures, Spring 2012: https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdu...
Re: Topics in Advanced Data Structures [pdf]
#56> Traditional data structures assume a single-threaded execution model and break if multiple operations canbe performed at once. (Just imagine how awful it would be if you tried to access a splay tree with multiplethreads.) Can you design data structures that work safely in a parallel model – or, better yet, take maxi-mum advantage of parallelism? In many cases, the answer is yes, but the data structures look nothing…
Check out CRDTs - https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
Re: Topics in Advanced Data Structures [pdf]
#57Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.
There's a general class of problems to be solved with data structures, which is that you have a collection of records of data, and you're trying to find [1] a record, or collection of records, given some criteria. In essence, you have a database of some kind, so it should not surprise you to learn that databases (and things that are databases but not normally thought of as such--filesystems, for example) rely very he…
>I fully expect to see these tools start to become available over the next decade or so, given the current progress of program synthesis I see in the academic literature.
Interesting. I did know about program verification efforts (trying to prove that programs are correct), but had never heard of program synthesis (assuming it is somewhat different from code generation). Do you know of any examples of the kinds of areas it can be applied to?
Re: Topics in Advanced Data Structures [pdf]
#58Hm, where else are Lowest Common Ancestors in tree-structures useful? Storing for instance ORDPATH/DeweyIDs allows to simply check for a common prefix (they are hierarchical node labels). I think maybe for locking in a storage system with multiple read/write transactions or to determine which of two given nodes is the firs one in preorder, which is useful for XQuery/XPath processing (to determine the so caslled docum…
Lowest Common Ancestor shows up in graph theory, particularly to help compute dominator trees or dominator frontiers.
These problems arise in compilers that convert programs into static single assignment (SSA) form.
Re: Topics in Advanced Data Structures [pdf]
#59Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.
There's a general class of problems to be solved with data structures, which is that you have a collection of records of data, and you're trying to find [1] a record, or collection of records, given some criteria. In essence, you have a database of some kind, so it should not surprise you to learn that databases (and things that are databases but not normally thought of as such--filesystems, for example) rely very he…
Stratos Idreis's team has been working on exactly this. Automatic design of data structures based on workload.
Their work has been on HN before: https://news.ycombinator.com/item?id=18314555
Re: Topics in Advanced Data Structures [pdf]
#60Earlier quoted context omitted.
There's a general class of problems to be solved with data structures, which is that you have a collection of records of data, and you're trying to find [1] a record, or collection of records, given some criteria. In essence, you have a database of some kind, so it should not surprise you to learn that databases (and things that are databases but not normally thought of as such--filesystems, for example) rely very he…
>I fully expect to see these tools start to become available over the next decade or so, given the current progress of program synthesis I see in the academic literature. Interesting. I did know about program verification efforts (trying to prove that programs are correct), but had never heard of program synthesis (assuming it is somewhat different from code generation). Do you know of any examples of the kinds of ar…
The best overview of the topic I know of is https://www.microsoft.com/en-us/research/wp-content/uploads/..., which describes the state of the field ~18 months ago.
The major field where it's already being applied is in automating the conversion of data--building the program that can take "John Doe" and turn it into "John Doe" just by example. You can also do similar generalization to automate things like constructing highly repetitive graphics (e.g., draw a few teeth of a gear and the program does the rest). Superoptimization is the other main prong, where you really combine the synthesis and the verification to get correct faster code.