## UGC NET Computer Science : June 2012 – Paper 3 (Solved Papers)

Question 1 |

The upper bound of computing time of m coloring decision problem is

O(n ^{m}) | |

O(nm ^{n}) | |

O(nm) | |

O(n ^{m}m^{n}) |

Question 2 |

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 |

Question 3 |

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. |

Question 4 |

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 |

Question 5 |

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 states | |

2 ^{n} states | |

n + 1 states | |

n + 2 states |