A group of butterfly lovers examine n butterflies to determine which are part of the same...

Transcribed Image Text:

A group of butterfly lovers examine n butterflies to determine which are part of the same species. Their examination produces a set of m assertions of the form S(x, y), meaning "butterflies z and y are of the same species". Assume these assertions are all accurate, and that "same species" is an equivalence relation. Also assume that if the assertions together with the rules for equivalence relations do not imply that two butterflies are of the same species, then they belong to different species. a) (8p) Give an algorithm that has as input the list of butterflies and assertions, and two butterflies z and y, and returns a boolean stating whether and y are of the same species. Argue that your algorithm is correct and analyze its running time. b) (5p) Give an algorithm that has as input the list of butterflies and assertions and returns the number of different butterfly species. Argue that your algorithm is correct and analyze its running time. c) (7p) Give an algorithm that takes as input the list of butterflies and the list of assertions and returns a minimum-size subset of assertions that suffice to answer for any two butterflies whether they are of the same species, i.e., question (a). Argue that your algorithm is correct and analyze its running time. A group of butterfly lovers examine n butterflies to determine which are part of the same species. Their examination produces a set of m assertions of the form S(x, y), meaning "butterflies z and y are of the same species". Assume these assertions are all accurate, and that "same species" is an equivalence relation. Also assume that if the assertions together with the rules for equivalence relations do not imply that two butterflies are of the same species, then they belong to different species. a) (8p) Give an algorithm that has as input the list of butterflies and assertions, and two butterflies z and y, and returns a boolean stating whether and y are of the same species. Argue that your algorithm is correct and analyze its running time. b) (5p) Give an algorithm that has as input the list of butterflies and assertions and returns the number of different butterfly species. Argue that your algorithm is correct and analyze its running time. c) (7p) Give an algorithm that takes as input the list of butterflies and the list of assertions and returns a minimum-size subset of assertions that suffice to answer for any two butterflies whether they are of the same species, i.e., question (a). Argue that your algorithm is correct and analyze its running time.

Answer rating: 100% (QA)

This problem involves handling relationships between butterflies based on assertions about their species Here are the algorithms for each part a Algorithm to Check Species Equality python def samespec... View the full answer