COMP3027 Assignment 5 The University of Sydney 2018 semester 1 School of IT
数据结构作业代写 Consider the following decision problem:4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals
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-SAT ∈NP
(ii)Prove that 4-SAT ∈ NPHard
(iii)Thereby prove that 4-SAT ∈ NPComplete
Task 2: [30 marks]
Consider the following decision problems:
- Minimum-Spanning-Tree: Given a weighted graph tt = (V, E) and an integer d, does there exist a spanning tree of tt with weight at most d?
- Minimum-Spanning-2-Forest: Given a weighted graph tt = (V, E) and an integer d, does there exist a pair of subtrees T1= (V1, E1) and T2 = (V2, E2) of tt, such that V2 = V \ V1 (i.e. each vertex of tt is in either T1 or T2), and the weight of the two trees sum to at most d?数据结构作业代写
(i)Provethat Minimum-Spanning-2-Forest P 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-Forest ∈P
Task 3: [40 marks] 数据结构作业代写
Consider the following decision problem:
Alternating-Hamiltonian-Cycle: Given a graph tt = (V, E), and a subset A V of its vertices, does there exist a Hamiltonian Cycle of tt, such that the cycle alternates between vertices in A and vertices in V \ A?
For example, if V = {a1, a2, a3, b1, b2, b3} and A = {a1, a2, a3}, and there were edges between every vertex, then the answer would be YES, because a1, b1, a2, b2, a3, b3, a1 is both a Hamiltonian cycle and alternates between vertices in A and vertices not in A.
(i)Prove that Alternating-Hamiltonian-Cycle ∈NP
(ii)Prove that Alternating-Hamiltonian-Cycle ∈ NPHard
(iii)Thereby prove that Alternating-Hamiltonian-Cycle ∈ NPComplete
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, it’s 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 (it’s an unnecessarily precise level of detail for these reductions, and usually harder to follow than prose.)
- Please try to be fairly
- It’sreasonable to write things like these without having to explain precisely how it’s done:
-‘checkthat P is a simple path’ 数据结构作业代写
-‘checkthat all the subsets are disjoint’
- You don’t need to detail data structures etc., unless the choice of structure is important for showing that the time complexity is still polynomial.
- Don’t forget that you’re not trying to solve these 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 thegraph?数据结构作业代写
- Independent-Set: Given a graph tt = (V, E) and an integer k, is there a subset of vertices S ⊆Vsuch that |S| ≥ k and for each edge at most one of its endpoints is in S?
- Knapsack: Given a set of items with weights and values, an integer capacity C, and an integer k, is it possible to select a subset of items with total weight no greater than C, but total value at least k?
- Set-Cover: Given a set of elements U , a collection of subsets of it, and an integer k, does there exist a collection of k of these subsets whose union covers U ?
- Subset-Sum: Given a set of integers S and an integer k, is there a subset of S which sums to k?
- Traveling-Salesman-Problem: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length ≤D?
- Vertex-Cover: Given a graph tt = (V, E) and integer k, is there a subset of vertices S ⊆ V such that |S| ≤ k and for each edge at least one of its endpoints is inS?
其他代写：algorithm代写 analysis代写 app代写 assembly代写 assignment代写 C++代写 code代写 course代写 dataset代写 java代写 web代写 北美作业代写 编程代写 考试助攻 program代写 cs作业代写 source code代写
