ANALYSIS of ALGORITHMS, Bulletin Board
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Some cpmplexity problems
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.
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
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.
P(K;G) - is chromatic number of graph. Proof : for graph with n nodes
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 |