StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFamily Tree Algorithm
text
Body
copied!<p>I'm working on putting together a problem set for an intro-level CS course and came up with a question that, on the surface, seems very simple:</p> <blockquote> <p>You are given a list of people with the names of their parents, their birth dates, and their death dates. You are interested in finding out who, at some point in their lifetime, was a parent, a grandparent, a great-grandparent, etc. Devise an algorithm to label each person with this information as an integer (0 means the person never had a child, 1 means that the person was a parent, 2 means that the person was a grandparent, etc.)</p> </blockquote> <p>For simplicity, you can assume that the family graph is a DAG whose undirected version is a tree.</p> <p>The interesting challenge here is that you can't just look at the shape of the tree to determine this information. For example, I have 8 great-great-grandparents, but since none of them were alive when I was born, in their lifetimes none of them were great-great-grandparents.</p> <p>The best algorithm I can come up with for this problem runs in time O(n<sup>2</sup>), where n is the number of people. The idea is simple - start a DFS from each person, finding the furthest descendant down in the family tree that was born before that person's death date. However, I'm pretty sure that this is not the optimal solution to the problem. For example, if the graph is just two parents and their n children, then the problem can be solved trivially in O(n). What I'm hoping for is some algorithm that is either beats O(n<sup>2</sup>) or whose runtime is parameterized over the shape of the graph that makes it fast for wide graphs with a graceful degradation to O(n<sup>2</sup>) in the worst-case.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload