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

16. In Activity - Selection problem, each activity i has a start time si and a finish time fi where si ≤ fi. Activities i and j are compatible if:

  • 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.
Cancel reply
Cancel reply

17. Given two sequences X and Y : X = < a, b, c, b, d, a, b > Y = < b, d, c, a, b, a > . The longest common subsequence of X and Y is :

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

Cancel reply
Cancel reply

20. Floyd-Warshall algorithm utilizes __________ to solve the all-pairs shortest paths problem on a directed graph in __________ time.

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