Description
Problem 1:
Given a set C, a collection of subsets of C and an integer k ≥ 1, the Set-Packing
problem asks if there are k subsets from the collection which are pairwise disjoint
(i.e. no two sets share an element). Show that the Set-Packing problem is NPcomplete.
2
Problem 2:
Given a Boolean CNF (conjunctive normal form) formula ϕ and an integer k ≥ 1,
the Stingy-SAT problem asks whether the formula has a satisfying assignment
in which at most k variables are set to true. Prove that Stingy-SAT is NPcomplete.
3
Problem 3:
Given a set C, a collection of subsets of C and an integer k ≥ 1, the Set-Cover
problem asks whether there are at most k subsets from the collection which cover
C, i.e. whose union includes all of C. Show that Set-Cover is NP-complete. Do
not use a reduction from a problem which is very similar to Set-Cover.
4
Problem 4:
Consider a list with n unique positive integers, and suppose we iterate through
the numbers one by one in a random order. As we do this, we maintain a
variable b equal to the largest number we have seen so far. Initially b is set to
0. Compute the expected number of times b is updated.
For example, if the input list is [4, 7, 5], and we iterate through the list in
the order 3, 1, 2, then b is updated twice, when we see 5 and 7.
5
