At the Computer Science Department at the beginning of the first semester there are p freshmen (study) groups: group i contains ni students, for all i = 1, p. For the second semester the Department wants to reorganize these groups in such a way that:
(1) the new organizing schema has r groups;
(2) the new group j contains mj students, for any j = 1, r;
(3) any new group cannot contain more than c students which were classmates in a same old group from the former organizing schema (c ∈ NN∗ \ {1}).
We want to know if such a new organizing schema exists.
(a) Devise a network flow model for building (if possible) the new organizing schema.
(b) Prove a characterization of the existence of a solution to this problem in terms of maximum flow in the above network. (In the affirmative case provide a way of building the new schema: which old group will have to cede and how many students to which new group).
(c) What is the time complexity for deciding if a solution exists? (Discuss the time complexity for at least three algorithms.)
2 Peter Breuer: as far, as I understand, there is a constraint on composition of newly organized groups, e.g. it is not possible to keep them unrearranged. Does your hydrologic analogy take it into account?
- Badges
- Science topic
- Similar topics
- Computer Science