These homework problems are due at the start of class on Thursday, May 28.

Problem 8.1 from [DPV] (TSP optimization versus search)
Problem 8.3 from [DPV] (Stingy SAT)
Problem 8.4 parts (a),(b),(c) from [DPV] (Clique-3)
Problem 8.8 from [DPV] (Exact 4-SAT)
Problem 4.21 part (b) from [DPV] (arbitrage) **You must do this problem by a reduction
to the problem of detecting whether a graph has a negative weight cycle.