# UGC NET COMPUTER SCIENCE SOLVED PAPERS 2014-16 - UGC NET Computer Science Paper 3 December 2015

>>>>>>>>UGC NET Computer Science Paper 3 December 2015

• A

si≥ fj  • B

sj ≥ fi  • C

si ≥ fj or sj ≥ fi  • D

si ≥ fj and sj ≥ fi or  • Option : C
• Explanation :
Two activities are compatible if their starting time and finish time does not overlap i.e. their execution must not overlap and starting time of one process must be greater then or equal to second process. i.e. si ≥ fj or sj ≥ fi. So, option (C) is correct.

• A

<b, c, a>  • B

<c, a, b>  • C

< b, c, a, a>  • D

< b, c, b, a>  • Option : D
• Explanation :
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
A sequence G is said to be a common subsequence of X and Y, if Z is a subsequence of both X and Y.
Here X = <a, b, c, b, d, a, >, the sequences <b,c,a>, <c,a,b>, <b,c,b,a> are subsequences of X.
Given a second sequence of symbols Y = <b, d, c, a, b, a>, then <b,c,a>, <c,a,b>, <b,c,b,a> are common subsequences to both X and Y.
However, the longest common subsequence of X and Y is <b,c,b,a>

• A

O(d n k)  • B

O(d nk)  • C

O((d +n) k)  • D

O(d (n + k))  • A

O(lg n)  • B

O(lg n)  • C

O(n lg n)  • D

None of the above  • A

Greedy algorithm, θ (V3)  • B

Greedy algorithm, θ (V2 lgn)  • C

Dynamic programming, θ (V3)  • D

Dynamic programming, θ (V2 lgn)  • Option : C
• Explanation :
Floyd-Warshall algorithm utilizes dynamic programming to solve the all-pairs shortest paths problem on a directed graph in θ (V3) time.