Skimanner

This is a long problem but it has me totally lost so I'm gonna type it out and hope for the best. I'm studying for a mid-term so I don't want the exact answer to it, I just wanna understand what the algorithm is supposed to do. The only thing I'm really sure of is that it should be a breath-first search since the runtime needs to be O(m+n). Thanks in advance for any help.

Some of your friends have become amateur lepidopterists (they study butterflies). Often when they return from a trip with specimens of butterflies, it is very difficult for them to tell how many distinct species they've caught, thanks to the fact that many species look very similar to one another.

One day they return with n butterflies, and they believe that each belongs to one of two different species, which we'll call A and B for purposes of this discussion. They'd like to divide the n specimens into two groups, that that belong to A and those that belong to B but it's very hard for them to directly label any one specimen. So they decide to adopt the following approach.

For each pair of specimens i and j, they study them carefully side by side. If they're confident enouch in their judgment, then they label the pair (i,j) either "same" (meaning they believe them both to come from the same species) or "different" (meaning they believe them to com from different species). They also have the option of rendering no judgment on a given pair, in which case we'll call the pair ambiguous.

So now they have the collection of n specimens, as well as a collection of m judgments (either "same" or "different") for the pairs that were not declared to be ambiguous. They'd like to know if this data is consistent with the idea that each butterfly is from one of species A or B. So more concretely, we'll declare the m judgments to be consistent if it is possible to label each specimen either A or B in such a way that for each pair (i,j) labeled "same," it is the case that ia and j have the same label; and for each pair (i,j) labeled "different," it is the case that i and j have different labels. They're in the middle of tediously working out whether their judgments are consistent, when one of them realizes that you probably have an algorithm that would answer this question right away.

Give an algorithm with running time O(m+n) that determines whether the m judgments are consistent.

Sane

The algorithm involves traversing a graph. Whether you do this with a DFS or a BFS is up to you, but I would strongly suggest a DFS. A BFS is typically reserved for the special cases where you need to process nodes in order of distance from the source.

Create some sample data, take out a sheet of paper, and then draw a graph where a vertex represents a butterfly (n of these) and an edge represents a label (m of these). Draw a green-coloured edge between butterflies that are the same. Draw a red-coloured edge between butterflies that are different. Draw no edge between ambiguities.

Look at the graph, and see if you can solve it by hand. How were you able to tell if it's consistent or not? If you don't know how you did it, then try again on some more data until you see the pattern. Can you generalize your observations? Turn these observations into concrete statements (or constraints) that must be satisfied for it to be consistent.

Then you can do a series of graph traversals to gather the information necessary to evaluate and test the requirements for consistency.

__________________
|¯_/ . /¯\ . |¯\|¯| |_¯ PFO's Folding@Home Team
/¯_| /_/\_\ |_|\_| |__ Sane's Monthly Algorithms Challenges

Skimanner

So what were looking at here is that we are gonna have a given graph with colored edges based on there judgements and as we go through the DFS we compare the color of the edge the graph has to see if its consistent with the color it should be?

Sane

It's not "as we go through the DFS we compare the colors". Thoroughly reread my last post. In particular, the part about "turning your observations into concrete statements (or constraints) that must be satisfied". Then as you traverse the graph, you can gather data about the graph. Afterwards, you use this data and compare it with what you expect. The important part is you need to be able to solve this problem, by hand, to figure out what this data is.

__________________
|¯_/ . /¯\ . |¯\|¯| |_¯ PFO's Folding@Home Team
/¯_| /_/\_\ |_|\_| |__ Sane's Monthly Algorithms Challenges