Homework 12
Last updated: Thu, 9 May 2024 12:37:05 -0400
Out: Wed May 08, 12:00pm EST (noon)
Due: Wed May 15, 12:00pm EST (noon) (no late hw accepted!)
This assignment explores the time complexity classes P and NP.
Homework Problems
Scheduling in P? (6 + 6 + 6 = 18 pts)
Scheduling Courses in NP? (9 + 9 = 18 points)
Dynamic Progamming (10 + 10 = 20 points)
README (4 points)
Total: 60 points
Submitting
Submit your solution to this assignment in Gradescope hw12. Please assign each page to the correct problem and make sure your solutions are legible.
A submission must also include a README containing the required information.
1 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 \textbf{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 \textbf{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.
2 Scheduling Courses in NP?
Now, for the same generalized problem as in Scheduling in P?, assume the following additional information is known about the courses and classrooms:
each course has some number of students enrolled,
each classroom has some maximum capacity,
each course has an instructor,
each course instructor can specify some (subset of all the) classrooms that they do not want to teach in.
each course is only assigned to one classroom,
no two courses are assigned to the same classroom,
each course is not assigned to a classroom where the instructor does not want to teach,
each course is assigned to a classroom whose max capacity is greater than or equal to the number of enrolled students.
Formally, define a language (Co is a set of courses and Cl is a set of classrooms):
L = \left\{\left\langle Co,Cl\right\rangle\mid \textrm{there is a valid schedule for } Co\textrm{ and } Cl\right\}
Give two separate proofs that the problem of finding a valid assignment of courses to classrooms is in \textbf{NP}.
Be sure to structure each proof in the form of a Statements and Justifications table. In particular be careful about the justifications for each proof (they won’t be the same). The "Examples Table" for each proof requires at least 1 example not in the language and 1 example in the language.
Creating a verifier requires a certificate. Make sure to be precise about explaining what kind of value the certificate is and what it represents.
Creating a non-deterministic TM requires a precise explanation about when the TM uses non-determinism, i.e., exactly how and when the computation branches.
3 Dynamic Progamming
Assume you have a Python program consisting of n function definitions (f_1 to f_n). Each function takes a single argument that is a number and produces a number output. Now assume, given some input, you are asked to come up with an algorithm that finds whether some sequence of function calls (each function may be called at most once, but not every function needs to be called) that produces a result less than some threshold.
Formally, define the following language (where F is a set of functions f_1 to f_n, x is the initial input, and k is the threshold value):
P = \left\{\left\langle F,x,k\right\rangle\mid \textrm{there is seq of fn calls on }x\textrm{ whose result is} < k\right\}
Give a brute-force algorithm for deciding this language
Give a polynomial time algorithm deciding this language. Your answer must use dynamic programming.