You\'re helping a group of ethnographers analyze some oral history data they\'ve

Question

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,... ,Pn. 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 Pi died before person Pj was born; or for some i and j the life spans of Pi and Pj 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 simultaneously hold. 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.

Explanation / Answer

I am not sure, but I think if a directed graph is used for the first part (determining if the birth and deaths are valid) with each vertex one person, and each edge is the relationship provided i.e 2 4. Then this is simply validated by determining if a cycle is present. If no cycle exists, it must be valid.. Just an observation: if you take the second example and remove the last input value (1 4), you would have a directed graph that looks something like Code: Select all 3 --> 1 --> 2 --> 4 But adding (1 4) caused a shift to something more like Code: Select all 3 --> 2 / V V 1 4 Which still has no cycles. Also, if you only had the inputs after the first # and not the second #, I think you'd end up with two disjoint graphs. Ultimately you're going to have several cases, two of which would be (i) inputs from only (1), and (ii) inputs from (1) and (2). i'm taking this general approach for the first set of requirements (death before birth): form a directed graph like above, where 3 -> 2 if (3, 2) is in the first set of constraints. Once this is formed, find a vertex with in-degree 0 (nothing must come before it), place it in the timeline, and then cut it and all edges coming out of it from the graph. Then repeat with a new starting point. If there are vertices left, and no vertex has in-degree 0, then there is an inconsistency in the data. Does this make sense? I'm not sure what to do with the overlaps yet.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.