Some cpmplexity problems

[Yelena Shabtai <YelenaShabtai@imi-telecom.com>]

Hello !

My name is Yelena. I am learning course "Complexity of  the algorithms".
I have some problem and don't know how to solve them.
If you have time to help me I will very appreciate. 


Problem 1.
T(N) - time of computation  2 matrices (A,B) of n*n 
S(N) - time of computation A of n in power 2 .
Proof : T(n) = q(S(n))
AB <> BA
Hint: Go to more big matrices


Problem 2.
Find algorithm for  calculating max independent set in the graph in form
of the tree.
Computation time should be O(V).
Hint: Tree has nodes with degree 1.


Problem 3.
P(K;G) - is chromatic number of graph. Proof : for graph with n nodes
there is 
  0 <= s < n  and  number of ways for coloring the graph G can be
described as sum 
of poloniums of the form K(K-1)(K-2)... (K-s).

 

Thank in advance,
Yelena