TAMAOI
7th December 2012, 02:04
4.inspired by the example of that great Cornellian, Vladimir Nabokov, some
of your frien.ds have become amateur lepidopterists (they study butterflies).
Often when they return from a trip with specimens of butterf~es,
it is very difficult for them to tell how many distinct species theyve
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 well call A and B for
purposes of this discussion. Theyd like to divide the n specimens into
two groups--those that belong to . A and those that belong to B--but its
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 theyre confident enough in their judgment, then they 1abe! the
pair (i,j) either "same" (meaning they believe them both to come from
the same species) or "different" (meaning they believe them to come from
different species). They also have the option of rendering no judgment
on a given pair, in which case well 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. Theyd 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, well 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 i andj have the same label; and for each
pair (i,j) labeled "different," it is the case that i andj have different labels.
Theyre 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.
3. The algorithm described in Section 3.6 for computing a topological ordering
of a DAG repeatedly finds a node with no incoming edges and deletes
it. This will eventually produce a topological ordering, provided that the
? input graph really is a DAG.
But suppose that were given an arbitrary graph that may or may not
be a DAG. Extend the topological ordering algorithm so that, given an
input directed graph G, it outputs one of two things: (a) a topological
ordering, thus establishing that a is a DAG; or (b) a cycle in G, thus
establishing that a is not a DAG. The nmning time of your algorithm
should be O(m + n) for a directed graph with n nodes and m edges.
of your frien.ds have become amateur lepidopterists (they study butterflies).
Often when they return from a trip with specimens of butterf~es,
it is very difficult for them to tell how many distinct species theyve
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 well call A and B for
purposes of this discussion. Theyd like to divide the n specimens into
two groups--those that belong to . A and those that belong to B--but its
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 theyre confident enough in their judgment, then they 1abe! the
pair (i,j) either "same" (meaning they believe them both to come from
the same species) or "different" (meaning they believe them to come from
different species). They also have the option of rendering no judgment
on a given pair, in which case well 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. Theyd 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, well 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 i andj have the same label; and for each
pair (i,j) labeled "different," it is the case that i andj have different labels.
Theyre 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.
3. The algorithm described in Section 3.6 for computing a topological ordering
of a DAG repeatedly finds a node with no incoming edges and deletes
it. This will eventually produce a topological ordering, provided that the
? input graph really is a DAG.
But suppose that were given an arbitrary graph that may or may not
be a DAG. Extend the topological ordering algorithm so that, given an
input directed graph G, it outputs one of two things: (a) a topological
ordering, thus establishing that a is a DAG; or (b) a cycle in G, thus
establishing that a is not a DAG. The nmning time of your algorithm
should be O(m + n) for a directed graph with n nodes and m edges.