Question

Continuing on the context of courses at UNBSJ, let’s imagine that the Department of Computer Science would like to get more detailed feedback on the courses that it offers. This would be done through a focus group made up of students taking at least one CS course this year. In order to have a complete coverage, there would be a need to have students from every CS course being offered. However, we would also want to minimize the total number of students that will take part into this group, so as to make the discussions easier to manage (assuming that a very large group would make it hard to get everybody to truly participate in the discussions). More formally, here is the "CS focus group" problem: given a value k (smaller than the number of CS courses), and a set of students with the list of courses they are taking, is it possible to find k students to be part of this focus group, so that feedback could be collected on all courses offered?

a)Show that this problem is NP-complete.

b)What would you change in your proof for a similar problem, but where the students chosen for the CS focus group cannot be taking an ENGG course at the same time?

c)Propose a randomized algorithm to solve the problem in part a . Your algorithm should be much faster than any deterministic algorithm (i.e., non-randomized algorithm). Is your algorithm a Monte-Carlo one or a Las Vegas one? Is it biased? Explain why (for both questions).

Answer 1

To show the 'CS focus group' problem as NP-complete, it must be proven to be in NP and reducible to a known NP-complete problem. Part b would require adjusting the proof to include the new constraint of excluding ENGG course-takers. A randomized algorithm for part c could be Monte-Carlo or Las Vegas, and should avoid sample bias by ensuring equal selection chances.

Step-by-step explanation:

The 'CS focus group' problem refers to selecting a group of k students from different computer science courses to gather comprehensive feedback while minimizing group size. To prove this problem is NP-complete, we would need to demonstrate that it is both in NP and that any problem in NP can be reduced to it in polynomial time, a process that often involves relating it to known NP-complete problems like Set Cover or Vertex Cover. The goal is to create a subset of students that collectively covers all the CS courses, which is a similar conceptual framework as these well-known problems.

For part b, if the constraint is added where students cannot be taking an ENGG course simultaneously, the proof would still follow a similar structure but would need additional components to capture the increased complexity of the problem. This might involve modifying the reduction to account for the additional constraint or showing that this version of the problem is also NP-hard separately.

Regarding part c, a randomized algorithm might approach the problem by repeatedly selecting random groups of students until it finds one that covers all courses or reaches a specified iteration limit. Depending on whether the algorithm guarantees a correct solution (and thus may run indefinitely) or provides a probable solution within a fixed number of steps, it would be classified as Las Vegas or Monte-Carlo, respectively. To avoid a biased outcome, the student selection process within the algorithm must ensure that each student has an equal chance of being chosen.