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

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 m 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.

Find: An optimal way to schedule students to steps such thatthere is the least amount of switching as possible.

(a) Describe the optimal substructure of this problem

(b) Describe the greedy algorithm that could find an optimal wayto schedule the students.

In your PDF, based on your answer to part b, give a full proofthat your greedy algorithm returns an optimal solution.

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… . . .