Adoption

We are going to focus on the full problem for now. We’ll briefly discuss the subtask afterwards.

Start with special cases of the problem. Suppose we have a minimal case, where n = 1.

1. Suppose Alice and Bob are the only two people applying for one cat and one dog. How would you determine who gets which pet?
   • It’s easy if one prefers cats and the other prefers dogs. But your method has to work even if both prefer the same type of animal.

Now, apply this to larger inputs.

2. Can you extend the criterion from the previous question, to decide who gets which pet in larger test cases?
   • Reflector:
     • What potential pitfalls can you think of?
     • Devise some challenging test cases, and explain why they are challenging.
   • Other group members:
     • Prepare a convincing argument that your approach is correct.
3. Design an algorithm which determines who gets which pet.
   • Analyse the time complexity of your algorithm.
   • Estimate the running time of an implementation of your algorithm.
4. Write a program which implements your algorithm.
   • Recorder: lead the implementation
   • Presenter: if your group hasn’t come across a C++ feature that would help to solve the problem, approach other groups or the instructors for advice.
   • Reflector:
     • Propose some challenging test cases and explain why they are challenging
     • Test cases should attempt to expose flaws in the algorithm as well as flaws in the implementation.
   • Unfortunately, judging isn’t available for this problem.

For an extension, we’ll think about the intended solution for the subtask. Note that you need some material from future lectures to solve the following problem.

5. Suppose you didn’t make the observations in the previous questions. Rather than determining who gets which pet by a clever rule, propose an algorithm which exhausts the possible allocations of pets without repeated work.
   • Discuss the correctness of your algorithm.
   • Analyse the time complexity of your algorithm.
   • Estimate the running time of an implementation of your algorithm, using the constraints of the subtask.
   • Write a program which implements your algorithm, and test it.