As discussed in class Thursday, problem 3.12 needs a rather different type of output than problem 3.4. 3.12 wants an ordering, whereas 3.4 wants a boolean. Also, we saw that 3.4 is "close" to being a bipartiteness question, which doesn't involve orderings at all, as far as we know.
So no, #12 doesn't look much like #4. I advise finding an algorithm in the main part of the chapter that has more features in common with what #12 asks for, and then work on finding the right (di)graph to apply it to. I'd also suggest reviewing Thursday's lecture.
Problem 3.10 - I think we are looking for the shortest path (length s) and any additional paths of the same length. We report that there are m paths of length s. We are not interested in paths of length greater than s. Is this correct?
Looking at number 12 - it seems to be a natural Topological Ordering of a DAG graph, if the data is valid. If the data is not valid, you can't have a DAG, or build a topological ordering.
I don't think you can assume that P_i was born before P_j, at least that's the way I've been approaching the problem. It seems like the key with that fact is how exactly it interacts with the first set of facts and what this says about inconsistencies.
Lucas - I'm not actually assuming P_i was born before P_j. If you use nodes for both birth and death dates, and directed edges connecting earlier dates to later dates, you should be able to use the resulting graph to look for a topological ordering. If there is one, you've verified the data. If not, the data is invalid....
I am still struggling with problem 4 - If I'm reading it right - are we throwing out the inconclusive data and only working with the "same" or Different" sets? Why I'm wondering, is that the second paragraph on page 108 starts: "So now they have the collection of "n" specimens as well as a collection of "m" judgements (either "same" or "different") for the pairs that were not declared to be ambiguous."
That seems to indicate we are not looking at the ambiguous pairs, and that "n" is not the same as the total number of butterflies collected...
Re problem 3.12, your input is going to consist of statements like "Bach and Washington overlapped" (perhaps known because we found a letter from one to the other), or "Shakespeare died before Washington was born." The second type of statement gives full information about the relative order of their births and deaths, while the first type only gives partial information. In particular, it doesn't tell you that Bach was born before Washington.
Is the problem #12 basically a butterfly problem?
ReplyDeleteAs discussed in class Thursday, problem 3.12 needs a rather different type of output than problem 3.4. 3.12 wants an ordering, whereas 3.4 wants a boolean. Also, we saw that 3.4 is "close" to being a bipartiteness question, which doesn't involve orderings at all, as far as we know.
ReplyDeleteSo no, #12 doesn't look much like #4. I advise finding an algorithm in the main part of the chapter that has more features in common with what #12 asks for, and then work on finding the right (di)graph to apply it to. I'd also suggest reviewing Thursday's lecture.
Problem 3.10 - I think we are looking for the shortest path (length s) and any additional paths of the same length. We report that there are m paths of length s. We are not interested in paths of length greater than s. Is this correct?
ReplyDeleteThanks,
Ken Potter
Problem 3.12 - For the case that the life spans of P_i and P_j overlap, was P_i born befor P_j, or can we not assume that?
ReplyDeleteThanks,
Ken Potter
Looking at number 12 - it seems to be a natural Topological Ordering of a DAG graph, if the data is valid. If the data is not valid, you can't have a DAG, or build a topological ordering.
ReplyDeleteKen,
ReplyDeleteI don't think you can assume that P_i was born before P_j, at least that's the way I've been approaching the problem. It seems like the key with that fact is how exactly it interacts with the first set of facts and what this says about inconsistencies.
Lucas - I'm not actually assuming P_i was born before P_j. If you use nodes for both birth and death dates, and directed edges connecting earlier dates to later dates, you should be able to use the resulting graph to look for a topological ordering. If there is one, you've verified the data. If not, the data is invalid....
ReplyDeleteI am still struggling with problem 4 - If I'm reading it right - are we throwing out the inconclusive data and only working with the "same" or Different" sets? Why I'm wondering, is that the second paragraph on page 108 starts: "So now they have the collection of "n" specimens as well as a collection of "m" judgements (either "same" or "different") for the pairs that were not declared to be ambiguous."
ReplyDeleteThat seems to indicate we are not looking at the ambiguous pairs, and that "n" is not the same as the total number of butterflies collected...
Re problem 3.12, your input is going to consist of statements like
ReplyDelete"Bach and Washington overlapped" (perhaps known because we found a letter from one to the other), or "Shakespeare died before Washington was born." The second type of statement gives full information about the relative order of their births and deaths, while the first type only gives partial information. In particular, it doesn't tell you that Bach was born before Washington.
Re problem 10, Ken has summarized it correctly.