CSC 477/677 Assignment 7

Due date, December 5, 2002, 5:30 PM.

1. Competitiveness is defined to be the ratio of the cost (or benefit) of an algorithm operating with imperfect information to the cost of a theoretical optimal algorithm which operates with perfect information.
   Consider the "fairy tale" problem described on page 328 of your textbook. Compute the deterministic competitiveness, and the randomized competitiveness, of this problem.
2. Explain the difference between a Las Vegas algorithm and a Monte Carlo algorithm. Is randomized quicksort a Las Vegas or a Monte Carlo algorithm?
3. I have told you in class that boolean satisfiability is NP-complete. But some special forms of that problem are in the class P.
   We say that a boolean expression is in 2-conjunctive normal form if it is the conjunction of clauses where each clause is the disjunction of two terms, each of which is a variable or the negative of a variable. Here are some examples.
   Find a polynomial time algorithm that decides whether a boolean expression in 2-conjunctive normal form is satisfiable. Use your algorithm (by hand, not by computer) to decide whether each of the three examples is satisfiable.
4. To be posted later ...
5. To be posted later ...
6. To be posted later ...