Chapter 8, exercises 1, 2, 3, 9.
Read the rest of the problems at the end of chapter 8.
Consider the problem of a CS department at a University on Long Island trying to schedule its courses for the semester. The department doesn't want students to have to choose between two courses at the same time, so they've declared the following principle: any two courses that a student might need to take in the same semester will be offered in different time slots. (In the case of multiple sections, this should be understood to mean that there is at least one section of one course, and at least one section of the other, that don't conflict.) To determine what courses a student might need to take in the same semester, they use prerequisites: if CSC 171 is a prerequisite for CSC 172, for example, then no student will be taking them both in the same semester (and anybody who tries deserves what (s)he gets). The department wants to know whether it's possible to schedule all of their courses in a specified number of time slots, consistent with this principle.
Prove that this problem is NP-complete.
Write a brute-force program to solve the Independent Set problem: given a graph and a natural number k, is there a set of k vertices no two of which are adjacent? (It will presumably take exponential time. Don't worry about this, as long as it's correct. ) Ideally, it should return an independent set of the desired size if it finds one, but I'll accept a program that correctly reports whether there is one.
Then write a program that takes in an instance of the Clique problem (given a graph and a natural number k, is there a set of k vertices that are all adjacent to one another?) and solves it by doing polynomially much work and then invoking your previous Independent Set program. Ideally, it should return a k-clique if it finds one, but I'll accept a program that correctly reports whether there is a k-clique.
Extra credit: write a program that takes in an instance of 3-CNF-SAT (given a conjunction of 3-way disjunctions of literals, where a literal is either a variable or a negated variable, is there a way to assign all the variables that makes the expression come out true?) and solves it by doing polynomially much work and then invoking your previous Independent Set program. Ideally, it should return a satisfying variable assignment if it finds one, but I'll accept a program that correctly reports whether there is a satisfying variable assignment.