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 P_1,P_2...P_n. 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 Pj was born; or for some i and j, the life spans of P_i and P_j 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 cun exist-that is, the facts collected by the ethnographers are not internally consistent.

Explanation / Answer

  So the problem reduces to simply attempting to find a topological ordering on the graph of events.

If one is found, then we have a possible ordering of events, consistent with the data. If one is not found, it must be because the graph has a cycle, and therefore the data is inconsistent.

The below Algorithm explains the create node format of each people and their degree and life and death, birth situations here.

ALGORITHM:

    proc create-node( event )

      out-adj-list[event] <- empty-list

      in-degree[event] <- 0

    endproc

    proc create-edge( start, end )

      push( out-adj-list[ start ], end )

      in-degree[ end ] <- in-degree[ end ] + 1

    endproc

    for p in { P_i }

      create-node( birth[p] )

      create-node( death[p] )

      create-edge( birth[p], death[p] )

    endfor

    for (p, q) in DiedBefore

      create-edge( death[p], birth[q] )

    endfor

    for (p, q) in Coexisted

      create-edge( birth[p], death[q] )

      create-edge( birth[q], death[p] )

    endfor

    eligible-node-list <- empty-list

    for p in { P_i }

      if in-degree[ birth[p] ] = 0

        push(eligible-node-list, birth[p])

      endif

    endfor

    event-date-separation = 200yrs / (2*|{P_i}|)

    order <- 0

    while eligible-node-list is non-empty

      event = pop(eligible-node-list)

      order <- order + 1

      dates[ event ] = START_DATE + order * event-date-separation

      for following-event in out-adj-list[event]

        in-degree[ following-event ] <- in-degree[ following-event ] - 1

if in-degree[ following-event ] = 0

                        push( eligible-node-list, following-event )

            endif

      endfor

    endwhile

    if order < 2*|{P_i}|

      return INCONSISTENT_DATA

    else

      return CONSISTENT_DATA, dates

    endif

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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