Give an algorithm with polynomial running time to do this

Assignment Help Computer Engineering

Reference no: EM132118892

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 those 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 two following forms:

• Person Pi died before person Pj was born.

• The life spans of Pi and Pj overlapped at least partially. (Here Pi and Pj are two specific people whom the fact is about.)

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 algorithm with polynomial running time 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.

Reference no: EM132118892

Questions Cloud

Prove that finding an acceptable arrangement : "Marge may not point her arms up while Ned, Apu, and Smithers point their arms down." Prove that finding an acceptable arrangement of arm positions is NP-hard.

Compute the greatest common divisor of two given numbers : Based on these observations, implement a function to compute the greatest common divisor of two given numbers >= 1.

What information do you need to carry out the proposal : You're called in to consult for a company that's issuing about 100 new wireless mobile devices to selected employees.

What is the recurrence for the running time : We're given an array of n numbers, A[1 · · · n] and want to add up the n numbers. What is the recurrence for the running time? Solve it.

Give an algorithm with polynomial running time to do this : 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.

Qualitative research and statistical analysis : Research question and is most appropriate in the specific circumstances. Students should clearly justify their recommended research and analysis methods

Write an identity for the opt value : Imagine further that each such function has maximum value at most s, corresponding to the project being fully finished.

What is the range of radio frequencies in technologies : What is the range of radio frequencies in wireless technologies? What are the pros and cons of the lowest and highest frequencies?

How are they similar and how are they different : Radio buttons and check boxes are two of many different kinds of components that can be included in a graphical user interface.

User Account

All Pages