程序代写案例-CSCC63-Assignment 3

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
CSCC63 Assignment 3
Due 11:59pm, April 12
Warning: Your electronic submission of a PDF to Crowdmark affirms that this assignment is your own
work and no one else’s, and is in accordance with the University of Toronto Code of Behaviour on Academic
Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSCC63. Note that
using Google or any other online resource is considered plagiarism.
We have stated in class that a number of languages are NP-complete: these include 3SAT, Clique, 3COL,
VC, Subset-Sum, and Ham-Path. You may assume that these languages are NP-complete here.
You may also refer to the fact that 2SAT and 2COL are in P.
1. (15 marks) Consider the language Contains-Subgraph:
INPUT: Two graphs G and H.
QUESTION: Does G contain H as a subgraph?
Show that Contains-Subgraph is NP-complete.
2. (15 marks) Consider the language 1-2-3-Subset:
INPUT: A finite multiset S of integers.
QUESTION: Can S be partitioned into three disjoint sets A, B, and C such that

x∈C x =
3
(∑
x∈A x
)
and

x∈B = 2
(∑
x∈A
)
?
Show that 1-2-3-Subset is NP-complete.
3. (15 marks) Consider the language Many-Paths:
INPUT: A directed graph G, two vertices s and t, and a number k.
QUESTION: Are there at least k disjoint paths from s to t, all of which have different lengths?
By disjoint paths, we mean that the only vertices any two of the paths share are s and t.
Show that Many-Paths is NP-complete.
4. (15 marks) Consider the language Choice-Set:
INPUT: A finite set S of integers, an integer k, and a finite collection of sets X1, X2, . . . Xm such
that for every i, |Xi| ≥ 3 and Xi ⊆ S.
QUESTION: Is there a size k subset T ⊆ S such that for every i, T ∩Xi 6= ∅?
Show that Choice-Set is NP-complete.
5. (10 marks) Consider the following function:
Longest:
INPUT: A directed graph G and two nodes s and t.
OUTPUT: The length of the longest s to t path in G.
It is possible to show that unless P = NP, there is no way of approximating this function with an
approximation ratio of better than 1/2.
Strengthen this result to show that there is no way to approximate this function with any approximation
ratio better than 1/4.
1
6. (10 marks) We’ve argued that 2SAT and 2COL are both in P. Here’s another problem in P:
DAG-HAM-PATH
INPUT: A DAG (directed acyclic graph) G, and two nodes s and t.
QUESTION: Does G have a Hamiltonian path from s to t?
Write an algorithm to prove that DAG-HAM-PATH is in P.
7. (10 marks) Consider the following problem:
Test-3COL:
INPUT: A graph G and a subset S ⊆ V of vertices.
QUESTION: Is there an assignment of the colours {red, blue, green} to the vertices in S that
does not match any valid 3-colouring on all of G?
Show that Test-3COL is in PSPACE.
8. (10 marks) Show that #3COL is #P-complete by finding a parsimonious reduction from #3SAT.
9. Bonus (10 marks — your mark will be rounded to the nearest multiple of 2.5) Show that #HAM-
PATH is #P-complete by finding a parsimonious reduction from #3SAT.
Note: For problems 8 and 9, you may find the “Polytime Reductions” handout useful as a starting
point.
2

欢迎咨询51作业君
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468