Loading ...
Sorry, an error occurred while loading the content.

Re: Combining two criticisms (was: Re: [hackers-il] Question to graph theorists - non-recursive binary tree traversal algorithm?)

Expand Messages
  • guy keren
    ... ofcourse i was right. omer had tried to show that some basic issues of computation theory are wrong, or some very hard problems are actually easy to solve.
    Message 1 of 12 , Aug 25, 2005
    • 0 Attachment
      On Thu, 25 Aug 2005, Arik Baratz wrote:

      > On 25/08/05, Omer Zak <omerz@...> wrote:
      > > - Processes need to access the tree in different orders (prefix vs.
      > > postfix traversal, for example)?
      > > - Processes need to skip different parts of the tree while traversing
      > > it.
      > > - The tree is dynamically modified by another process (stipulating that
      > > there are locking mechanisms such that processes in middle of tree
      > > traversal are not confused by the change) and it is expensive to unroll
      > > the tree after each modification.
      >
      > Hm.. I just came back from my thinking place, and it seems to me like
      > Guy may be right after all. Your NextSibling() node method needs to
      > know what you mean by 'next', so it has to somehow remember where in
      > relation to other siblings you are now. It has to go to the parent,
      > and look for the 'next' sibling. You need to keep information
      > regarding which is the next sibling somewhere, and that somewhere is
      > different for each process...

      ofcourse i was right. omer had tried to show that some basic issues of
      computation theory are wrong, or some very hard problems are actually
      easy to solve. what are the chances of him being right about this?

      you cannot traverse a tree using an O(1) ammount of extra memory - i think
      if omer looks properly, he'll find proofs for this theorem.

      as i said, omer's in a very strange mood today - it's not like him to come
      up with so many fataly flawed ideas. could it be that someone took over
      omer's email account and is trying to ruin his reputation? :0

      --
      guy

      "For world domination - press 1,
      or dial 0, and please hold, for the creator." -- nob o. dy
    • Omer Zak
      ... If the tree nodes have links to their siblings and parents, and if the memory occupied by the links is not counted as extra memory (reasonable when the
      Message 2 of 12 , Aug 25, 2005
      • 0 Attachment
        On Thu, 2005-08-25 at 16:33 +0300, guy keren wrote:
        > On Thu, 25 Aug 2005, Arik Baratz wrote:
        >
        > > On 25/08/05, Omer Zak <omerz@...> wrote:
        > > > - Processes need to access the tree in different orders (prefix vs.
        > > > postfix traversal, for example)?
        > > > - Processes need to skip different parts of the tree while traversing
        > > > it.
        > > > - The tree is dynamically modified by another process (stipulating that
        > > > there are locking mechanisms such that processes in middle of tree
        > > > traversal are not confused by the change) and it is expensive to unroll
        > > > the tree after each modification.
        > >
        > > Hm.. I just came back from my thinking place, and it seems to me like
        > > Guy may be right after all. Your NextSibling() node method needs to
        > > know what you mean by 'next', so it has to somehow remember where in
        > > relation to other siblings you are now. It has to go to the parent,
        > > and look for the 'next' sibling. You need to keep information
        > > regarding which is the next sibling somewhere, and that somewhere is
        > > different for each process...
        >
        > ofcourse i was right. omer had tried to show that some basic issues of
        > computation theory are wrong, or some very hard problems are actually
        > easy to solve. what are the chances of him being right about this?
        >
        > you cannot traverse a tree using an O(1) ammount of extra memory - i think
        > if omer looks properly, he'll find proofs for this theorem.

        If the tree nodes have links to their siblings and parents, and if the
        memory occupied by the links is not counted as extra memory (reasonable
        when the trees are read-only accessed by several processes, each of
        which needs to maintain its own traversal state) - then you can consider
        the tree as a maze (each vertex is a corridor and each node is a meeting
        place of few corridors). You then follow the maze using the right hand
        law. When using the right hand law, you do not need more than O(1)
        read-write memory.

        Of course, when only a single process needs to traverse the tree at the
        same time, it is more economical to maintain the O(log N) read-write
        memory than to spend space on redundant links in the tree.

        > as i said, omer's in a very strange mood today - it's not like him to come
        > up with so many fataly flawed ideas. could it be that someone took over
        > omer's email account and is trying to ruin his reputation? :0

        Thanks for the belated compliment on my past ideas.
        If you feel bored by my flawed but nevertheless interesting (at least to
        my ego) ideas, which were publicized in an attempt to wake up the
        Hackers-IL mailing list, can you post your own speculative (translation:
        flawed) but interesting ideas?
        --- Omer
        --
        Jara Cimrman! He is one of the unsung geniuses--scientist, engineer,
        inventor and literary critic.
        My own blog is at http://www.livejournal.com/users/tddpirate/

        My opinions, as expressed in this E-mail message, are mine alone.
        They do not represent the official policy of any organization with which
        I may be affiliated in any way.
        WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
      • Omer Zak
        [... snipped ...] If the tree nodes have links to their siblings and parents, and if the memory occupied by the links is not counted as extra memory
        Message 3 of 12 , Aug 25, 2005
        • 0 Attachment
          [... snipped ...]
          If the tree nodes have links to their siblings and parents, and if the
          memory occupied by the links is not counted as extra memory (reasonable
          when the trees are read-only accessed by several processes, each of
          which needs to maintain its own traversal state) - then you can consider
          the tree as a maze (each vertex is a corridor and each node is a meeting
          ^^^^^^ should be "edge"
          place of few corridors). You then follow the maze using the right hand
          law. When using the right hand law, you do not need more than O(1)
          read-write memory.

          Of course, when only a single process needs to traverse the tree at the
          same time, it is more economical to maintain the O(log N) read-write
          memory than to spend space on redundant links in the tree.
          [... snipped ...]
          --- Omer
          --
          Jara Cimrman! He is one of the unsung geniuses--scientist, engineer,
          inventor and literary critic.
          My own blog is at http://www.livejournal.com/users/tddpirate/

          My opinions, as expressed in this E-mail message, are mine alone.
          They do not represent the official policy of any organization with which
          I may be affiliated in any way.
          WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
        • guy keren
          ... aha, but you are forgetting that you do not have an upper-bound on the number of children for a given node. consider this: [ P ] [C1] [C2] [C3] [C4]
          Message 4 of 12 , Aug 25, 2005
          • 0 Attachment
            On Fri, 26 Aug 2005, Omer Zak wrote:

            > If the tree nodes have links to their siblings and parents, and if the
            > memory occupied by the links is not counted as extra memory (reasonable
            > when the trees are read-only accessed by several processes, each of
            > which needs to maintain its own traversal state) - then you can consider
            > the tree as a maze (each vertex is a corridor and each node is a meeting
            > place of few corridors).You then follow the maze using the right hand
            > law.When using the right hand law, you do not need more than O(1)
            > read-write memory.

            aha, but you are forgetting that you do not have an upper-bound on the
            number of children for a given node. consider this:


            [ P ]


            [C1] [C2] [C3] [C4] [C5] [C6] [C7] [C8] [C9] [C10] [C11]


            lets say we were in C2, and are now returning to P. we now need to find
            which is the next node we should visit. the only way to make this in O(1),
            is that each node will keep a link to its sibling. add these links too,
            then. (if this operation is not O(1), it makes your scanning algorithm
            less efficient then O(N)).

            if you'll want to scan the tree in reverse order, you'll need the siblings
            list to be bidirectional.

            if you'll want to make a BFS scan, rather then DFS.....

            so, you see, you're creating a tree that lends itself to one manner of
            traversal, and does not work for other types of traversals.

            this could be useful for specific types of problems, ofcourse, but this is
            not the generic issue of traversing a tree structure.

            > Of course, when only a single process needs to traverse the tree at the
            > same time, it is more economical to maintain the O(log N) read-write
            > memory than to spend space on redundant links in the tree.

            log N is relevant assuming a balanced tree. in fact, it's not log N, but
            log (largest number of children of a single parent).

            > > as i said, omer's in a very strange mood today - it's not like him to come
            > > up with so many fataly flawed ideas. could it be that someone took over
            > > omer's email account and is trying to ruin his reputation? :0
            >
            > Thanks for the belated compliment on my past ideas.
            > If you feel bored by my flawed but nevertheless interesting (at least to
            > my ego) ideas, which were publicized in an attempt to wake up the
            > Hackers-IL mailing list, can you post your own speculative (translation:
            > flawed) but interesting ideas?

            if you can't bring up something useful - it's better to keep the list
            quiet. would you like me to bring up my mission-imposible project of
            devising an algorithm that automatically translates C programs into C++
            programs while introducing classes based on usage relations between data
            and functions in the original C program?

            --
            guy

            "For world domination - press 1,
            or dial 0, and please hold, for the creator." -- nob o. dy
          • Omer Zak
            ... How about that what-is-its-name transformation, which establishes an equivalence relationship between general and binary trees? Then you need to deal only
            Message 5 of 12 , Aug 25, 2005
            • 0 Attachment
              On Fri, 2005-08-26 at 02:13 +0300, guy keren wrote:

              > aha, but you are forgetting that you do not have an upper-bound on the
              > number of children for a given node. consider this:
              >
              >
              > [ P ]
              >
              >
              > [C1] [C2] [C3] [C4] [C5] [C6] [C7] [C8] [C9] [C10] [C11]
              >
              >
              > lets say we were in C2, and are now returning to P. we now need to find
              > which is the next node we should visit. the only way to make this in O(1),
              > is that each node will keep a link to its sibling. add these links too,
              > then. (if this operation is not O(1), it makes your scanning algorithm
              > less efficient then O(N)).

              How about that what-is-its-name transformation, which establishes an
              equivalence relationship between general and binary trees?

              Then you need to deal only with two children per node.

              > if you'll want to scan the tree in reverse order, you'll need the siblings
              > list to be bidirectional.
              >
              > if you'll want to make a BFS scan, rather then DFS.....
              >
              > so, you see, you're creating a tree that lends itself to one manner of
              > traversal, and does not work for other types of traversals.
              >
              > this could be useful for specific types of problems, ofcourse, but this is
              > not the generic issue of traversing a tree structure.

              OK, I give up.
              I propose a bicycle as a transportation vehicle, pointing out that it is
              the best solution for some specialized transportation situations.
              You reply by reminding us that most of the transportation needs of
              humans are better served by cars and airplanes.

              > if you can't bring up something useful - it's better to keep the list
              > quiet. would you like me to bring up my mission-imposible project of
              > devising an algorithm that automatically translates C programs into C++
              > programs while introducing classes based on usage relations between data
              > and functions in the original C program?

              Sounds cool and interesting. Can you tell us more about it?
              How do you avoid the trivial solution of enclosing function declarations
              by extern "C" { ... } declarations?
              --- Omer
              --
              Every good master plan involves building a time machine. Moshe Zadka
              My own blog is at http://www.livejournal.com/users/tddpirate/

              My opinions, as expressed in this E-mail message, are mine alone.
              They do not represent the official policy of any organization with which
              I may be affiliated in any way.
              WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
            Your message has been successfully submitted and would be delivered to recipients shortly.