Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Pseudo-Distances within a depth-determination problem

  1. Nov 16, 2008 #1
    I was given the following problem description for a depth-determination problem, however I am completly unable to figure out how this "pseudo-distance" feature works, if anyone has any clues and can provide a uber-simple example it would be much appreciated - I just can't see how it works/applies.

    In the depth-determination problem, we maintain a forest F = {Ti} of rooted trees. We use the disjoint-set forest S=Si, where each set Si (which is itself a tree) corresponds to a tree Ti in the forest F. The tree structure within a set Si, however, does not necessarily correspond to that of Ti. In fact, the implementation of Si does not record the exact parent-child relationships but nevertheless allows us to determine any node’s depth in Ti.

    The key idea is to maintain each node v a ”pseudo-distance” d[v], which is defined so that the sum of the pseudo-distances along the path from v to the root of its set Si equals the depth of v in Ti. That is, if the path from v to its root in v0 , v1 , . . . , vk , where v0 = v and vk is Si’s root, then the depth of v in Ti is the sum of d[vj] where j=0 to j=k.
  2. jcsd
  3. Nov 16, 2008 #2
    The definition of "pseudo-distance" seems to be recursive here. Could you check the wording of the question?
  4. Nov 16, 2008 #3
    Very possible that is it recursive - because the wording is copy/paste from the problem statement - I just don't see how it works...

    If Si is a subtree of Ti (but they don't necessarily have the same root) then how can d[v] in Si allow you to calculate the depth it Ti? Or am I looking at this completly wrong?

  5. Nov 16, 2008 #4
    It is common to have a recursive algorithm. But a definition that is recursive would not help the cause of defining or explaining something.
    For example:
    "A rectangle is a rectangle that has opposite sides parallel and adjacent side perpendicular to each other."
    is a faulty definition.
  6. Nov 16, 2008 #5
    I see your point - but this is given in the textbook, not sure how else to interpret it...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook