The CS department has received several applications for teaching assistant positions from its students. The applicants are provided with the list of available courses and asked to submit a list of their preferences. The TA committee at UTCS prepares a sorted list of the applicants (according to the applicants' background and experience) for each course and the total number of TAs needed for the course. Note that there are more students than available TA spots. There can also be multiple TAS per course, though a single TA can only be assigned to 1 course. Making matter more complicated, applicants and the committee can be indifferent between certain options. For example, a TA could have Algorithms at the top of their list, a tie between OS and Graphics, and Advanced Underwater Basketweaving in last place. The committee can be in a similar position, e.g. with applicant A being the top pick for a particular class, A2 being the second choice, and A3 and A4 tied for third. We will say that A prefers C to Cliff C is ranked higher than C" on his preference list (i.e. they are not tied). The committee wants to apply an algorithm to produce stable assignments such that each student is assigned to at most one course. The assignment of the TAs to courses is strongly stable if none of the following situations arises. 1. If an applicant A and a course C are not matched, but A prefers C more than his assigned course, and C prefers A more than, at least, one of the applicants assigned to it. 2. If there is unmatched applicant A, and there is a course C with an empty spot or an applicant A' assigned to it such that C prefers A to A'. Your task is to do the following: i Modify the Gale-Shapley algorithm to find a stable assignment for the TAs-Courses matching problem. Write pseudo code of modified algorithm. (5 points) ii Prove that the modified algorithm produces stable TAS-Courses assignments. (5 points) IIIO Ourse The CS department has received several applications for teaching assistant positions from its students. The applicants are provided with the list of available courses and asked to submit a list of their preferences. The TA committee at UTCS prepares a sorted list of the applicants (according to the applicants' background and experience) for each course and the total number of TAs needed for the course. Note that there are more students than available TA spots. There can also be multiple TAS per course, though a single TA can only be assigned to 1 course. Making matter more complicated, applicants and the committee can be indifferent between certain options. For example, a TA could have Algorithms at the top of their list, a tie between OS and Graphics, and Advanced Underwater Basketweaving in last place. The committee can be in a similar position, e.g. with applicant A being the top pick for a particular class, A2 being the second choice, and A3 and A4 tied for third. We will say that A prefers C to Cliff C is ranked higher than C" on his preference list (i.e. they are not tied). The committee wants to apply an algorithm to produce stable assignments such that each student is assigned to at most one course. The assignment of the TAs to courses is strongly stable if none of the following situations arises. 1. If an applicant A and a course C are not matched, but A prefers C more than his assigned course, and C prefers A more than, at least, one of the applicants assigned to it. 2. If there is unmatched applicant A, and there is a course C with an empty spot or an applicant A' assigned to it such that C prefers A to A'. Your task is to do the following: i Modify the Gale-Shapley algorithm to find a stable assignment for the TAs-Courses matching problem. Write pseudo code of modified algorithm. (5 points) ii Prove that the modified algorithm produces stable TAS-Courses assignments. (5 points) IIIO Ourse