Assigned:
Wed 17 Mar 2004
Due:
Wed 24 Mar 2004
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: 4 of the following 5 problems
Points: 25 pts per problem
Hint: Reduce from 3SAT. Each card will correspond to a variable, and flipping the card will correspond to setting its truth value. Each row on a card will correspond to a clause, and the absence or presence of a hole will correspond to whether that clause is satisfied by the variable setting or not. You will need one additional specially designed card as well.