An English conversation school plans to make pairs of students and teachers for private lessons. Given a set of students and a set of teachers, we make disjoint pairs of a student and a teacher, which we call a -match. Answer the following questions:
(1) How many -matches exist?
(2) For , given a list of preferable teachers by students (Table 1)
draw a graph , and show a -match which maximizes the number of students who are fulfilled.
Student
Teachers
Table 1: List of Preferences
(3) Let the size of a set . Show an algorithm to get a -match which maximizes the number of students who are fulfilled and its complexity.
(4) For , given a ranked list of teachers by students (Table 2), show a -match which minimizes the total sum of ranks.
(5) In addition to the ranked list of teachers by students, consider a ranked list of students by teachers. Given a -match, if there exists no pair of student and teacher who would both get the higher rank than that of the current partner of the given -match, then, this -match is called an -match. For , given a ranked list of students by teachers (Table 3) in addition to the Table 2, show an -match.
Ranking
1
2
3
4
5
6
7
Table 2: Rank of teachers by students
Ranking
1
2
3
4
5
6
7
Table 3: Rank of students by teachers
(6) For , show an algorithm to get an -match and its complexity.
(7) We will develop a real software system for private lessons for an English conversation school. List possible study items (example: web reservation), and describe each item in two lines.