代写polynomial-time、代做2CNF formula、代写c/c++，Python编程语言、Java代写

日期：2019-04-24 11:01

There are four problems on the final.

Note: Recall that there is no collaboration on the final.

Problem 8.1. A hospital is trying to schedule their doctors for night shifts over the next n

nights. There are d doctors. Each doctor i can only work certain nights Pi due to personal

constraints. For night k, the hospital needs exactly sk doctors to do the night shift. To be

fair, the hospital doesn’t want any doctor to do more than m night shifts.

Give a polynomial-time algorithm to determine whether the hospital can schedule their

doctors so that all the constraints are met. If the hospital can, your algorithm should also

output for each doctor the list of its night shifts.

Problem 8.2. Let M2C be the following problem. Given a 2CNF formula φ and an integer

k, decide if φ has a satisfying assignment with at least k variables set to true. In other words:

M2C = {(φ, k) : φ is a 2CNF which has a satisying assignment with ≥ k variables true}.

For example, consider φ = (x ∨ y) ∧ (y ∨ z). We have that (φ, 2) ∈ M2C because

you can set x and y to true and z to false, but (φ, 3) 6∈ M2C.

Give a polynomial-time reduction from CLIQUE to M2C. Prove that the reduction is

correct.

(Hint: It may be useful to notice that a set of nodes C is a clique if and only if for every

{i, j} which is not an edge, at least one of i and j is not in C.)

Problem 8.3. For your co-op you are developing the next state-of-the-art flight search

engine. You have the list of all n daily flights in the world. For each flight you have starting

city, destination city, departure time, arrival time, and price. (The arrival time is always

after the departure time.) A customer currently at city cs wants to get to city cd. It is now

time ct

.

1. Describe an algorithm to compute the earliest possible time the customer can arrive

at destination, using any number of flights and at any cost.

2. Same as 1., but now the customer won’t pay more than cp in total for the trip.

3. Same as 2., but in addition the customer won’t do more than cf flights. (Note you

have both a constraint on the price and on the number of flights.)

Your running time should be polynomial in n.

Problem 8.4. Starting with an empty AA tree, you do the following operations in order:

insert(3), insert(5), insert(1), insert(2), insert(7), insert(8), insert(6), insert(4), delete(2),

delete(6). Draw the tree after each insertion and deletion, including the levels of the nodes.

(Note that insertion and deletion call other functions. You are only required to draw the tree

at the end of insertion and deletion; but feel free to draw intermediate trees for convenience.)

60