Algorithms Assignment 9

1. A set of Pokemon cards consists of n different cards. The cards are sold as different sized
randomly selected packs. Each pack is a subset of the set of Pokemon cards. There are
m such packs. You happen to know which cards were placed in which packs. You want
to select a minimum set of packs such that you will get at least one of every every card in
the set.
a) Express this optimization problem (Pokemon) formally with input and output
conditions as a decision problem.
b) Give a verification algorithm for this problem.
c) Prove your verification algorithm is correct. Prove your verification algorithm runs
in polynomial time.

2. Consider the Pokemon problem from above. Now you will prove it is NP-hard by stating
and proving correct your polynomial time reduction. The NP-complete problem you
will use for your reduction is the Vertex Cover problem.
a) Give a reduction from Vertex Cover to Pokemon. The reduction takes input to
Vertex Cover and converts it into input to Pokemon.
b) Prove your reduction is correct. Prove your reduction runs in polynomial time.

Last Completed Projects