Suppose we have a set U={1,2,,n}. Let S be an unknown subset of U, such that we do not know its size or members. However, we do have a devise that can answer the following queries: given a subset T of U of our choosing, the devise tells us whether T and S have an element in common or not. We want to use this devise to learn S in its entirety and output it. 1. How many possible subsets S are there? 2. Give an algorithm that finds S using n queries. 3. Show that at least n queries are necessary to learn S. (Hint: Try to adapt the idea behind the proof that comparison-based sorting requires (nlogn) comparisons to this setting.)