3/29 停課一次

March 29 因為老師要去 IEEE AINA 2005 (http://www.mine.tku.edu.tw/AINA2005/) 會議報告論文，停止上課一次。補課時間會再和同學們商量。

Homework 3

Find an instance of weighted vertex cover problem which is “bad” for the algorithm if you are greed at W(v)/D(v).
How bad could it be?

Due: April 7th.

Homework 1 & Homework 2 are also due on April 7th.

Homework 2

1. n Given a graph G, find a polynomial algorithm to determine whether G is bi-connected.
2. nIf G is bi-connected, find a polynomial algorithm to find a Hamiltonian cycle on G2.

Homework 1

Homework 1: Is 2-SAT NP-complete? Given a polynomial algorithm if you think it is not; or prove it is NP-complete by reduction from an NP-complete problem.