3. What Kind of Bear are You? [25 points] You are at your cabin in the...

Transcribed Image Text:

3. What Kind of Bear are You? [25 points] You are at your cabin in the deep woods and have taken many pictures of bears - some of them are grizzly bears, some of them are brown bears, and some of them are black bears. You have no problem telling which ones are black bears so you can easily tag all those photos as black bears, put them in a Black Bear folder, and be done with them, but you absolutely cannot remember what allows you to tell whether a photo is of a grizzly bear or a brown bear. Being in the deep woods, you also don't have cell service or internet and so can't run your favorite deep net image classification algorithms. What you can do is look at two photos and say "those are the same species" or "those are different species." You do a bunch of such comparisons and write them all down. You then start with one of the photos and say "let's call this species, species A" and put it in folder A. Your goal is to perfectly place every animal into a folder A (“all of these are species A") or folder B ("all of these are species B") where species B is the other remaining species (though you aren't sure whether A means grizzly bear or brown bear). Given your data, you need to respond with one of three options: • Inconsistent: you have analyzed the pictures in such a way that you can't possibly classify them all into species A and B correctly (for example you said photo 1 and 2 were the same species, photo 2 and 3 were different species, and photos 1 and 3 were the same species). Underspecified: your answers aren't inconsistent, but there is at least one picture that (from the data you've collected so far) could validly be either species A or species B. • Exact answer: your answers aren't inconsistent, and every photo can be only one of species A or B. Describe an algorithm to return which of those three cases the input matches, and if you're in the exact answer case to store the species labels for each photo. Sample Input I: There are 4 images. Image 1 and 2 are different species Image 3 and 4 are the same species Image 1 is "species A" Correct Output: Underspecified Sample Input II: There are 4 images. Image 1 and 2 are different species Image 1 and 4 are the same species Image 3 and 4 are different species Image 1 and 3 are different species Image 1 is "species A" Correct Output: Exact Answer Sample Input III: There are 4 images. Image 1 and 2 are different species Image 1 and 4 are the same species Image 3 and 4 are different species Image 1 and 3 are the same species Image 1 is "species A" Correct Output: Inconsistent (a) Give pseudocode (and/or English) to solve this problem. You will probably want to construct at least one graph, you can assume creating vertices and edges takes O(1) time each, and you can give an English/mathematical description of the vertices and edges (don't worry about code constructs for creating it). Any algorithm from class you use as a black box without modification does not need to be written out in full but you need to specify exactly how to modify it if you make changes to it. (b) In proving that your algorithm is correct you may use known properties of any analysis of any algorithm from class as well as any of the data structures and their properties from 332. (c) For analyzing the running time of your algorithm, assume that you have p photos that are either grizzly or brown bears, s pairs identified as "the same" and d pairs identified as "different." Give a big-O bound in terms of p, s, d. 3. What Kind of Bear are You? [25 points] You are at your cabin in the deep woods and have taken many pictures of bears - some of them are grizzly bears, some of them are brown bears, and some of them are black bears. You have no problem telling which ones are black bears so you can easily tag all those photos as black bears, put them in a Black Bear folder, and be done with them, but you absolutely cannot remember what allows you to tell whether a photo is of a grizzly bear or a brown bear. Being in the deep woods, you also don't have cell service or internet and so can't run your favorite deep net image classification algorithms. What you can do is look at two photos and say "those are the same species" or "those are different species." You do a bunch of such comparisons and write them all down. You then start with one of the photos and say "let's call this species, species A" and put it in folder A. Your goal is to perfectly place every animal into a folder A (“all of these are species A") or folder B ("all of these are species B") where species B is the other remaining species (though you aren't sure whether A means grizzly bear or brown bear). Given your data, you need to respond with one of three options: • Inconsistent: you have analyzed the pictures in such a way that you can't possibly classify them all into species A and B correctly (for example you said photo 1 and 2 were the same species, photo 2 and 3 were different species, and photos 1 and 3 were the same species). Underspecified: your answers aren't inconsistent, but there is at least one picture that (from the data you've collected so far) could validly be either species A or species B. • Exact answer: your answers aren't inconsistent, and every photo can be only one of species A or B. Describe an algorithm to return which of those three cases the input matches, and if you're in the exact answer case to store the species labels for each photo. Sample Input I: There are 4 images. Image 1 and 2 are different species Image 3 and 4 are the same species Image 1 is "species A" Correct Output: Underspecified Sample Input II: There are 4 images. Image 1 and 2 are different species Image 1 and 4 are the same species Image 3 and 4 are different species Image 1 and 3 are different species Image 1 is "species A" Correct Output: Exact Answer Sample Input III: There are 4 images. Image 1 and 2 are different species Image 1 and 4 are the same species Image 3 and 4 are different species Image 1 and 3 are the same species Image 1 is "species A" Correct Output: Inconsistent (a) Give pseudocode (and/or English) to solve this problem. You will probably want to construct at least one graph, you can assume creating vertices and edges takes O(1) time each, and you can give an English/mathematical description of the vertices and edges (don't worry about code constructs for creating it). Any algorithm from class you use as a black box without modification does not need to be written out in full but you need to specify exactly how to modify it if you make changes to it. (b) In proving that your algorithm is correct you may use known properties of any analysis of any algorithm from class as well as any of the data structures and their properties from 332. (c) For analyzing the running time of your algorithm, assume that you have p photos that are either grizzly or brown bears, s pairs identified as "the same" and d pairs identified as "different." Give a big-O bound in terms of p, s, d.

Answer rating: 100% (QA)

a Heres an algorithm to solve this problem Explanation To solve this problem we can use the concept of connected components in a graph We will create a graph where each photo is represented as a node ... View the full answer