[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Some cpmplexity problems

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,

Date Prev | Date Next | Date Index | Thread Index