Home
Syllabus
Classwork
The same rules apply here as for the take-home exam. You should not obtain help from anybody or anything, except your instructor, your written class notes, the textbook (Dasgupta, Papadimitriou, & Vazirani, available on paper or on-line), and the course Web site.
This assignment, worth 15 points, is due at 1:10pm, Friday, March 27. You should submit your solution on paper, either handwritten or typed. E-mailed solutions will not be accepted.
Suppose you visit a seven-year-old cousin who's been given a set of n refrigerator magnets for a foreign language using an alphabet with σ letters. (Note that there may be multiple magnets representing some letters.) You decide to teach your cousin how to spell words from that language, so you pick up a dictionary listing words in the language and try to find some set of words that uses every magnet in your cousin's set.
[A student observed that this description does not specify whether we might use some words from the dictionary multiple times. You can interpret the preceding paragraph either way, whichever is more convenient for your solution.]
Show that this MAGNET WORDS problem is NP-hard by reduction from ZOE, which is already known to be NP-hard. Recall that in ZOE, we're given an matrix of zeroes and ones, containing w columns and h rows, and we want to select some subset of the w columns so that all the selected columns add up to a column of h 1's.