CMSC 27200: Final Exam
代写算法 | NP问题 | 代写aws | assignment代写 – 这道题目是np方面的exam, 涵盖了np等方面, 这是值得参考的算法代写的题目
Important notes:
- 24 hours from download to submission. Extra-time accommodations with the University are honored to the letter (please remind us, but you may submit the ordinary way on Gradescope). In any case, the exam should be submitted not later than midday Saturday (11:59a). Exceptions in limited circumstances only; must be cleared in advance.
- Open book/notes, no collaboration, no web consultation (besides class re- sources), no asking Ed Qs except private clarification or logistics questions to staff. Afterwards, no discussing with students who have not yet taken the exam.
- There are 5 problems, but you are to choose only oneof Problems 4 and 5 to complete. So a completed exam will do{P 1 , P 2 , P 3 }and one ofP4 orP5. If you submit partial work on each ofP 4 , P5, you must clearly indicate which one you want graded.
- Its good to look over all the problem statements first. Read carefully.
- Show your work.Answers without justification will be given little credit.
Problem1 (25 points).(Stores and social value) On a long stretch of semi-rural residential road, there are many houses but no stores to provide local service. Locals want access to Bookstores, Drugstores, and Grocery stores (B, D, G). New zoning l aws allow for stores to be constructed atn evenly-spaced positions 1, 2 ,… , n. Each position i [n] receives applications from a nonempty subsetSi of the business types. E.g. ifSi = {B, D}then a bookstore and drugstore have each applied to open at positioni. We can choose one and only one of the applications to fulfill at each location. (Each application comes from a separate entrepreneur, so we can make independent choices per location.) An assignmentis a functionFwhich chooses a single element siof{B, D, G}, for eachi, and we sayFis feasibleifsiSifor eachi. We consider the population to be evenly distributed across thenlocations. A resident at positioniis said to have easy access tothe stores at positions{i 1 , i, i+ 1 }, except for the boundary cases:i= 1 residents have easy access to locations{ 1 , 2 } andi=nhave easy access to{n 1 , n}. Thesocial valueof an assignmentFis defined as asumof its social value for the residents at locationsi, fori= 1,… , n. The social value for residents atiis defined as the number of distinct store typesthey have easy access to.
Give an algorithmwhich, on input describingS 1 ,… , Sn, computes the max- imum social value of any feasible assignmentF. (You dont have to output an assignment, just the optimal value.) The running time should be bounded by a poly- nomial function ofn. Prove correctness and efficiency. (You need not minimize the runtime or give the best-possible runtime bound for your algo, as long as you prove a poly-time upper bound.)
Example: ifn= 4 and
S 1 = {B, G}, S 2 = {B, D}, S 3 = {B, D, G}, S 4 = {B, G}
then the assignment
F = (s 1 , s 2 , s 3 , s 4 ) = (B, D, G, B)
is feasible and has social value 2 + 3 + 3 + 2, which is clearly best-possible, since residents at each position have easy access to distinct store types at each position within their range. (Note that this may not be possible in general, in which case you should output the largest social value obtained by a feasible assignment.)
Solution 1.Write your solution to Problem 1 here. Expand this area as needed.
Problem2 (25 points).(Saturated edges) For both parts below we are given a directed graphG= (V, E) with distinguished source vertexs, sink vertext, integer edge capacitiesce>0 for eacheE, and a flowf={f(e)}defined on edges. An edge is calledsaturatediff(e) =ce.
(a) we say that the flowf is ablocking flowif for every directed path froms totthere is a saturated edge somewhere along the path. Does it follow thatfis a maximumstflow? Prove or give a counterexample.
(b) Iff is a maximumstflow, consider the set ofT of saturated edges. Is the total capacity ofTequal to the minimum total directed capacity of anys-tcut? Prove or give a counterexample.
Solution 2.Write your solution to Problem 2 here. Expand this area as needed.
Problem3 (25 points).(Disconnecting graphs) Consider the following problem, DISCONNECTION:
Input: an undirected, connected graphG.
Output: the minimum value k such that there exist k edges whose removal disconnects the graph into two or more connected components.
Give an algorithmfor this problem whose runtime is bounded by a polynomial inn=|V(G)|, the number of vertices. Prove correctness and efficiency.
Observe: There are no source/sink nodes in the problem statement. Also, the input graph is undirected and unweighted. Keep this in mind and supply details if/when applying algorithms developed for other types of graphs.
Solution 3.Write your solution to Problem 3 here. Expand this area as needed.
DO THIS PROBLEM OR PROBLEM 5, BUT NOT BOTH
Problem4 (25 points).(3-SAT with restricted variable occurrences) Prove that the following special caseof the 3-SAT (3-CNF satisfiability) problem, which well call 3-SAT(4), is NP-complete.
Input:a collection of clausesC 1 ,… , Cmover Boolean variablesx 1 ,… , xn, where each clauseCjis an OR of at most 3 variables or negated variables,^1 e.g.
(x 1 x 3 x 7 ), (x 2 x 4 ), etc. and, such that each variablexiappears in at most 4of the clausesCj. (Here we include negated appearances in this count, e.g. ifx 1 appears twice positively then it can appear only twice in negated form.) These clauses represent the CNF (conjunctive normal form) formula
F =
j
Cj
Decide: is there an assignment to the variables that simultaneously satisfies every clauseCj? Equivalently, is there an assignment that satisfiesF?
Hint: at least one of the following known NP-complete problems is a good choice to make use of in your proof: 3-SAT, Hamiltonian Cycle in undirected graphs, 3- Coloring. (The other two may be less convenient, so choose carefully.)
Example: F= (x 1 x 3 x 4 ) (x 2 x 4 ) (x 3 x 4 ) is a CNF formula in which each clauseC 1 , C 2 , C 3 is of width at most 3, and each variable appears at most 4 times. In fact each variable appears at most 3 times, but thats certainly allowed by the problem. This is a YES instance of 3-SAT(4), sinceF is satisfied by e.g. the assignment (y 1 , y 2 , y 3 , y 4 ) = (0, 1 , 0 ,1).
(^1) Recall:is inclusive OR, i.e. 11 = 10 = 01 = 1. Also,is AND.
Solution 4.Write your solution to Problem 4 here. Expand this area as needed.
DO THIS PROBLEM OR PROBLEM 4, BUT NOT BOTH
Problem5 (25 points).(Banquets) Sometime in the not-too-distant future, friends gather for a banquet-style dinner at a large restaurant. There arenpeople and ndishes. (Again: we expect the same numberof people and dishes! Important!!) Every participant only likes certain dishes. We consider a decision problemin which we wish to know if we can seat thenpeople around a circular table with a dish between every pair of participants, so that every participant likes both dishes placed at their sides.
Input: Annnbinary matrixMsuch thatMi,j= 1 if personilikes dishjand Mi,j= 0 otherwise.
Decide:Whether there is an arrangement of all the people and dishes around a circular table, with a dish between any two adjacent people, such that every person likes both dishes placed at their two sides. Note: every dish comes in a single plate and can be only placed in a single position.
Show that this decision problem, BANQUETS, is NP-complete. (The banquet is still a success.)
Hint: at least one of the following known NP-complete problems is a good choice to make use of in your proof: 3-SAT, Hamiltonian Cycle in undirected graphs, 3- Coloring. (The other two may be less convenient, so choose carefully.)
Solution 5 .Write your solution to Problem 5 here. Expand this area as needed.