1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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