Question

Courses offered at UNB are scheduled as a set of non-contiguous time slots (e.g., MWF 12:30). When a student takes multiple courses, he or she must ensure that the courses taken are not overlapping. Let’s imagine that someone looks at the course timetable, and is interested in taking as many of them as possible (foolishly thinking that there isn’t much extra work to do outside classes). Note: we will not be looking at prerequisites here. For simplicity, let’s also assume that the time slots that a course can be in are by blocks of full hours only, between 9am and 4pm (i.e., no course would start or end at other times than 9am, 10am, 11am, …, 3pm, or 4pm). For example, the following schedule would be valid under these circumstances for CS2043: MWF from 10am to 11am, and a lab on Monday from 2pm to 4pm.

Prove that this "Maximum Course Selection" problem is NPcomplete. More precisely, the problem is: having a list of possible courses, each covering a non-empty set of time periods during the week (under the restrictions above), is it possible to choose k of such courses such that they are not overlapping in time?

Answer 1

The 'Maximum Course Selection' problem can be proven to be NP-complete by reducing it to the 'Subset Sum' problem.

Step-by-step explanation:

The given problem, known as the 'Maximum Course Selection' problem, can be proven to be NP-complete. This means that it is very difficult to find an optimal solution in a reasonable amount of time. The proof of NP-completeness can be done by reducing it to a known NP-complete problem, such as the 'Subset Sum' problem.

Here's how the reduction can be done:

1. Assume that we have a list of time slots, where each time slot is represented as a number between 1 and n.
2. For each course, create a set of time slots that the course covers. For example, if a course covers time slots 2, 3, and 4, create a set {2, 3, 4}.
3. Create the 'Subset Sum' problem by setting the target sum to k, where k is the number of courses that need to be selected without overlapping.
4. If there is a subset of courses whose time slots, when added together, equal k, then it is possible to choose k courses without overlapping.
5. By proving that the 'Maximum Course Selection' problem can be reduced to the 'Subset Sum' problem, we can conclude that the 'Maximum Course Selection' problem is NP-complete.