As part of the annual computer science competition, the mentors of the m competition teams have agreed on a new system of selecting the new students, with the aim of creating the best possible team. Each team is entitled to have 8 students in its team. Depending on the already existing number of students of each group (students who have not graduated and belonged to a group in the previous year remain in the group), each of them has the right to register a different number of new students, i.e. group i can to register. There are n new students, where each of them is interested in competing in some of the teams.

Each group has a ranking of all students in order of preference, and each student has a ranking of all groups in order of preference. Assume that there are more students than the m group places offered. The goal is to find a way of assigning students to at most one team (i.e. a student cannot compete in two or more teams), in such a way that all the offered positions of all teams are filled (i.e. 100% filling of the of offered positions). Note that since there are more students than the places offered, it follows that some students may not be selected from a group.
 
A placement (matching) of a student to a group is stable if none of the following situations occur:  Type A instability: There are students m and m' and a group O such that  m is not assigned to any group, and  m' is assigned to O, but O prefers m to m'.  Type B instability: There are students m and m' and groups O and O' such that  m is assigned to O and m' is assigned to O', and  O prefers m' to m and m' prefers O to O'.
 
Remark: Essentially we have the problem of Stable Marriages, with the difference that (i) groups may want more than one student, and (ii) there is a surplus of students.
 
 (a) Using the Backtracking technique, design an efficient algorithm that for each instance of the problem finds a stable assignment of students to groups. Analyze the Time Complexity of your algorithm, giving the necessary explanations. Hint: Use as a basis the version of the gale shapley algorithm.
 
 
 
No code just explain the algorithm and some pseudocode