This is a Question of the Design and Analysis of Algorithms class, please help H

Question

This is a Question of the Design and Analysis of Algorithms class, please help

Here's a beautiful question I found in an algorithms textbook. It has a very simple solution, but you have to be a little bit creative: You're helping a group of ethnographers analyze some oral history data they?ve collected by interviewing members of a village to learn about the lives of people who?ve lived there over the past two hundred years. From these interviews, they?ve learned about a set of n people (all of them now deceased), whom we?ll denote P1, P2,. . . , P. They?ve also collected facts about when these people lived relative to one another. Each fact has one of the following two forms: . For some i and j, person P died before person P was born; or . For some i and j, the life spans of P and P overlapped at least partially. Naturally, they?re not sure that all these facts are correct; memories are not so good, and a lot of this was passed down by word of mouth. So what they?d like you to determine is whether the data they?ve collected is at least internally consistent, in the sense that there could have existed a set of people for which all the facts they?ve learned hold simultaneously. Give an efficient algorithm to do this: either it should produce proposed dates of birth and death for each of the n people so that all the facts hold true, or it should report (correctly) that no such dates can exist?that is, the facts collected by the ethnographers are not internally consistent. To make the question a bit more precise, you are asked to develop an algorithm that runs in O(n + m log n) time, where n denotes the number of people and m denotes the number of facts collected about these people. Argue that your algorithm is correct and that its running time is indeed O(n + m logn).

Explanation / Answer

The method to use here is to construct a bipartite directed graph, where the nodes represent events births and deaths of the various n people (so there are 2n nodes). Draw edges from one node to another when we have a fact that states that the former precedes the latter. In particular P_i exists, and was born before they died, so (birth(P_i), death(P_i)) is an edge. if person P_i died before P_j was born, (death(P_i), birth(P_j)) is an edge. if the life spans of P_i and P_j overlapped at least partially, then both (birth(P_i), death(P_j)) and (birth(P_j), death(P_i)) are edges (if either's death preceded the other's birth, then they couldn't have coexisted) For any path a -> b -> c in the graph, we have date(a) a_3 -> ... -> a_m -> a_1, then we have date(a_1)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---