Lemma (3.18) If G has a topological ordering, then G is a DAG.

Lemma (3.20) If G is a DAG, then G has a topological ordering.

2. (25) [DAG and topological ordering] Textbook Exercise 12 in Chapter 3. State how you can solve the problem by using the topological ordering algorithm and give the resulting running time complexity. Assume the topological ordering algorithm is given, so you do not need to describe the steps of topological ordering in your answer. Consider an adjacency list to represent the graph constructed to solve this problem. Clarification: the data collected is "internally inconsistent" if there exist two conflicting birth-death date records, that is, if the records say that "P, died before P, was born" and that "P, died before Pi was born." Hint: build a graph G as follows: (a) for each person Pi, represent his or her birth and death as two nodes bi and di respectively; (b) in case person P, died before person P, was born, then add an edge (di, b,); (c)in case the life spans of Pi and Pj overlapped at least partially, then add (bi, dj) if Pi was born before P, died or (b, di) if Pj was born before Pi died. Hint: see Lemma 3.18 (p101) and Lemma 3.20 (p102) in the textbook. 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 Pi, 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