Analyze: Oral History Data Organization
Not what you're looking for?
You are helping scientists analyze oral history data they have collected by interviewing members of a village.
From these interviews they have learned about a set of n people (all are dead now) whom we will denote P1, P2, ... Pn. They have 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 are not sure that all these facts are correct. What they would like you to determine is whether the data they have collected is at least internally consistent, in the sense that there could have existed a set of people for which all the facts they have learned simultaneously hold.
An efficient algorithm is proposed to do this: either it produces proposed dates of birth and death for each of the n people so that all the facts hold true, or it reports (correctly) that no such dates can exist. That is the facts collected by the scientists are not internally consistent.
Purchase this Solution
Solution Summary
This solution is comprised of a detailed, step by step response which is provided within a pdf. file. The pdf. file is supplemented with diagrams which help to make this solution easier to understand.
Solution Preview
Please view the attached file for the complete solution. There are many diagrams which accompany this solution which can only be viewed in the attached pdf. file.
For every person Pi we introduce two nodes: Pib and Pid, where
- Pib is a birth date and
- Pid, is death date of the person Pi
A directed edge reflects a precedence relation between birth ...
Purchase this Solution
Free BrainMass Quizzes
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.
Excel Introductory Quiz
This quiz tests your knowledge of basics of MS-Excel.
Word 2010: Tables
Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.
Basic Networking Questions
This quiz consists of some basic networking questions.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.