CSC 363 — Assignment 4
Due Thursday, April 16th, 5:00pm, via MarkUs
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources
(people, print, electronic) outside the course and lecture notes, that you consulted.
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct but that are hard to understand may not receive full marks. Mark values for each question are contained in the [square brackets].
1. Consider the Set-Cover problem: given sets C and S, where S is a set of subsets of C, find a smallest subset of S, denoted by T, such that the union of all the elements of T equals C. For example, let
C = {1,2,3,4,5,6,7}
S = {{1,2,3},{2,4},{6,7},{5,7},{3,4,5},{5,6},{1}}.
Then, T = {{1, 2, 3}, {3, 4, 5}, {6, 7}}, since
{1, 2, 3} ∪ {3, 4, 5} ∪ {6, 7} = C
and there does not exist a two element subset of S such that said subset is a set construction of C. Let
Set-Cover = {< C, S, k > |Over C and S there exists a set construction of size k or less}. Show that set cover is NP-Complete. For your reduction you do not need a formal proof, but
clearly explain how it works. [10]
2. Recall the language A from the midterm:
A={
Prove A is NP-Hard by showing 3-SAT ≤P A. [10]
1