Need help with 12 () Student Home-myFSU × A ts_ (CENL Hw4-coP4531.pdf BryteWave:

Question

Need help with 12

() Student Home-myFSU × A ts_ (CENL Hw4-coP4531.pdf BryteWave: Algorithm D, × x CSecure https://shelf.brytewave.com//books/9780133072525/cfi/1361/4/4@0.00:44.1 : Apps D New Tab Online Derivative Ca M ITSDocs: Create Co in Uni ho do l list db wvim notes in Unix, how do l cha D c string Pass ord O introduction to OOP I Sieve 12. 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 P, 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 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 simultaneously hold. Give an efficient algorithm to do this: either it should produce pro- posed 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. 2:09 PM 1017/2017

Explanation / Answer

P1, P2, .... Pn are the n people

Here we are constructing a graph where there are 2*n nodes

Consider two nodes for each person such that

Pib - node for the date of birth of ith person

Pid - node for the date of death of ith person

there will be an edge from Pib to Pid as Pid > Pib for all i

from the data if

i person has dead befor j dies

then we will add edges from both the nodes of ith person to both nodes of jth person

if i and j have some partial overelapping life span

then add an edge from Pib to Pjd and from Pjb to Pid

Now after constructing this directed graph check whether the graph has cycle, if the graph has cycle then the data is internally inconsistent else the data is consistent

If the data is consitstent then we will find topological ordering of the graph and assign the dates from small to high value for every node.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---