The University of Illinois has decided to try something new to assign incoming freshmen room- mates for Fall 2019. Each student will fill out a long, personal survey. Then the university will run a sophisticated program to rate how compatible each pair of students is on an integer scale of -5 to 5. The average compatibility value of an assignment of students to rooms is the average of the compatibility values over every pair of students who are roommates. The university is only willing to actually assign students to rooms if the average compatibility value of the assignment is at leastA, for some constant A.

Unfortunately, the University does not have enough quality space for all incoming freshmen. Any freshmen who are not assigned a room have the option of living in large dormitory rooms with other such students. These students are NOT counted in the value of the assignment.

Assume that the quality rooms can fit a total of n freshmen. The university will randomly pickn freshmen out of all incoming freshmen, and check if there is some assignment for those students with compatibility value at least A. If not, they will again randomly pick n freshman out of all incoming freshmen, and check if there is some assignment with compatibility value at least A. They will keep doing this until they find an acceptable subset of freshmen of size n. Once they have done this, they will find an optimal assignment of the n freshmen to rooms.

There are two problems that need to be solved. Both problems use a compatibility matrix C, where C[a,b] is how compatible students a and b are.

(1) Given an n n compatibility matrix C for n students, r rooms with sizes s1, s2, . . . , sr, where n = ri=1 si, and a target A; determine if there is some assignment of the students to the rooms with average compatibility value at least A.

(2) Given an n n compatibility matrix C for n students, and r rooms with sizes s1, s2, . . . , sr, where n = ri=1 si; find an optimal assignment of the students to the rooms.

These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual you have no idea how to write such programs. For both problems, you find an efficient program on the Internet that solves that problem. Unfortunately your budget will only allow you to buy one such program.

Assume that you have a program that solves the second problem in time (nj), for j 1. Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm?

Assume that you have a program that solves the first problem in time (nk), for k 1. Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm?