﻿ data structure3代写 Assignment代写 Task代写 course代写

# data structure3代写 Assignment代写 Task代写 course代写

2021-04-13 17:58 星期二 所属： course代写 浏览：37 ## COMP3027 Assignment 5 The University of Sydney 2018 semester 1 School of IT

data structure3代写 Consider the following decision problem:4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals

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? data structure3代写

(i)Prove that 4-SAT NP

(ii)Prove that 4-SAT NPHard

(iii)Thereby prove that 4-SAT NPComplete

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?data structure3代写

(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)

### Task 3: [40 marks] data structure3代写

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 data structure3代写

• 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 data structure3代写

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’ data structure3代写

-‘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.data structure3代写

• 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?data structure3代写

• 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? 