[Solved]Running Physics Experiment N Complicated Steps Students Sign Steps Help Experiment Require Q37138465

You are running a physics experiment with n complicated steps,and students sign-up for some steps to help. Your experimentrequires n steps, and each of the students gives you a list ofwhich steps they can help out with (steps require special skills).From experience, you know things run most smoothly when you have aslittle switching of shifts as possible.

For example, if your experiment has <1, 2, 3, 4, 5, 6>steps

• Student 1: <1, 2, 3, 5>
• Student 2: <2, 3, 4>
• Student 3: <1, 4, 5, 6>
  Your optimal solution would be:
  Student 1 <1, 2, 3>, Student 2 does no steps, Student 3 does<4, 5, 6>. Only 1 switch

Another example if your experiment has 8 steps <1, 2, 3, 4,5, 6, 7, 8>

• Student 1: <5, 7, 8>
• Student 2: <2, 3, 4, 5, 6>
• Student 3: <1, 5, 7, 8>
• Student 4: <1, 3, 4, 8>
  Your optimal solutions could be any one of these:
  • Student 1 does no steps, Student 2 does <2, 3, 4, 5, 6>,Student 3 does <1, 7, 8>, Student 4 does no steps –> 3switches
  • Student 1 does <7, 8>, Student 2 does <2, 3, 4, 5,6>, Student 3 does <1>, Student 4 does nothing –> 3switches
  • Student 1 does no steps, Student 2 does <2, 3, 4, 5, 6>,Student 3 does <7, 8>, Student 4 does <1> –> 3switches

Given: n number of steps, m number of students that give you alist of steps (sorted) they can participate in. Assume there’s alookup table where you can find if student X signed up for step Yin O(1), so no need to factor that into your runtime.

a. Code your greedy algorithm in the file”PhysicsExperiment.java” under the “scheduleExperiments” methodwhere it says “Your code here”. Read through the documentation forthat method. Note that I’ve already set up the lookup tableautomatically for every test case. Do not touch the other methodsexcept possibly the main method to build your own test cases (butdelete/comment out your own test cases in the submission). Run thecode without your implementation first and you should see this:
With your implementation, your final output should look somethinglike this:

//

/**
* Physics Experiment
* Author
* Does this compile or finish running within 5 seconds? Y/N
*/

/**
* This class implements a greedy scheduler to assign students
* to steps in a physics experiment. There are three test cases inthe main
* method. Please read through the whole file before attempting tocode the
* solution.
*
* You will only be graded on code you add to thescheduleExperiments method.
* Do not mess with the existing formatting and identation.
* You don’t need to use the helper methods, but if they come inhandy setting
* up a custom test case, feel free to use them.
*/
public class RSA {

/**
* The actual greedy scheduler you will be implementing!
* @param numStudents The number of students who can participate,m
* @param numSteps The number of steps in the experiment, n
* @param signUpTable An easy lookup tool, signUpTable[x][Y] =student X signed up or did not sign up for step Y.
* Example:
signUpTable[1][3] = 1 if Student 1 signed up for Step 3
signUpTable[1][3] = 0 if Student 1 didn’t sign up for Step 3
* @return scheduleTable: a table similar to the signUpTable wherescheduleTable[X][Y] = 1 means
* student X is assigned to step Y in an optimal schedule
*/
public int[][] scheduleExperiments(
int numStudents,
int numSteps,
int[][] signUpTable
) {
// Your scheduleTable is initialized as all 0’s so far. Your codewill put 1’s
// in the table in the right places based on the returndescription
int[][] scheduleTable = new int[numStudents + 1][numSteps + 1];

// Your code goes here

return scheduleTable;
}

/**
* Makes the convenient lookup table based on the steps each studentsays they can do
* @param numSteps the number of steps in the experiment
* @param studentSignUps student sign ups ex: {{1, 2, 4}, {3, 5},{6, 7}}
* @return a lookup table so if we want to know if student x can dostep y,
lookupTable[x][y] = 1 if student x can do step y
lookupTable[x][y] = 0 if student x cannot do step y
*/
public int[][] makeSignUpLookup(int numSteps, int[][]studentSignUps) {
int numStudents = studentSignUps.length;
int[][] lookupTable = new int[numStudents+1][numSteps + 1];
for (int student = 1; student <= numStudents; student++) {
int[] signedUpSteps = studentSignUps[student-1];
for (int i = 0; i < signedUpSteps.length; i++) {
lookupTable[student][signedUpSteps[i]] = 1;
}
}
return lookupTable;
}

/**
* Prints the optimal schedule by listing which steps each studentwill do
* Example output is Student 1: 1, 3, 4
* @param schedule The table of 0’s and 1’s of the optimal schedule,where
* schedule[x][y] means whether in the optimal schedule student x isdoing step y
*/
public void printResults(int[][] schedule) {
for (int student = 1; student < schedule.length; student++){
int[] curStudentSchedule = schedule[student];
System.out.print(“Student ” + student + “: “);
for (int step = 1; step < curStudentSchedule.length; step++){
if (curStudentSchedule[step] == 1) {
System.out.print(step + ” “);
}
}
System.out.println(“”);
}
}

/**
* This validates the input data about the experiment stepsign-ups.
* @param numStudents the number of students
* @param numSteps the number of steps
* @param signUps the data given about which steps each student cando
* @return true or false whether the input sign-ups match the givennumber of
* students and steps, and whether all the steps are guaranteed atleast
* one student.
*/
public boolean inputsValid(int numStudents, int numSteps, intsignUps[][]) {
int studentSignUps = signUps.length;

// Check if there are any students or signups
if (numStudents < 1 || studentSignUps < 1) {
System.out.println(“You either did not put in any student or anysignups”);
return false;
}

// Check if the number of students and sign-up rowsmatches
if (numStudents != studentSignUps) {
System.out.println(“You input ” + numStudents + ” students but yoursignup suggests ” + signUps.length);
return false;
}

// Check that all steps are guaranteed in the signups
int[] stepsGuaranteed = new int[numSteps + 1];
for (int i = 0; i < studentSignUps; i++) {
for (int j = 0; j < signUps[i].length; j++) {
stepsGuaranteed[signUps[i][j]] = 1;
}
}
for (int step = 1; step <= numSteps; step++) {
if (stepsGuaranteed[step] != 1) {
System.out.println(“Your signup is incomplete because not all stepsare guaranteed.”);
return false;
}
}

return true;
}

/**
* This sets up the scheduling test case and calls the schedulingmethod.
* @param numStudents the number of students
* @param numSteps the number of steps
* @param signUps which steps each student can do, in order ofstudents and steps
*/
public void makeExperimentAndSchedule(int experimentNum, intnumStudents, int numSteps, int[][] signUps) {
System.out.println(“—-Experiment ” + experimentNum +”—-“);
if (!inputsValid(numStudents, numSteps, signUps)) {
System.out.println(“Experiment signup info is invalid”);
return;
}
int[][] signUpsLookup = makeSignUpLookup(numSteps, signUps);
int[][] schedule = scheduleExperiments(numStudents, numSteps,signUpsLookup);
printResults(schedule);
System.out.println(“”);
}

/**
* You can make additional test cases using the same format. In factthe helper functions
* I’ve provided will even check your test case is set up correctly.Do not touch any of
* of the existing lines. Just make sure to comment out or deleteany of your own test cases
* when you submit. The three experiment test cases existing in thismain method should be
* the only output when running this file.
*/
public static void main(String args[]){
RSA pe = new RSA();

// Experiment 1: Example 1 from README, 3 students, 6steps:
int[][] signUpsExperiment1 = {{1, 2, 3, 5}, {2, 3, 4}, {1, 4, 5,6}};
pe.makeExperimentAndSchedule(1, 3, 6, signUpsExperiment1);

// Experiment 2: Example 2 from README, 4 students, 8steps
int[][] signUpsExperiment2 = {{5, 7, 8}, {2, 3, 4, 5, 6}, {1, 5, 7,8}, {1, 3, 4, 8}};
pe.makeExperimentAndSchedule(2, 4, 8, signUpsExperiment2);

// Experiment 3: Another test case, 5 students, 11 steps
int[][] signUpsExperiment3 = {{7, 10, 11}, {8, 9, 10}, {2, 3, 4, 5,7}, {1, 5, 6, 7, 8}, {1, 3, 4, 8}};
pe.makeExperimentAndSchedule(3, 5, 11, signUpsExperiment3);
}
}

-Experiment 1—- Student 1: Student 2: Student 3: Experiment 2- Student 1: Student 2: Student 3: Student 4: Experiment 3—- Student 1: Student 2: Student 3: Student 4: Student 5: We were unable to transcribe this imageShow transcribed image text -Experiment 1—- Student 1: Student 2: Student 3: Experiment 2- Student 1: Student 2: Student 3: Student 4: Experiment 3—- Student 1: Student 2: Student 3: Student 4: Student 5:

Expert Answer

---

Answer to You are running a physics experiment with n complicated steps, and students sign-up for some steps to help. Your experim… . . .