tag:blogger.com,1999:blog-2564777502681463717.post1645424467616349700..comments2023-12-31T10:17:57.560-05:00Comments on Teaching, Playing, and Programming: Designing a Data StructureChris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-2564777502681463717.post-19752884488636968552008-05-21T15:36:00.000-04:002008-05-21T15:36:00.000-04:00i dare say that you won't care about invariants un...i dare say that you won't care about invariants until you have to debug the code of somebody who didn't know about the idea, and wrote up a mess.<BR/><BR/>in other words, invariants can be hard to motivate because they can seem like bondage or esoteric math foo, rather than something that just helps me ship the darned product.<BR/><BR/>i don't currently agree with that thought, but acknowledge that some folks (apparently) think that way. and i probably did when i was first told about them in CS211, or whatever class it was.Raoul Dukehttps://www.blogger.com/profile/07354740962526930549noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-33422848103929683312008-05-21T07:31:00.000-04:002008-05-21T07:31:00.000-04:00Ravi: I think a good way to learn about how these ...Ravi: I think a good way to learn about how these invariants work is to study a bunch of the standard data structures. But instead of stopping at just learning how that data structure works, really pay attention to the invariant and notice exactly where the algorithms take advantage of it. Think of variations of the invariant and explore how those variations would affect the algorithms.<BR/><BR/>It can be very useful to compare different designs of the same kind of data structure to see how they solve the same problems in different ways. For example, compare red-black trees and AVL trees, or leftist heaps and binomial heaps.<BR/><BR/>You don't need a list of problems, just start with things like priority queues, dictionaries, and sequences.<BR/><BR/>In my book, <A HREF="http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html" REL="nofollow">Purely Functional Data Structures</A>, I discuss a bunch of techniques for designing data structures. Many of them are particularly suited to functional data structures, but many of them apply more widely. Probably the most widespread is "numerical representations", where you design the data structure in analogy to a number system, and design the algorithms on the data structure in analogy to operations on those numbers.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-79865535457836340142008-05-21T00:21:00.000-04:002008-05-21T00:21:00.000-04:00"One reason for this is that many data structures ..."One reason for this is that many data structures depend on non-obvious invariants. Most students are pretty shaky on the whole idea of invariants to begin with"<BR/><BR/><BR/>Good Point. What do you think students can do to increase their familiarity with such invariants? read research papers? learn more theory? Is there a list of "design your own data structure" problems somewhere?<BR/><BR/>I am very interested in learning how to design (vs implement) data structures. Any pointers/advice would be greatly appreciated.<BR/><BR/>Thanks in advance.Ravihttps://www.blogger.com/profile/03630087669712445498noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-43874401899958097532008-05-20T20:19:00.000-04:002008-05-20T20:19:00.000-04:00Fred: I'm not sure which two trees you mean, the o...Fred: I'm not sure which two trees you mean, the original two trees being merged or the two subtrees being recursively merged.<BR/><BR/>Keeping the original two trees would work if there was only ever a single merge, but when there can be arbitrarily many merges, then deleteMin ends up taking linear time.<BR/><BR/>Keeping the two subtrees is a problem, because then the new root effectively has three children instead of two. Merge again and you have a node with four children, then five, six, etc. Again, you end up with operations taking linear time.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-67412987918333808352008-05-20T19:04:00.000-04:002008-05-20T19:04:00.000-04:00Hmm...it seems like you could just keep the two tr...Hmm...it seems like you could just keep the two trees in memory separately, pick the least of the min's at findMin/deleteMin time, still hit all of your constraints, and probably have it be a bit simpler. Is there something I'm missing? It's a neat exercise, though!Fredhttps://www.blogger.com/profile/04004443408033708716noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-82664195208443848572008-05-20T17:03:00.000-04:002008-05-20T17:03:00.000-04:00I agree with the first comment, if we had done exe...I agree with the first comment, if we had done exercises such as this in my algorithm courses I might still use some of the data structures apart from the linked list and hash table.<BR/><BR/>Very nice description, makes me want to revisit my algorithm exercises and do something with them.Jonashttps://www.blogger.com/profile/13305083487496448806noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-32644361942353635972008-05-20T15:28:00.000-04:002008-05-20T15:28:00.000-04:00Somewhat simpler would be an exercise in combining...Somewhat simpler would be an exercise in combining structures to come up with hybrids like: a linked list with O(1) lookup via a hash table, 'threaded' trees (linked list + tree structure) and even simply linked lists that are 'multithreaded' for efficiency.pjzhttps://www.blogger.com/profile/00937068117282447089noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-79392592358365522172008-05-20T14:46:00.000-04:002008-05-20T14:46:00.000-04:00I wish you had taught my algorithms/data structure...I wish you had taught my algorithms/data structures courses. :) <BR/><BR/>I think very often in courses professors don't emphasize the importance of the student designing (not simply implementing). I find that reading research publications are often a wonderful way of learning because you can delve into the design process and insights of the researcher, not simply the outcomes, which textbooks tend to focus upon. However undergrads (and sometimes grad-students) rarely have the opportunity to read research publications in a course... sad.<BR/><BR/>Too bad I'm still a poor Master's student, I really want to purchase your book: Purely Functional Data Structures. :)<BR/><BR/>P.S. -- I am friends with one of your students, Scott Lobdell, at West Point.Anonymousnoreply@blogger.com