UGC NET Computer Science : June 2012 – Paper 3 (Solved Papers)admin
The upper bound of computing time of m coloring decision problem is
The equivalent grammar corresponding to the grammar G : S ® aA, A ® BB, B ® aBb| Î is
S®aA, A®BB, B®aBb
S®a|aA, A®BB|B, B®aBb|ab
S®a|aA, A®BB|B, B®aBb
S®a|aA, A®BB, B®aBb|ab
Which one of the following statements is incorrect ?
Cyclometric complexity for a flow graph G is V(G) = E–N+2, where E is the number of edges & N is the number of nodes in the flow graph
Cyclometric complexity for a flow graph G is V(G) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph.
The number of regions corresponds to the cyclomatic complexity.
Cyclometric complexity for a flow graph G is V(G) = P + 1, where P is the number of predicate nodes contained in the flow graph G.
Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true ?
Weight (u, v) > 12
Weight (u, v) <= 12
Weight (u, v) >= 12
Weight (u, v) = 12
Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains
n + 1 states
n + 2 states