CS代考 CS4820/5820 Algorithm 算法 – cscodehelp代写
Introduction to Analysis of Algorithms Prelim 2 CS4820/5820 Fall 2021
Due to last-minute emergencies, it is possible that some students in the course will be taking this exam slightly late. In order to ensure that all students are provided with equitable preparation for this exam, we ask you to sign the following agreement not to discuss the contents of this exam in the presence of anyone who hasn’t taken the exam until Saturday, November 20, 2021:
AGREEMENT: I, , agree not to share verbal, written, or digital information about the following exam with anyone outside of (1) the in- structor, (2) the teaching assistants for the course, and (3) students in the current semester of CS4820/5820 who I know have already taken this exam before Saturday, November 20, 2021.
SIGNATURE:
Please clearly write your name and NetID in the box below. Also, write your NetID on the
top of each page of the exam.
This prelim consists of 5 questions on a total of 8 pages (4 double-sided sheets of paper), worth a total of 50 points. Please provide the answer at the space right under the question. You may also use the back of this page or the last page for additional space, but please mark on the question page itself if you are using this as part of an answer.
This exam is closed-book and closed-notes. When you are asked to design and analyze an algo- rithm, you must present a full description of the algorithm and an analysis of its running time. The algorithm’s running time is required to be polynomial in the input size. You may reduce problems to ones presented in textbooks, lectures, or homework, in which case you need not explain the details of the algorithm, and can simply state its running time. However, you still must provide the full protocol to reduce to the existing problem, as well as a correct running time analysis of the combined process of reducing the new problem to the existing one and executing the algorithm for the reduced problem. On this prelim, to save time, please only prove what we ask for in each problem.
Important: Follow the directions to each question carefully, placing your answers in the designated spaces (otherwise, the autograder may ignore your answer).
Copyright Anke van Zuylen. Problems and solutions may not be posted publicly without permission of the copyright1 holder.
NAME: NETID:
This page can be used as extra space. Please mark on the question page itself if you are using this page for part of an answer.
Copyright Anke van Zuylen. Problems and solutions may not be posted publicly without permission of the copyright2 holder.
1. Consider the flow network, at an intermediary stage of the Ford-Fulkerson algorithm. Let f denote the current flow in the network. Each edge e has a label in the form “fe©ce”, where fe is value that f assigns to e, and ce is the edge capacity.
s 2©2 0©4 3©3 t
(a) (1 point) Give the capacity of the s-t cut A,B where A rs,a,b,cx,B rd,tx. cA,B 13
(b) (2 points) Draw the residual graph, Gf, below, and use it to identify an augmenting path, P (i.e., an s-t path in Gf ) and its bottleneck capacity, δ.
(c) (2 points) Let f¬ be the flow that results from augmenting δ units of flow onto f along P. Draw f¬ below. Do not label the edge capacities, only write the value f¬ assigns to each edge. Also, give the value of f¬.
P s cad t δ2
(d) (2 points) Identify a minimum s-t cut A,B in G and its capacity.
A rs, c x, B rt, a,b,d x, cA ,B 8
(e) (1 point) Fill in the the appropriate circle below to indicate whether the following state- ment is true or false. No explanation is required.
q True / q False : f¬ is a maximum flow in G.
Copyright Anke van Zuylen. Problems and solutions may not be posted publicly without permission of the copyright3 holder.
Solution: True. f¬ is a maximum flow in G by the Max-Flow Min-Cut theorem, since it has value equal to the capacity of cut A, B.
2. For each of the following statements, indicate whether it is true or false by filling in the appropriate circle. You do not need to explain your choices.
(a) (2 points) Consider a directed graph G V,E with source s and sink t, and integer capacityce %0oneachedgee”E. Letf beans-tflowinG,andletA,Bbean arbitrary s-t cut.
q True / q False : The value of f equals the net flow across A, B:
vf = v,w”E
= fv,w. v,w”E
Solution: True; we proved this in lecture using the fact that flow conservation must
hold at every node except s and t.
(b) (2 points) Suppose that X ” NP and that Y is a decision problem of unknown complexity. Suppose we prove that Y ” NP, and that we find a polynomial-time reduction X &P Y .
q True / q False : Y is NP-complete.
Solution: False. It’s possible that both X, Y ” P (meaning Y is not NP-hard if PjNP).
It’s also possible that Y is not a decision problem, meaning Y “© NP.
(c) (2 points) Let UniqueStableMatching denote the problem of deciding if a stable matching instance has a unique stable matching. (You showed on Homework 1 how to solve this problem by running the Gale-Shapley algorithm twice.)
q True / q False : Assuming P j NP, there is no polynomial-time reduction from UniqueStableMatching to SAT.
Solution: False; UniqueStableMatching is in P and thus it is also in NP. SAT is NP-complete, and thus any problem in NP can be reduced to it in polynomial time.
Copyright Anke van Zuylen. Problems and solutions may not be posted publicly without permission of the copyright4 holder.
3. Given a flow network G V,E,s,t,c, and a maximum s-t flow f, the UniqueMinCut problem asks whether G has a unique minimum-capacity s-t cut.
(a) (2 points) Select the correct answer: UniqueMinCut is
q solvable in polynomial-time / q NP-complete.
(b) (6 points) Briefly give the reasoning why the answer you circled is correct.
If you believe UniqueMinCut is solvable in polynomial time, describe a polynomial time algorithm that would decide it. You do not need to give the running time or prove that your algorithm is correct.
If you believe UniqueMinCut is NP-complete, describe a reduction from an NP- complete problem to UniqueMinCut. You do not need to prove that the UniqueM- inCut is in NP, nor prove that your reduction is correct.
Solution: UniqueMinCut ” P. Consider the following algorithm.
Construct the residual graph Gf .
Perform BFS on Gf from s to compute a min-cut A1, B1 with A1 rnodes reachable from sx, and B1 V ̄ A1.
Perform BFS on the reversed residual graph GRf from t to compute a min-cut A2,B2 with B2 rnodes reachable from tx, and A2 V ̄ B2.
If A1 A2, output “yes,” otherwise output “no.”
Copyright Anke van Zuylen. Problems and solutions may not be posted publicly without permission of the copyright5 holder.
4. (16 points) A boolean formula φx1, , xn is called doubly satisfiable if there are two distinct truth assignments to its variables x1, , xn for which φ is true.
The decision problem DoubleSat takes as input a boolean formula φ in conjunctive normal form1 and outputs whether φ is doubly satisfiable. For example, on input
φx1,x2,x3x1 1×2 0 x2 1×3 0 x1 1×3,
DoubleSat would return “yes”, since we can make φ true by setting x1 T, x2 F, x3 T,
andalsobysettingx1 F,x2 T,x3 F.
Prove that DoubleSat is NP-complete. Include all steps of an NP-completeness proof.
Solution: First, we argue that DoubleSat ” NP. Let a certificate consist of the two truth assignments x and y. This certificate has length On, where n is the number of variables in φ, which is polynomial in the input length. The verifier should first check that x and y are distinct via an On element-wise comparison. Next, it must verify that both x and y are satisfying truth assignments for φ. This can be done for each assignment by iterating first over the clauses of φ and then over the literals in each clause, checking that the assignment sets at least one literal per clause to true. This requires Omn time, where m is the number of clauses, for an overall polynomial runtime of the verifier.
Next, we argue that DoubleSat is NP-Hard via a reduction from Sat. Let φ be a boolean formula input for Sat. We transform φ into a new boolean formula φ2 for DoubleSat as follows:
Let xn1,xn2 be variables that do not appear in φ.
Take φ2 φ 0 xn1 1 xn2.
φ2 has length Omn, so can be constructed in Omn time. We argue that φ is satisfiable
¿ φ2 is doubly satisfiable.
For the forward direction, suppose x is a satisfying assignment of φ. Then, x < rxn1 T,xn2 Fx and x < rxn1 F,xn2 Tx are both satisfying assignments of φ2, as the variables assignments in x ensure that the first m clauses in φ2 are true, and both possible assignments of xn1,xn2 ensure the last clause in φ2 is true. For the reverse direction, suppose that φ2 is doubly satisfiable. Notably, it has some satisfying truth assignment x. The first m clauses in φ2, that is φ, depends only on the first n variables, x1xn in x. But then, these assignments in x give a satisfying assignment of φ. 1In other words, the input is the same as the input to SAT. Copyright Anke van Zuylen. Problems and solutions may not be posted publicly without permission of the copyright6 holder. 5. (12 points) A shipping company is deciding whether to do business in a country. The company has information about potential shipping opportunities organized as a graph G V, E. The vertex set V is a list of potential ports. For each port v ” V , the company estimates a cost bv % 0 to build a terminal. Each edge e u, v ” E is labeled with an integer ce % 0, representing an estimated amount of cargo that can be shipped between u and v. The company can handle all of this cargo if and only if it has built terminals at both ports u and v. Each unit of cargo that they ship earns the company a profit of p. The company will do business in the country if there is a set of ports S N V for which the cost to build terminals at these ports is less than the profits from handling all traffic between them. Give an algorithm that decides whether there is such a set S (so your algorithm should return either “yes” or “no”). The runtime of your algorithm should be polynomial in n ¶V ¶, m ¶E¶, and B = bv. You must fully explain how your algorithm works, and analyze the running time, but you do not have to provide a proof of correctness. Solution: Solution 1: Reduction to Project Selection This is a project selection problem, where the positive-profit projects are the edges of G (with profit pce for edge e) and the negative-profit projects are the nodes of G (with profit bv for node v); doing project e u,v requires us to also do projects u and v. Find the project selection A of maximum profit, and answer yes if and only if the profit of A is greater than 0. (The set S of ports where the company should build terminals is the set of nodes for which the corresponding project is in A.) Solution 2: Reduction to Minimum s-t Cut We can solve this problem by reducing it to a minimum s-t cut problem. Create a flow graph G V ,E where: V rs,tx
