===========================================================================
CSC 363H                  Tutorial Exercises Week 8             Spring 2007
===========================================================================

 To refresh your knowledge in asymptotic notation, please go through exrcises 7.1, 7.2 
 on page 294.

 1.  Let G=(V,E) be a graph. A _clique_ of size k is a set C (subset of V)
   containing exactly k vertices that are all connected to one another.
   Formally, for every u and v in C, the edge (u,v) is present in G.

   Example: a clique of size 3 is a "triangle".

 -  Consider the following problem: does a graph G contain a clique of size k?
   Formalize this problem as a language membership problem and show it is in NP
   by giving a polytime verifier for it.

 -  Consider a "brute-force" approach for solving the k-clique problem above.
   What is the running time of this algorithm?

 -  Consider the following problem: does a graph G contain a triangle?
   Formalize this problem as a language membership problem and show it is in P.


 2.  Consider the union operation on laguages.
   Show that both P and NP are closed under union.


 3.  Consider the complementation operation on languages.
   Show that P is closed under complementation.
   Is NP closed under complementation? Explain what is different
   from the proof that P is closed under complementation.