HW8

Submit a single .pdf for the written problems and .java codes for the coding problems to me via email by the date of the deadline (11:59 pm)

(1) Please show ALL of your work (Step by Step).

(2) Provide as many details as possible for the designed algorithms (exact pseudocode) from now on. 

1. [Written 10pt] A game of chess can be posed as the following decision problem: given a legal positioning of chess pieces and information about which side is to move, determine whether that side can win. Is this decision problem decidable?

2. [Written 10pt] A certain problem can be solved by an algorithm whose running time is in O(n^{log n}). Which of the following assertions is true? Why?

a. The problem is tractable. b. The problem is intractable. c. Impossible to tell.

3. [Written 10pt] For each of the following graphs, find its chromatic number (the min number of colors you need to color the graph so that no two adjacent vertices have the same color).

4. [Written 10pt] Design a polynomial-time algorithm for the graph 2-coloring problem: determine whether vertices of a given graph can be colored in no more than two colors so that no two adjacent vertices are colored the same color.

5. [Written 20pt] State the decision version for each of the following problems and outline a polynomial-time algorithm that verifies whether or not a proposed solution solves the problem. (You may assume that a proposed solution represents a legitimate input to your verification algorithm.)

a. knapsack problem

b. bin packing problem

6. [Written 10pt] Show that the decision version of the knapsack problem is NP-complete. (Hint: In your reduction, make use of the partition problem: given n positive integers, partition them into two disjoint subsets with the same sum of their elements. The partition problem is NP-complete.) 

7. [Written 10pt] In a Set Cover problem, we are given a ground set U = {x1, x2, ... , xn}, a collection of m subsets Si ⊆ U of that ground set, and an integer k. Can you select a collection C of at most k of these subsets such that taken together, they “cover” all of U? Show that the Set Cover problem is NP-complete. (Hint: use Vertex Cover)

8. [Written 10pt] Show Integer Programming is NP-complete. (Hint: use 3-SAT)

9. [Written 30pt] Define the following: 

a. The class of P

b. The class of NP

c. The problem that is NP-complete