Algorithm Design - Kleinberg and Tardos Chapter 3 Problem 12 Page 112 You’re hel

Question

Algorithm Design - Kleinberg and Tardos

Chapter 3 Problem 12

Page 112

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 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.

Explanation / Answer

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 A
• Subjects

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