CS341 Lecture : Assignment #5 This is the fifth assignment from winter 2010 term
16 Oct 2011
School
Department
Course
Professor
Document Summary
Please read http://www. student. cs. uwaterloo. ca/~cs341/policies. html rst for general in- structions: [12 marks] turn each of the following optimization problems into a decision problem and show that the corresponding decision problem is in np. (a) [6 marks] Input: a set s of n numbers a1, . , an and an integer k n. Output: a partition of s into k subsets s1, . [note: the subsets do not have to be contiguous blocks, so the problem is di erent from. Input: an undirected graph g = (v, e) with n vertices and an integer k n. Input: an undirected graph g = (v, e) of maximum degree at most 4 and an integer k. Output: yes i there exists a subset s of size at least k such that for every u, v s, we have uv (cid:54) e (i. e. , s is an independent set). and the decision problem 3-is:
