Will upvote if all parts are answered! Thank you.
2. (30 points) Suppose four students Alice, Bob, Carol, and David are selected to cover tutoring hours for Computer Science, Monday through Thursday. Each student submitted a preference for which day of the week they would like to work (from 1 to 5 5 being the highest preference and 1 being the lowest preference). Each student's preference is shown below: Mon Tue Wed Thu Alice 5 2 3 1 Bob 5 3 4 1 Carol 2 1 3 4 David 4 4 2 3 The supervisor responsible for setting the schedule has decided that she just wants to maximize the overall preferences of the group (i.e., the sum of each student's ratings for their assigned day). Each student should be assigned exactly one day, and each day should be covered. (a) Let A,B,C,D represent the four students. How many different permutations does the supervisor have to assign the four students to the slots for Monday through Thursday? Use the Johnson-Trotter algorithm to generate the permutations according to the minimal change property. (b) Describe an exhaustive search approach for solving the problem and apply your strategy to solve the problem. (c) Suppose that the situation has changed so that some of the students have conflicts on certain days (denoted as a 0 for their preference rating). The supervisor must set the schedule according to an additional constraint that no student may be assigned to a day which he/she has marked with a 0. How does this change your exhaustive search strategy? Does it change the runtime of your solution? Why or why not? (d) Returning to the original version of the problem (i.e., no conflicts), suppose instead that there are six qualified tutors from among whom the supervisor can choose for the four slots. How many permutations need to be evaluated to solve this problem via an exhaustive search? 2. (30 points) Suppose four students Alice, Bob, Carol, and David are selected to cover tutoring hours for Computer Science, Monday through Thursday. Each student submitted a preference for which day of the week they would like to work (from 1 to 5 5 being the highest preference and 1 being the lowest preference). Each student's preference is shown below: Mon Tue Wed Thu Alice 5 2 3 1 Bob 5 3 4 1 Carol 2 1 3 4 David 4 4 2 3 The supervisor responsible for setting the schedule has decided that she just wants to maximize the overall preferences of the group (i.e., the sum of each student's ratings for their assigned day). Each student should be assigned exactly one day, and each day should be covered. (a) Let A,B,C,D represent the four students. How many different permutations does the supervisor have to assign the four students to the slots for Monday through Thursday? Use the Johnson-Trotter algorithm to generate the permutations according to the minimal change property. (b) Describe an exhaustive search approach for solving the problem and apply your strategy to solve the problem. (c) Suppose that the situation has changed so that some of the students have conflicts on certain days (denoted as a 0 for their preference rating). The supervisor must set the schedule according to an additional constraint that no student may be assigned to a day which he/she has marked with a 0. How does this change your exhaustive search strategy? Does it change the runtime of your solution? Why or why not? (d) Returning to the original version of the problem (i.e., no conflicts), suppose instead that there are six qualified tutors from among whom the supervisor can choose for the four slots. How many permutations need to be evaluated to solve this problem via an exhaustive search
