Scheduling in P$?$

Image that WISER is down, so UMB has hired you to compute possible course schedules for the school.

A schedule is an assignment $($mapping$)$ of courses to classrooms. If there are $100$ different courses and $100$ different classrooms, compute the maximum number of possible schedules to consider in a brute$-$force algorithm.

Now assume you are asked to find a valid schedule and you have a constant$-$time verifier that can check one assignment of courses to classrooms. Explain why this brute$-$force algorithm to find a valid schedule is actually in

P

P$.$

Now imagine the brute$-$force algorithm from above is generalized to

$$

n different courses and

$$

n different classrooms. Explain the worst case run time of this algorithm to find valid assignment, in terms of

$$

n$,$ and explain why it is no longer in

P

P$.$

Finally, assume that checking the validity of one assignment gives enough information to eliminate half of the remaining unchecked assignments $($round down$).$ Give an algorithm to find a valid schedule, using this new knowledge after each check, that runs in at most polynomial time.