Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Per-problem assessment:
• 5 (Perfect): Correct solution
• 4 (Good effort): Good effort, solution may or may not be correct.
• 2 (Poor effort): Some basic misunderstandings demonstrated that could have
been cleared up by reading the notes or giving a serious try.
• 0 (No effort): No progress towards a solution.
Problem 0 (assessment: self_______ final_______)
Consider the Simple Knapsack problem instance
IB = 2, 5, 8, 9, 11, 15, C = 18
Follow the polynomial time reduction algorithm in the class
notes to write down an equivalent instance I
A of the Set
Partition problem.
Problem 1 (assessment: self_______ final_______)
The Set Partition instance I
A from above should be
satisfiable. Write down a certificate for it.
Problem 2 (assessment: self_______ final_______)
The proof of correctness for the polynomial time reduction
algorithm in the class notes shows how to convert a certificat
for IA to a certificate for IB. Follow
the algorithm and write downt the certificate for IB.