Data Structures|Assignment代写 – 这是一个典型的数据结构代写，是图方面的内容，属于比较难的一类数据结构题目, 涉及NP问题
assignment
Task 1: [30 marks]
Consider the following decision problem:
- 4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment?
(i) Prove that 4-SATNP
(ii) Prove that 4-SATNP Hard
(iii) Thereby prove that 4-SATNP Complete
Task 2: [30 marks]
Consider the following decision problems:
- Minimum-Spanning-Tree: Given a weighted graphG= (V, E) and an integerd, does there exist a spanning tree ofGwith weight at mostd?
- Minimum-Spanning-2-Forest: Given a weighted graphG= (V, E) and an integerd, does there exist a pair of subtreesT 1 = (V 1 , E 1 ) andT 2 = (V 2 , E 2 ) ofG, such thatV 2 =V\V 1 (i.e. each vertex of Gis in eitherT 1 orT 2 ), and the weight of the two trees sum to at mostd?
(i) Prove that Minimum-Spanning-2-ForestP Minimum-Spanning-Tree (you may assume that the
weights are positive and that the graph has at least 2 vertices)
(ii) Use this reduction to help you prove that Minimum-Spanning-2-ForestP
Task 3: [40 marks]
Consider the following decision problem:
- Alternating-Hamiltonian-Cycle: Given a graphG= (V, E), and a subsetAV of its vertices, does there exist a Hamiltonian Cycle ofG, such that the cycle alternates between vertices inAand vertices inV\A? For example, ifV={a 1 , a 2 , a 3 , b 1 , b 2 , b 3 }andA={a 1 , a 2 , a 3 }, and there were edges between every vertex, then the answer would be YES, because{a 1 , b 1 , a 2 , b 2 , a 3 , b 3 , a 1 }is both a Hamiltonian cycle and alternates between vertices inAand vertices not inA.
(i) Prove that Alternating-Hamiltonian-CycleNP
(ii) Prove that Alternating-Hamiltonian-CycleNP Hard
(iii) Thereby prove that Alternating-Hamiltonian-CycleNP Complete
1
Submission details
- Submission deadline is Sunday 10th June, at 23:59pm. Late submissions without special consider- ation will be subject to the penalties specified in the first lecture (25% per day or part thereof.)
- Submit your answers as a single document (preferably a pdf or doc file) to Canvas. Your work must be typed text (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise.
- Your assignment will be subject to automatic and manual plagiarism detection systems. Remember, its acceptable to discuss high level ideas with your peers, but you should not share the detail of your work, such as (but not limited to) parts of the actual algorithms, (counter)examples, proofs, writing, or code.
Level of detail required in this assignment
- Please do not write pseudocode (its an unnecessarily precise level of detail for these reductions, and usually harder to follow than prose.)
- Please try to be fairly concise.
- Its reasonable to write things like these without having to explain precisely how its done:
- check thatPis a simple path
- check that all the subsets are disjoint
- You dont need to detail Data Structures etc., unless the choice of structure is important for showing that the time complexity is still polynomial.
- Dont forget that youre not trying tosolvethese problems, you only need to find polynomial time certifiers / polynomial time reductions as appropriate.
Appendix: NP Complete problems
This is just a short list of some well known NP Complete problems that have been mentioned in lectures, in case you need inspiration for problems to reduce from for your NP Completeness proofs.
- 3-Colour: Given a graph, is it possible to colour the vertices using at most 3 colours, such that no pair of adjacent vertices have the same colour?
- 3-SAT: Given a formula in Conjunctive Normal Form, where each clause has exactly 3 literals, is there a satisfying truth assignment?
- Circuit-SAT: Given a combinatorial circuit of AND, OR, and NOT gates, is there a way to set the circuit inputs such that the output is 1?
- Hamiltonian-Cycle: Given a graph, is there a simple cycle which visits every vertex of the graph?
- Independent-Set: Given a graphG= (V, E) and an integerk, is there a subset of verticesSV such that|S|kand for each edge at most one of its endpoints is inS?
- Knapsack: Given a set of items with weights and values, an integer capacityC, and an integerk, is it possible to select a subset of items with total weight no greater thanC, but total value at least k?
- Set-Cover: Given a set of elementsU, a collection of subsets of it, and an integerk, does there exist a collection ofkof these subsets whose union coversU?
- Subset-Sum: Given a set of integersSand an integerk, is there a subset ofSwhich sums tok?
- Traveling-Salesman-Problem: Given a set ofncities and a pairwise distance functiond(u, v), is there a tour of lengthD?
- Vertex-Cover: Given a graphG= (V, E) and integerk, is there a subset of verticesSV such that|S|kand for each edge at least one of its endpoints is inS?